Repository files navigation

Gunrock is a CUDA library for graph-processing designed specifically for theGPU. It uses a high-level, bulk-synchronous, data-centric abstraction focusedon operations on a vertex or edge frontier. Gunrock achieves a balance betweenperformance and expressiveness by coupling high performance GPU computingprimitives and optimization strategies with a high-level programming modelthat allows programmers to quickly develop new graph primitives with smallcode size and minimal GPU programming knowledge.

For more details, please visit ourwebsite,readWhy Gunrock,our TOPC 2017 paperGunrock: GPU Graph Analytics,look at ourresults,and find more details in ourpublications.SeeRelease Notes to keep up with the our latest changes.

Gunrock is featured on NVIDIA's list ofGPU Accelerated Libraries as the only external library for GPU graph analytics.

Service	System	Environment	Status
Jenkins	Ubuntu 16.04.4 LTS	CUDA 9.1, GCC/G++ 5.4

• For Frequently Asked Questions, see theFAQ.

• For information on building Gunrock, seeBuilding Gunrock.

• The "tests" subdirectory included with Gunrock has a comprehensive testapplication for most the functionality of Gunrock.

• For the programming model we use in Gunrock, seeProgramming Model.

• We have also provided code samples for how to useGunrock's C interfaceand how tocall Gunrock primitives from Python,as well asannotated codefor two typical graph primitives.

• For details on upcoming changes and features, see theRoad Map.

We are gradually adding summaries of our results to these web pages (please let us know if you would like other comparisons). These summaries also include a table of results along with links to the configuration and results of each individual run. We detail ourmethodology for our measurements here.

• Gunrock performance compared with other engines for graph analytics
• Setting parameters for direction-optimized BFS
• Gunrock results on different GPUs
• Gunrock BFS throughput as a function of frontier size
• Multi-GPU Gunrock Speedups andMulti-GPU Gunrock Scalability
• Multi-GPU Gunrock Partition Performance
• Comparison to Groute

For reproducibility, we maintain Gunrock configurations and results in our githubgunrock/io repository.

We are happy to run experiments with other engines, particularly if those engines output results in our JSON format / a format that can be easily parsed into JSON format.

To report Gunrock bugs or request features, please file an issuedirectly usingGithub.

Yangzihao Wang, Yuechao Pan, Andrew Davidson, Yuduo Wu, Carl Yang, Leyuan Wang, Muhammad Osama, Chenshan Yuan, Weitang Liu, Andy T. Riffel, and John D. Owens.Gunrock: GPU Graph Analytics. ACM Transactions on Parallel Computing, 4(1):3:1–3:49, August 2017. [DOI |http]

Yuechao Pan, Yangzihao Wang, Yuduo Wu, Carl Yang, and John D. Owens.Multi-GPU Graph Analytics. In Proceedings of the 31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, pages 479–490, May/June 2017.[DOI |http]

Yangzihao Wang, Sean Baxter, and John D. Owens.Mini-Gunrock: A Lightweight Graph Analytics Framework on the GPU. In Graph Algorithms Building Blocks, GABB 2017, pages 616–626, May 2017. [DOI |http]

Leyuan Wang, Yangzihao Wang, Carl Yang, and John D. Owens.A Comparative Study on Exact Triangle Counting Algorithms on the GPU. In Proceedings of the 1st High Performance Graph Processing Workshop, HPGP '16, pages 1–8, May 2016.[DOI |http]

Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens.Gunrock: A High-Performance Graph Processing Library on the GPU.In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming,PPoPP '16, pages 11:1–11:12, March 2016. Distinguished Paper. [DOI |http]

Yuduo Wu, Yangzihao Wang, Yuechao Pan, Carl Yang, and John D. Owens.Performance Characterization for High-Level Programming Models for GPU GraphAnalytics. In IEEE International Symposium on Workload Characterization,IISWC-2015, pages 66–75, October 2015. Best Paper finalist. [DOI |http]

Carl Yang, Yangzihao Wang, and John D. Owens.Fast Sparse Matrix and Sparse Vector Multiplication Algorithm on the GPU.In Graph Algorithms Building Blocks, GABB 2015, pages 841–847, May 2015.[DOI |http]

Afton Geil, Yangzihao Wang, and John 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, pages 63–68, October 2014.[DOI |http]

GTC 2018,Latest Development of the Gunrock Graph Processing Library on GPUs, March 2018. [slides |video]

GTC 2018,Writing Graph Primitives with Gunrock, March 2018. [slides |video]

GTC 2016,Gunrock: A Fast and Programmable Multi-GPU Graph Processing Library, April 2016. [slides]

NVIDIAwebinar, April 2016. [slides]

GPU Technology Theater at SC15,Gunrock: A Fast and Programmable Multi-GPU Graph processing Library, November 2015. [slides |video]

GTC 2014,High-Performance Graph Primitives on the GPU: design and Implementation of Gunrock, March 2014. [slides |video]

• Yangzihao Wang,University of California, Davis

• Yuechao Pan, University of California, Davis

• Yuduo Wu,University of California, Davis

• Carl Yang,University of California, Davis

• Leyuan Wang,University of California, Davis

• Weitang Liu, University of California, Davis

• Muhammad Osama,University of California, Davis

• Chenshan Shari Yuan, University of California, Davis

• Andy Riffel, University of California, Davis

• Huan Zhang,University of California, Davis

• John Owens,University of California, Davis

Thanks to the following developers who contributed code: Theconnected-component implementation was derived from code written byJyothish Soman, Kothapalli Kishore, and P. J. Narayanan and describedin their IPDPSW '10 paperA Fast GPU Algorithm for GraphConnectivity (DOI).The breadth-first search implementation and many of the utilityfunctions in Gunrock are derived from theb40c library ofDuane Merrill. Thealgorithm is described in his PPoPP '12 paperScalable GPU GraphTraversal (DOI). Thanksto Erich Elsen and Vishal Vaidyanathan fromRoyal Caliber and theOnu Team for their discussion onlibrary development and the dataset auto-generating code. Thanks toAdam McLaughlin for his technical discussion. Thanks to Oded Greenfor his technical discussion and an optimization in the CC primitive.Thanks to theAltair andVega-lite teams in theInteractive Data Lab at the University of Washington for graphing help. We appreciate the technical assistance, advice, and machine access from many colleagues at NVIDIA: Chandra Cheij, Joe Eaton, Michael Garland, Mark Harris, Ujval Kapasi, David Luebke, Duane Merrill, Nikolai Sakharnykh, and Cliff Woolley.

This work was funded by the DARPA XDATA program under AFRL ContractFA8750-13-C-0002, by NSF awards CCF-1017399, OCI-1032859, andCCF-1629657, by DARPA STTR award D14PC00023, and by DARPA SBIR awardW911NF-16-C-0020. Our XDATA principal investigator is Eric Whyne ofData Tactics Corporation and our DARPAprogram managers are Dr. Christopher White (2012--2014) andMr. Wade Shen(2015--present). Thanks to Chris, Wade, and DARPA business managerGabriela Araujo for their support during the XDATA program.

Gunrock is copyright The Regents of the University ofCalifornia, 2013--2018. The library, examples, and all source code arereleased underApache 2.0.