1 #ifndef LIBGEODECOMP_GEOMETRY_PARTITIONS_CHECKERBOARDINGPARTITION_H
2 #define LIBGEODECOMP_GEOMETRY_PARTITIONS_CHECKERBOARDINGPARTITION_H
3 
4 #include <libgeodecomp/geometry/partitions/partition.h>
5 
6 namespace LibGeoDecomp {
7 
8 template<int DIM>
9 class CheckerboardingPartition : public Partition<DIM>
10 {
11 public:
12     using Partition<DIM>::startOffsets;
13     using Partition<DIM>::weights;
14 
15     inline explicit CheckerboardingPartition(
16         const Coord<DIM>& origin = Coord<DIM>(),
17         const Coord<DIM>& dimensions = Coord<DIM>(),
18         const long& offset = 0,
19         const std::vector<std::size_t>& weights = std::vector<std::size_t>(2)) :
20         Partition<DIM>(offset, weights),
21         origin(origin),
22         dimensions(dimensions)
23     {
24         nodeGridDim = getNodeGridDim(weights.size());
25     }
26 
getRegion(const std::size_t node)27     Region<DIM> getRegion(const std::size_t node) const
28     {
29         Coord<DIM> logicalCoord(node % nodeGridDim.x(),
30                                (node % (nodeGridDim.x() * nodeGridDim.y()))/ nodeGridDim.x());
31         if (DIM > 2){
32             logicalCoord[2] = node / (nodeGridDim.x() * nodeGridDim.y());
33         }
34 
35         Coord<DIM> realStart;
36         Coord<DIM> realEnd;
37         for(int i = 0; i < DIM; ++i){
38             realStart[i] = logicalCoord[i] * dimensions[i] / nodeGridDim[i];
39             realEnd[i] = (logicalCoord[i]+1) * dimensions[i] / nodeGridDim[i];
40         }
41         Region<DIM> r;
42         r << CoordBox<DIM>(origin + realStart, realEnd - realStart);
43         return r;
44     }
45 
46 private:
47     Coord<DIM> origin;
48     Coord<DIM> dimensions;
49     Coord<DIM> nodeGridDim;
50 
getNodeGridDim(const std::size_t totalNodes)51     Coord<DIM> getNodeGridDim(const std::size_t totalNodes) const
52     {
53         std::size_t remainingNodes = totalNodes;
54         std::size_t limit = sqrt(remainingNodes);
55         std::vector<std::size_t> primes = primeFactors(limit);
56         std::vector<std::pair<std::size_t, int> > factors;
57 
58         for (std::vector<std::size_t>::reverse_iterator i = primes.rbegin();
59              i != primes.rend();
60              ++i) {
61             int occurences = 0;
62             while ((remainingNodes % *i) == 0) {
63                 ++occurences;
64                 remainingNodes /= *i;
65             }
66 
67             if (occurences > 0) {
68                 factors.push_back(std::make_pair(*i, occurences));
69             }
70         }
71 
72         if (remainingNodes != 1) {
73             push_front(factors, std::make_pair(remainingNodes, 1));
74         }
75 
76         Coord<DIM> ret = Coord<DIM>::diagonal(1);
77 
78         for (std::vector<std::pair<std::size_t, int> >::iterator i = factors.begin();
79              i != factors.end();
80              ++i) {
81             std::size_t prime = i->first;
82             int occurences = i->second;
83 
84             for (int i = 0; i < occurences; ++i) {
85                 *minElement(ret) *= prime;
86             }
87         }
88 
89         std::sort(&ret[0], &ret[0] + DIM);
90         return ret;
91     }
92 
minElement(Coord<DIM> & coord)93     inline int *minElement(Coord<DIM>& coord) const
94     {
95         int *ret = &coord[0];
96 
97         for (int i = 1; i < DIM; ++i) {
98             if (coord[i] < *ret) {
99                 ret = &coord[0] + i;
100             }
101         }
102 
103         return ret;
104     }
105 
primeFactors(std::size_t limit)106     inline std::vector<std::size_t> primeFactors(std::size_t limit) const
107     {
108         std::vector<std::size_t> primes;
109 
110         primes.push_back(2);
111 
112         for (std::size_t i = 3; i <= limit; i += 2) {
113             std::vector<std::size_t>::iterator iter = primes.begin();
114             for (; iter != primes.end(); ++iter) {
115                 if ((i % *iter) == 0) {
116                     break;
117                 }
118             }
119 
120             if (iter == primes.end()) {
121                 primes.push_back(i);
122             }
123         }
124 
125         return primes;
126     }
127 };
128 
129 }
130 
131 #endif
132