{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T20:52:10Z","timestamp":1789505530731,"version":"build-2803163510"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,2,18]],"date-time":"2015-02-18T00:00:00Z","timestamp":1424217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NVIDIA Graduate Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,2,18]]},"abstract":"<jats:p>Breadth-First Search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. It is also representative of a class of parallel computations whose memory accesses and work distribution are both irregular and data dependent. Recent work has demonstrated the plausibility of GPU sparse graph traversal, but has tended to focus on asymptotically inefficient algorithms that perform poorly on graphs with nontrivial diameter.<\/jats:p>\n          <jats:p>We present a BFS parallelization focused on fine-grained task management constructed from efficient prefix sum computations that achieves an asymptotically optimal O(|V| + |E|) gd work complexity. Our implementation delivers excellent performance on diverse graphs, achieving traversal rates in excess of 3.3 billion and 8.3 billion traversed edges per second using single- and quad-GPU configurations, respectively. This level of performance is several times faster than state-of-the-art implementations on both CPU and GPU platforms.<\/jats:p>","DOI":"10.1145\/2717511","type":"journal-article","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T15:32:19Z","timestamp":1424705539000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":60,"title":["High-Performance and Scalable GPU Graph Traversal"],"prefix":"10.1145","volume":"1","author":[{"given":"Duane","family":"Merrill","sequence":"first","affiliation":[{"name":"NVIDIA Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Garland","sequence":"additional","affiliation":[{"name":"NVIDIA Corporation"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Grimshaw","sequence":"additional","affiliation":[{"name":"University of Virginia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,2,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2005.55"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.34"},{"key":"e_1_2_1_4_1","volume-title":"Bader and Kamesh Madduri","author":"David","year":"2006","unstructured":"David A. Bader and Kamesh Madduri . 2006 b. GT graph: A synthetic graph generator suite. http:\/\/www.cse.psu.edu\/~madduri\/software\/GTgraph. David A. Bader and Kamesh Madduri. 2006b. GT graph: A synthetic graph generator suite. http:\/\/www.cse.psu.edu\/~madduri\/software\/GTgraph."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654078"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.42122"},{"key":"e_1_2_1_8_1","volume-title":"Synthesis of Parallel Algorithms. Morgan Kaufmann","author":"Blelloch Guy E.","unstructured":"Guy E. Blelloch . 1990. Prefix sums and their applications . In Synthesis of Parallel Algorithms. Morgan Kaufmann , San Francisco , 35--60. Guy E. Blelloch. 1990. Prefix sums and their applications. In Synthesis of Parallel Algorithms. Morgan Kaufmann, San Francisco, 35--60."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/110382.110597"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2009.5306797"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.52"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/362790.362798"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.43"},{"key":"e_1_2_1_15_1","volume-title":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001.Introduction to Algorithms","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001.Introduction to Algorithms , 2 nd Ed. MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001.Introduction to Algorithms, 2nd Ed. MIT Press.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687501"},{"key":"e_1_2_1_18_1","volume-title":"9th DIMACS implementation challenge","author":"DIMACS.","unstructured":"DIMACS. 2011. 9th DIMACS implementation challenge . http:\/\/www.dis.uniroma1.it\/~challenge9\/download.shtml. DIMACS. 2011. 9th DIMACS implementation challenge. http:\/\/www.dis.uniroma1.it\/~challenge9\/download.shtml."},{"key":"e_1_2_1_19_1","volume-title":"10th DIMACS implementation challenge","author":"DIMACS.","unstructured":"DIMACS. 2012. 10th DIMACS implementation challenge . http:\/\/www.cc.gatech.edu\/dimacs10\/index.shtml. DIMACS. 2012. 10th DIMACS implementation challenge. http:\/\/www.cc.gatech.edu\/dimacs10\/index.shtml."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375527.1375559"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391473"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS'09)","author":"Gonzalez Joseph","year":"2009","unstructured":"Joseph Gonzalez , Yucheng Low , and Carlos Guestrin . 2009 . Residual splash for optimally parallelizing belief propagation . In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS'09) . 177--184. Joseph Gonzalez, Yucheng Low, and Carlos Guestrin. 2009. Residual splash for optimally parallelizing belief propagation. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS'09). 177--184."},{"key":"e_1_2_1_23_1","unstructured":"Graph List. 2011. The graph 500 list. http:\/\/www.graph500.org\/.  Graph List. 2011. The graph 500 list. http:\/\/www.graph500.org\/."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 14th International Conference on High Performance Computing (HiPC'07)","author":"Harish Pawan","unstructured":"Pawan Harish and P. J. Narayanan . 2007. Accelerating large graph algorithms on the GPU using CUDA . In Proceedings of the 14th International Conference on High Performance Computing (HiPC'07) . 197--208. Pawan Harish and P. J. Narayanan. 2007. Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th International Conference on High Performance Computing (HiPC'07). 197--208."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/7902.7903"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03889-6_5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1941553.1941590"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 1st Workshop on General Purpose Processing on Graphics Processing Units (GPGPU'07)","author":"Hussein Mohamed","year":"2007","unstructured":"Mohamed Hussein , Amitabh Varshney , and Larry Davis . 2007 . On implementing graph cuts on CUDA . In Proceedings of the 1st Workshop on General Purpose Processing on Graphics Processing Units (GPGPU'07) . Mohamed Hussein, Amitabh Varshney, and Larry Davis. 2007. On implementing graph cuts on CUDA. In Proceedings of the 1st Workshop on General Purpose Processing on Graphics Processing Units (GPGPU'07)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810479.1810534"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837289"},{"key":"e_1_2_1_32_1","unstructured":"Duane Merrill. 2011. Back40 computing: Fast and efficient software primitives for GPU computing. http:\/\/code.google.com\/p\/back40computing\/.  Duane Merrill. 2011. Back40 computing: Fast and efficient software primitives for GPU computing. http:\/\/code.google.com\/p\/back40computing\/."},{"key":"e_1_2_1_33_1","volume-title":"CS2009-14","author":"Merrill Duane","year":"2009","unstructured":"Duane Merrill and Andrew Grimshaw . 2009 . Parallel scan for stream architectures. Tech. rep . CS2009-14 , Department of Computer Science, University of Virginia. Duane Merrill and Andrew Grimshaw. 2009. Parallel scan for stream architectures. Tech. rep. CS2009-14, Department of Computer Science, University of Virginia."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626411000187"},{"key":"e_1_2_1_35_1","first-page":"2","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Newman Mark","year":"2004","unstructured":"Mark Newman and Michelle Girvan . 2004 . Finding and evaluating community structure in networks . Phys. Rev. E69 , 2 . Mark Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Phys. Rev. E69, 2.","journal-title":"Phys. Rev."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2008.917757"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389015"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70811"},{"key":"e_1_2_1_39_1","unstructured":"Shubhabrata Sengupta Mark Harris and Michael Garland. 2008. Efficient parallel scan algorithms for GPUs. https:\/\/research.nvidia.com\/sites\/default\/files\/publications\/nvr-2008-003.pdf.  Shubhabrata Sengupta Mark Harris and Michael Garland. 2008. Efficient parallel scan algorithms for GPUs. https:\/\/research.nvidia.com\/sites\/default\/files\/publications\/nvr-2008-003.pdf."},{"key":"e_1_2_1_40_1","volume-title":"Geng Daniel Liu, and Wen-Mei W. Hwu","author":"Stratton John A.","year":"2012","unstructured":"John A. Stratton , Christopher Rodrigues , I- Jui Sung , Nady Obeid , Li-Wen Chang , Nasser Anssari , Geng Daniel Liu, and Wen-Mei W. Hwu . 2012 . Parboil : A revised benchmark suite for scientific and commercial throughput computing. Tech. rep. IMPACT-12-01, Center for Reliable and High-Performance Computing . http:\/\/impact.crhc.illinois.edu\/Shared\/Docs\/impact-12-01.parboil.pdf. John A. Stratton, Christopher Rodrigues, I-Jui Sung, Nady Obeid, Li-Wen Chang, Nasser Anssari, Geng Daniel Liu, and Wen-Mei W. Hwu. 2012. Parboil: A revised benchmark suite for scientific and commercial throughput computing. Tech. rep. IMPACT-12-01, Center for Reliable and High-Performance Computing. http:\/\/impact.crhc.illinois.edu\/Shared\/Docs\/impact-12-01.parboil.pdf."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/97444.97686"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 21st International Conference on Parallel and Distributed Computing and Systems (PDCS'09)","author":"Xia Yinglong","unstructured":"Yinglong Xia and Viktor K. Prasanna . 2009. Topologically adaptive parallel breadth-first search on multicore processors . In Proceedings of the 21st International Conference on Parallel and Distributed Computing and Systems (PDCS'09) . Yinglong Xia and Viktor K. Prasanna. 2009. Topologically adaptive parallel breadth-first search on multicore processors. In Proceedings of the 21st International Conference on Parallel and Distributed Computing and Systems (PDCS'09)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2005.4"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2717511","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2717511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:44Z","timestamp":1750230044000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2717511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,18]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2,18]]}},"alternative-id":["10.1145\/2717511"],"URL":"https:\/\/doi.org\/10.1145\/2717511","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,18]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-02-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}