Research Article

Graph Traversal (GT) on Linear and Quadratic Graphic Processing Units with CPU

Fatemeh Eftekhari
Computer Engineer, Canada
* Corresponding author
DOI icon 10.24018/ejece.2023.7.2.515

Read Counter
360

Downloads
250

Citations

Share

Article Sidebar

Submitted 2023-03-13
Published 2023-04-26

Read counter = 360 times

Table of Contents

Article Main Content

Nowadays, Graph Traversal (GT) is a fundamental procedure for developing a measure in computing systems and algorithms. Graph traversal algorithms usually iterate input datasets of a graph to provide a logical convergence in every iteration. Graphic Processing Units (GPUs) have been utilized broadly as accelerators of GT due to their massive parallelism and accessibility of high-transfer speed memory. Furthermore, graph-based computation is pervasive and challenging for memory systems implementation in a specific time period. This paper provides quadratic and single GPUs, allowing developers to extend graph-based GPU computation effortlessly. The paper concentrates on the creditability and validation of sparse graphs in GPUs. Since the benchmark characteristic of Breadth-First Search (BFS) plays a critical role in graphs, this paper considers a primary characteristic benchmark for BFS computation usage. This paper explores the effectiveness and applicability of BFS for analyzing graph systems by utilizing the mentioned characteristics in BFS computation. This paper also utilizes the penalization of GPU BFS during the analysis and simulation results. In addition, using a comparative simulation result, this paper concludes that improved traversal rates speed up the computation and reduce memory usage for the single and quadratic GPU structures.
Keywords: Algorithm GPU Data Graph System High Performance Memory

References

  1. Moghimi SM, Hajjiah A, Dashti R. The Framework of Capital Governance in the Electrical Energy Distribution System. Indian Journal of Science and Technology. 2018 Aug; 11:29.
     Google Scholar
  2. Khorasani F, Vora K, Gupta R, Bhuyan LN. CuSha: vertex-centric graph processing on GPUs. In Proceedings of the 23rd international symposium on High-performance parallel and distributed computing 2014 Jun 23 (pp. 239-252).
     Google Scholar
  3. Kaczmarski K, Przymus P, Rz??ewski P. Improving high-performance GPU graph traversal with compression. In New Trends in Database and Information Systems II: Selected papers of the 18th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events, ADBIS 2014 Ohrid, Macedonia, September 7-10, 2014 Proceedings II 2015 (pp. 201-214). Springer International Publishing.
     Google Scholar
  4. Vora K, Xu G, Gupta R. Load the edges you need: A generic I/O optimization for disk-based graph processing. In 2016 {USENIX} Annual Technical Conference ({USENIX}{ATC} 16) 2016 (pp. 507-522).
     Google Scholar
  5. Wang Y, Pan Y, Davidson A, Wu Y, Yang C, Wang L, Osama M, Yuan C, Liu W, Riffel AT, Owens JD. Gunrock: GPU graph analytics. ACM Transactions on Parallel Computing (TOPC). 2017 Aug 23;4(1):1-49.
     Google Scholar
  6. Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal. ACM Sigplan Notices. 2012 Feb 25;47(8):117-28.
     Google Scholar
  7. Tian Y, Balmin A, Corsten SA, Tatikonda S, McPherson J. From" think like a vertex" to" think like a graph". Proceedings of the VLDB Endowment. 2013 Nov 1;7(3):193-204.
     Google Scholar
  8. Chen R, Shi J, Chen Y, Zang B, Guan H, Chen H. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing (TOPC). 2019 Jan 22;5(3):1-39.
     Google Scholar
  9. Busato F, Bombieri N. Configuring Graph Traversal Applications for GPUs: Analysis of Implementation Strategies and their Correlation with Graph Characteristics. In 2019 International Conference on High Performance Computing & Simulation (HPCS) 2019 Jul 15 (pp. 145-151). IEEE.
     Google Scholar
  10. Canesche M, Menezes M, Carvalho W, Torres FS, Jamieson P, Nacif JA, Ferreira R. Traversal: A fast and adaptive graph-based placement and routing for cgras. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2020 Sep 21;40(8):1600-12.
     Google Scholar
  11. Chen L, Li J, Sahinalp C, Marathe M, Vullikanti A, Nikolaev A, Smirnov E, Israfilov R, Qiu J. Subgraph2vec: Highly-vectorized tree-like subgraph counting. In 2019 IEEE International Conference on Big Data (Big Data) 2019 Dec 9 (pp. 483-492). IEEE.
     Google Scholar
  12. Han W, Mawhirter D, Wu B, Buland M. Graphie: Large-scale asynchronous graph traversals on just a GPU. In 2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT) 2017 Sep 9 (pp. 233-245). IEEE.
     Google Scholar
  13. Verstraaten M, Varbanescu AL, de Laat C. Mix-and-Match: A Model-driven Runtime Optimisation Strategy for BFS on GPUs. In 2018 IEEE/ACM 8th Workshop on Irregular Applications: Architectures and Algorithms (IA3) 2018 Nov 12 (pp. 53-60). IEEE.
     Google Scholar
  14. Gera P, Kim H, Sao P, Kim H, Bader D. Traversing large graphs on GPUs with unified memory. Proceedings of the VLDB Endowment. 2020 Mar 1;13(7):1119-33.
     Google Scholar
  15. Buluc A, Beamer S, Madduri K, Asanovic K, Patterson D. Distributed-Memory Breadth-First Search on Massive Graphs. In Parallel Graph Algorithms. Lawrence Berkeley National Lab. (LBNL), Berkeley, CA (United States); 2017 Sep 26.
     Google Scholar
  16. Beamer S, Asanovic K, Patterson D. Direction-optimizing breadth-first search. In SC'12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis 2012 Nov 10 (pp. 1-10). IEEE.
     Google Scholar
  17. Lin HH, Tu CH, Hwang YS. CUDABlock: A GUI programming tool for CUDA. In 2015 44th International Conference on Parallel Processing Workshops 2015 Sep 1 (pp. 37-42). IEEE.
     Google Scholar
  18. Hong S, Kim SK, Oguntebi T, Olukotun K. Accelerating CUDA graph algorithms at maximum warp. Acm Sigplan Notices. 2011 Feb 12;46(8):267-76.
     Google Scholar
  19. Zheng F, Tan H, Tian F. Parallel Performance Analysis for CUDA-Based Co-rank Framework on Bipartite Graphs Heterogeneous Network. In 2018 17th International Symposium on Distributed Computing and Applications for Business Engineering and Science (DCABES) 2018 Oct 19 (pp. 12-15). IEEE.
     Google Scholar
  20. Ghorpade J, Parande J, Kulkarni M, Bawaskar A. GPGPU processing in CUDA architecture. arXiv preprint arXiv:1202.4347. 2012 Feb 20.
     Google Scholar
  21. Harish P, Narayanan PJ. Accelerating large graph algorithms on the GPU using CUDA. In High Performance Computing?HiPC 2007: 14th International Conference, Goa, India, December 18-21, 2007. Proceedings 14 2007 (pp. 197-208). Springer Berlin Heidelberg.
     Google Scholar
  22. Www.cise.ufl.edu. 10th DIMACS Implementation Challenge. [Internet]. 2014. Available from: http://www.cc.gatech.edu/dimacs10/index.shtml.
     Google Scholar
  23. Merrill III DG. Allocation-oriented algorithm design with application to gpu computing. University of Virginia; 2011.
     Google Scholar
  24. Seyed Morteza Moghimi GS. Energy Management Optimizing in Multi Carrier Energy Systems Considering Net Zero Emission and CHP Temperature Effects. Physical Science International Journal, 2016 Jan 1;10(3).
     Google Scholar