Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Gunrock: GPU graph analytics
Wang Y., Pan Y., Davidson A., Wu Y., Yang C., Wang L., Osama M., Yuan C., Liu W., Riffel A., Owens J. ACM Transactions on Parallel Computing4 (1):1-49,2017.Type:Article
Date Reviewed: Nov 30 2017

Graphs are fundamental data structures for modeling social interactions, computer networks, and physical simulations. Graph analytic libraries provide optimized primitives and application programming interfaces (APIs) for performing computation on large-scale graph datasets. This paper describes Gunrock, a high-performance graph analytic library for general-purpose graph operations using graphic processing units (GPUs). Gunrock improves programmability by enabling developers to describe common graph analytic workloads using four primitive operations. In addition, the authors describe optimized implementations for each primitive on commodity GPUs.

Several implementations of large-scale graph analytic libraries are already available for single-node and distributed central processing unit (CPU) systems such as Boost, Pregel, GiGraph, and GraphLab. More recently, several efficient implementations of fundamental graph applications such as breadth-first search, connected components, and triangle counting have been developed for GPUs. Section 2 provides an excellent survey of graph analytic libraries.

Whereas previous approaches have modeled graph operations using a series of synchronized computations, the novelty of this work lies in the fact that such operations are performed using progressive updates to a data structure that consists of nodes or edges (referred to as a frontier). Unlike previous approaches that only perform vertex-centric computations, Gunrock allows operations on vertices or edges. The framework provides four primitives for expressing common graph analytic operations: advance, filter, segmented intersection, and compute. The authors illustrate these operations with an example, single-source shortest path, and compare the implementation with existing CPU-based and GPU-based graph analytic frameworks (section 3). An important issue addressed here is the efficient mapping of irregular operations on GPUs. Several strategies are described, including coarse-grained load balancing, dynamic grouping, and adjusting traversal direction.

The Gunrock graph analytic model suits a broad class of graph analytic algorithms as demonstrated by experiments performed on real-world datasets. An open-source version of the library is available for popular GPU platforms.

Reviewer:  Deepak Unnikrishnan Review #: CR145687 (1802-0111)
Bookmark and Share
 
Graphics Processors (I.3.1 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Parallel Algorithms (G.1.0 ... )
 
 
Single-Instruction-Stream, Multiple-Data-Stream Processors (SIMD) (C.1.2 ... )
 
 
Parallel Architectures (C.1.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Graphics Processors": Date
Introduction to volume rendering
Lichtenbelt B., Crane R., Naqvi S., Prentice-Hall, Inc., Upper Saddle River, NJ, 1998. Type: Book (9780138616830)
May 1 1999
Time/space tradeoffs for polygon mesh rendering
Bar-Yehuda R., Gotsman C. ACM Transactions on Graphics (TOG) 15(2): 141-152, 1996. Type: Article
Jul 1 1997
A programmable vertex shader with fixed-point SIMD datapath for low power wireless applications
Sohn J., Woo R., Yoo H.  Graphics hardware (Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, Grenoble, France, Aug 29-30, 2004)107-114, 2004. Type: Proceedings
Jul 8 2005
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy