Cache efficient data structures and algorithms for adaptive multidimensional multilevel finite element solvers

Due to the increasing gap between speed of CPU and speed of access to memory the latter is often the main bottleneck in modern high performance computing. Hierarchical cache architectures designed to avoid this problem conflict with the rather irregular memory access of modern adaptive multilevel algorithms which cause frequent cache misses. In this paper we present an algorithm for an adaptive multilevel FE solver that reduces random access and jumps in address space considerably. The grid is based on a fully adaptive space tree based on a d-dimensional hypercube where d is an arbitrary positive integer. The individual cells in the hierarchical space tree are ordered by a space-filling curve, the d-dimensional Peano curve, and the data processing is organized by a small set of stacks. Because access to a stack always stays local in memory, cache misses are very rare. The organizational overhead is very small. Only one bit per node to define the geometry of the domain and one bit per node to specify the refinement structure are needed allowing the solution of large-scale problems.