Theoretical measures of cache efficiency for tetrahedral adaptive meshes - A case study with a quasi space-filling curve order

We present a case study to improve the cache efficiency for a simulation on a tetrahedral bisection-based adaptive mesh, which does not support common space-filling curve (SFC) approaches to enumerate and sort the elements. The order of elements plays an important role for dynamically adaptive meshes. Meshes considered in this study change their topology during simulation time, i.e. h-adaptive methods, which generate and remove cells for local mesh refinement. These creation and removal processes lead to a non-consecutive numbering of the elements and randomly distribute the corresponding computational data in memory. Therefore, the mesh generator amatos gathers the data in arrays and provide them for numerical computations. This gathering naturally sorts data in memory and different ordering methods can be applied to increase cache efficiency of the simulation. As the sorting itself needs to be computed, keeping the overhead small is desirable. There exist fast iterative constructions of a SFC-induced order for certain bisection based refinement methods. However, we are not aware of any study analyzing the data locality for adaptive meshes not supporting the space-filling curve order. Our test case consists of an h-adaptive tracer simulation on a tetrahedral mesh, which denies a simple construction of an SFC. We perform a depth-first traversal of the refinement tree leading to a quasi space-filling curve (qSFC) order. We introduce the face sharing order as an easy-to-use-method to insert the elements into the tree and compare it to a more classical approach keeping explicitly track of the qSFC. For comparison we derive statistical measures of locality based on the mesh's connectivity and show that both qSFC strategies deliver a good quality, but with a slightly better performance of the face sharing order