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 a×b×c array of cells. If a block needs to be refined, it is replaced by 8 children, each with a×b×c 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 computers.
2. On parallel computers, the time 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 Supercomputing 1997 (SC'97).   Complete paper (PDF)   (html)

• 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-2018 Quentin F. Stout