2021/04/17 by Roger R. F. Araújo, Lutz Gross, Samuel Xavier-de-Souza +1
Computer Science · Earth and Planetary Sciences · Engineering · Mathematics · #Advanced Numerical Methods in Computational Mathematics #Algorithm #Cache #Computer graphics (images) #Computer science #Element (criminal law) #Geophysical Methods and Applications #Hilbert curve #Hilbert space #Locality #Mathematical analysis #Mathematics #Parallel computing #Polygon mesh #Seismic Imaging and Inversion Techniques #Theoretical computer science #acm:35Q68 #acm:35Q86 #acm:86-08 #cs.DC #cs.MS #cs.PF #msc:35Q68 #msc:35Q86 #msc:86-08
paper · pdf · doi:10.1016/j.cageo.2021.104938
23 pages, 12 figures
arxiv created 2021/04/17 · openalex publication_date 2021/09/20 · arxiv updated 2021/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We propose an algorithm based on Hilbert space-filling curves to reorder mesh elements in memory for use with the Spectral Element Method, aiming to attain fewer cache misses, better locality of data reference and faster execution. We present a technique to numerically simulate acoustic wave propagation in 2D domains using the Spectral Element Method, and discuss computational performance aspects of this procedure. We reorder mesh-related data via Hilbert curves to achieve sizable reductions in execution time under several mesh configurations in shared-memory systems. Our experiments show that the Hilbert curve approach works well with meshes of several granularities and also with small and large variations in element sizes, achieving reductions between 9% and 25% in execution time when compared to three other ordering schemes.