Alternate Distribution Algorithms

This page is summarizes the communication and distribution methods used by other codes.

• \(l\) is a specific level.
• \(g(l)\) is the number of grids on level \(l\).
• \(p\) is the number of processors.

CASTRO

Although CASTRO can run both on pure MPI and an OpenMP-MPI hybrid, this discussion will concern itself with pure MPI.

• At least one grid on each level is distributed to each core, meaning that \(\frac{g(l)}{l} >= 1\).

• Each level has an associated MultiFab object, holding the data from all the grids on that level.

• Each processor requires an array of boxes describing the index space on each level (similar to hypre).

• 2 distribution algorithms:
  • Crutchfield's Knapsack algorithm, (see Crutchfield '91, Rendleman '00).
  • Morton-ordering space-filling curve.
  • Dynamic switching between methods, based on \(g\) and \(p\).

ENZO

• Grid hierarchies are replicated on each processor.

• Root grid is split into \(N_{patches} >= p\) and refined grids remain on their processors until the structure of the level is complete.

• Acknowledges that their distribution algorithm is less than optimal (references to a grid-splitting technique by Lan, Taylor & Bryan, '01.

• Sibling search is sped up by using a coarse "chaining" mesh to map grids to neighbor lists. Reduces the number of neighbor comparisons from \(O(g^{2})\) to \(O(g)\).

Orion

• Orion uses an approximate heuristic algorithm by Kernighan & Lin (no reference found yet) to solve a knapsack-style distribution problem.

Flash

• All refinements are performed locally and resulting children stay local until refinements are completed. No information about root decomposition.

• PARAMESH enforces proper nesting.

• Flash uses a work-weighted Morton space-filling curve for load balancing. Warren & Salmon, '93, used it for their N-body code.

References

​Norman et al. 2007 — Enzo parallelization.

​Almgren et al. 2010 — CASTRO parallelization.

​Fryxell et al. 2000 — FLASH parallelization.

​Rendleman et al. 1999 — An additional resource on parallelization of AMR algorithms.