Elamur Research⌕
☰
home / papers / 2015 / Gunrock: A High-Performance Graph Processing Library on the GPU

Gunrock: A High-Performance Graph Processing Library on the GPU

Paper · 2015 · Yangzihao Wang, Andrew Davidson, Yuechao Pan et al.

Summary

Graph analytics maps poorly onto GPUs. Graph data leads to irregular memory access and branching, and fast GPU code usually means writing hand-tuned "hardwired" kernels for each algorithm. Gunrock is an open-source, bulk-synchronous graph library for a single GPU that tries to offer both speed and ease of programming. Most earlier GPU frameworks borrowed CPU models such as GAS or Pregel-style messaging. Gunrock instead builds everything around the frontier, the set of vertices or edges active in the current step. Programmers write primitives as operations that either compute on a frontier or produce a new one. Load balancing, kernel fusion, push-pull (direction-optimal) traversal, idempotent traversal and priority queues are handled inside the library.

The authors evaluate BFS, SSSP, BC, CC and PageRank on six graphs. Gunrock is typically at least ten times faster than BGL and PowerGraph, roughly matches hardwired GPU code, and beats other high-level GPU libraries. This makes high-performance GPU graph processing practical without deep GPU expertise.

Key points

  • Five primitives are evaluated: BFS, SSSP, BC, CC and PageRank.
  • Comparisons cover BGL (Boost), PowerGraph, Ligra, CuSha, MapGraph and hardwired GPU implementations.
  • The six test graphs are h09, i04, kron, rgg, roadnet and soc.
  • Load balancing is measured by warp execution efficiency (Table 4):
    • For PageRank, Gunrock stays near 99.4–99.6% across graphs, while CuSha ranges from about 63% to 91%.
    • Some competing frameworks ran out of GPU memory on several inputs.
  • A new primitive needs only a few hundred lines of code. The project was motivated by the authors spending two months on a single hardwired primitive.
  • Limitations stated by the authors:
    • Single-GPU only, and the graph must fit in device memory.
    • Kernel fusion still lags behind hardwired code, and this is the biggest remaining performance gap.
    • General dynamic graph support remains open.

Interesting ideas

  • I1. Organise around the active data, not the computation steps. Making "the set of items currently in play" the core object lets one abstraction cover many iterative algorithms. It also leaves room for optimisations underneath. The same design could suit iterative processing over other networks, such as trade-flow graphs or road and settlement networks.
  • I2. Separate "what" from "how". Users declare the operation on the frontier, and the library chooses how to distribute the work (fine- vs. coarse-grained mapping). Hiding performance-critical scheduling behind a small API lets non-experts get near-expert speed in any compute-heavy toolkit.
  • I3. Switch strategy by frontier size. Gunrock adopts Beamer et al.'s direction-optimal idea: alternate between pushing from the frontier and pulling toward it, depending on how large the frontier is. Choosing the algorithm at runtime from a cheap statistic is a widely transferable trick.
  • I4. Measure load balance directly. Reporting warp execution efficiency, the share of threads actually busy, shows why a framework is fast or slow, not just that it is. Other parallel pipelines could expose a similar utilisation metric alongside runtime.
  • I5. Sample the frontier for a rough start. The authors propose, as future work, taking a random subset of the frontier to compute an approximate or seeded solution before running on the full graph. This could speed up convergence of iterative methods on large data.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of California, DavisDavis · United States34 works · 42,940 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksComputer Vision and Pattern Recognition · 3,486 worksHardware and Architecture · 167 worksComputer Graphics and Computer-Aided Design · 16 works

🧭 Topics 1Research subjects and languages the work is about.GPU & parallel computing · 41 works

Cite

Cite as Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel and John D. Owens. 2015. Gunrock: A High-Performance Graph Processing Library on the GPU. PPoPP 2016.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/2851141.2851145 · arXiv 1501.05387

@inproceedings{wang2015gunrock,
  title = {{Gunrock: A High-Performance Graph Processing Library on the GPU}},
  author = {Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel and John D. Owens},
  booktitle = {PPoPP 2016},
  year = {2015},
  doi = {10.1145/2851141.2851145},
  eprint = {1501.05387},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1145/2851141.2851145}
}

References

37 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. S. Beamer, K. Asanović, and D. Patterson. Direction-optimizing breadth-first search. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC ’12, pages 12:1–12:10, Nov. 2012. find
  2. U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2):163–177, 2001. find
  3. M. Burtscher, R. Nasre, and K. Pingali. A quantitative study of irregular programs on GPUs. In IEEE International Symposium on Workload Characterization, IISWC-2012, pages 141–151, Nov. 2012. find
  4. D. Cederman and P. Tsigas. On dynamic load-balancing on graphics processors. In Graphics Hardware 2008, pages 57–64, June 2008. find
  5. A. Davidson, S. Baxter, M. Garland, and J. D. Owens. Work-efficient parallel GPU methods for single source shortest paths. In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium, pages 349–359, May 2014. find
  6. D. Delling, A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing, 73:940–952, Sept. 2010. find
  7. E. Elsen and V. Vaidyanathan. A vertex-centric CUDA/C++ API for large graph analytics on GPUs using the gather-apply-scatter abstraction, 2013. http://www.github.com/RoyalCaliber/ vertexAPI2. ↗
  8. Z. Fu, M. Personick, and B. Thompson. MapGraph: A high level API for fast development of high performance graph analytics on GPUs. In Proceedings of the Workshop on GRAph Data Management Experiences and Systems, GRADES ’14, pages 2:1–2:6, June 2014. find
  9. A. Geil, Y. Wang, and J. D. Owens. WTF, GPU! Computing Twitter’s who-to-follow on the GPU. In Proceedings of the Second ACM Conference on Online Social Networks, COSN ’14, Oct. 2014. find
  10. R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments, ALENEX08, pages 90–100, Jan. 2008. find
  11. A. Goel. The “who-to-follow” system at Twitter: Algorithms, impact, and further research. WWW 2014 industry track, 2014. find
  12. J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Power-Graph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI ’12, pages 17–30. USENIX Association, Oct. 2012. find
  13. D. Gregor and A. Lumsdaine. The parallel BGL: A generic library for distributed graph computations. In Parallel Object-Oriented Scientific Computing (POOSC), July 2005. find
  14. J. Greiner. A comparison of parallel algorithms for connected components. In Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’94, pages 16–25, June 1994. find
  15. S. Hong, H. Chafi, E. Sedlar, and K. Olukotun. Green-Marl: A DSL for easy and efficient graph analysis. In Proceedings of the Seventeenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVII, pages 349–362, Mar. 2012. find
  16. Y. Jia, V. Lu, J. Hoberock, M. Garland, and J. C. Hart. Edge v. node parallelism for graph centrality metrics. In W. W. Hwu, editor, GPU Computing Gems Jade Edition, chapter 2, pages 15–28. Morgan Kaufmann, Oct. 2011. find
  17. S. W. Keckler, W. J. Dally, B. Khailany, M. Garland, and D. Glasco. GPUs and the future of parallel computing. IEEE Micro, 31(5):7–17, Sept. 2011. find
  18. F. Khorasani, K. Vora, R. Gupta, and L. N. Bhuyan. CuSha: Vertex-centric graph processing on GPUs. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing, HPDC ’14, pages 239–252, June 2014. find
  19. Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A new parallel framework for machine learning. In Proceedings of the Twenty-Sixth Annual Conference on Uncertainty in Artificial Intelligence, UAI-10, pages 340–349, July 2010. find
  20. G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pages 135–146, June 2010. find
  21. R. C. McColl, D. Ediger, J. Poovey, D. Campbell, and D. A. Bader. A performance evaluation of open source graph databases. In Proceedings of the First Workshop on Parallel Programming for Analytics Applications, PPAA ’14, pages 11–18, Feb. 2014. find
  22. A. McLaughlin and D. A. Bader. Scalable and high performance betweenness centrality on the GPU. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC14, pages 572–583, Nov. 2014. find
  23. A. McLaughlin, J. Riedy, and D. A. Bader. A fast, energy-efficient abstraction for simultaneous breadth-first searches. In 2015 IEEE High Performance Extreme Computing Conference, HPEC ’15, Sept. 2015. find
  24. D. Merrill, M. Garland, and A. Grimshaw. Scalable GPU graph traversal. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, pages 117–128, Feb. 2012. find
  25. U. Meyer and P. Sanders. ∆-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, 49(1):114–152, Oct. 2003. 1998 European Symposium on Algorithms. find
  26. D. Nguyen, A. Lenharth, and K. Pingali. A lightweight infrastructure for graph analytics. In Proceedings of ACM Symposium on Operating Systems Principles, SOSP ’13, pages 456–471, Nov. 2013. find
  27. P. R. Pande and D. A. Bader. Computing betweenness centrality for small world networks on a GPU. In HPEC, 2011. find
  28. K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. Méndez-Lojo, D. Prountzos, and X. Sui. The tao of parallelism in algorithms. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI… find
  29. S. Salihoglu and J. Widom. HelP: High-level primitives for large-scale graph processing. In Proceedings of the Workshop on GRAph Data Management Experiences and Systems, GRADES ’14, pages 3:1–3:6, June 2014. find
  30. S. Sallinen, A. Gharaibeh, and M. Ripeanu. Accelerating direction-optimized breadth first search on hybrid architectures. CoRR, abs/1503.04359(1503.04359v1), Mar. 2015. find
  31. A. E. Sariyüce, K. Kaya, E. Saule, and U. V. Çatalyürek. Betweenness centrality on GPUs and heterogeneous architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, GPGPU-6, pages 76–85, Mar. 2013. find
  32. J. Shun and G. E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIG-PLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, pages 135–146, Feb. 2013. find
  33. J. G. Siek, L.-Q. Lee, and A. Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, Dec. 2001. find
  34. J. Soman, K. Kishore, and P. J. Narayanan. A fast GPU algorithm for graph connectivity. In 24th IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum, IPDPSW 2010, pages 1–8, Apr. 2010. find
  35. S. Tzeng, B. Lloyd, and J. D. Owens. A GPU task-parallel model with dependency resolution. IEEE Computer, 45(8):34–41, Aug. 2012. find
  36. Y. Wu, Y. Wang, Y. Pan, C. Yang, and J. D. Owens. Performance characterization for high-level programming models for GPU graph analytics. In IEEE International Symposium on Workload Characterization, IISWC-2015, pages 66–75, Oct. 2015. find
  37. J. Zhong and B. He. Medusa: Simplified graph processing on GPUs. IEEE Transactions on Parallel and Distributed Systems, 25(6):1543– 1552, June 2014. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2015-gunrock-high-performance-graph-processing/