On Graphs, GPUs, and Blind Dating: A Workload to Processor Matchmaking Quest
- 1 May 2013
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 851-862
- https://doi.org/10.1109/ipdps.2013.37
Abstract
Graph processing has gained renewed attention. The increasing large scale and wealth of connected data, such as those accrued by social network applications, demand the design of new techniques and platforms to efficiently derive actionable information from large scale graphs. Hybrid systems that host processing units optimized for both fast sequential processing and bulk processing (e.g., GPUaccelerated systems) have the potential to cope with the heterogeneous structure of real graphs and enable high performance graph processing. Reaching this point, however, poses multiple challenges. The heterogeneity of the processing elements (e.g., GPUs implement a different parallel processing model than CPUs and have much less memory) and the inherent irregularity of graph workloads require careful graph partitioning and load assignment. In particular, the workload generated by a partitioning scheme should match the strength of the processing element the partition is allocated to. This work explores the feasibility and quantifies the performance gains of such low-cost partitioning schemes. We propose to partition the workload between the two types of processing elements based on vertex connectivity. We show that such partitioning schemes offer a simple, yet efficient way to boost the overall performance of the hybrid system. Our evaluation illustrates that processing a 4-billion edges graph on a system with one CPU socket and one GPU, while offloading as little as 25% of the edges to the GPU, achieves 2x performance improvement over state-of-the-art implementations running on a dual-socket symmetric system. Moreover, for the same graph, a hybrid system with dualsocket and dual-GPU is capable of 1.13 Billion breadth-first search traversed edge per second, a performance rate that is competitive with the latest entries in the Graph500 list, yet at a much lower price point.Keywords
This publication has 22 references indexed in Scilit:
- A yoke of oxen and a thousand chickens for heavy lifting graph processingPublished by Association for Computing Machinery (ACM) ,2012
- Scalable GPU graph traversalPublished by Association for Computing Machinery (ACM) ,2012
- Fast Balanced Partitioning Is Hard Even on Grids and TreesLecture Notes in Computer Science, 2012
- Efficient Parallel Graph Exploration on Multi-Core CPU and GPUPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Accelerating CUDA graph algorithms at maximum warpPublished by Association for Computing Machinery (ACM) ,2011
- PregelPublished by Association for Computing Machinery (ACM) ,2010
- A network analysis of the Italian overnight money marketJournal of Economic Dynamics and Control, 2008
- Lethality and centrality in protein networksNature, 2001
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Some simplified NP-complete problemsPublished by Association for Computing Machinery (ACM) ,1974