Debian Codegraph @

src/atlas/grid/detail/partitioner/CheckerboardPartitioner.cc

raw
1 /*
2 * (C) Copyright 2013 ECMWF.
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 * In applying this licence, ECMWF does not waive the privileges and immunities
7 * granted to it by virtue of its status as an intergovernmental organisation
8 * nor does it submit to any jurisdiction.
9 */
10
11
12 #include "CheckerboardPartitioner.h"
13
14 #include <algorithm>
15 #include <cmath>
16 #include <ctime>
17 #include <functional>
18 #include <iostream>
19 #include <vector>
20
21
22 #include "atlas/grid/StructuredGrid.h"
23 #include "atlas/runtime/Exception.h"
24 #include "atlas/runtime/Log.h"
25 #include "atlas/util/MicroDeg.h"
26
27 using atlas::util::microdeg;
28
29 namespace atlas {
30 namespace grid {
31 namespace detail {
32 namespace partitioner {
33
34 CheckerboardPartitioner::CheckerboardPartitioner(): Partitioner() {}
35
36 // CheckerboardPartitioner::CheckerboardPartitioner(int N): Partitioner(N) {}
37
38 CheckerboardPartitioner::CheckerboardPartitioner(int N, const eckit::Parametrisation& config):
39 Partitioner(N, config) {
40 config.get("bands", nbands_);
41 config.get("regular", regular_);
42 if (regular_) {
43 split_x_ = false;
44 split_y_ = false;
45 }
46 config.get("split_x", split_x_);
47 config.get("split_y", split_y_);
48 }
49
50 CheckerboardPartitioner::CheckerboardPartitioner(const eckit::Parametrisation& config) :
51 Partitioner(config) {
52 config.get("bands", nbands_);
53 config.get("regular", regular_);
54 if (regular_) {
55 split_x_ = false;
56 split_y_ = false;
57 }
58 config.get("split_x", split_x_);
59 config.get("split_y", split_y_);
60 }
61
62
63 std::array<int,2> CheckerboardPartitioner::checkerboardDimensions(const Grid& grid) {
64 int nbands = checkerboard(grid).nbands;
65 int nparts = nb_partitions();
66 return {nparts/nbands, nbands};
67 }
68
69
70 // CheckerboardPartitioner::CheckerboardPartitioner(int N, int nbands): Partitioner(N), nbands_{nbands} {}
71
72 // CheckerboardPartitioner::CheckerboardPartitioner(int N, int nbands, bool checkerboard):
73 // Partitioner(N), nbands_{nbands} {}
74
75 CheckerboardPartitioner::Checkerboard CheckerboardPartitioner::checkerboard(const Grid& grid) const {
76 // grid dimensions
77 const RegularGrid rg(grid);
78 if (!rg) {
79 throw_Exception("Checkerboard Partitioner only works for Regular grids.", Here());
80 }
81
82 Checkerboard cb;
83
84 cb.nx = rg.nx();
85 cb.ny = rg.ny();
86 idx_t nparts = nb_partitions();
87
88 if (nbands_ > 0) {
89 cb.nbands = nbands_;
90 }
91 else {
92 // default number of bands
93 double zz = std::sqrt(double(nparts * cb.ny) / double(cb.nx)); // aim at +/-square regions
94 cb.nbands = std::floor(zz + 0.5);
95
96 if (cb.nbands < 1) {
97 cb.nbands = 1; // at least one band
98 }
99 if (cb.nbands > nparts) {
100 cb.nbands = nparts; // not more bands than procs
101 }
102
103 // true checkerboard means nbands must divide nparts
104 if (checkerboard_) {
105 while (nparts % cb.nbands != 0) {
106 cb.nbands--;
107 }
108 }
109 }
110 if (checkerboard_ && nparts % cb.nbands != 0) {
111 throw_Exception("number of bands doesn't divide number of partitions", Here());
112 }
113
114 return cb;
115 }
116
117 bool compare_Y_X(const CheckerboardPartitioner::NodeInt& node1, const CheckerboardPartitioner::NodeInt& node2) {
118 // comparison of two locations; X1 < X2 if it's to the south, then to the
119 // east.
120 if (node1.y < node2.y) {
121 return true;
122 }
123 if (node1.y == node2.y) {
124 return (node1.x < node2.x);
125 }
126 return false;
127 }
128
129 bool compare_X_Y(const CheckerboardPartitioner::NodeInt& node1, const CheckerboardPartitioner::NodeInt& node2) {
130 // comparison of two locations; X1 < X2 if it's to the east, then to the
131 // south.
132 if (node1.x < node2.x) {
133 return true;
134 }
135 if (node1.x == node2.x) {
136 return (node1.y < node2.y);
137 }
138 return false;
139 }
140
141 void CheckerboardPartitioner::partition(const Checkerboard& cb, int nb_nodes, NodeInt nodes[], int part[]) const {
142 size_t nparts = nb_partitions();
143 size_t nbands = cb.nbands;
144 size_t nx = cb.nx;
145 size_t ny = cb.ny;
146 long remainder;
147
148 /*
149 Sort nodes from south to north (increasing y), and west to east (increasing x).
150 Now we can easily split
151 the points in bands. Note this may not be necessary, as it could be
152 already by construction in this order, but then sorting is really fast
153 */
154
155 /*
156 Number of procs per band
157 */
158 std::vector<size_t> npartsb(nbands, 0); // number of procs per band
159 remainder = nparts;
160 for (size_t iband = 0; iband < nbands; iband++) {
161 npartsb[iband] = nparts / nbands;
162 remainder -= npartsb[iband];
163 }
164 // distribute remaining procs over first bands
165 for (size_t iband = 0; iband < remainder; iband++) {
166 ++npartsb[iband];
167 }
168
169 bool split_lons = split_x_;
170 bool split_lats = split_y_;
171
172 /*
173 Number of gridpoints per band
174 */
175 std::vector<size_t> ngpb(nbands, 0);
176 // split latitudes?
177 if (split_lats) {
178 remainder = nb_nodes;
179 for (size_t iband = 0; iband < nbands; iband++) {
180 ngpb[iband] = (nb_nodes * npartsb[iband]) / nparts;
181 remainder -= ngpb[iband];
182 }
183 // distribute remaining gridpoints over first bands
184 for (size_t iband = 0; iband < remainder; iband++) {
185 ++ngpb[iband];
186 }
187 }
188 else {
189 remainder = ny;
190 for (size_t iband = 0; iband < nbands; iband++) {
191 ngpb[iband] = nx * ((ny * npartsb[iband]) / nparts);
192 remainder -= ngpb[iband] / nx;
193 }
194 // distribute remaining rows over first bands
195 for (size_t iband = 0; iband < remainder; iband++) {
196 ngpb[iband] += nx;
197 }
198 }
199
200 // sort nodes according to Y first, to determine bands
201 std::sort(nodes, nodes + nb_nodes, compare_Y_X);
202
203 // for each band, select gridpoints belonging to that band, and sort them
204 // according to X first
205 size_t offset = 0;
206 int jpart = 0;
207 for (size_t iband = 0; iband < nbands; iband++) {
208 // sort according to X first
209 std::sort(nodes + offset, nodes + offset + ngpb[iband], compare_X_Y);
210
211 // number of gridpoints per task
212 std::vector<int> ngpp(npartsb[iband], 0);
213 remainder = ngpb[iband];
214
215 int part_ny = ngpb[iband] / cb.nx;
216 int part_nx = ngpb[iband] / npartsb[iband] / part_ny;
217
218 for (size_t ipart = 0; ipart < npartsb[iband]; ipart++) {
219 if (split_lons) {
220 ngpp[ipart] = ngpb[iband] / npartsb[iband];
221 }
222 else {
223 ngpp[ipart] = part_nx * part_ny;
224 }
225 remainder -= ngpp[ipart];
226 }
227 if (split_lons) {
228 // distribute remaining gridpoints over first parts
229 for (size_t ipart = 0; ipart < remainder; ipart++) {
230 ++ngpp[ipart];
231 }
232 }
233 else {
234 size_t ipart = 0;
235 while (remainder > part_ny) {
236 ngpp[ipart++] += part_ny;
237 remainder -= part_ny;
238 }
239 ngpp[npartsb[iband] - 1] += remainder;
240 }
241
242 // set partition number for each part
243 for (size_t ipart = 0; ipart < npartsb[iband]; ipart++) {
244 for (size_t jj = offset; jj < offset + ngpp[ipart]; jj++) {
245 part[nodes[jj].n] = jpart;
246 }
247 offset += ngpp[ipart];
248 ++jpart;
249 }
250 }
251 }
252
253 void CheckerboardPartitioner::partition(const Grid& grid, int part[]) const {
254 if (nb_partitions() == 1) // trivial solution, so much faster
255 {
256 for (idx_t j = 0; j < grid.size(); ++j) {
257 part[j] = 0;
258 }
259 }
260 else {
261 auto cb = checkerboard(grid);
262
263 std::vector<NodeInt> nodes(grid.size());
264 int n(0);
265
266 for (idx_t iy = 0; iy < cb.ny; ++iy) {
267 for (idx_t ix = 0; ix < cb.nx; ++ix) {
268 nodes[n].x = static_cast<int>(ix);
269 nodes[n].y = static_cast<int>(iy);
270 nodes[n].n = static_cast<int>(n);
271 ++n;
272 }
273 }
274
275 partition(cb, grid.size(), nodes.data(), part);
276 }
277 }
278
279 } // namespace partitioner
280 } // namespace detail
281 } // namespace grid
282 } // namespace atlas
283
284 namespace {
285 atlas::grid::detail::partitioner::PartitionerBuilder<atlas::grid::detail::partitioner::CheckerboardPartitioner>
286 __CheckerBoard("checkerboard");
287 }