Efficient breadth-first search on a heterogeneous processor
Authors:
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 373-382
Abstract
Accelerating breadth-first search (BFS) can be a compelling value-add given its pervasive deployment. The current state-of-the-art hybrid BFS algorithm selects different traversal directions based on graph properties, thereby, possessing heterogeneous characteristics. Related work has studied this heterogeneous BFS algorithm on homogeneous processors. In recent years heterogeneous processors have become mainstream due to their ability to maximize performance under restrictive thermal budgets. However, current software fails to fully leverage the heterogeneous capabilities of the modern processor, lagging behind hardware advancements. We propose a “hybrid++” BFS algorithm for an accelerated processing unit (APU), a heterogeneous processor which fuses the CPU and GPU cores on a single die. Hybrid++ leverages the strength of CPUs and GPUs for serial and data-parallel execution, respectively, to carefully partition BFS by selecting the appropriate execution-core and graph-traversal direction for every search iteration. Our results illustrate that on a variety of graphs ranging from social- to road-networks, hybrid++ yields a speedup of up to 2× compared to the multithreaded hybrid algorithm. Execution of hybrid++ on the APU is also 2.3× more energy efficient than that on a discrete GPU.Keywords
This publication has 19 references indexed in Scilit:
- Traversing Trillions of Edges in Real Time: Graph Exploration on Large-Scale Parallel Machines2014
- Efficient Hybrid Breadth-First Search on GPUsLecture Notes in Computer Science, 2013
- Efficient Parallel Graph Exploration on Multi-Core CPU and GPU2011
- Accelerating CUDA graph algorithms at maximum warp2011
- An effective GPU implementation of breadth-first search2010
- Pregel2010
- Qilin2009
- Accelerating Large Graph Algorithms on the GPU Using CUDA2008
- Better Approximation of Betweenness Centrality2008
- Graph-based technologies for intelligence analysisCommunications of the ACM, 2004