Accelerating BFS via Data Structure-Aware Prefetching on GPU
Open Access
- 16 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 6, 60234-60248
Abstract
Breadth First Search (BFS) is a key graph traversing algorithm for many graph analytics applications. In recent decades, as the scale of the graph analytics problem has become larger and larger, it has raised many interests to accelerate graph traversing on GPU. However, due to the irregular memory access pattern of BFS, a great number of the memory divergent accesses harm the efficiency of GPU dramatically. Data prefetching can fetch useful data into the on-chip memory in advance to reduce the latency of accessing the off-chip memory. However, traditional prefetching techniques on GPU cannot deal with irregular memory accesses efficiently. By analyzing BFS algorithms for GPU, we find an opportunity to design an efficient prefetching mechanism by using the explicit information of the graph data structure. In this paper, we propose DSAP, a data structure-aware prefetcher on GPU that generates prefetching requests based on the well-defined data structure access pattern of BFS. Also, we introduce an adaptive fine-grain prefetching management to adjust the status of the prefetching granularity dynamically to balance the cache resource contention and data prefetching based on the utilization of the prefetched data.We implement DSAP on GPGPU-sim simulator and evaluate six datasets from three different kinds of applications. DSAP can achieve a geometrical mean IPC improvement of 28%, up to 48.4%, compared to that of GPU with no prefetching technique, while as a contrast, a stride-based global history buffer (GHB) prefetching mechanism makes no effects on improving BFS performance for these datasets. Also, we use the GPUWattch to estimate the power consumption and the power increases 8.3% in average and up to 11.8%, but the total energy cost drops 15.1% in average.Keywords
Funding Information
- NSF of China (61433019, 61472435, 61572058, 61672526, 61202129, U14352217)
- YESS (20150090)
- Research Project of NUDT (ZK17-03-06)
This publication has 35 references indexed in Scilit:
- Stash2015
- DaCache2015
- GPUWattchACM SIGARCH Computer Architecture News, 2013
- Orchestrated scheduling and prefetching for GPGPUsACM SIGARCH Computer Architecture News, 2013
- A GPGPU compiler for memory optimization and parallelism managementACM SIGPLAN Notices, 2010
- Program optimization space pruning for a multithreaded gpu2008
- Sequential hardware prefetching in shared-memory multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1995
- Effective hardware-based data prefetching for high-performance processorsIEEE Transactions on Computers, 1995
- Evaluating stream buffers as a secondary cache replacementACM SIGARCH Computer Architecture News, 1994
- Stride directed prefetching in scalar processorsACM SIGMICRO Newsletter, 1992