include/pops/parallel/load_balance.hpp Source FileΒΆ

adc_cpp: include/pops/parallel/load_balance.hpp Source File
adc_cpp 0.3.0
Model-free C++23 core for coupled hyperbolic-elliptic systems on adaptive (AMR) meshes, with MPI and GPU (Kokkos) backends
load_balance.hpp
Go to the documentation of this file.
1#pragma once
2
3#include <pops/mesh/layout/box_array.hpp>
4#include <pops/mesh/layout/distribution_mapping.hpp>
5
6#include <algorithm>
7#include <cstdint>
8#include <numeric>
9#include <vector>
10
29
30namespace pops {
31
32// Spread the bits of x (16 useful bits) onto the even positions of a 64-bit word.
33inline std::uint64_t part1by1(std::uint64_t x) {
34 x &= 0xffffffffULL;
35 x = (x | (x << 16)) & 0x0000ffff0000ffffULL;
36 x = (x | (x << 8)) & 0x00ff00ff00ff00ffULL;
37 x = (x | (x << 4)) & 0x0f0f0f0f0f0f0f0fULL;
38 x = (x | (x << 2)) & 0x3333333333333333ULL;
39 x = (x | (x << 1)) & 0x5555555555555555ULL;
40 return x;
41}
42
43// Morton key (Z-order) interleaving (x, y): x on the even bits, y on the odd bits.
44inline std::uint64_t morton_key(std::uint32_t x, std::uint32_t y) {
45 return part1by1(x) | (part1by1(y) << 1);
46}
47
48// Box indices sorted along the Morton curve (low corner, shifted by the bounding
49// box to stay positive).
50inline std::vector<int> morton_order(const BoxArray& ba) {
51 const int n = ba.size();
52 std::vector<int> order(n);
53 std::iota(order.begin(), order.end(), 0);
54 if (n == 0)
55 return order;
56 const Box2D bb = ba.bounding_box();
57 std::vector<std::uint64_t> key(n);
58 for (int i = 0; i < n; ++i)
59 key[i] = morton_key(static_cast<std::uint32_t>(ba[i].lo[0] - bb.lo[0]),
60 static_cast<std::uint32_t>(ba[i].lo[1] - bb.lo[1]));
61 std::sort(order.begin(), order.end(), [&](int a, int b) { return key[a] < key[b]; });
62 return order;
63}
64
65// Z-order distribution: contiguous segments of ~equal load along the SFC.
66// Guarantees that with nboxes >= nranks each rank receives at least one box.
67inline DistributionMapping make_sfc_distribution(const BoxArray& ba, int nranks) {
68 const int n = ba.size();
69 std::vector<int> rank(n, 0);
70 if (n == 0 || nranks <= 1)
71 return DistributionMapping(std::move(rank));
72
73 const std::vector<int> order = morton_order(ba);
74 std::int64_t total = ba.num_cells();
75 const double target = double(total) / nranks; // target load per rank
76
77 std::int64_t acc = 0;
78 int r = 0;
79 for (int k = 0; k < n; ++k) {
80 const int b = order[k];
81 rank[b] = r;
82 acc += ba[b].num_cells();
83 // advance to the next rank if the target share is reached AND enough boxes
84 // remain to give at least one box to each remaining rank.
85 const int boxes_left = n - 1 - k;
86 const int ranks_left = nranks - 1 - r;
87 if (r < nranks - 1 && acc >= target * (r + 1) && boxes_left >= ranks_left)
88 ++r;
89 }
90 return DistributionMapping(std::move(rank));
91}
92
93// Knapsack distribution (LPT): heaviest box -> least loaded rank.
94inline DistributionMapping make_knapsack_distribution(const BoxArray& ba, int nranks) {
95 const int n = ba.size();
96 std::vector<int> rank(n, 0);
97 if (n == 0 || nranks <= 1)
98 return DistributionMapping(std::move(rank));
99
100 std::vector<int> order(n);
101 std::iota(order.begin(), order.end(), 0);
102 std::sort(order.begin(), order.end(),
103 [&](int a, int b) { return ba[a].num_cells() > ba[b].num_cells(); });
104
105 std::vector<std::int64_t> load(nranks, 0);
106 for (int b : order) {
107 int r = 0;
108 for (int q = 1; q < nranks; ++q)
109 if (load[q] < load[r])
110 r = q;
111 rank[b] = r;
112 load[r] += ba[b].num_cells();
113 }
114 return DistributionMapping(std::move(rank));
115}
116
117// Imbalance = max load / average load (1.0 = perfect).
118inline double load_imbalance(const BoxArray& ba, const DistributionMapping& dm, int nranks) {
119 if (nranks <= 0 || ba.size() == 0)
120 return 1.0;
121 std::vector<std::int64_t> load(nranks, 0);
122 for (int i = 0; i < ba.size(); ++i)
123 load[dm[i]] += ba[i].num_cells();
124 std::int64_t mx = 0, sum = 0;
125 for (std::int64_t l : load) {
126 mx = std::max(mx, l);
127 sum += l;
128 }
129 const double avg = double(sum) / nranks;
130 return avg > 0 ? mx / avg : 1.0;
131}
132
133} // namespace pops
box_array.hpp
BoxArray: the set of boxes tiling a level (disjoint, covering).
pops::BoxArray
Ordered list of boxes tiling a level.
Definition box_array.hpp:22
pops::BoxArray::num_cells
std::int64_t num_cells() const
Total number of valid cells (sum of num_cells over all boxes).
Definition box_array.hpp:49
pops::BoxArray::size
int size() const
Number of boxes in the tiling.
Definition box_array.hpp:42
pops::BoxArray::bounding_box
Box2D bounding_box() const
Smallest box enclosing all boxes (empty box if the tiling is empty).
Definition box_array.hpp:57
pops::DistributionMapping
Owning MPI rank of each box, indexed by GLOBAL box index (parallel to a BoxArray).
Definition distribution_mapping.hpp:19
distribution_mapping.hpp
DistributionMapping: maps each box (by global index) to its owning MPI rank.
pops
Definition amr_hierarchy.hpp:29
pops::load_imbalance
double load_imbalance(const BoxArray &ba, const DistributionMapping &dm, int nranks)
Definition load_balance.hpp:118
pops::part1by1
std::uint64_t part1by1(std::uint64_t x)
Definition load_balance.hpp:33
pops::sum
Real sum(const MultiFab &mf, int comp=0)
Sum of the VALID cells of component comp, reduced over ALL ranks (all_reduce).
Definition multifab.hpp:121
pops::make_sfc_distribution
DistributionMapping make_sfc_distribution(const BoxArray &ba, int nranks)
Definition load_balance.hpp:67
pops::morton_key
std::uint64_t morton_key(std::uint32_t x, std::uint32_t y)
Definition load_balance.hpp:44
pops::morton_order
std::vector< int > morton_order(const BoxArray &ba)
Definition load_balance.hpp:50
pops::make_knapsack_distribution
DistributionMapping make_knapsack_distribution(const BoxArray &ba, int nranks)
Definition load_balance.hpp:94
pops::Box2D
2D integer index space, cell-centered.
Definition box2d.hpp:37
pops::Box2D::lo
int lo[2]
Definition box2d.hpp:38
Generated by doxygen 1.9.8