A GPU‐Adapted Structure for Unstructured Grids

• Published in: Computer graphics forum 2017-05, Vol.36 (2), p.495-507
• Main Authors: Zayer, Rhaleb, Steinberger, Markus, Seidel, Hans‐Peter
• Format: Article
• Language: English
• Subjects: Categories and Subject Descriptors (according to ACM CCS); Computer graphics; Computer memory; Computer peripherals; Data structures; Finite element method; G.1.0 [Mathematics of Computing]: General—Parallel algorithms; G.1.3 [Mathematics of Computing]: Numerical Linear Algebra — Sparse, structured, and very large systems; Graphics processing units; Hardware; I.3.1 [Computer Graphics]: Hardware Architecture—Graphics processors; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms, languages, and systems; I.3.6 [Computer Graphics]: Methodology and Techniques — Graphics data structures and data types; Linear algebra; Machinery and equipment; Mathematical analysis; Matrix algebra; Matrix methods; Matrix representation; Multiplication; Sparsity; Structured grids (mathematics); Unstructured grids (mathematics); Vector processing (computers)
• ISSN: 0167-7055; 1467-8659
• DOI: 10.1111/cgf.13144

A key advantage of working with structured grids (e.g., images) is the ability to directly tap into the powerful machinery of linear algebra. This is not much so for unstructured grids where intermediate bookkeeping data structures stand in the way. On modern high performance computing hardware, the conventional wisdom behind these intermediate structures is further challenged by costly memory access, and more importantly by prohibitive memory resources on environments such as graphics hardware. In this paper, we bypass this problem by introducing a sparse matrix representation for unstructured grids which not only reduces the memory storage requirements but also cuts down on the bulk of data movement from global storage to the compute units. In order to take full advantage of the proposed representation, we augment ordinary matrix multiplication by means of action maps, local maps which encode the desired interaction between grid vertices. In this way, geometric computations and topological modifications translate into concise linear algebra operations. In our algorithmic formulation, we capitalize on the nature of sparse matrix‐vector multiplication which allows avoiding explicit transpose computation and storage. Furthermore, we develop an efficient vectorization to the demanding assembly process of standard graph and finite element matrices.