Boosting memory access locality of the spectral element method with Hilbert Space-Filling Curves

Abstract

The wave equation is pervasive in mathematical physics and engineering, and we need to solve it repeatedly to simulate wave propagations in software. The spectral element method, one of several approaches for the numerical solution of the wave equation, discretizes the underlying domain in a mesh made of elements and nodes, and traverses every element and every node at each time step as it marches the target equation through time. We propose a memory reordering algorithm, meant to be used with the spectral element method, that rearranges mesh-related data to reduce the number of cache misses and boost locality of data reference, thereby improving the execution speed of the mesh traversal process. We devise a spectral element method formulation for 2D waves over unstructured meshes made of triangles, and we pair it to our memory reordering algorithm to construct an acoustic wave propagation simulator. Our experiments show that the reordering technique based on Hilbert space-filling curves performs well in meshes of different granularities, and also when the variation in element sizes is either small or large. In addition, we compare the proposed approach with three other memory reordering schemes, and find that our algorithm runs between 9% and 25% faster than the alternatives we tested. We recommend this memory reordering algorithm to any application that requires successive traversals across domains.