Abstract: We have created a data structure which combines flexible adaptivity with high performance for both serial and parallel computers. Using it, we were able to sustain 17Gflops on a simulation of the magneto-hydrodynamic (MHD) properties of the solar wind emanating from the sun, using a 512-processor Cray T3D at NASA Goddard. This simulation included 5 levels of resolution adaptivity, and on-going work of our NASA Grand Challenge Team will exploit the adaptivity over vastly greater ranges.

The data structure is an adaptive grid which partitions a given region into regular cells. Its closest relative is the oct-tree, but there are several important differences. Adaptive blocks can be thought of as being similar to the leaves of an oct-tree, where each leaf is a block which partitions its region of space into an regular axbxc array of cells. If a block needs to be refined, it is replaced by 8 children, each with axbxc cells, where each cell's extent in each dimension is 1/2 the extent of its parent's cells. If the 8 children need to be coarsened, they are replaced by their parent. In our application, each block points to the blocks it shares a face with, though in other applications one may also need pointers to blocks sharing an edge or corner.

The primary advantages of adaptive blocks over oct-trees are:

1. By using arrays of cells, instead of individual cells, we were able to exploit loop optimizations over individual blocks. This increased our FLOP rate by more than a factor of 3. This optimization is useful for both serial and parallel machines.
2. On parallel machines, the message-passing to exchange neighbor information is amortized over a block, instead of single cell. The space required to store the pointers is similarly amortized. The use of neighbor pointers, instead of parent/child ones, speeds up the process of locating relevant cells.
3. If the solution-adaptation needs to adjust rapidly (e.g., tracking shock waves), the use of blocks allows one to anticipate needed refinement since entire subregions are refined. This permits less-frequent adaptation, which lowers overhead.

This paper appears in Proceedings SC'97.   Complete paper (PDF)   (html)   (Postscript)

• A more recent, flexible, parallel implementation of adaptive blocks on the sphere.
• Our work on space environment modeling.
• My publications, and an overview of my work, in parallel computing
• A modest explanation of parallel computing, and a tutorial.

Copyright © 2006-2008 Quentin F. Stout