A GPU-Adapted Structure for Unstructured Grids

dc.contributor.authorZayer, Rhaleben_US
dc.contributor.authorSteinberger, Markusen_US
dc.contributor.authorSeidel, Hans-Peteren_US
dc.contributor.editorLoic Barthe and Bedrich Benesen_US
dc.date.accessioned2017-04-22T16:27:30Z
dc.date.available2017-04-22T16:27:30Z
dc.date.issued2017
dc.description.abstractA 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.en_US
dc.description.number2
dc.description.sectionheadersGPU and Data Structures
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume36
dc.identifier.doi10.1111/cgf.13144
dc.identifier.issn1467-8659
dc.identifier.pages495-507
dc.identifier.urihttps://doi.org/10.1111/cgf.13144
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13144
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.6 [Computer Graphics]
dc.subjectMethodology and Techniques
dc.subjectGraphics data structures and data types.
dc.subjectI.3.5 [Computer Graphics]
dc.subjectComputational Geometry and Object Modeling
dc.subjectGeometric algorithms
dc.subjectlanguages
dc.subjectand systems.
dc.subjectI.3.1 [Computer Graphics]
dc.subjectHardware Architecture
dc.subjectGraphics processors. G.1.3 [Mathematics of Computing]
dc.subjectNumerical Linear Algebra
dc.subjectSparse
dc.subjectstructured
dc.subjectand very large systems. G.1.0 [Mathematics of Computing]
dc.subjectGeneral
dc.subjectParallel algorithms.
dc.titleA GPU-Adapted Structure for Unstructured Gridsen_US
Files
Collections