2 Problem Description

Dynamically adaptive numerical techniques for solving differential equations provide a means for concentrating computational effort to appropriate regions in the computational domain. These techniques lead to more efficient and cost-effective solutions to time dependent problems exhibiting localized features. In the case of SAMR methods, this is achieved by tracking regions in the domain that require additional resolution and dynamically overlaying finer grids over these regions. These methods start with a base coarse grid with minimum acceptable resolution that covers the entire computational domain. As the solution progresses, regions in the domain requiring additional resolution are tagged and finer grids are overlaid on the tagged regions of the coarse grid. Refinement proceeds recursively so that regions on the finer grid requiring more resolution are similarly tagged and even finer grids are overlaid on these regions. The resulting grid structure is a dynamic adaptive grid hierarchy. The adaptive grid hierarchy of the AMR formulation by Berger and Oliger [2] is shown in Figure 1.

Figure 1: Adaptive Grid Hierarchy - 2D (Berger-Oliger AMR scheme)

Distributed implementations of SAMR applications partition the adaptive grid hierarchy across available processors, and operate on the local portions of this domain in parallel. The overall performance of these applications is thus limited by the ability to partition the underlying grid hierarchies at runtime to expose all inherent parallelism, minimize communication and synchronization overheads, and balance load. A critical requirement of the load partitioner is to maintain logical locality across partitions at different levels of the hierarchy and at the same level when they are decomposed and mapped across processors. The maintenance of locality minimizes the total communication and synchronization overheads. Distributed SAMR applications primarily require two types of communications: Inter-level Communications: These communications are defined between component grids at different levels of the grid hierarchy and consist of prolongations (coarse to fine transfers) and restrictions (fine to coarse transfers). Inter-level communications require a gather/scatter type operation based on an interpolation or averaging stencil. These communications can lead to serialization bottlenecks for a naive decomposition of the grid hierarchy. Intra-level Communication: Intra-level communications (also called ghost communications) are required to update the grid-elements along the boundaries of local portions of a distributed grid. These communications consist of near-neighbor exchanges based on the stencil defined by the difference operator. The communications are regular, and can be scheduled to overlap with computations on the interior region of the local portion of distributed grids. The HPA strategy is based on the composite decomposition of the adaptive grid hierarchy that maintains domain locality [11]. This decomposition technique partitions the grid hierarchy such that all inter-level communication is local to a processor. This scheme uses space filling curves (SFC) [13], which are a class of locality preserving recursive mappings from $n$-dimensional space to $1$-dimensional space. In HPA, after obtaining the composite representation of the adaptive grid hierarchy using SFC, we partition it and assign spans of the curve to processor groups in a hierarchical manner. This strategy takes advantages of the composite decomposition which reduces intra-level communications and localizes inter-level communication. Furthermore, it enables communications in different groups to proceed concurrently, localizes data-movement operations and can enable incremental redistribution.