GraphPEG
Open Access
- 10 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 18 (3), 1-24
- https://doi.org/10.1145/3450440
Abstract
Due to massive thread-level parallelism, GPUs have become an attractive platform for accelerating large-scale data parallel computations, such as graph processing. However, achieving high performance for graph processing with GPUs is non-trivial. Processing graphs on GPUs introduces several problems, such as load imbalance, low utilization of hardware unit, and memory divergence. Although previous work has proposed several software strategies to optimize graph processing on GPUs, there are several issues beyond the capability of software techniques to address. In this article, we present GraphPEG, a graph processing engine for efficient graph processing on GPUs. Inspired by the observation that many graph algorithms have a common pattern on graph traversal, GraphPEG improves the performance of graph processing by coupling automatic edge gathering with fine-grain work distribution. GraphPEG can also adapt to various input graph datasets and simplify the software design of graph processing with hardware-assisted graph traversal. Simulation results show that, in comparison with two representative highly efficient GPU graph processing software framework Gunrock and SEP-Graph, GraphPEG improves graph processing throughput by 2.8× and 2.5× on average, and up to 7.3× and 7.0× for six graph algorithm benchmarks on six graph datasets, with marginal hardware cost.Keywords
Funding Information
- NSF of China (61872374 and 61672526)
This publication has 41 references indexed in Scilit:
- A scalable processing-in-memory accelerator for parallel graph processingPublished by Association for Computing Machinery (ACM) ,2015
- Fine-grain task aggregation and coordination on GPUsACM SIGARCH Computer Architecture News, 2014
- Work-Efficient Parallel GPU Methods for Single-Source Shortest PathsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2014
- Design and Implementation of Digital Filters for Mobile Healthcare ApplicationsInternational Journal of Electronics and Electrical Engineering, 2014
- A lightweight infrastructure for graph analyticsPublished by Association for Computing Machinery (ACM) ,2013
- Medusa: Simplified Graph Processing on GPUsIEEE Transactions on Parallel and Distributed Systems, 2013
- Green-MarlACM SIGARCH Computer Architecture News, 2012
- Scalable GPU graph traversalACM SIGPLAN Notices, 2012
- A GPU implementation of inclusion-based points-to analysisACM SIGPLAN Notices, 2012
- CarbonACM SIGARCH Computer Architecture News, 2007