The accurate solution of many problems in science and engineering requires the resolution of unpredictable, localized physical phenomena. Examples include shock waves in computational fluid dynamics [1] and the near-singular atomic core potentials in materials design [6]. The key feature of these problems is that some portions of the problem domain---for example, regions containing the shock waves or the atomic nuclei---require higher resolution, and thus more computational effort, than other areas of the computational space.
Structured adaptive numerical methods [2,5,19] dynamically place computational resources, such as CPU cycles and memory, only where needed to meet accuracy requirements; thus, they can achieve better accuracy for the same computational resources as compared to non-adaptive methods. Although structured adaptive mesh methods incur some overhead costs associated with adaptivity, such as error estimation and data structure management, these overheads are insignificant when compared to the savings gained through selective refinement [3].
Adaptive mesh methods are difficult to implement on serial architectures---not to mention parallel machines---because they rely on dynamic, complicated data structures with irregular communication patterns. On parallel platforms, the programmer is burdened with the responsibility of managing data distributed across processor memories and orchestrating interprocessor communication and synchronization. Because adaptive mesh applications change in response to the dynamics of the problem, little can be known about the structure of the computation at compile-time. Thus, decisions about data decomposition, the assignment of work to processors, and the calculation of communication patterns must be made at run-time. It is an open research question whether the irregularity of an adaptive mesh application can be efficiently supported in a data parallel language such as High Performance Fortran [14]. In Section 4.3, we present computational results which show that the restrictions imposed by a data parallel implementation would significantly impact performance.
We have developed an efficient, portable, parallel software infrastructure for structured adaptive mesh methods which hides these implementation details. It presents computational scientists with high-level tools which allow them to concentrate on the application and mathematics instead of low-level concerns of data distribution and interprocessor communication. Such support enables scientists to develop parallel, portable, efficient applications in a fraction of the time that would have been required if the application had been developed from scratch. Our structured adaptive mesh API (Application Programmer Interface), implemented as a collection of C++ classes, is built on the parallelization and communication mechanisms of the LPARX run-time system [16]. Our software runs on a variety of high-performance computer platforms, including the Cray C-90, IBM SP2, Intel Paragon, and networks of workstations under PVM [23].
We have applied our adaptive software infrastructure to the solution of eigenvalue problems arising in materials design [6,15]. By exploiting adaptivity in our applications, we have reduced memory consumption and computation time by more than two orders of magnitude over an equivalent uniform mesh method.
This paper is organized as follows. Section 2 introduces the salient features of structured adaptive mesh algorithms to motivate the software facilities required by the adaptive mesh library. In Section 3, we describe the adaptive mesh API and its facilities. Section 4 analyzes in detail parallel performance and library overheads. We then review related research and conclude with an analysis and discussion.