domain::BlockZCurveProcDistribution< Dim > Struct Template Reference

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.

Detailed Description

template<size_t Dim>
struct domain::BlockZCurveProcDistribution< Dim >

Distribution strategy for assigning elements to CPUs using a Morton ('Z-order') space-filling curve to determine placement within each block.

Details

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_ts 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:

• If there are 8 blocks, 16 elements per block, 16 cores, and all cores are allowed to have elements: each core gets an allowance of 128 / 16 = 8 elements, so each core gets half of a block, and the 8 elements for each core within the block are chosen via Z-order curve for the respective blocks.
• If there are 3 blocks, 4 elements per block, 4 cores, and all cores are allowed to have elements: each core gets an allowance of 12 / 4 = 3 elements. Core 0 gets three elements from the first block, core 1 gets one element from the first block and two elements from the second block, core 2 gets two elements from the second block and one from the third, and core 3 gets the remaining three elements from the third block. Each collection of elements within the blocks are then assigned using intervals along the Z-order curve for each block.
• Same as the previous example, 3 blocks, 4 elements per block, and 4 cores, except now we require that physical cores 1 and 3 don't have any elements on them. The new distribution would look like:
  • Elements on old core 0 -> new core 0
  • No elements on new core 1
  • Elements on old core 1 -> new core 2
  • No elements on new core 3
  • Elements on old core 2 -> new core 4
  • Elements on old core 3 -> new core 5

Note

In the third example, even though only 4 cores are used to place elements, the simulation is required to be run on at least 6 cores (4 cores for elements + 2 cores without elements)

Morton curves are a simple and easily-computed space-filling curve that (unlike Hilbert curves) permit diagonal traversal. See, for instance, [107] 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:

        x-->
        0   1   2   3
      ----------------
y  0 |  0   2   4   6
|    |  | / | / | / |
v  1 |  1   3   5   7

(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.

Warning

The use of the Morton curve to generate a well-clustered element distribution currently assumes that the refinement is uniform over each block, with no internal structure that would be generated by, for instance AMR. This distribution method will need alteration to perform well for blocks with internal structure from h-refinement. Morton curves can be defined recursively, so a generalization of the present method is possible for blocks with internal refinement

---

The documentation for this struct was generated from the following file:

• src/Domain/ElementDistribution.hpp