Gunrock v0.3 released! Check out the Release-Note!
Gunrock is a CUDA library for graph-processing designed specifically for the GPU. It uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge. For more details, please read Why-Gunrock, our paper on arXiv: Gunrock: A High-Performance Graph Processing Library on the GPU, and check out the Publications section.
Homepage for Gunrock: http://gunrock.github.io/
For Frequently Asked Questions, see FAQ.
The "tests" subdirectory included with Gunrock has a comprehensive test application for most functionality of Gunrock.
For the programming model we use in Gunrock, see Programming Model.
To use our stats logging and performance chart generation pipeline. Please check out Gunrock-to-JSON.
To report Gunrock bugs or request features, please file an issue directly using Github.
This release (0.3) has only been tested on Linux Mint 15 (64-bit) and Ubuntu 12.04 (64-bit) with CUDA 5.5, 6.0, 6.5, and 7.0 installed. We expect Gunrock to build and run correctly on other 64-bit and 32-bit Linux distributions, Mac OS, and Windows.
CUDA version 5.5 (or greater) and compute capability 3.0 (or greater) is required.
Several graph primitives' CPU validation code uses Boost Graph Library. We are also using Boost Spirit, filesystem, and timer in our utility code. A boost version > 1.53.0 is required.
Gunrock is implemented in CUDA C/C++. It requires the CUDA Toolkit. Please see the NVIDIA CUDA homepage to download CUDA as well as the CUDA Programming Guide and CUDA SDK, which includes many CUDA code examples. Please refer to NVIDIA CUDA Getting Started Guide for Linux for detailed information.
Yuduo Wu, Yangzihao Wang, Yuechao Pan, Carl Yang, and John D. Owens. Performance Characterization for High-Level Programming Models for GPU Graph Analytics. In IEEE International Symposium on Workload Characterization, IISWC2015, October 2015
Yuechao Pan, Yangzihao Wang, Yuduo Wu, Carl Yang, and John D. Owens. Multi-GPU Graph Analytics. CoRR, abs/1504.04804, Apr. 2015. arXiv
Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. Gunrock: A High-Performance Graph Processing Library on the GPU. CoRR, abs/1501.05387v2, March 2015. arXiv
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, May 2015. 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
Framework: In v0.3 we have integrated single-GPU and multi-GPU frameworks into a unified framework. We are exploring more operators such as Gather-Reduce and matrix operators. Generally we want to find the right set of operators that can abstract most graph primitives while delivering high performance.
Primitives: Our near-term goal is to implement maximal independent set algorithm and graph matching algorithm, build better support for bipartite graph algorithms, and explore community detection algorithms. The long term goal includes algorithms on dynamic graphs, priority queue support, graph partitioning and multi-GPU algorithms.
Yangzihao Wang, University of California, Davis
Yuechao Pan, University of California, Davis
Yuduo Wu, University of California, Davis
Carl Yang, University of California, Davis
Andy Riffel, University of California, Davis
John Owens, University of California, Davis
Thanks to the following developers who contributed code: The connected-component implementation was derived from code written by Jyothish Soman, Kothapalli Kishore, and P. J. Narayanan and described in their IPDPSW '10 paper A Fast GPU Algorithm for Graph Connectivity (DOI). The breadth-first search implementation and many of the utility functions in Gunrock are derived from the b40c library of Duane Merrill. The algorithm is described in his PPoPP '12 paper Scalable GPU Graph Traversal (DOI). Thanks to Erich Elsen and Vishal Vaidyanathan from Royal Caliber and the Onu Team for their discussion on library development and the dataset auto-generating code. Thanks to Adam McLaughlin for his technical discussion. Thanks to Oded Green on his technical discussion and an optimization in CC primitive.
This work was funded by the DARPA XDATA program under AFRL Contract FA8750-13-C-0002 and by NSF awards CCF-1017399 and OCI-1032859. Our XDATA principal investigator is Eric Whyne of Data Tactics Corporation and our DARPA program manager is Dr. Christopher White (2012-2014) and Mr. Wade Shen(2015-now).
Gunrock is copyright The Regents of the University of California, 2015. The library, examples, and all source code are released under Apache 2.0.