ElementDistribution.hpp
1 // Distributed under the MIT License.
2 // See LICENSE.txt for details.
3 
4 #pragma once
5 
6 #include <array>
7 #include <cstddef>
8 #include <utility>
9 #include <vector>
10 
12 
13 namespace domain {
14 
15 /*!
16  * \brief Distribution strategy for assigning elements to CPUs using a
17  * Morton ('Z-order') space-filling curve to determine placement within each
18  * block.
19  *
20  * \details The element distribution assigns a balanced number of elements to
21  * each processor. This distribution is computed by first greedily assigning to
22  * each processor an allowance of
23  * [total number of elements]/[number of processors] elements from one or more
24  * blocks, starting with the lowest number block that still has elements to
25  * contribute to an allowance.
26  * Then, once those allowances are determined, a separate Z-order curve is
27  * established for each block and the elements are assigned to processors within
28  * each block by greedily filling each processors' allowance by contiguous
29  * intervals along the Z-order curve.
30  * Some examples:
31  * - If there are 8 blocks, 16 elements per block, and 16 cores: each core gets
32  * an allowance of 128 / 16 = 8 elements, so each core gets half of a block, and
33  * the 8 elements for each core within the block are chosen via Z-order curve
34  * for the respective blocks.
35  * - If there are 3 blocks, 4 elements per block, and 4 cores: each core gets
36  * an allowance of 12 / 4 = 3 elements. The first core gets three elements from
37  * the first block, the second gets one element from the first block and two
38  * elements from the second block, the third gets two elements from the second
39  * block and one from the third, and the fourth core gets the remaining three
40  * elements from the third block. Each collection of elements within the blocks
41  * are then assigned using intervals along the Z-order curve for each block.
42  *
43  * Morton curves are a simple and easily-computed space-filling curve that
44  * (unlike Hilbert curves) permit diagonal traversal. See, for instance,
45  * \cite Borrell2018 for a discussion of mesh partitioning using space-filling
46  * curves.
47  * A concrete example of the use of a Morton curve in 2d is given below.
48  *
49  * A sketch of a 2D block with 4x2 elements, with each element labeled according
50  * to the order on the Morton curve:
51  * ```
52  * x-->
53  * 0 1 2 3
54  * ----------------
55  * y 0 | 0 2 4 6
56  * | | | / | / | / |
57  * v 1 | 1 3 5 7
58  * ```
59  * (forming a zig-zag path, that under some rotation/reflection has a 'Z'
60  * shape).
61  *
62  * The Morton curve method is a quick way of getting acceptable spatial locality
63  * -- usually, for approximately even distributions, it will ensure that
64  * elements are assigned in large volume chunks, and the structure of the Morton
65  * curve ensures that for a given processor and block, the elements will be
66  * assigned in no more than two orthogonally connected clusters. In principle, a
67  * Hilbert curve could potentially improve upon the gains obtained by this class
68  * by guaranteeing that all elements within each block form a single orthognally
69  * connected cluster.
70  *
71  * The assignment of portions of blocks to processors may use partial blocks,
72  * and/or multiple blocks to ensure an even distribution of elements to
73  * processors.
74  * We currently make no distinction between dividing elements between processors
75  * within a node and dividing elements between processors across nodes. The
76  * current technique aims to have a simple method of reducing communication
77  * globally, though it would likely be more efficient to prioritize minimization
78  * of inter-node communication, because communication across interconnects is
79  * the primary cost of communication in charm++ runs.
80  *
81  * \warning The use of the Morton curve to generate a well-clustered element
82  * distribution currently assumes that the refinement is uniform over each
83  * block, with no internal structure that would be generated by, for instance
84  * AMR.
85  * This distribution method will need alteration to perform well for blocks with
86  * internal structure from h-refinement. Morton curves can be defined
87  * recursively, so a generalization of the present method is possible for blocks
88  * with internal refinement
89  */
90 template <size_t Dim>
94  refinements_by_block) noexcept;
95 
96  /// Gets the suggested processor number for a particular element,
97  /// determined by the greedy block assignment and Morton curve element
98  /// assignment described in detail in the parent class documentation.
99  size_t get_proc_for_element(const ElementId<Dim>& element_id) const noexcept;
100 
101  private:
102  // in this nested data structure:
103  // - The block id is the first index
104  // - There is an arbitrary number of CPUs per block, each with an element
105  // allowance
106  // - Each element allowance is represented by a pair of proc number, number of
107  // elements in the allowance
109  block_element_distribution_;
110 };
111 } // namespace domain
utility
vector
domain::BlockZCurveProcDistribution
Distribution strategy for assigning elements to CPUs using a Morton ('Z-order') space-filling curve t...
Definition: ElementDistribution.hpp:91
Parallel::number_of_procs
int number_of_procs(const DistribObject &distributed_object) noexcept
Number of processing elements.
Definition: Info.hpp:24
ElementId< Dim >
ElementId.hpp
cstddef
array
domain::BlockZCurveProcDistribution::get_proc_for_element
size_t get_proc_for_element(const ElementId< Dim > &element_id) const noexcept
Gets the suggested processor number for a particular element, determined by the greedy block assignme...