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, const std::vector< std::array< size_t, Dim >> &refinements_by_block) noexcept | |
| 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 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. This distribution is computed by first greedily assigning to each processor an allowance of [total number of elements]/[number of processors] 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 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, [90] 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 orthognally 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.