Grus
Open Access
- 9 February 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 18 (2), 1-25
- https://doi.org/10.1145/3444844
Abstract
Today’s GPU graph processing frameworks face scalability and efficiency issues as the graph size exceeds GPU-dedicated memory limit. Although recent GPUs can over-subscribe memory with Unified Memory (UM), they incur significant overhead when handling graph-structured data. In addition, many popular processing frameworks suffer sub-optimal efficiency due to heavy atomic operations when tracking the active vertices. This article presents Grus, a novel system framework that allows GPU graph processing to stay competitive with the ever-growing graph complexity. Grus improves space efficiency through a UM trimming scheme tailored to the data access behaviors of graph workloads. It also uses a lightweight frontier structure to further reduce atomic operations. With easy-to-use interface that abstracts the above details, Grus shows up to 6.4× average speedup over the state-of-the-art in-memory GPU graph processing framework. It allows one to process large graphs of 5.5 billion edges in seconds with a single GPU.Keywords
Funding Information
- National Key Research 8 Development Program of China (2018YFB1003503)
- National Natural Science Foundation of China (61972247)
This publication has 45 references indexed in Scilit:
- Scalable Data-Driven PageRank: Algorithms, System Issues, and Lessons LearnedPublished by Springer Science and Business Media LLC ,2015
- Fast Sparse Matrix and Sparse Vector Multiplication Algorithm on the GPUPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Gunrock: a high-performance graph processing library on the GPUPublished by Association for Computing Machinery (ACM) ,2015
- Scalable and High Performance Betweenness Centrality on the GPUPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Massive atomics for massive parallelism on GPUsACM SIGPLAN Notices, 2014
- X-StreamPublished by Association for Computing Machinery (ACM) ,2013
- Atomic-free irregular computations on GPUsPublished by Association for Computing Machinery (ACM) ,2013
- A yoke of oxen and a thousand chickens for heavy lifting graph processingPublished by Association for Computing Machinery (ACM) ,2012
- Scalable GPU graph traversalACM SIGPLAN Notices, 2012
- The webgraph framework IPublished by Association for Computing Machinery (ACM) ,2004