Automated tiling of unstructured mesh computations with application to seismological modeling

DOI10.1145/3302256zbMATH Open1471.65211arXiv1708.03183OpenAlexW2963179825WikidataQ113310036 ScholiaQ113310036MaRDI QIDQ5237429FDOQ5237429

Authors: Fabio Luporini, Michael Lange, C. Jacobs, J. Ramanujam, Paul H. J. Kelly, Gerard Gorman 

Publication date: 18 October 2019

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Abstract: Sparse tiling is a technique to fuse loops that access common data, thus increasing data locality. Unlike traditional loop fusion or blocking, the loops may have different iteration spaces and access shared datasets through indirect memory accesses, such as A[map[i]] -- hence the name "sparse". One notable example of such loops arises in discontinuous-Galerkin finite element methods, because of the computation of numerical integrals over different domains (e.g., cells, facets). The major challenge with sparse tiling is implementation -- not only is it cumbersome to understand and synthesize, but it is also onerous to maintain and generalize, as it requires a complete rewrite of the bulk of the numerical computation. In this article, we propose an approach to extend the applicability of sparse tiling based on raising the level of abstraction. Through a sequence of compiler passes, the mathematical specification of a problem is progressively lowered, and eventually sparse-tiled C for-loops are generated. Besides automation, we advance the state-of-the-art by introducing: a revisited, more efficient sparse tiling algorithm; support for distributed-memory parallelism; a range of fine-grained optimizations for increased run-time performance; implementation in a publicly-available library, SLOPE; and an in-depth study of the performance impact in Seigen, a real-world elastic wave equation solver for seismological problems, which shows speed-ups up to 1.28x on a platform consisting of 896 Intel Broadwell cores.

Full work available at URL: https://arxiv.org/abs/1708.03183

Recommendations

• scientific article; zbMATH DE number 1729264
• Generating efficient tiled code for distributed memory machines
• scientific article; zbMATH DE number 1520614
• Combined selection of tile sizes and unroll factors using iterative compilation
• Optimal orthogonal tiling of 2-D iterations

zbMATH Keywords

finite element methodunstructured meshperformance optimizationloop tilingcompilerloop fusionsparse tiling

Mathematics Subject Classification ID

Seismology (including tsunami modeling), earthquakes (86A15) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50) Computational methods for problems pertaining to geophysics (86-08)

Cited In (1)

• SLOPE

Uses Software

• PETSc
• METIS
• ParaView
• VOLNA
• VTune
• Firedrake
• OP2
• COFFEE
• FIAT

This page was built for publication: Automated tiling of unstructured mesh computations with application to seismological modeling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237429)