Debian Codegraph @

src/atlas/grid/detail/partitioner/EqualRegionsPartitioner.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 #include "atlas/grid/detail/partitioner/EqualRegionsPartitioner.h"
12
13 #include <algorithm>
14 #include <cmath>
15 #include <ctime>
16 #include <functional>
17 #include <iostream>
18 #include <vector>
19
20 #include "atlas/grid/Iterator.h"
21 #include "atlas/grid/StructuredGrid.h"
22 #include "atlas/parallel/mpi/Buffer.h"
23 #include "atlas/parallel/mpi/mpi.h"
24 #include "atlas/parallel/omp/sort.h"
25 #include "atlas/runtime/Exception.h"
26 #include "atlas/runtime/Log.h"
27 #include "atlas/runtime/Trace.h"
28 #include "atlas/util/MicroDeg.h"
29 #include "atlas/util/vector.h"
30
31
32 using atlas::util::microdeg;
33
34 namespace atlas {
35 namespace grid {
36 namespace detail {
37 namespace partitioner {
38
39 namespace {
40 static bool valid_mpi_size(size_t size) {
41 return size < size_t(std::numeric_limits<int>::max());
42 }
43
44
45 template <class Iterator, class Sentinel = Iterator>
46 struct range_t {
47 Iterator b;
48 Sentinel e;
49 Iterator begin() const { return b; }
50 Sentinel end() const { return e; }
51 // unused:
52 // bool empty() const { return begin() == end(); }
53 };
54
55 template <class Iterator, class Sentinel>
56 range_t<Iterator, Sentinel> range(Iterator b, Sentinel e) {
57 return {b, e};
58 }
59
60 template <typename Container, typename Int>
61 range_t<typename Container::const_iterator, typename Container::const_iterator> subrange(
62 const Container& c, std::initializer_list<Int>&& _range) {
63 const Int rbegin = _range.begin()[0];
64 const Int rend = _range.begin()[1];
65 return range(c.begin() + rbegin, c.begin() + rend);
66 }
67
68 } // namespace
69
70 double gamma(const double& x) {
71 double p[14];
72 double w, y;
73 int k, n;
74 p[0] = 0.999999999999999990e+00;
75 p[1] = -0.422784335098466784e+00;
76 p[2] = -0.233093736421782878e+00;
77 p[3] = 0.191091101387638410e+00;
78 p[4] = -0.024552490005641278e+00;
79 p[5] = -0.017645244547851414e+00;
80 p[6] = 0.008023273027855346e+00;
81 p[7] = -0.000804329819255744e+00;
82 p[8] = -0.000360837876648255e+00;
83 p[9] = 0.000145596568617526e+00;
84 p[10] = -0.000017545539395205e+00;
85 p[11] = -0.000002591225267689e+00;
86 p[12] = 0.000001337767384067e+00;
87 p[13] = -0.000000199542863674e+00;
88 n = round(x - 2);
89 w = x - (n + 2);
90 y = ((((((((((((p[13] * w + p[12]) * w + p[11]) * w + p[10]) * w + p[9]) * w + p[8]) * w + p[7]) * w + p[6]) * w +
91 p[5]) *
92 w +
93 p[4]) *
94 w +
95 p[3]) *
96 w +
97 p[2]) *
98 w +
99 p[1]) *
100 w +
101 p[0];
102 if (n > 0) {
103 w = x - 1;
104 for (k = 2; k <= n; ++k) {
105 w = w * (x - k);
106 }
107 }
108 else {
109 w = 1;
110 for (k = 0; k <= -n - 1; ++k) {
111 y = y * (x + k);
112 }
113 }
114 return w / y;
115 }
116
117 double area_of_cap(const double& s_cap) {
118 //
119 // AREA_OF_CAP Area of spherical cap
120 //
121 // AREA_OF_CAP(S_CAP) sets AREA to be the area of an S^2 spherical
122 // cap of spherical radius S_CAP.
123 //
124 return 4.0 * M_PI * std::pow(std::sin(0.5 * s_cap), 2);
125 }
126
127 double area_of_collar(const double& a_top, const double& a_bot) {
128 // AREA_OF_COLLAR Area of spherical collar
129 //
130 // AREA_OF_COLLAR(A_TOP, A_BOT) sets AREA to be the area of an S^2 spherical
131 // collar specified by A_TOP, A_BOT, where A_TOP is top (smaller) spherical
132 // radius,
133 // A_BOT is bottom (larger) spherical radius.
134 //
135 return area_of_cap(a_bot) - area_of_cap(a_top);
136 }
137
138 double sradius_of_cap(const double& area) {
139 // SRADIUS_OF_CAP(AREA) returns the spherical radius of
140 // an S^2 spherical cap of area AREA.
141 //
142 return 2. * std::asin(0.5 * std::sqrt(area / M_PI));
143 }
144
145 double area_of_ideal_region(int N) {
146 //
147 // AREA_OF_IDEAL_REGION(N) sets AREA to be the area of one of N equal
148 // area regions on S^2, that is 1/N times AREA_OF_SPHERE.
149 //
150 double area_of_sphere = 2. * std::pow(M_PI, 1.5) / gamma(1.5);
151 return area_of_sphere / static_cast<double>(N);
152 }
153
154 double polar_colat(int N) {
155 //
156 // Given N, determine the colatitude of the North polar spherical cap.
157 //
158 double polar_c(0);
159 if (N == 1) {
160 polar_c = M_PI;
161 }
162 if (N == 2) {
163 polar_c = 0.5 * M_PI;
164 }
165 if (N > 2) {
166 polar_c = sradius_of_cap(area_of_ideal_region(N));
167 }
168 return polar_c;
169 }
170
171 double ideal_collar_angle(int N) {
172 //
173 // IDEAL_COLLAR_ANGLE The ideal angle for spherical collars of an EQ partition
174 //
175 // IDEAL_COLLAR_ANGLE(N) sets ANGLE to the ideal angle for the
176 // spherical collars of an EQ partition of the unit sphere S^2 into N regions.
177 //
178 return std::sqrt(area_of_ideal_region(N));
179 }
180
181 void ideal_region_list(int N, const double& c_polar, int n_collars, double r_regions[]) {
182 //
183 // IDEAL_REGION_LIST The ideal real number of regions in each zone
184 //
185 // List the ideal real number of regions in each collar, plus the polar caps.
186 //
187 // Given N, c_polar and n_collars, determine r_regions, a list of the ideal
188 // real
189 // number of regions in each collar, plus the polar caps.
190 // The number of elements is n_collars+2.
191 // r_regions[1] is 1.
192 // r_regions[n_collars+2] is 1.
193 // The sum of r_regions is N.
194 //
195 // real(wp),intent(out) :: r_regions(n_collars+2)
196 double ideal_region_area, ideal_collar_area;
197 r_regions[0] = 1.;
198 if (n_collars > 0) {
199 //
200 // Based on n_collars and c_polar, determine a_fitting,
201 // the collar angle such that n_collars collars fit between the polar caps.
202 //
203 double a_fitting = (M_PI - 2. * c_polar) / static_cast<double>(n_collars);
204 ideal_region_area = area_of_ideal_region(N);
205 for (int collar_n = 0; collar_n < n_collars; ++collar_n) {
206 ideal_collar_area = area_of_collar(c_polar + collar_n * a_fitting, c_polar + (collar_n + 1) * a_fitting);
207 r_regions[1 + collar_n] = ideal_collar_area / ideal_region_area;
208 }
209 }
210 r_regions[2 + n_collars - 1] = 1.;
211 }
212
213 int num_collars(int N, const double& c_polar, const double& a_ideal) {
214 //
215 // NUM_COLLARS The number of collars between the polar caps
216 //
217 // Given N, an ideal angle, and c_polar,
218 // determine n_collars, the number of collars between the polar caps.
219 //
220 bool enough = (N > 2) && (a_ideal > 0);
221 if (enough) {
222 return std::max(1, static_cast<int>(round((M_PI - 2. * c_polar) / a_ideal)));
223 }
224 else {
225 return 0;
226 }
227 }
228
229 void round_to_naturals(int N, int ncollars, double r_regions[], int n_regions[]) {
230 // ROUND_TO_NATURALS Round off a given list of numbers of regions
231 //
232 // Given N and r_regions, determine n_regions,
233 // a list of the natural number of regions in each collar and the polar caps.
234 // This list is as close as possible to r_regions, using rounding.
235 // The number of elements is n_collars+2.
236 // n_regions[1] is 1.
237 // n_regions[n_collars+2] is 1.
238 // The sum of n_regions is N.
239 //
240 double discrepancy = 0.;
241 for (int zone_n = 0; zone_n < ncollars + 2; ++zone_n) {
242 n_regions[zone_n] = round(r_regions[zone_n] + discrepancy);
243 discrepancy += r_regions[zone_n] - n_regions[zone_n];
244 }
245 }
246
247 void cap_colats(int N, int n_collars, const double& c_polar, int n_regions[], double c_caps[]) {
248 // CAP_COLATS Colatitudes of spherical caps enclosing cumulative sum of
249 // regions
250 //
251 // Given dim, N, c_polar and n_regions, determine c_caps,
252 // an increasing list of colatitudes of spherical caps which enclose the same
253 // area
254 // as that given by the cumulative sum of regions.
255 // The number of elements is n_collars+2.
256 // c_caps[1] is c_polar.
257 // c_caps[n_collars+1] is Pi-c_polar.
258 // c_caps[n_collars+2] is Pi.
259 //
260 // c_caps = cap_colats(dim,N,c_polar,n_regions);
261
262 c_caps[0] = c_polar;
263 double ideal_region_area = area_of_ideal_region(N);
264 int subtotal_n_regions = 1;
265 for (int collar_n = 0; collar_n < n_collars; ++collar_n) {
266 subtotal_n_regions = subtotal_n_regions + n_regions[1 + collar_n];
267 c_caps[collar_n + 1] = sradius_of_cap(subtotal_n_regions * ideal_region_area);
268 }
269 c_caps[n_collars + 1] = M_PI;
270 }
271
272 // Disable optimisation for Cray (See ATLAS-327)
273 #ifdef _CRAYC
274 #pragma _CRI noopt
275 #endif
276 void eq_caps(int N, std::vector<int>& n_regions, std::vector<double>& s_cap) {
277 //
278 // eq_regions uses the zonal equal area sphere partitioning algorithm to
279 // partition
280 // the surface of a sphere into N regions of equal area and small diameter.
281 //
282
283 if (N == 1) {
284 //
285 // We have only one region, which must be the whole sphere.
286 //
287 n_regions.resize(1);
288 s_cap.resize(1);
289 n_regions[0] = 1;
290 s_cap[0] = M_PI;
291 // int n_regions_ns=1;
292 }
293 else {
294 //
295 // Given N, determine c_polar
296 // the colatitude of the North polar spherical cap.
297 //
298 const double c_polar = polar_colat(N);
299
300 //
301 // Given N, determine the ideal angle for spherical collars.
302 // Based on N, this ideal angle, and c_polar,
303 // determine n_collars, the number of collars between the polar caps.
304 //
305 const int n_collars = num_collars(N, c_polar, ideal_collar_angle(N));
306
307 // int n_regions_ns=n_collars+2;
308 //
309 // Given N, c_polar and n_collars, determine r_regions,
310 // a list of the ideal real number of regions in each collar,
311 // plus the polar caps.
312 // The number of elements is n_collars+2.
313 // r_regions[0] is 1.
314 // r_regions[2+n_collars-1] is 1.
315 // The sum of r_regions is N.
316 std::vector<double> r_regions(n_collars + 2);
317 ideal_region_list(N, c_polar, n_collars, r_regions.data());
318 //
319 // Given N and r_regions, determine n_regions, a list of the natural number
320 // of regions in each collar and the polar caps.
321 // This list is as close as possible to r_regions.
322 // The number of elements is n_collars+2.
323 // n_regions[0] is 1.
324 // n_regions[2+n_collars-1] is 1.
325 // The sum of n_regions is N.
326 //
327 n_regions.resize(n_collars + 2);
328 round_to_naturals(N, n_collars, r_regions.data(), n_regions.data());
329 //
330 // Given dim, N, c_polar and n_regions, determine s_cap,
331 // an increasing list of colatitudes of spherical caps which enclose the
332 // same area
333 // as that given by the cumulative sum of regions.
334 // The number of elements is n_collars+2.
335 // s_cap[0] is c_polar.
336 // s_cap[n_collars] is Pi-c_polar.
337 // s_cap[n_collars+1] is Pi.
338 //
339 s_cap.resize(n_collars + 2);
340 cap_colats(N, n_collars, c_polar, n_regions.data(), s_cap.data());
341 }
342 // int n_regions_ew=maxval(n_regions(:));
343 }
344 // Reenable optimisation for Cray (See ATLAS-327)
345 #ifdef _CRAYC
346 #pragma _CRI opt
347 #endif
348
349 void eq_regions(int N, double xmin[], double xmax[], double ymin[], double ymax[]) {
350 // EQ_REGIONS Recursive zonal equal area (EQ) partition of sphere
351 //
352 // Syntax
353 // [regions,dim_1_rot] = eq_regions(dim,N,options);
354 //
355 // Description
356 // REGIONS = EQ_REGIONS(dim,N) uses the recursive zonal equal area sphere
357 // partitioning algorithm to partition S^dim (the unit sphere in dim+1
358 // dimensional space) into N regions of equal area and small diameter.
359 //
360 // The arguments dim and N must be positive integers.
361 //
362 // The result REGIONS is a (dim by 2 by N) array, representing the regions
363 // of S^dim. Each element represents a pair of vertex points in spherical
364 // polar
365 // coordinates.
366 //
367 // Each region is defined as a product of intervals in spherical polar
368 // coordinates. The pair of vertex points regions(:,1,n) and regions(:,2,n)
369 // give
370 // the lower and upper limits of each interval.
371 //
372 // REGIONS = EQ_REGIONS(dim,N,'offset','extra') uses experimental extra
373 // offsets for S^2 and S^3 to try to minimize energy. If dim > 3, extra
374 // offsets
375 // are not used.
376 //
377 // REGIONS = EQ_REGIONS(dim,N,extra_offset) uses experimental extra offsets
378 // if extra_offset is true or non-zero.
379 //
380 // [REGIONS,DIM_1_ROT] = EQ_REGIONS(dim,N) also returns DIM_1_ROT, a cell
381 // array containing N rotation matrices, one per region, each of size dim by
382 // dim.
383 // These describe the R^dim rotation needed to place the region in its final
384 // position.
385 //
386 // [REGIONS,DIM_1_ROT] = EQ_REGIONS(dim,N,'offset','extra') partitions S^dim
387 // into N regions, using extra offsets, and also returning DIM_1_ROT, as
388 // above.
389 //
390
391 if (N == 1) {
392 //
393 // We have only one region, which must be the whole sphere.
394 //
395 xmin[0] = 0.;
396 ymin[0] = -0.5 * M_PI;
397 xmax[0] = 2. * M_PI;
398 ymax[0] = 0.5 * M_PI;
399 return;
400 }
401 //
402 // Start the partition of the sphere into N regions by partitioning
403 // to caps defined in the current dimension.
404 //
405 std::vector<int> n_regions;
406 std::vector<double> s_cap;
407 eq_caps(N, n_regions, s_cap);
408 //
409 // s_cap is an increasing list of colatitudes of the caps.
410 //
411 //
412 // We have a number of zones: two polar caps and a number of collars.
413 // n_regions is the list of the number of regions in each zone.
414 //
415 int n_collars = n_regions.size() - 2;
416 //
417 // Start with the top cap.
418 //
419 xmin[0] = 0.;
420 ymin[0] = 0.5 * M_PI - s_cap[0];
421 xmax[0] = 2. * M_PI;
422 ymax[0] = 0.5 * M_PI;
423
424 int region_n = 1;
425 for (int collar_n = 0; collar_n < n_collars; ++collar_n) {
426 for (int region_ew = 0; region_ew < n_regions[collar_n + 1]; ++region_ew) {
427 xmin[region_n] = 2. * M_PI / (static_cast<double>(n_regions[collar_n + 1])) * region_ew;
428 ymin[region_n] = 0.5 * M_PI - s_cap[collar_n + 1];
429 xmax[region_n] = 2. * M_PI / (static_cast<double>(n_regions[collar_n + 1])) * (region_ew + 1.);
430 ymax[region_n] = 0.5 * M_PI - s_cap[collar_n];
431 ++region_n;
432 }
433 }
434 //
435 // End with the bottom cap.
436 //
437 xmin[N - 1] = 0.;
438 ymin[N - 1] = -0.5 * M_PI;
439 xmax[N - 1] = 2. * M_PI;
440 ymax[N - 1] = 0.5 * M_PI - s_cap[s_cap.size() - 2];
441 }
442
443 void EqualRegionsPartitioner::init() {
444 N_ = nb_partitions();
445 std::vector<double> s_cap;
446 eq_caps(N_, sectors_, s_cap);
447 bands_.resize(s_cap.size());
448 for (size_t n = 0; n < s_cap.size(); ++n) {
449 bands_[n] = 0.5 * M_PI - s_cap[n];
450 }
451 }
452
453 EqualRegionsPartitioner::EqualRegionsPartitioner():
454 Partitioner() {
455 init();
456 }
457
458 EqualRegionsPartitioner::EqualRegionsPartitioner(int N):
459 EqualRegionsPartitioner(N, util::NoConfig()) {
460 }
461
462 EqualRegionsPartitioner::EqualRegionsPartitioner(int N, const eckit::Parametrisation& config):
463 Partitioner(N,config) {
464 std::string crds;
465 if (config.get("coordinates", crds)) {
466 if (crds == "lonlat") {
467 coordinates_ = Coordinates::LONLAT;
468 }
469 }
470 init();
471 }
472
473 EqualRegionsPartitioner::EqualRegionsPartitioner(const eckit::Parametrisation& config):
474 Partitioner(config) {
475 std::string crds;
476 if (config.get("coordinates", crds)) {
477 if (crds == "lonlat") {
478 coordinates_ = Coordinates::LONLAT;
479 }
480 }
481 init();
482 }
483
484 int EqualRegionsPartitioner::partition(const double& x, const double& y) const {
485 int b = band(y);
486 int p = 0;
487 for (int n = 0; n < b; ++n) {
488 p += sectors_[n];
489 }
490 return p + sector(b, x);
491 }
492
493 int EqualRegionsPartitioner::band(const double& y) const {
494 return std::distance(bands_.begin(), std::lower_bound(bands_.begin(), bands_.end(), y, std::greater<double>()));
495 }
496
497 int EqualRegionsPartitioner::sector(int band, const double& x) const {
498 constexpr double two_pi = 2. * M_PI;
499 constexpr double div_two_pi = 1. / (2. * M_PI + 1.e-8);
500 double xreg = x;
501 if (x < 0.) {
502 xreg += two_pi;
503 }
504 else if (x > two_pi) {
505 xreg -= two_pi;
506 }
507 return std::floor(xreg * sectors_[band] * div_two_pi);
508 }
509
510 void EqualRegionsPartitioner::where(int partition, int& band, int& sector) const {
511 int p = 0;
512 for (size_t b = 0; b < bands_.size(); ++b) {
513 for (int s = 0; s < sectors_[b]; ++s) {
514 if (partition == p) {
515 band = b;
516 sector = s;
517 return;
518 }
519 ++p;
520 }
521 }
522 }
523
524 bool compare_NS_WE(const EqualRegionsPartitioner::NodeInt& node1, const EqualRegionsPartitioner::NodeInt& node2) {
525 if (node1.y > node2.y) {
526 return true;
527 }
528 if (node1.y == node2.y) {
529 return (node1.x < node2.x);
530 }
531 return false;
532 }
533
534 bool compare_WE_NS(const EqualRegionsPartitioner::NodeInt& node1, const EqualRegionsPartitioner::NodeInt& node2) {
535 if (node1.x < node2.x) {
536 return true;
537 }
538 if (node1.x == node2.x) {
539 return (node1.y > node2.y);
540 }
541 return false;
542 }
543
544 void EqualRegionsPartitioner::partition(int nb_nodes, NodeInt nodes[], int part[]) const {
545 ATLAS_TRACE("EqualRegionsPartitioner::partition");
546
547 // std::clock_t init, final;
548 // init=std::clock();
549 // std::cout << "partition start (" << nb_nodes << " points)" << std::endl;
550 int nb_parts = N_;
551 int p;
552 int i;
553 int begin;
554 int end;
555 int band;
556
557 /*
558 Sort nodes from north to south, and west to east. Now we can easily split
559 the points in bands. Note, for RGG, this should not be necessary, as it is
560 already by construction in this order, but then sorting is really fast
561 */
562
563 // std::sort( nodes, nodes+nb_nodes, compare_NS_WE);
564
565 /*
566 For every band, now sort from west to east, and north to south. Inside every
567 band
568 we can now easily split nodes in sectors.
569 */
570 int chunk_size = nb_nodes / nb_parts;
571 int chunk_remainder = nb_nodes - chunk_size * nb_parts;
572 int remainder = chunk_remainder;
573 std::vector<int> count;
574 count.reserve(nb_parts);
575 end = 0;
576 for (band = 0; band < nb_bands(); ++band) {
577 begin = end;
578 for (p = 0; p < nb_regions(band); ++p) {
579 count.push_back(chunk_size + (remainder-- > 0 ? 1 : 0));
580 end += count.back();
581 }
582 std::sort(nodes + begin, nodes + end, compare_WE_NS);
583 }
584
585 /*
586 Create list that tells in original node numbering which part the node belongs
587 to
588 */
589 end = 0;
590 for (p = 0; p < nb_parts; ++p) {
591 begin = end;
592 end = begin + count[p];
593 for (i = begin; i < end; ++i) {
594 part[nodes[i].n] = p;
595 }
596 }
597
598 /*
599 This piece of code is to reorder back along latitudes
600 */
601
602 // begin = 0;
603 // for( p=0; p<nb_parts; ++p )
604 // {
605 // int end = std::floor((p+1)*chunk_size);
606 // std::sort( nodes+begin, nodes+end, compare_NS_WE );
607 // begin = end;
608 // }
609 // final=std::clock()-init;
610 // std::cout << "partition stop (took " << (double)final /
611 // ((double)CLOCKS_PER_SEC) << "s)" << std::endl;
612 }
613
614 void EqualRegionsPartitioner::partition(const Grid& grid, int part[]) const {
615 if (N_ == 1) { // trivial solution, so much faster
616 atlas_omp_parallel_for(idx_t j = 0; j < grid.size(); ++j) { part[j] = 0; }
617 }
618 else {
619 ATLAS_TRACE("EqualRegionsPartitioner::partition");
620
621 ATLAS_ASSERT(grid.projection().units() == "degrees");
622
623 const auto& comm = mpi::comm(mpi_comm());
624 int mpi_rank = static_cast<int>(comm.rank());
625 int mpi_size = static_cast<int>(comm.size());
626
627 atlas::vector<NodeInt> nodes(grid.size());
628 int* nodes_buffer = reinterpret_cast<int*>(nodes.data());
629 long nb_workers = comm.size();
630
631 /*
632 Sort nodes from north to south, and west to east. Now we can easily split
633 the points in bands. Note, for StructuredGrid, this should not be necessary,
634 as it is
635 already by construction in this order, but then sorting is really fast
636 */
637
638 if (StructuredGrid(grid) && (coordinates_ == Coordinates::XY)) {
639 // The grid comes sorted from north to south and west to east by
640 // construction
641 // ATLAS_ASSERT to make sure.
642 StructuredGrid structured_grid(grid);
643 //ATLAS_ASSERT( structured_grid.y( 1 ) < structured_grid.y( 0 ) );
644 ATLAS_ASSERT(structured_grid.x(1, 0) > structured_grid.x(0, 0));
645
646 ATLAS_TRACE("Take shortcut");
647
648
649 if (atlas_omp_get_max_threads() > 1) {
650 atlas_omp_parallel {
651 const idx_t num_threads = atlas_omp_get_num_threads();
652 const idx_t thread_num = atlas_omp_get_thread_num();
653 const idx_t begin = static_cast<idx_t>(thread_num * size_t(structured_grid.size()) / num_threads);
654 const idx_t end =
655 static_cast<idx_t>((thread_num + 1) * size_t(structured_grid.size()) / num_threads);
656 idx_t thread_j_begin = 0;
657 std::vector<idx_t> thread_i_begin(structured_grid.ny());
658 std::vector<idx_t> thread_i_end(structured_grid.ny());
659 idx_t n = 0;
660 for (idx_t j = 0; j < structured_grid.ny(); ++j) {
661 if (n + structured_grid.nx(j) > begin) {
662 thread_j_begin = j;
663 thread_i_begin[j] = begin - n;
664 break;
665 }
666 n += structured_grid.nx(j);
667 }
668 idx_t thread_j_end{thread_j_begin};
669 for (idx_t j = thread_j_begin; j < structured_grid.ny(); ++j) {
670 idx_t i_end = end - n;
671 if (j > thread_j_begin) {
672 thread_i_begin[j] = 0;
673 }
674 if (i_end > structured_grid.nx(j)) {
675 thread_i_end[j] = structured_grid.nx(j);
676 n += structured_grid.nx(j);
677 }
678 else {
679 thread_i_end[j] = i_end;
680 thread_j_end = j + 1;
681 break;
682 }
683 }
684 int nn = begin;
685 for (idx_t j = thread_j_begin; j < thread_j_end; ++j) {
686 int y = microdeg(structured_grid.y(j));
687 for (idx_t i = thread_i_begin[j]; i < thread_i_end[j]; ++i, ++nn) {
688 nodes[nn].x = microdeg(structured_grid.x(i, j));
689 nodes[nn].y = y;
690 nodes[nn].n = nn;
691 }
692 }
693 ATLAS_ASSERT(nn == end);
694 }
695 }
696 else {
697 int n(0);
698 for (idx_t j = 0; j < structured_grid.ny(); ++j) {
699 int y = microdeg(structured_grid.y(j));
700 for (idx_t i = 0; i < structured_grid.nx(j); ++i, ++n) {
701 nodes[n].x = microdeg(structured_grid.x(i, j));
702 nodes[n].y = y;
703 nodes[n].n = n;
704 }
705 }
706 }
707 }
708 else {
709 ATLAS_TRACE("sort all");
710
711 std::vector<eckit::mpi::Request> requests;
712
713 for (int w = 0; w < nb_workers; ++w) {
714 idx_t w_begin = w * grid.size() / N_;
715 idx_t w_end = (w + 1) * grid.size() / N_;
716 if (w == nb_workers - 1) {
717 w_end = grid.size();
718 }
719 idx_t w_size = w_end - w_begin;
720
721 int work_rank = std::min(w, mpi_size - 1);
722
723 if (mpi_rank == 0) {
724 ATLAS_ASSERT(valid_mpi_size(w_size * 3));
725 requests.push_back(comm.iReceive(nodes_buffer + w_begin * 3, w_size * 3,
726 /* source= */ work_rank, /* tag= */ 0));
727 }
728
729 if (mpi_rank == work_rank) {
730 atlas::vector<NodeInt> w_nodes(w_size);
731 int* w_nodes_buffer = reinterpret_cast<int*>(w_nodes.data());
732
733 if (coordinates_ == Coordinates::XY) {
734 ATLAS_TRACE_SCOPE("create one bit - Coordinates::XY") {
735 if (true) // optimized experimental when true (still need to
736 // benchmark)
737 {
738 int i = w_begin;
739 int j(0);
740 for (const auto& point : subrange(grid.xy(), {w_begin, w_end})) {
741 w_nodes[j].x = microdeg(point[0]);
742 w_nodes[j].y = microdeg(point[1]);
743 w_nodes[j].n = i++;
744 ++j;
745 }
746 }
747 else {
748 idx_t i(0);
749 idx_t j(0);
750 for (const auto& point : grid.xy()) {
751 if (i >= w_begin && i < w_end) {
752 w_nodes[j].x = microdeg(point[0]);
753 w_nodes[j].y = microdeg(point[1]);
754 w_nodes[j].n = i;
755 ++j;
756 }
757 ++i;
758 }
759 }
760 }
761 }
762 else if (coordinates_ == Coordinates::LONLAT) {
763 ATLAS_TRACE_SCOPE("create one bit - Coordinates::LONLAT") {
764 if (true) // optimized experimental when true (still need to
765 // benchmark)
766 {
767 int i = w_begin;
768 int j(0);
769 for (const auto& point : subrange(grid.lonlat(), {w_begin, w_end})) {
770 w_nodes[j].x = microdeg(point[0]);
771 w_nodes[j].y = microdeg(point[1]);
772 w_nodes[j].n = i++;
773 ++j;
774 }
775 }
776 else {
777 idx_t i(0);
778 idx_t j(0);
779 for (const auto& point : grid.xy()) {
780 if (i >= w_begin && i < w_end) {
781 w_nodes[j].x = microdeg(point[0]);
782 w_nodes[j].y = microdeg(point[1]);
783 w_nodes[j].n = i;
784 ++j;
785 }
786 ++i;
787 }
788 }
789 }
790 }
791 else {
792 ATLAS_THROW_EXCEPTION("Should not be here");
793 }
794 ATLAS_TRACE_SCOPE("sort one bit") { omp::sort(w_nodes.begin(), w_nodes.end(), compare_NS_WE); }
795 ATLAS_TRACE_SCOPE("send to rank0") {
796 ATLAS_ASSERT(valid_mpi_size(w_size * 3));
797 comm.send(w_nodes_buffer, w_size * 3, /* dest= */ 0, /* tag= */ 0);
798 }
799 }
800 }
801 ATLAS_TRACE_MPI(WAIT) {
802 for (auto request : requests) {
803 comm.wait(request);
804 }
805 }
806 ATLAS_TRACE_SCOPE("merge sorted") {
807 for (int w = 0; w < nb_workers; ++w) {
808 int w_begin = w * grid.size() / N_;
809 int w_end = (w + 1) * grid.size() / N_;
810 if (w == nb_workers - 1) {
811 w_end = grid.size();
812 }
813 if (w != 0) {
814 std::inplace_merge(nodes.begin(), nodes.begin() + w_begin, nodes.begin() + w_end,
815 compare_NS_WE);
816 }
817 }
818 }
819 ATLAS_TRACE_MPI(BROADCAST) {
820 ATLAS_ASSERT(valid_mpi_size(grid.size() * 3));
821 comm.broadcast(nodes_buffer, grid.size() * 3, /* root= */ 0);
822 }
823 } // sort all
824
825 /*
826 For every band, now sort from west to east, and north to south. Inside every
827 band
828 we can now easily split nodes in sectors.
829 */
830
831 ATLAS_TRACE_SCOPE("sort bands") {
832 ATLAS_TRACE_BARRIERS(false); // avoid deadlock
833
834 std::vector<eckit::mpi::Request> requests;
835
836 int nb_parts = N_;
837 size_t nb_nodes = grid.size();
838 size_t chunk_size = nb_nodes / nb_parts;
839 size_t chunk_remainder = nb_nodes - chunk_size * nb_parts;
840 int remainder = chunk_remainder;
841 std::vector<size_t> count;
842 count.reserve(nb_parts);
843 std::vector<size_t> displs;
844 displs.reserve(nb_parts + 1);
845 std::vector<size_t> b_count;
846 b_count.reserve(nb_bands());
847 std::vector<size_t> b_displs;
848 b_displs.reserve(nb_bands() + 1);
849
850 {
851 size_t end = 0;
852 for (int band = 0; band < nb_bands(); ++band) {
853 b_displs.emplace_back(end);
854 size_t b_size(0);
855 for (int p = 0; p < nb_regions(band); ++p) {
856 size_t w_size = chunk_size + (remainder-- > 0 ? size_t(1) : size_t(0));
857 displs.emplace_back(end);
858 count.emplace_back(w_size);
859 end += w_size;
860 b_size += w_size;
861 }
862 b_count.emplace_back(b_size);
863 }
864 displs.emplace_back(end);
865 b_displs.emplace_back(end);
866 }
867
868 int w(0);
869 for (int band = 0; band < nb_bands(); ++band) {
870 int w0 = w;
871 int w0_work_rank = std::min(w0, mpi_size - 1);
872
873 for (int p = 0; p < nb_regions(band); ++p) {
874 size_t w_begin = displs[w];
875 size_t w_size = count[w];
876 size_t w_end = w_begin + w_size;
877 int work_rank = std::min(w, mpi_size - 1);
878
879 if (mpi_rank == w0_work_rank) {
880 if (mpi_rank != work_rank) {
881 ATLAS_ASSERT(valid_mpi_size(w_size * 3));
882 requests.push_back(comm.iReceive(nodes_buffer + w_begin * 3, w_size * 3,
883 /* source= */ work_rank, /* tag= */ 0));
884 }
885 }
886 if (work_rank == mpi_rank) {
887 ATLAS_TRACE_SCOPE("sort bit of band on each MPI rank") {
888 omp::sort(nodes.data() + w_begin, nodes.data() + w_end, compare_WE_NS);
889 }
890 if (mpi_rank != w0_work_rank) {
891 ATLAS_TRACE_SCOPE("send bit of band to band leader " + std::to_string(w0_work_rank)) {
892 ATLAS_ASSERT(valid_mpi_size(w_size * 3));
893 comm.send(nodes_buffer + w_begin * 3, w_size * 3,
894 /* dest= */ w0_work_rank, /* tag= */ 0);
895 }
896 }
897 }
898 ++w;
899 }
900 }
901 ATLAS_TRACE_MPI(WAIT) {
902 for (auto request : requests) {
903 comm.wait(request);
904 }
905 }
906 requests.clear();
907 std::vector<int> w0_band(nb_bands());
908 for (int band = 0, w = 0; band < nb_bands(); ++band) {
909 w0_band[band] = w;
910 w += nb_regions(band);
911 }
912
913 for (int band = 0; band < nb_bands(); ++band) {
914 int w0 = w0_band[band];
915 int w0_work_rank = std::min(w0, mpi_size - 1);
916 if (mpi_rank == w0_work_rank) {
917 auto nodes_band_begin = nodes.begin() + b_displs[band];
918 auto nodes_band_end = nodes_band_begin + b_count[band];
919 auto blocks_size_begin = count.begin() + w0;
920 auto blocks_size_end = blocks_size_begin + nb_regions(band);
921 ATLAS_TRACE_SCOPE("band leader merging bits for band " + std::to_string(band)) {
922 omp::merge_blocks(nodes_band_begin, nodes_band_end, blocks_size_begin, blocks_size_end,
923 compare_WE_NS);
924 }
925 }
926 }
927
928 for (int band = 0; band < nb_bands(); ++band) {
929 int w0 = w0_band[band];
930 size_t w0_begin = b_displs[band];
931 size_t w0_size = b_count[band];
932 int w0_work_rank = std::min(w0, mpi_size - 1);
933
934 if (mpi_rank == 0) {
935 if (mpi_rank != w0_work_rank) {
936 ATLAS_ASSERT(valid_mpi_size(w0_size * 3));
937 requests.push_back(comm.iReceive(nodes_buffer + w0_begin * 3, w0_size * 3,
938 /* source= */ w0_work_rank, /* tag= */ 0));
939 }
940 }
941 if (mpi_rank == w0_work_rank) {
942 ATLAS_TRACE_SCOPE("send band to rank 0") {
943 if (mpi_rank != 0) {
944 ATLAS_ASSERT(valid_mpi_size(w0_size * 3));
945 comm.send(nodes_buffer + w0_begin * 3, w0_size * 3, /* dest= */ 0,
946 /* tag= */ 0);
947 }
948 }
949 }
950 }
951 if (mpi_rank == 0) {
952 ATLAS_TRACE_SCOPE("rank 0 waiting for all bands to come in") {
953 ATLAS_TRACE_MPI(WAIT) {
954 for (auto request : requests) {
955 comm.wait(request);
956 }
957 }
958 }
959 }
960
961
962 /*
963 Create list that tells in original node numbering which part the node
964 belongs to
965 */
966 for (int p = 0; p < nb_parts; ++p) {
967 size_t begin = displs[p];
968 size_t end = begin + count[p];
969 atlas_omp_parallel_for(size_t i = begin; i < end; ++i) { part[nodes[i].n] = p; }
970 }
971 ATLAS_TRACE_MPI(BROADCAST) {
972 ATLAS_ASSERT(valid_mpi_size(nb_nodes));
973 comm.broadcast(part, nb_nodes, 0);
974 }
975
976 } // sort bands
977 } // else
978 }
979
980 } // namespace partitioner
981 } // namespace detail
982 } // namespace grid
983 } // namespace atlas
984
985 namespace {
986 atlas::grid::detail::partitioner::PartitionerBuilder<atlas::grid::detail::partitioner::EqualRegionsPartitioner>
987 __EqualRegions("equal_regions");
988 }