An Efficient Bread First Search Algorithm on CPU and GPU
Subject Areas : electrical and computer engineeringP. Keshavarzi 1 * , H. Deldari 2 , S. Abrishami 3
1 -
2 - Ferdosi University
3 - Ferdosi University
Keywords: Bread first search (BFS) graphic processing unit (GPU) central processing unit (CPU) kernel,
Abstract :
Graphs are powerful data representations used in enormous computational domains. In graph-based applications, a systematic exploration of graph such as a breath first search often is a fundamental component in the processing of the vast data sets. In this paper we presented a hybrid method that in each level of processing of graph chooses the best implementation of algorithms implemented on CPU or GPU, while avoid poor performance on low and high degree graphs. Our method shows improved performance over the current state-of-the-art implementation and our results proves it.
[1] J. Nickolls and W. J. Dally, "The GPU computing era," IEEE Micro, vol. 30, no. 2, pp. 56-69, Mar./Apr. 2010.
[2] T. Coffman, S. Greenblatt, and S. Marcus, "Graph-based technologies for intelligence analysis," Communications of the ACM, vol. 47, no. 3, pp. 45-47, Mar. 2004.
[3] R. Sim and N. Roy, "Global a-optimal robot exploration in slam," in Proc. IEEE Int. Conf. on, Robotics and Automation, ICRA'05, vol. pp. 661-666, Barcelona, Spain, Apr. 2005.
[4] S. Heryrani Nobari, Scalable Data-Parallel Graph Algorithms from Generation to Management, Ph.D. Thesis, University of Singapore, 2012.
[5] U. Brandes, "A faster algorithm for betweenness centrality," the J. of Mathematical Sociology, vol. 25, no. 2, pp. 163-177, 2001.
[6] A. Lumsdaine, D. Gregor, B. Hendrickson, J. Berry, and J. W. Berry, "Challenges in parallel graph processing," Parallel Processing Letters, vol. 17, no. 1, pp. 5-20, 2007.
[7] S. Skiena, The Algorithm Design Manual, Springer, pp. 166-168, 1998.
[8] M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Physiscal Review E, vol. 69, no. 2, 16 pp., Feb. 2004.
[9] L. Luo, M. Wong, and W. M. Hwu, "An effective GPU implementation of breadth-first search," in Proc. of the 47th Design Automation Conf., pp. 52-55, 2010.
[10] S. Hong, T. Oguntebi, and K. Olukotun, "Efficient parallel graph exploration on multi-core CPU and GPU," in Proc. of the 2011 Inte. Conf. on Parallel Architectures and Compilation Techniques, pp. 78-88, 2011.
[11] https://developer.nvidia.com/about-cuda
[12] P. Harish and P. J. Narayanan, "Accelerating large graph algorithms on the GPU using CUDA," in HiPC, vol. 4873, Springer, Dec. 2007.
[13] S. Xiao and W. C. Feng, "Inter-block GPU communication via fast barrier synchronization," in Proc. IEEE Int. Symp. on Parallel & Distributed Processing, IPDPS'10, 12 pp., 2010.
[14] NVidia, C Best Practices Guide, NVIDIA Corp., Santa Clara, CA, US, 2012.
[15] http://www.dis.uniroma1.it/~challenge9/
[16] Stanford Large Network Dataset Collection, Feb. 2013, http://snap.stanford.edu/data