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