Which Graph Representation to Select for Static Graph-Algorithms on a CUDA-capable GPU

Blaß T, Philippsen M (2019)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2019

Publisher: ACM

City/Town: New York, NY, USA

Pages Range: 22-31

Conference Proceedings Title: Proceedings of the 12th Workshop on General Purpose Processing Using GPUs

Event location: Providence, RI US

ISBN: 978-1-4503-6255-9

URI: http://ieeetcca.org/2018/12/16/12th-workshop-on-general-purpose-processing-using-gpu-gpgpu-2019-asplos-2019/

DOI: 10.1145/3300053.3319416

Abstract

GPUs seem to be ideal for algorithms that work in parallel. A number of ways to represent graphs in GPU memory are known. But so far there are no guidelines to select the representation that is likely to result in the best performance.

This a comprehensive study investigates for CUDA-capable GPUs how different graph representations influence the performance of highly optimized graph processing algorithms that traverse the graphs without modifying them. We evaluate three different graph exchange formats and how efficiently they can be imported into eight graph data structures. We use ten state-of-the-art benchmarks that employ different traversals pattern. We evaluate them on 19 input graphs with different characteristics. The measurements show that there is not a single best data structure; the runtime performance can vary up to a factor of 2 between two representations.

The main contribution is a set of rules that helps in picking the best-performing graph representation for a given situation.

Authors with CRIS profile

Thorsten Blaß Lehrstuhl für Informatik 2 (Programmiersysteme) Michael Philippsen Lehrstuhl für Informatik 2 (Programmiersysteme)

Related research project(s)

Parallel code analysis on a GPU (ParCAn) July 1, 2013 - Sept. 30, 2020

How to cite

APA:

Blaß, T., & Philippsen, M. (2019). Which Graph Representation to Select for Static Graph-Algorithms on a CUDA-capable GPU. In ACM (Eds.), Proceedings of the 12th Workshop on General Purpose Processing Using GPUs (pp. 22-31). Providence, RI, US: New York, NY, USA: ACM.

MLA:

Blaß, Thorsten, and Michael Philippsen. "Which Graph Representation to Select for Static Graph-Algorithms on a CUDA-capable GPU." Proceedings of the 12th Workshop on General Purpose Processing Using GPUs, Providence, RI Ed. ACM, New York, NY, USA: ACM, 2019. 22-31.

BibTeX: Download