A Non-static Data Layout Enhancing Parallelism and Vectorization in Sparse Grid Algorithms

Gerrit Buse, Dirk Pfluger, Alin Murarasu, Riko Jacob

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations


The name sparse grids denotes a highly space-efficient, grid-based numerical technique to approximate high-dimensional functions. Although employed in a broad spectrum of applications from different fields, there have only been few tries to use it in real time visualization (e.g. [1]), due to complex data structures and long algorithm runtime. In this work we present a novel approach inspired by principles of I/0-efficient algorithms. Locally applied coefficient permutations lead to improved cache performance and facilitate the use of vector registers for our sparse grid benchmark problem hierarchization. Based on the compact data structure proposed for regular sparse grids in [2], we developed a new algorithm that outperforms existing implementations on modern multi-core systems by a factor of 37 for a grid size of 127 million points. For larger problems the speedup is even increasing, and with execution times below 1 s, sparse grids are well-suited for visualization applications. Furthermore, we point out how a broad class of sparse grid algorithms can benefit from our approach. © 2012 IEEE.
Original languageEnglish (US)
Title of host publication2012 11th International Symposium on Parallel and Distributed Computing
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages8
ISBN (Print)9781467325998
StatePublished - Jun 2012
Externally publishedYes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): UK-C0020
Acknowledgements: This publication is based on work supported by Award No.UK-C0020, made by King Abdullah University of Science andTechnology (KAUST).
This publication acknowledges KAUST support, but has no KAUST affiliated authors.


Dive into the research topics of 'A Non-static Data Layout Enhancing Parallelism and Vectorization in Sparse Grid Algorithms'. Together they form a unique fingerprint.

Cite this