AMROC Main     Blockstructured Adaptive Mesh Refinement in object-oriented C++

Design of AMROC's DAGH

previous     next
The most important elementary classes inside DAGH are the BBox-class and the GridData-class. BBox defines a rectangular box in a global integer index space. Methods for geometric operations on boxes like concatenation or intersection are available. GridData adds consecutive data storage to a BBox-object.

The geometrical description of all refinement areas is stored in hierarchical GridBoxLists inside GridHierarchy. Several "distributed'' GridFunctions of various storage types create GridDataBlock-objects with a GridData-objects for the raw data according to these lists. The GridHierarchy consists of global GridBoxLists storing the complete refinement information and GridBoxLists for each processor's local contribution. During computation, the grid hierarchy is dynamically repartitioned under the restriction that higher level data must be assigned to the same processor as the coarsest level data. As GridDataBlock-objects are generated directly from these local GridBoxLists, all GridFunctions become equally distributed following the actual "floor plan''. Redistribution over processors is carried out automatically as a natural part of the AMR-algorithm whenever the grid hierarchy changes.

Note that the described data representation model assigns multiple GridDataBlock-objects stored in different GridFunctions to a single subgrid. The AMR-algorithm utilizes rectangular data blocks of various storage type to handle a single refinement grid, but in our design these blocks are accessed via GridDataBlock-objects kept in different GridFunctions.

This special design follows from the perception that the tedious technical overhead in implementing the AMR-method in a distributed memory environment can be simplified significantly, if commonality in organizing rectangular data blocks independent of their storage type is exploited. This common functionality is concentrated inside the GridFunction-class and by employing template data types and compile-time parameters carefully all GridFunction-objects are derived from this base class without a loss of computational performance.

AMR requires hierarchical GridFunctions of various spatial dimensions, with complex storage data types and with differently sized overlap regions. Deriving all GridFunction-objects from one base class guarantees a common interface and most parts of AMROC have been coded independently of spatial dimensions and size of the vector of state.

A change of the hierarchy is initiated by clustering flagged cells into suitable BBoxes. Each processor has to generate a properly nested BBoxList of new refinement regions in his actual contribution of the computational domain. These lists are used to update the global grid hierarchy. A global union of these BBoxLists is constructed on each level. The workload of the entire hierachy is estimated and accumulated in GridUnit-objects. The minimal size of a GridUnit is one cell of the coarsest level. The usage of larger GridUnits can be enforced with GridHierarchy.setgucfactor(), the GridUnit-coarsening factor. The partitioning algorithm called by DAGHDistribution breaks up the derived composite GridUnitList in load-balanced portions and assigns a local GridUnitList to each processor. Each node derives its new local GridBoxList by intersecting its local GridUnitList with the global union of BBoxLists.

The algorithm used for partitioning the computational domain has to meet several requirements. It must balance the estimated workload, while maintaining patches of sufficient size. The algorithm should be fast, because it is executed after each regrid operation. Additionally, communication for redistributing GridFunctions and synchronizing them during calculation should be minimal. DAGH employs a generalization of the Peano-Hilbert space-filling curve as a partitioner that. It is implemented in the PeanoHilbert-class. Note that the generalized Peano-Hilbert space-filling curve can only be defined on a domain with equal extends on all sides that are a power of 2. Therefore the domain that is internally used for the space-filling curve usually exceed the computational domain (see fig. 4). This is the reason why the space-filling curve can not produce perfectly connected distributions in all cases.

After recomposing GridHierarchy's local GridBoxList all GridFunctions have to be redistributed. It depends on the type of the particular GridFunction how the newly created patches have to be initialized.

Figure 4: Usage of Hilbert's space-filling curve as a partitoner (left). All data of all levels is distributed to the same node (right).
Usage of Hilbert's space-filling curve as a partitoner (left). All
data of all levels is distributed to the same node (right).


Quickstart       Users Guide     Programmers Reference     Installation      Examples     Download

AMROC Main      Home      Contact
last update: 6/1/04