Cache-Optimal Data-Structures for Hierarchical Methods on Adaptively Refined Space-Partitioning Grids

摘要

The most efficient numerical methods for the solution of partial differential equations, multigrid methods on adaptively refined grids, imply several drawbacks from the point of view of memory-efficiency on high-performance computer architectures: First, we loose the trivial structure expressed by the simple i, j-indexing of grid points or cells. This effect is even worsened by the usage of hierarchical data and - if implemented in a naive way - leads to both increased storage requirements (neighbour-hoodrelations possibly modified difference stencils) and a less efficient data access (worse locality of data and additional data dependencies), in addition. Our approach to overcome this quandary between numerical and hardware-efficiency relies on structured but still highly flexible adaptive grids, the so-called space-partitioning grids, cell-oriented operator evaluations, and the construction of very efficient data structures based on the concept of space-filling curves. The focus of this paper is in particular on the technical and algorithmical details concerning the interplay between data structures, space-partitioning grids and space-filling curves.