Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 :
4 : #pragma once
5 :
6 : #include <array>
7 : #include <cstddef>
8 : #include <iosfwd>
9 : #include <optional>
10 : #include <unordered_map>
11 : #include <unordered_set>
12 : #include <utility>
13 : #include <vector>
14 :
15 : /// \cond
16 : template <size_t Dim>
17 : class Block;
18 :
19 : template <size_t Dim>
20 : class ElementId;
21 :
22 : namespace Options {
23 : class Option;
24 : template <typename T>
25 : struct create_from_yaml;
26 : } // namespace Options
27 :
28 : namespace Spectral {
29 : enum class Basis : uint8_t;
30 : enum class Quadrature : uint8_t;
31 : } // namespace Spectral
32 : /// \endcond
33 :
34 : namespace domain {
35 : /// The weighting scheme for assigning computational costs to `Element`s for
36 : /// distributing balanced compuational costs per processor (see
37 : /// `BlockZCurveProcDistribution`)
38 1 : enum class ElementWeight {
39 : /// A weighting scheme where each `Element` is assigned the same computational
40 : /// cost
41 : Uniform,
42 : /// A weighting scheme where each `Element`'s computational cost is equal to
43 : /// the number of grid points in that `Element`
44 : NumGridPoints,
45 : /// A weighting scheme where each `Element`'s computational cost is weighted
46 : /// by both the number of grid points and minimum spacing between grid points
47 : /// in that `Element` (see `get_num_points_and_grid_spacing_cost()` for
48 : /// details)
49 : NumGridPointsAndGridSpacing
50 : };
51 :
52 0 : std::ostream& operator<<(std::ostream& os, ElementWeight weight);
53 :
54 : /// \brief Get the cost of each `Element` in a list of `Block`s where
55 : /// `element_weight` specifies which weight distribution scheme to use
56 : ///
57 : /// \details It is only necessary to pass in a value for `i1_basis` and
58 : /// `i1_quadrature` if the value for `element_weight` is
59 : /// `ElementWeight::NumGridPointsAndGridSpacing`. Otherwise, the argument isn't
60 : /// needed and will have no effect if it does have a value.
61 : ///
62 : /// The `extents_override` gives, for individual `Element`s, the extents to use
63 : /// in place of their block's `initial_extents` when computing their cost (e.g.
64 : /// to weight an element that runs a finite-difference scheme by its
65 : /// finite-difference grid). It is ignored for `ElementWeight::Uniform` and must
66 : /// be empty for `ElementWeight::NumGridPointsAndGridSpacing`, since that weight
67 : /// builds a DG mesh from the extents.
68 : template <size_t Dim>
69 1 : std::unordered_map<ElementId<Dim>, double> get_element_costs(
70 : const std::vector<Block<Dim>>& blocks,
71 : const std::vector<std::array<size_t, Dim>>& initial_refinement_levels,
72 : const std::vector<std::array<size_t, Dim>>& initial_extents,
73 : ElementWeight element_weight,
74 : const std::optional<Spectral::Basis>& i1_basis,
75 : const std::optional<Spectral::Quadrature>& i1_quadrature,
76 : const std::unordered_map<ElementId<Dim>, std::array<size_t, Dim>>&
77 : extents_override = {});
78 :
79 : /*!
80 : * \brief Distribution strategy for assigning elements to CPUs using a
81 : * Morton ('Z-order') space-filling curve to determine placement within each
82 : * block, where `Element`s are distributed across CPUs
83 : *
84 : * \details The element distribution attempts to assign a balanced total
85 : * computational cost to each processor that is allowed to have `Element`s.
86 : * First, each `Block`'s `Element`s are ordered by their Z-curve index (see more
87 : * below). `Element`s are traversed in this order and assigned to CPUs in order,
88 : * moving onto the next CPU once the target cost per CPU is met. The target cost
89 : * per CPU is defined as the remaining cost to distribute divided by the
90 : * remaining number of CPUs to distribute to. This is an important distinction
91 : * from simply having one constant target cost per CPU defined as the total cost
92 : * divided by the total number of CPUs with elements. Since the total cost of
93 : * `Element`s on a processor will nearly never add up to be exactly the average
94 : * cost per CPU, this means that we would either have to decide to overshoot or
95 : * undershoot the average as we iterate over the CPUs and assign `Element`s. If
96 : * we overshoot the average on each processor, the final processor could have a
97 : * much lower cost than the rest of the processors and we run the risk of
98 : * overshooting so much that one or more of the requested processors don't get
99 : * assigned any `Element`s at all. If we undershoot the average on each
100 : * processor, the final processor could have a much higher cost than the others
101 : * due to remainder cost piling up. This algorithm avoids these risks by instead
102 : * adjusting the target cost per CPU as we finish assigning cost to previous
103 : * CPUs.
104 : *
105 : * Morton curves are a simple and easily-computed space-filling curve that
106 : * (unlike Hilbert curves) permit diagonal traversal. See, for instance,
107 : * \cite Borrell2018 for a discussion of mesh partitioning using space-filling
108 : * curves.
109 : * A concrete example of the use of a Morton curve in 2d is given below.
110 : *
111 : * A sketch of a 2D block with 4x2 elements, with each element labeled according
112 : * to the order on the Morton curve:
113 : * ```
114 : * x-->
115 : * 0 1 2 3
116 : * ----------------
117 : * y 0 | 0 2 4 6
118 : * | | | / | / | / |
119 : * v 1 | 1 3 5 7
120 : * ```
121 : * (forming a zig-zag path, that under some rotation/reflection has a 'Z'
122 : * shape).
123 : *
124 : * The Morton curve method is a quick way of getting acceptable spatial locality
125 : * -- usually, for approximately even distributions, it will ensure that
126 : * elements are assigned in large volume chunks, and the structure of the Morton
127 : * curve ensures that for a given processor and block, the elements will be
128 : * assigned in no more than two orthogonally connected clusters. In principle, a
129 : * Hilbert curve could potentially improve upon the gains obtained by this class
130 : * by guaranteeing that all elements within each block form a single
131 : * orthogonally connected cluster.
132 : *
133 : * The assignment of portions of blocks to processors may use partial blocks,
134 : * and/or multiple blocks to ensure an even distribution of elements to
135 : * processors.
136 : * We currently make no distinction between dividing elements between processors
137 : * within a node and dividing elements between processors across nodes. The
138 : * current technique aims to have a simple method of reducing communication
139 : * globally, though it would likely be more efficient to prioritize minimization
140 : * of inter-node communication, because communication across interconnects is
141 : * the primary cost of communication in charm++ runs.
142 : *
143 : * \warning The use of the Morton curve to generate a well-clustered element
144 : * distribution currently assumes that the refinement is uniform over each
145 : * block, with no internal structure that would be generated by, for instance
146 : * AMR.
147 : * This distribution method will need alteration to perform well for blocks with
148 : * internal structure from h-refinement. Morton curves can be defined
149 : * recursively, so a generalization of the present method is possible for blocks
150 : * with internal refinement
151 : *
152 : * \tparam Dim the number of spatial dimensions of the `Block`s
153 : */
154 : template <size_t Dim>
155 1 : struct BlockZCurveProcDistribution {
156 0 : BlockZCurveProcDistribution() = default;
157 :
158 : /// The `number_of_procs_with_elements` argument represents how many procs
159 : /// will have elements. This is not necessarily equal to the total number of
160 : /// procs because some global procs may be ignored by the fifth argument
161 : /// `global_procs_to_ignore`.
162 1 : BlockZCurveProcDistribution(
163 : const std::unordered_map<ElementId<Dim>, double>& element_costs,
164 : size_t number_of_procs_with_elements,
165 : const std::vector<Block<Dim>>& blocks,
166 : const std::vector<std::array<size_t, Dim>>& initial_refinement_levels,
167 : const std::unordered_set<size_t>& global_procs_to_ignore = {});
168 :
169 : /// Gets the suggested processor number for a particular `ElementId`,
170 : /// determined by the Morton curve weighted element assignment described in
171 : /// detail in the parent class documentation.
172 1 : size_t get_proc_for_element(const ElementId<Dim>& element_id) const;
173 :
174 : const std::vector<std::vector<std::pair<size_t, size_t>>>&
175 0 : block_element_distribution() const {
176 : return block_element_distribution_;
177 : }
178 :
179 : private:
180 : // in this nested data structure:
181 : // - The block id is the first index
182 : // - There is an arbitrary number of CPUs per block, each with an element
183 : // allowance
184 : // - Each element allowance is represented by a pair of proc number, number of
185 : // elements in the allowance
186 : std::vector<std::vector<std::pair<size_t, size_t>>>
187 0 : block_element_distribution_;
188 : };
189 : } // namespace domain
190 :
191 : template <>
192 0 : struct Options::create_from_yaml<domain::ElementWeight> {
193 : template <typename Metavariables>
194 0 : static domain::ElementWeight create(const Options::Option& options) {
195 : return create<void>(options);
196 : }
197 : };
198 :
199 : template <>
200 0 : domain::ElementWeight
201 : Options::create_from_yaml<domain::ElementWeight>::create<void>(
202 : const Options::Option& options);
|
