Scalable SIMD-Efficient Graph Processing on GPUs
Authors:
- Farzad KhorasaniFKFarzad Khorasani
- Rajiv GuptaRGRajiv Gupta
- Laxmi N. BhuyanLBLaxmi N. Bhuyan
- 1 October 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 1089795X,p. 39-50
Abstract
The vast computing power of GPUs makes them an attractive platform for accelerating large scale data parallel computations such as popular graph processing applications. However, the inherent irregularity and large sizes of real-world power law graphs makes effective use of GPUs a major challenge. In this paper we develop techniques that greatly enhance the performance and scalability of vertex-centric graph processing on GPUs. First, we present Warp Segmentation, a novel method that greatly enhances GPU device utilization by dynamically assigning appropriate number of SIMD threads to process a vertex with irregular-sized neighbors while employing compact CSR representation to maximize the graph size that can be kept inside the GPU global memory. Prior works can either maximize graph sizes (VWC uses the CSR representation) or device utilization (e.g., CuSha uses the CW representation, however, CW is roughly 2.5x the size of CSR). Second, we further scale graph processing to make use of multiple GPUs while proposing Vertex Refinement to address the challenge of judiciously using the limited bandwidth available for transferring data between GPUs via the PCIe bus. Vertex refinement employs parallel binary prefix sum to dynamically collect only the updated boundary vertices inside GPUs' outbox buffers for dramatically reducing inter-GPU data transfer volume. Whereas existing multi-GPU techniques (Medusa, TOTEM) perform high degree of wasteful vertex transfers. On a single GPU, our framework delivers average speedups of 1.29x to 2.80x over VWC. When scaled to multiple GPUs, our framework achieves up to 2.71x performance improvement compared to inter-GPU vertex communication schemes used by other multi-GPU techniques (i.e., Medusa, TOTEM).Keywords
This publication has 19 references indexed in Scilit:
- MedusaACM SIGMOD Record, 2014
- CuSha2014
- Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths2014
- Multi-threaded Graph Partitioning2013
- Dymaxion2011
- Efficient Parallel Graph Exploration on Multi-Core CPU and GPU2011
- Efficient PageRank and SpMV Computation on AMD GPUs2010
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- The dynamics of viral marketingACM Transactions on the Web, 2007
- CHALLENGES IN PARALLEL GRAPH PROCESSINGParallel Processing Letters, 2007