Parallelization of BFS Graph Algorithm using CUDA

Chetan D. Pise, Shailendra W. Shende
Department of Information Technology,Yeshwantrao Chavan College of Engineering Nagpur University, Nagpur, Maharashtra 441 110, INDIA
International Journal of Computing and Technology (IJCAT), Volume 1, Issue 3, 2014


   title={Parallelization of BFS Graph Algorithm using CUDA},

   author={Pise, Chetan D and Shende, Shailendra W},



Download Download (PDF)   View View   Source Source   



Graphs play a very important role in the field of Science and Technology for finding the shortest distance between any two places. This Paper demonstrate the recent technology named as CUDA (Compute Unified Device Architecture) working for BFS Graph Algorithm. There are some Graph algorithms are fundamental to many disciplines and application areas. Large graphs are common in scientific and engineering applications consisting operation on million of vertices and edges[1, 11, 12, 18, 19]. To have faster execution of such operations parallel computation is very essential to reduce overall computation time. Today’s Graphics processing units (GPUs) have high computation power. and low price. Compute Unified Device Architecture (CUDA) software interface by NVIDIA, becoming a new programming approach of the general purpose computing on graphics processing units (GPGPU). Massively Multithreaded architecture of a CUDA device makes various threads to run in parallel and hence making optimum use of available computation power of GPU. In this paper we are demonstrating the comparison between different large data sets, which are in term of kernel execution that are carried out on GPU using CUDA. In most of the applications GPU can be used as an inexpensive co-processor. Breadth-first search (BFS) is a core primitive for graph traversal and very much important for graph analysis.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: