A GPU‐Adapted Structure for Unstructured Grids. (23rd May 2017)

• Record Type: Journal Article
• Authors: Zayer, Rhaleb; Steinberger, Markus; Seidel, Hans‐Peter
• Is Part Of: Computer graphics forum. Volume 36:Number 2(2017)
• Page Start: 495
• Page End: 507
• Publication Date: 2017-05-23
• Subjects: Categories and Subject Descriptors (according to ACM CCS) -- I.3.6 [Computer Graphics]: Methodology and Techniques — Graphics data structures and data types -- I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms, languages, and systems -- I.3.1 [Computer Graphics]: Hardware Architecture—Graphics processors -- G.1.3 [Mathematics of Computing]: Numerical Linear Algebra — Sparse, structured, and very large systems -- G.1.0 [Mathematics of Computing]: General—Parallel algorithms; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13144
• Languages: English
• ISSNs: 0167-7055

Abstract

Abstract: 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.