DIY 3.0 data-parallel out-of-core C++ library

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List

All Classes Namespaces Functions Typedefs Groups Pages
common.hpp
1 #ifndef DIY_PARTNERS_COMMON_HPP
2 #define DIY_PARTNERS_COMMON_HPP
3
4 #include "../decomposition.hpp"
5 #include "../types.hpp"
6
7 namespace diy
8 {
9
10 struct RegularPartners
11 {
12 // The record of group size per round in a dimension
13 struct DimK
14 {
15 DimK(int dim_, int k_):
16 dim(dim_), size(k_) {}
17
18 int dim;
19 int size; // group size
20 };
21
22 typedef std::vector<int> CoordVector;
23 typedef std::vector<int> DivisionVector;
24 typedef std::vector<DimK> KVSVector;
25
26 // The part of RegularDecomposer that we need works the same with either Bounds (so we fix them arbitrarily)
27 typedef DiscreteBounds Bounds;
28 typedef RegularDecomposer<Bounds> Decomposer;
29
30 template<class Decomposer_>
31 RegularPartners(const Decomposer_& decomposer, int k, bool contiguous = true):
32 divisions_(decomposer.divisions),
33 contiguous_(contiguous) { factor(k, divisions_, kvs_); fill_steps(); }
34 RegularPartners(const DivisionVector& divs,
35 const KVSVector& kvs,
36 bool contiguous = true):
37 divisions_(divs), kvs_(kvs),
38 contiguous_(contiguous) { fill_steps(); }
39
40 size_t rounds() const { return kvs_.size(); }
41 int size(int round) const { return kvs_[round].size; }
42 int dim(int round) const { return kvs_[round].dim; }
43
44 int step(int round) const { return steps_[round]; }
45
46 const DivisionVector& divisions() const { return divisions_; }
47 const KVSVector& kvs() const { return kvs_; }
48 bool contiguous() const { return contiguous_; }
49
50 static
51 inline void factor(int k, const DivisionVector& divisions, KVSVector& kvs);
52
53 inline void fill(int round, int gid, std::vector<int>& partners) const;
54 inline int group_position(int round, int c, int step) const;
55
56 private:
57 inline void fill_steps();
58 static
59 inline void factor(int k, int tot_b, std::vector<int>& kvs);
60
61 DivisionVector divisions_;
62 KVSVector kvs_;
63 bool contiguous_;
64 std::vector<int> steps_;
65 };
66
67 }
68
69 void
70 diy::RegularPartners::
71 fill_steps()
72 {
73 if (contiguous_)
74 {
75 std::vector<int> cur_steps(divisions().size(), 1);
76
77 for (size_t r = 0; r < rounds(); ++r)
78 {
79 steps_.push_back(cur_steps[kvs_[r].dim]);
80 cur_steps[kvs_[r].dim] *= kvs_[r].size;
81 }
82 } else
83 {
84 std::vector<int> cur_steps(divisions().begin(), divisions().end());
85 for (size_t r = 0; r < rounds(); ++r)
86 {
87 cur_steps[kvs_[r].dim] /= kvs_[r].size;
88 steps_.push_back(cur_steps[kvs_[r].dim]);
89 }
90 }
91 }
92
93 void
94 diy::RegularPartners::
95 fill(int round, int gid, std::vector<int>& partners) const
96 {
97 const DimK& kv = kvs_[round];
98 partners.reserve(kv.size);
99
100 int step = this->step(round); // gids jump by this much in the current round
101
102 CoordVector coords;
103 Decomposer::gid_to_coords(gid, coords, divisions_);
104 int c = coords[kv.dim];
105 int pos = group_position(round, c, step);
106
107 int partner = c - pos * step;
108 coords[kv.dim] = partner;
109 int partner_gid = Decomposer::coords_to_gid(coords, divisions_);
110 partners.push_back(partner_gid);
111
112 for (int k = 1; k < kv.size; ++k)
113 {
114 partner += step;
115 coords[kv.dim] = partner;
116 partner_gid = Decomposer::coords_to_gid(coords, divisions_);
117 partners.push_back(partner_gid);
118 }
119 }
120
121 // Tom's GetGrpPos
122 int
123 diy::RegularPartners::
124 group_position(int round, int c, int step) const
125 {
126 // the second term in the following expression does not simplify to
127 // (gid - start_b) / kv[r]
128 // because the division gid / (step * kv[r]) is integer and truncates
129 // this is exactly what we want
130 int g = c % step + c / (step * kvs_[round].size) * step;
131 int p = c / step % kvs_[round].size;
132 static_cast<void>(g); // shut up the compiler
133
134 // g: group number (output)
135 // p: position number within the group (output)
136 return p;
137 }
138
139 void
140 diy::RegularPartners::
141 factor(int k, const DivisionVector& divisions, KVSVector& kvs)
142 {
143 // factor in each dimension
144 std::vector< std::vector<int> > tmp_kvs(divisions.size());
145 for (unsigned i = 0; i < divisions.size(); ++i)
146 factor(k, divisions[i], tmp_kvs[i]);
147
148 // interleave the dimensions
149 std::vector<int> round_per_dim(divisions.size(), 0);
150 while(true)
151 {
152 // TODO: not the most efficient way to do this
153 bool changed = false;
154 for (unsigned i = 0; i < divisions.size(); ++i)
155 {
156 if (round_per_dim[i] == (int) tmp_kvs[i].size())
157 continue;
158 kvs.push_back(DimK(i, tmp_kvs[i][round_per_dim[i]++]));
159 changed = true;
160 }
161 if (!changed)
162 break;
163 }
164 }
165
166 // Tom's FactorK
167 void
168 diy::RegularPartners::
169 factor(int k, int tot_b, std::vector<int>& kv)
170 {
171 int rem = tot_b; // unfactored remaining portion of tot_b
172 int j;
173
174 while (rem > 1)
175 {
176 // remainder is divisible by k
177 if (rem % k == 0)
178 {
179 kv.push_back(k);
180 rem /= k;
181 }
182 // if not, start at k and linearly look for smaller factors down to 2
183 else
184 {
185 for (j = k - 1; j > 1; j--)
186 {
187 if (rem % j == 0)
188 {
189 kv.push_back(j);
190 rem /= k;
191 break;
192 }
193 }
194 if (j == 1)
195 {
196 kv.push_back(rem);
197 rem = 1;
198 }
199 } // else
200 } // while
201 }
202
203
204 #endif
diy::RegularPartners
Definition: common.hpp:10
diy::RegularDecomposer
Decomposes a regular (discrete or continuous) domain into even blocks; creates Links with Bounds alon...
Definition: decomposition.hpp:75
diy::Bounds
Definition: types.hpp:16
diy::RegularPartners::DimK
Definition: common.hpp:13