One of the principal characteristics of the algorithms described above is that they are difficult to implement: they are more complicated than traditional finite difference methods, and often the data structures involved are not easily represented in traditional procedural programming environments used in scientific computing. To manage this algorithmic complexity, we use a collection of libraries written in a mixture of Fortran and C++ [13] that implements a domain-specific set of abstractions [17] for the combination of algorithms described above. In this approach, the high-level data abstractions are implemented in C++, while the bulk of the floating point work is performed on rectangular arrays in calls to Fortran routines.
The design approach used here is based on two ideas. The first is that the mathematical structure of of the algorithm domain specified above maps naturally into a combination of data structures and operations on those data structures, which can be embodied in C++ classes. The second is that the mathematical structure of the algorithms can be factored into a hierarchy of abstractions, leading to an analogous factorization of the framework into reusable components, or layers. This reusability is realized by a combination of generic programming and sub-classing. Following the nomenclature in [16], base classes are defined as pure virtual Protocol classes, and applications interact with the framework through the Template Method and Abstract Factory design patterns.
A principal advantage to this design is the relative stability of the API's as seen by the applications developer. While implementations may change considerably to enhance performance or in response to changes in the architecture, these changes are less likely to cause major upheavals to the applications programs. This is because the API's reflect the mathematical structure of the algorithms, which remain a relatively fixed target.
The starting point for this activity will be the Chombo software library, developed by the Applied Numerical Algorithms Group as part of the Berkeley Lab AMR release. This library was designed using the approach described here to provide the AMR support required for a wide variety of algorithmic extensions. The layered architecture for Chombo consists of five major components.
Layer 1: Classes for representing data and computations on unions of rectangles, including a mechanism for managing the distribution of rectangular patches across processors, and an interface to Fortran for obtaining acceptable uniprocessor performance. This is meant to support an underlying coarse-grained model of parallelism based on domain decomposition.
Layer 2: Classes for representing inter-level interactions, such as averaging and interpolation, interpolation of coarse-fine boundary conditions, and managing conservation at coarse-fine boundaries.
Layer 3: Classes that implement algorithms on AMR data, such as the Berger-Oliger time-stepping algorithm and AMR multigrid.
Layer 4: Implementations of specific applications or classes of applications using these tools, such as a Berger-Oliger algorithm for hyperbolic conservation laws or for incompressible flow, and AMR multigrid for Poisson's equation.
Utility Layer: Support for problem setup, I/O, and visualization that leverages existing de-facto standards, such as I/O, which is built on top of HDF5.
These classes are designed to be reusable by using several mechanisms. The most important form of reuse is by composition. Various complex applications are built from different combinations of simpler and more general components. The class structure used here is a mapping of the mathematical abstractions used to describe the algorithms. We have found that such a mapping leads to substantial reuse of the classes across applications.