Parallel Breadth First Search on GPU Clusters

Zhisong Fu, Harish Kumar Dasari, Martin Berzins, Bryan Thompson
SYSTAP, LLC. 4501 Tower Road, Greensboro, NC 27410, USA
Scientific Computing and Imaging Institute, University of Utah, UUSCI-2014-002, 2014


   title={Parallel Breadth First Search on GPU Clusters},

   author={Fu, Zhisong and Dasari, Harish Kumar and Berzins, Martin and Thompson, Bryan},



Download Download (PDF)   View View   Source Source   Source codes Source codes




Fast, scalable, low-cost, and low-power execution of parallel graph algorithms is important for a wide variety of commercial and public sector applications. Breadth First Search (BFS) imposes an extreme burden on memory bandwidth and network communications and has been proposed as a benchmark that may be used to evaluate current and future parallel computers. Hardware trends and manufacturing limits strongly imply that many core devices, such as NVIDIA GPUs and the Intel Xeon Phi, will become central components of such future systems. GPUs are well known to deliver the highest FLOPS/watt and enjoy a very significant memory bandwidth advantage over CPU architectures. Recent work has demonstrated that GPUs can deliver high performance for parallel graph algorithms and, further, that it is possible to encapsulate that capability in a manner that hides the low level details of the GPU architecture and the CUDA language but preserves the high throughput of the GPU. We extend previous research on GPUs and on scalable graph processing on super-computers and demonstrate that a high-performance parallel graph machine can be created using commodity GPUs and networking hardware.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: