Adaptive mesh refinement techniques for multiple spatial dimensions were first developed by Berger and Oliger [2] to solve time-dependent hyperbolic partial differential equations. These techniques are based on previous work on locally nested refinement structures in one spatial dimension by Bolstad [4]. Adaptive mesh refinement methods were later used by Berger and Colella to resolve shock waves in computational fluid dynamics [1]. Our work with adaptive mesh methods applies this same computational methodology to elliptic partial differential equations and adaptive eigenvalue problems [15].
Berger and Saltzman have implemented a parallel 2d adaptive mesh refinement code in Connection Machine Fortran for the CM-2 [3]. Their data parallel implementation required that all regions of refinement be the same size. As a result, the application over-refined some portions of the computational space, using 60% more memory than an equivalent implementation without the uniform size restriction. Our experiments indicate that uniform refinement regions also result in excessive overheads in three dimensions (see Section 4.3). Because of compiler limitations, their code did not execute efficiently on the CM-5.
Quinlan et al. have developed an adaptive mesh library called AMR++, based on the P++ data parallel C++ \ array class library [17]. P++ supports fine-grain data parallel operations on arrays distributed across collections of processors; it automatically manages data decomposition, interprocessor communication, and synchronization. In contrast to this fine-grain array parallelism, we employ a coarse-grain parallelism in which operations are applied in parallel to entire collections of arrays.
An object oriented library for structured adaptive mesh refinement has been developed at Lawrence Livermore National Laboratory [9]. This software is intended to support hyperbolic gas dynamics applications running on vector supercomputers. The basic abstractions employed in are very similar to our own; in fact, Livermore's adaptive mesh refinement libraries are being parallelized using portions of the LPARX software.
Parashar and Browne are developing a software infrastructure supporting parallel adaptive mesh refinement methods for black hole interactions [21]. Their method is based on a clever load balancing and processor mapping strategy that maps grids to processors through locality-preserving space filling curves. We plan to compare their grid generation and data decomposition strategies with ours in the near future.