SpECTRE
v2023.01.13
|
Distribution strategy for assigning elements to CPUs using a Morton ('Z-order') space-filling curve to determine placement within each block. More...
#include <ElementDistribution.hpp>
Public Member Functions | |
BlockZCurveProcDistribution (size_t number_of_procs_with_elements, const std::vector< std::array< size_t, Dim > > &refinements_by_block, const std::unordered_set< size_t > &global_procs_to_ignore={}) | |
The number_of_procs_with_elements argument represents how many procs will have elements. This is not necessarily equal to the total number of procs because some global procs may be ignored by the third argument global_procs_to_ignore | |
size_t | get_proc_for_element (const ElementId< Dim > &element_id) const |
Gets the suggested processor number for a particular element, determined by the greedy block assignment and Morton curve element assignment described in detail in the parent class documentation. | |
Distribution strategy for assigning elements to CPUs using a Morton ('Z-order') space-filling curve to determine placement within each block.
The element distribution assigns a balanced number of elements to each processor that is allowed to have elements (default all). Specify which processors aren't allowed to have elements by passing in an unordered set of size_t
s corresponding to the processor number. This distribution is computed by first greedily assigning to each available processor an allowance of [total number of elements]/[number of processors available] elements from one or more blocks, starting with the lowest number block that still has elements to contribute to an allowance. Then, once those allowances are determined, a separate Z-order curve is established for each block and the elements are assigned to processors within each block by greedily filling each available processors' allowance by contiguous intervals along the Z-order curve. Some examples:
Morton curves are a simple and easily-computed space-filling curve that (unlike Hilbert curves) permit diagonal traversal. See, for instance, [125] for a discussion of mesh partitioning using space-filling curves. A concrete example of the use of a Morton curve in 2d is given below.
A sketch of a 2D block with 4x2 elements, with each element labeled according to the order on the Morton curve:
(forming a zig-zag path, that under some rotation/reflection has a 'Z' shape).
The Morton curve method is a quick way of getting acceptable spatial locality – usually, for approximately even distributions, it will ensure that elements are assigned in large volume chunks, and the structure of the Morton curve ensures that for a given processor and block, the elements will be assigned in no more than two orthogonally connected clusters. In principle, a Hilbert curve could potentially improve upon the gains obtained by this class by guaranteeing that all elements within each block form a single orthogonally connected cluster.
The assignment of portions of blocks to processors may use partial blocks, and/or multiple blocks to ensure an even distribution of elements to processors. We currently make no distinction between dividing elements between processors within a node and dividing elements between processors across nodes. The current technique aims to have a simple method of reducing communication globally, though it would likely be more efficient to prioritize minimization of inter-node communication, because communication across interconnects is the primary cost of communication in charm++ runs.