and try to build up a hierarchical framework for designing graph operators
that includes not only graph traversal and computation building blocks such as
all five graph operators we have in Gunrock today, but also memory- and
workload-optimization building blocks that can be plugged into and replaced in
our higher-level graph operator implementation.

####  8.2.4. New Graph Primitives

Our current set of graph primitives are mostly textbook-style algorithms. One
future work is to expand this list to more complex graph primitives spanning
from network analysis, machine learning, data mining, and graph queries.

Graph Coloring and Maximal Independent Set:

Efficient graph matching and coloring algorithms (Cohen and CastonGuay, 2012)
can be computed by Gunrock more efficiently than previous work. Maximal
independent set (MIS) algorithms follow the same path. Both primitives can be
implemented using Gunrock’s current operator set with new operators such as
neighborhood reduction and multi-level priority queue potentially improving
their performance. These primitives can serve as the building blocks for
asynchrony and task-level parallelism.

Strongly Connected Component:

A directed graph is strongly connected if any node can reach any other node.
This algorithm is traditionally a problem related to depth-first search, which
is considered unsuitable for GPUs. However, Slota et al.’s work (2014)
improved on Barnat et al.’s DFS-based work (2011) and avoids DFS by combining
BFS and graph coloring.

More Traversal-based Algorithms:

To make use of our efficient graph traversal operators, we can modify our BFS
to implement several other similar primitives: 1)  _st_ -connectivity, which
simultaneously processes two BFS paths from $s$ and $t$; 2) A* search as a
BFS-based path finding and search algorithm; 3) Edmonds-Karp as a BFS-based
maximum flow algorithm; 4) {reverse} Cuthill-McKee algorithm, a sparse matrix
bandwidth reduction algorithm based on BFS; 5) belief propagation, a sum-
product message passing algorithm based on BFS; and finally 6) radii
estimation, a $k$-sample BFS-based algorithm for estimating the maximum radius
of the graph.

Subgraph Isomorphism:

Most optimized subgraph matching algorithms on CPUs (Han et al., 2013) are
based on backtracking strategies which follow a recursive routine cannot
efficiently be adapted to GPUs. Recent subgraph matching on large graphs on
the GPU (Tran et al., 2015) and distributed memory cloud (Sun et al., 2012;
Bröcheler et al., 2010), both of which use graph traversal extensively, and
could fit nicely and turn out to work more efficiently in Gunrock’s framework.
However, these methods are memory-bound which suggests a focus on more
effective filtering and joining methods. Extensions to our current segmented
intersection operator more flexible input format support for query graphs will
potentially make subgraph matching in Gunrock perform better.

_k_ -SAT:

_k_ -SAT is a type of Boolean satisfiability problem that can be represented
as an iterative updating process on a bipartite graph. Combining the sampling
operator and our efficient traversal operator, it potentially fits nicely into
Gunrock.

SGD and MCMC:

Both Stochastic Gradient Descent in matrix completion and Markov Chain Monte
Carlo have large amounts of parallelism. The former can be presented as either
an iterative bipartite graph traversal-updating algorithm (Kaleem et al.,
2015) or a conflict-free subgraph parallel updating algorithm. In order to
decrease the number of conflict updates and increase the data re-usage rate,
the incomplete matrix is divided into sub-matrices where graph coloring can
help identify the conflict-free elements in those small sub-matrices. Graph
coloring can take advantage of Gunrock’s efficient traversal operator to
achieve better performance. MCMC’s iterative dense update makes it a good
candidate for matrix-based graph algorithms. However, Gunrock operators can
also represent this problem.

####  8.2.5. New Graph Datatypes

All graph processing systems on the GPU use CSR and edge lists internally. We
see significant opportunity in designing suitable graph datatypes and data
structures to enable graph primitives on mutable graphs and matrix-typed graph
primitives.

Mutable Graphs:

The meaning of mutable is twofold: mutable by primitive, and mutable by input
data. _Mutable by algorithm_ means that the graph primitive changes the graph
structure, and includes primitives such as MST, community detection, mesh
refinement, and Karger’s mincut. The operations related include simple ones
such as adding/removing nodes/edges, and more complex ones such as forming
supervertices. Currently there is no good solution for handling general graph
mutations on GPUs with efficiency. _Mutable by input data_ means that we
process our algorithms on input datasets that change over time (so we would
like to both incrementally update the graph data structure and incrementally
update a solution given the incremental change in the data structure). We need
to provide either approximated results or the capability of doing incremental
computation.

Adjacency Matrix Form:

Matrix-based graph algorithms are also widely used for graph processing such
as BFS and PageRank. Our sparse-matrix sparse-vector operator and its
application to BFS (Yang et al., 2015) has shed light on more applications in
matrix form such as MIS, PageRank, SSSP, and several spectral methods, which
are used in algorithms like collaborative filtering.

Optimized Graph Topology Format:

The work of Wu et al. (Wu et al., 2013) shows how data reorganization can help
with memory uncoalescing. However, for graph analytics, we need to design
better strategies since the memory access indices (node IDs in the frontier)
change dynamically every iteration. Both CuSha (Khorasani et al., 2014) and
Graphicionado (Chen et al., 2016) proposed optimizations on memory access via
edge-list grouping according to source node ID and destination node ID. Such
optimizations, and a well-designed cache framework, would reduce random memory
access during graph analytics. It is also an open question if bandwidth
reduction algorithms such as reverse Cuthill-McKee would bring better memory
locality for graph analytics.

Rich-data-on-{vertices,edges}:

Complex networks often contain rich data on vertices and/or edges. Currently
Gunrock puts all the information on edges/vertices into a data structure on
the GPU, which is not ideal. Adding the capability of loading partial
edge/vertex information onto the GPU could enable graph query tasks and allow
us to support several network analysis primitives that use this rich
information during their computation.

###  8.3. Summary

Gunrock was born when we spent two months writing a single hardwired GPU graph
primitive. We knew that for GPUs to make an impact in graph analytics, we had
to raise the level of abstraction in building graph primitives. With this
work, we show that with appropriate high-level programming model and low-level
optimizations, parallel graph analytics on the GPU can be both simple and
efficient. More specifically, this work has achieved its two high-level goals:

  * •

Our data-centric, frontier-focused programming model has proven to map
naturally to the GPU, giving us both good performance and good flexibility. We
have also found that implementing this abstraction has allowed us to integrate
numerous optimization strategies, including multiple load-balancing strategies
for traversal, direction-optimal traversal, and a two-level priority queue.
The result is a framework that is general (able to implement numerous simple
and complex graph primitives), straightforward to program (new primitives only
take a few hundred lines of code and require minimal GPU programming
knowledge), and fast (on par with hardwired primitives and faster than any
other programmable GPU graph library).

  * •

Our open-sourced GPU graph processing library Gunrock provides a graph
analytics framework for three types of users: 1) data scientists who want to
take the advantage of the GPU’s superior computing power in big data
applications; 2) algorithm designers who want to use the existing efficient
graph operators in Gunrock to create new graph algorithms and applications;
and 3) researchers who want to reproduce the results of our research, or make
improvements to our core components. We hope that in the future, Gunrock will
serve as a standard benchmark for graph processing on the GPU.

## Acknowledgments

Thanks to our DARPA program managers Wade Shen and Christopher White, and
DARPA business manager Gabriela Araujo, for their support during this project.
Thanks to the Altair and Vega-lite teams in the Interactive Data Lab at the
University of Washington for graphing help. Joe Mako provided the speedup
chart design. 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. Thanks also to our colleagues at Onu
Technology: Erich Elsen, Guha Jayachandran, and Vishal Vaidyanathan.

We gratefully acknowledge the support of the DARPA XDATA program (US Army
award W911QX-12-C-0059); DARPA STTR awards D14PC00023 and D15PC00010; NSF
awards CCF-1017399, OCI-1032859, and CCF-1629657; and UC Lab Fees Research
Program Award 12-LR-238449.

## References

  * (1)
  * Aberger et al. (2015) Christopher R. Aberger, Andres Nötzli, Kunle Olukotun, and Christopher Ré. 2015\.  EmptyHeaded: Boolean Algebra Based Graph Processing.  CoRR abs/1503.02368 (2015).  http://arxiv.org/abs/1503.02368
  * Ashkiani et al. (2016) Saman Ashkiani, Andrew A. Davidson, Ulrich Meyer, and John D. Owens. 2016.  GPU Multisplit. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2016). 12:1–12:13.  DOI:http://dx.doi.org/10.1145/2851141.2851169
  * Barnat et al. (2011) Jiri Barnat, Petr Bauch, Lubos Brim, and Milan Ceska. 2011\.  Computing Strongly Connected Components in Parallel on CUDA. In Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium (IPDPS ’11). IEEE Computer Society, Washington, DC, USA, 544–555.  DOI:http://dx.doi.org/10.1109/IPDPS.2011.59
  * Baxter (2013) Sean Baxter. 2013\.  Modern GPU Multisets. (2013).  https://nvlabs.github.io/moderngpu/sets.html.
  * Baxter (2016) Sean Baxter. 2013–2016.  Moderngpu: Patterns and Behaviors for GPU Computing. (2013–2016).  http://moderngpu.github.io/moderngpu.
  * Beamer et al. (2012) Scott Beamer, Krste Asanović, and David Patterson. 2012\.  Direction-Optimizing Breadth-First Search. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC ’12). Article 12, 10 pages.  DOI:http://dx.doi.org/10.1109/SC.2012.50
  * Billeter et al. (2009) Markus Billeter, Ola Olsson, and Ulf Assarsson. 2009\.  Efficient Stream Compaction on Wide SIMD Many-core Architectures. In Proceedings of the Conference on High Performance Graphics 2009 (HPG ’09). ACM, New York, NY, USA, 159–166.  DOI:http://dx.doi.org/10.1145/1572769.1572795
  * Brandes (2001) Ulrik Brandes. 2001\.  A faster algorithm for betweenness centrality.  Journal of Mathematical Sociology 25, 2 (2001), 163–177.  DOI:http://dx.doi.org/10.1080/0022250X.2001.9990249
  * Bröcheler et al. (2010) M. Bröcheler, A. Pugliese, and V. S. Subrahmanian. 2010\.  COSI: Cloud Oriented Subgraph Identification in Massive Social Networks. In Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining (ASONAM ’10). IEEE Computer Society, Washington, DC, USA, 248–255.  DOI:http://dx.doi.org/10.1109/ASONAM.2010.80
  * Burtscher et al. (2012a) Martin Burtscher, Rupesh Nasre, and Keshav Pingali. 2012a.  A Quantitative Study of Irregular Programs on GPUs. In Proceedings of the 2012 IEEE International Symposium on Workload Characterization (IISWC) (IISWC ’12). IEEE Computer Society, Washington, DC, USA, 141–151.  DOI:http://dx.doi.org/10.1109/IISWC.2012.6402918
  * Burtscher et al. (2012b) Martin Burtscher, Rupesh Nasre, and Keshav Pingali. 2012b.  A Quantitative Study of Irregular Programs on GPUs. In IEEE International Symposium on Workload Characterization (IISWC-2012). 141–151.  DOI:http://dx.doi.org/10.1109/IISWC.2012.6402918
  * Busato and Bombieri (2015) F. Busato and N. Bombieri. 2015.  BFS-4K: An Efficient Implementation of BFS for Kepler GPU Architectures.  IEEE Transactions on Parallel and Distributed Systems 26, 7 (July 2015), 1826–1838.  DOI:http://dx.doi.org/10.1109/TPDS.2014.2330597
  * Cederman and Tsigas (2008) Daniel Cederman and Philippas Tsigas. 2008.  On Dynamic Load-Balancing on Graphics Processors. In Graphics Hardware 2008. 57–64.  DOI:http://dx.doi.org/10.2312/EGGH/EGGH08/057-064
  * Chen et al. (2016) Yunji Chen, Tao Luo, Shaoli Liu, Shijin Zhang, Liqiang He, Jia Wang, Ling Li, Tianshi Chen, Zhiwei Xu, Ninghui Sun, and Olivier Temam. 2016.  Graphicionado: A High-Performance and Energy-Efficient Accelerator for Graph Analytics. In Proceedings of the 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-49). IEEE Computer Society, Washington, DC, USA.
  * Cohen and CastonGuay (2012) Jonathan Cohen and Patrice CastonGuay. 2012.  Efficient Graph Matching and Coloring on the GPU.  GPU Technology Conference (March 2012).  http://on-demand.gputechconf.com/gtc/2012/presentations/S0332-Efficient-Graph-Matching-and-Coloring-on-GPUs.pdf
  * Davidson et al. (2014) Andrew Davidson, Sean Baxter, Michael Garland, and John D. Owens. 2014.  Work-Efficient Parallel GPU Methods for Single Source Shortest Paths. In Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2014). 349–359.  DOI:http://dx.doi.org/10.1109/IPDPS.2014.45
  * Delling et al. (2010) Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2010.  PHAST: Hardware-accelerated shortest path trees.  J. Parallel and Distrib. Comput. 73 (Sept. 2010), 940–952.  DOI:http://dx.doi.org/10.1016/j.jpdc.2012.02.007
  * Elsen and Vaidyanathan (2013) Erich Elsen and Vishal Vaidyanathan. 2013.  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.
  * Fu et al. (2014) Zhisong Fu, Michael Personick, and Bryan Thompson. 2014\.  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). Article 2, 6 pages.  DOI:http://dx.doi.org/10.1145/2621934.2621936
  * Geil et al. (2014) Afton Geil, Yangzihao Wang, and John D. Owens. 2014\.  WTF, GPU! Computing Twitter’s Who-To-Follow on the GPU. In Proceedings of the Second ACM Conference on Online Social Networks (COSN ’14). 63–68.  DOI:http://dx.doi.org/10.1145/2660460.2660481
  * Gharaibeh et al. (2014) Abdullah Gharaibeh, Tahsin Reza, Elizeu Santos-Neto, Lauro Beltrao Costa, Scott Sallinen, and Matei Ripeanu. 2014.  Efficient Large-Scale Graph Processing on Hybrid CPU and GPU Systems.  CoRR abs/1312.3018, 1312.3018v2 (Dec. 2014).  arXiv:1312.3018v2
  * Goel et al. (2015) Ashish Goel, Pankaj Gupta, John Sirois, Dong Wang, Aneesh Sharma, and Siva Gurumurthy. 2015\.  The Who-To-Follow System at Twitter: Strategy, Algorithms, and Revenue Impact.  Interfaces 45, 1 (Feb. 2015), 98–107.  DOI:http://dx.doi.org/10.1287/inte.2014.0784
  * Gonzalez et al. (2012) Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012\.  PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI ’12). USENIX Association, 17–30.
  * Gonzalez et al. (2014) Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014.  GraphX: Graph Processing in a Distributed Dataflow Framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI’14). USENIX Association, Berkeley, CA, USA, 599–613.  http://dl.acm.org/citation.cfm?id=2685048.2685096
  * Green et al. (2012) Oded Green, Robert McColl, and David A. Bader. 2012\.  GPU Merge Path: A GPU Merging Algorithm. In Proceedings of the 26th ACM International Conference on Supercomputing (ICS ’12). ACM, New York, NY, USA, 331–340.  DOI:http://dx.doi.org/10.1145/2304576.2304621
  * Green et al. (2014a) Oded Green, Lluís-Miquel Munguía, and David A. Bader. 2014a.  Load Balanced Clustering Coefficients. In Proceedings of the First Workshop on Parallel Programming for Analytics Applications (PPAA ’14). 3–10.  DOI:http://dx.doi.org/10.1145/2567634.2567635
  * Green et al. (2014b) Oded Green, Pavan Yalamanchili, and Lluís-Miquel Munguía. 2014b.  Fast Triangle Counting on the GPU. In Proceedings of the Fourth Workshop on Irregular Applications: Architectures and Algorithms (IA3 ’14). 1–8.  DOI:http://dx.doi.org/10.1109/IA3.2014.7
  * Gregor and Lumsdaine (2005) Douglas Gregor and Andrew Lumsdaine. 2005.  The Parallel BGL: A Generic Library for Distributed Graph Computations. In Parallel Object-Oriented Scientific Computing (POOSC).
  * Greiner (1994) John Greiner. 1994\.  A Comparison of Parallel Algorithms for Connected Components. In Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’94). 16–25.  DOI:http://dx.doi.org/10.1145/181014.181021
  * Gupta et al. (2013) Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Zadeh. 2013\.  WTF: The Who to Follow Service at Twitter. In Proceedings of the International Conference on the World Wide Web. 505–514.
  * Han et al. (2013) Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013\.  Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD ’13). ACM, New York, NY, USA, 337–348.  DOI:http://dx.doi.org/10.1145/2463676.2465300
  * Harish and Narayanan (2007) 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). Springer-Verlag, Berlin, Heidelberg, 197–208.  DOI:http://dx.doi.org/10.1007/978-3-540-77220-0_21
  * Harris et al. (2016) Mark Harris, John D. Owens, Shubho Sengupta, Yao Zhang, and Andrew Davidson. 2009–2016.  CUDPP: CUDA Data Parallel Primitives Library. (2009–2016).  http://cudpp.github.io/.
  * Hong et al. (2012) Sungpack Hong, Hassan Chafi, Edic Sedlar, and Kunle Olukotun. 2012.  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). 349–362.  DOI:http://dx.doi.org/10.1145/2189750.2151013
  * Hong et al. (2011) Sungpack Hong, Sang Kyun Kim, Tayo Oguntebi, and Kunle Olukotun. 2011.  Accelerating CUDA Graph Algorithms at Maximum Warp. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP ’11). 267–276.  DOI:http://dx.doi.org/10.1145/1941553.1941590
  * Jia et al. (2011) Yuntao Jia, Victor Lu, Jared Hoberock, Michael Garland, and John C. Hart. 2011.  Edge v. Node Parallelism for Graph Centrality Metrics.  In GPU Computing Gems Jade Edition, Wen-mei W. Hwu (Ed.). Morgan Kaufmann, Chapter 2, 15–28.  DOI:http://dx.doi.org/10.1016/B978-0-12-385963-1.00002-2
  * Kaleem et al. (2015) Rashid Kaleem, Sreepathi Pai, and Keshav Pingali. 2015\.  Stochastic Gradient Descent on GPUs. In Proceedings of the 8th Workshop on General Purpose Processing Using GPUs (GPGPU 2015). ACM, New York, NY, USA, 81–89.  DOI:http://dx.doi.org/10.1145/2716282.2716289
  * Keckler et al. (2011) Stephen W. Keckler, William J. Dally, Brucek Khailany, Michael Garland, and David Glasco. 2011\.  GPUs and the Future of Parallel Computing.  IEEE Micro 31, 5 (Sept. 2011), 7–17.  DOI:http://dx.doi.org/10.1109/MM.2011.89
  * Kepner et al. (2016) Jeremy Kepner, Peter Aaltonen, David Bader, Aydın Buluç, Franz Franchetti, John Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Jose Moreira, John D. Owens, Carl Yang, Marcin Zalewski, and Timothy Mattson. 2016\.  Mathematical Foundations of the GraphBLAS. In Proceedings of the IEEE High Performance Extreme Computing Conference.  DOI:http://dx.doi.org/10.1109/HPEC.2016.7761646
  * Khorasani et al. (2014) Farzad Khorasani, Keval Vora, Rajiv Gupta, and Laxmi N. Bhuyan. 2014.  CuSha: Vertex-centric Graph Processing on GPUs. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing (HPDC ’14). 239–252.  DOI:http://dx.doi.org/10.1145/2600212.2600227
  * Kwak et al. (2010) Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010\.  What is Twitter, a social network or a news media?. In Proceedings of the International Conference on the World Wide Web. 591–600.  DOI:http://dx.doi.org/10.1145/1772690.1772751
  * Kyrola et al. (2012) Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012\.  GraphChi: Large-scale Graph Computation on Just a PC. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI’12). USENIX Association, Berkeley, CA, USA, 31–46.  http://dl.acm.org/citation.cfm?id=2387880.2387884
  * Leskovec (2016) Jure Leskovec. 2009–2016.  SNAP: Stanford Large Network Dataset Collection. (2009–2016).  http://snap.stanford.edu/data/.
  * Liu and Huang (2015) Hang Liu and H. Howie Huang. 2015.  Enterprise: Breadth-first Graph Traversal on GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’15). ACM, New York, NY, USA, Article 68, 12 pages.  DOI:http://dx.doi.org/10.1145/2807591.2807594
  * Liu et al. (2016) Hang Liu, H. Howie Huang, and Yang Hu. 2016.  iBFS: Concurrent Breadth-First Search on GPUs. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD ’16). ACM, New York, NY, USA, 403–416.  DOI:http://dx.doi.org/10.1145/2882903.2882959
  * Low et al. (2010) Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein. 2010.  GraphLab: A New Parallel Framework for Machine Learning. In Proceedings of the Twenty-Sixth Annual Conference on Uncertainty in Artificial Intelligence (UAI-10). 340–349.
  * Malewicz et al. (2010) Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010\.  Pregel: A System for Large-scale Graph Processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD ’10). 135–146.  DOI:http://dx.doi.org/10.1145/1807167.1807184
  * McColl et al. (2014) Robert Campbell McColl, David Ediger, Jason Poovey, Dan Campbell, and David A. Bader. 2014\.  A Performance Evaluation of Open Source Graph Databases. In Proceedings of the First Workshop on Parallel Programming for Analytics Applications (PPAA ’14). 11–18.  DOI:http://dx.doi.org/10.1145/2567634.2567638
  * McLaughlin and Bader (2014) Adam McLaughlin and David A. Bader. 2014.  Scalable and High Performance Betweenness Centrality on the GPU. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC14). 572–583.  DOI:http://dx.doi.org/10.1109/SC.2014.52
  * McLaughlin and Bader (2015) A. McLaughlin and D. A. Bader. 2015.  Fast Execution of Simultaneous Breadth-First Searches on Sparse Graphs. In 2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS). 9–18.  DOI:http://dx.doi.org/10.1109/ICPADS.2015.10
  * McLaughlin et al. (2015) A. McLaughlin, J. Riedy, and D. A. Bader. 2015.  A fast, energy-efficient abstraction for simultaneous breadth-first searches. In 2015 IEEE High Performance Extreme Computing Conference (HPEC). 1–6.  DOI:http://dx.doi.org/10.1109/HPEC.2015.7322466
  * Merrill et al. (2012) Duane Merrill, Michael Garland, and Andrew Grimshaw. 2012\.  Scalable GPU Graph Traversal. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’12). 117–128.  DOI:http://dx.doi.org/10.1145/2145816.2145832
  * Meyer and Sanders (2003) U. Meyer and P. Sanders. 2003.  $\Delta$-stepping: a parallelizable shortest path algorithm.  Journal of Algorithms 49, 1 (Oct. 2003), 114–152.  DOI:http://dx.doi.org/10.1016/S0196-6774(03)00076-2 1998 European Symposium on Algorithms.
  * Nguyen et al. (2013) Donald Nguyen, Andrew Lenharth, and Keshav Pingali. 2013\.  A Lightweight Infrastructure for Graph Analytics. In Proceedings of ACM Symposium on Operating Systems Principles (SOSP ’13). 456–471.  DOI:http://dx.doi.org/10.1145/2517349.2522739
  * Pai and Pingali (2016) Sreepathi Pai and Keshav Pingali. 2016.  A Compiler for Throughput Optimization of Graph Algorithms on GPUs.  SIGPLAN Not. 51, 10 (Oct. 2016), 1–19.  DOI:http://dx.doi.org/10.1145/3022671.2984015
  * Pan et al. (2016) Yuechao Pan, Yangzihao Wang, Yuduo Wu, Carl Yang, and John D. Owens. 2016.  Multi-GPU Graph Analytics.  CoRR abs/1504.04804, 1504.04804v3 (April 2016).  arXiv:cs.DC/1504.04804v3
  * Pande and Bader (2011) Pushkar R. Pande and David A. Bader. 2011.  Computing Betweenness Centrality for Small World Networks on a GPU. In 2011 IEEE Conference on High Performance Embedded Computing.
  * Pearce et al. (2014) Roger Pearce, Maya Gokhale, and Nancy M. Amato. 2014\.  Faster Parallel Traversal of Scale Free Graphs at Extreme Scale with Vertex Delegates. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’14). IEEE Press, Piscataway, NJ, USA, 549–559.  DOI:http://dx.doi.org/10.1109/SC.2014.50
  * Pingali et al. (2011) Keshav Pingali, Donald Nguyen, Milind Kulkarni, Martin Burtscher, M. Amber Hassaan, Rashid Kaleem, Tsung-Hsien Lee, Andrew Lenharth, Roman Manevich, Mario Méndez-Lojo, Dimitrios Prountzos, and Xin Sui. 2011.  The Tao of Parallelism in Algorithms. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’11). 12–25.  DOI:http://dx.doi.org/10.1145/1993498.1993501
  * Polak (2015) Adam Polak. 2015\.  Counting Triangles in Large Graphs on GPU.  CoRR abs/1503.00576 (2015).  http://arxiv.org/abs/1503.00576
  * Roy et al. (2013) Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013\.  X-Stream: Edge-centric Graph Processing using Streaming Partitions. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. ACM, 472–488.
  * Salihoglu and Widom (2014) Semih Salihoglu and Jennifer Widom. 2014.  HelP: High-level Primitives For Large-Scale Graph Processing. In Proceedings of the Workshop on GRAph Data Management Experiences and Systems (GRADES ’14). Article 3, 6 pages.  DOI:http://dx.doi.org/10.1145/2621934.2621938
  * Sallinen et al. (2015) Scott Sallinen, Abdullah Gharaibeh, and Matei Ripeanu. 2015\.  Accelerating Direction-Optimized Breadth First Search on Hybrid Architectures.  CoRR abs/1503.04359, 1503.04359v1 (March 2015).  arXiv:cs.DC/1503.04359v1
  * Sariyüce et al. (2013) Ahmet Erdem Sariyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek. 2013\.  Betweenness Centrality on GPUs and Heterogeneous Architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units (GPGPU-6). 76–85.  DOI:http://dx.doi.org/10.1145/2458523.2458531
  * Schank and Wagner (2005) Thomas Schank and Dorothea Wagner. 2005.  Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study. In Proceedings of the 4th International Conference on Experimental and Efficient Algorithms (WEA’05). 606–609.  DOI:http://dx.doi.org/10.1007/11427186_54
  * Seo et al. (2015) Hyunseok Seo, Jinwook Kim, and Min-Soo Kim. 2015.  GStream: A Graph Streaming Processing Method for Large-scale Graphs on GPUs. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015). ACM, New York, NY, USA, 253–254.  DOI:http://dx.doi.org/10.1145/2688500.2688526
  * Shi et al. (2015) Xuanhua Shi, Junling Liang, Sheng Di, Bingsheng He, Hai Jin, Lu Lu, Zhixiang Wang, Xuan Luo, and Jianlong Zhong. 2015\.  Optimization of Asynchronous Graph Processing on GPU with Hybrid Coloring Model. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015). 271–272.  DOI:http://dx.doi.org/10.1145/2688500.2688542
  * Shun and Blelloch (2013) Julian Shun and Guy E. Blelloch. 2013.  Ligra: a lightweight graph processing framework for shared memory. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’13). 135–146.  DOI:http://dx.doi.org/10.1145/2442516.2442530
  * Shun and Tangwongsan (2015) J. Shun and K. Tangwongsan. 2015.  Multicore Triangle Computations Without Tuning. In IEEE 31st International Conference on Data Engineering. 149–160.  DOI:http://dx.doi.org/10.1109/ICDE.2015.7113280
  * Siek et al. (2001) Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. 2001\.  The Boost Graph Library: User Guide and Reference Manual.  Addison-Wesley.
  * Slota et al. (2014) G. M. Slota, S. Rajamanickam, and K. Madduri. 2014\.  BFS and Coloring-Based Parallel Algorithms for Strongly Connected Components and Related Problems. In 2014 IEEE 28th International Parallel and Distributed Processing Symposium. 550–559.  DOI:http://dx.doi.org/10.1109/IPDPS.2014.64
  * Soman et al. (2010) Jyothish Soman, Kothapalli Kishore, and P J Narayanan. 2010\.  A Fast GPU Algorithm for Graph Connectivity. In 24th IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum (IPDPSW 2010). 1–8.  DOI:http://dx.doi.org/10.1109/IPDPSW.2010.5470817
  * Sun et al. (2012) Zhao Sun, Hongzhi Wang, Haixun Wang, Bin Shao, and Jianzhong Li. 2012.  Efficient Subgraph Matching on Billion Node Graphs.  Proc. VLDB Endow. 5, 9 (May 2012), 788–799.  DOI:http://dx.doi.org/10.14778/2311906.2311907
  * Tran et al. (2015) Ha-Nguyen Tran, Jung-jae Kim, and Bingsheng He. 2015.  Fast Subgraph Matching on Large Graphs using Graphics Processors.  In Database Systems for Advanced Applications, Matthias Renz, Cyrus Shahabi, Xiaofang Zhou, and Muhammad Aamir Cheema (Eds.). Lecture Notes in Computer Science, Vol. 9049. Springer International Publishing, 299–315.  DOI:http://dx.doi.org/10.1007/978-3-319-18120-2_18
  * Tzeng et al. (2012) Stanley Tzeng, Brandon Lloyd, and John D. Owens. 2012\.  A GPU Task-Parallel Model with Dependency Resolution.  IEEE Computer 45, 8 (Aug. 2012), 34–41.  DOI:http://dx.doi.org/10.1109/MC.2012.255
  * Wang et al. (2013) Guozhang Wang, Wenlei Xie, Alan J. Demers, and Johannes Gehrke. 2013.  Asynchronous Large-Scale Graph Processing Made Easy. In CIDR. www.cidrdb.org.
  * Wang et al. (2016b) Leyuan Wang, Yangzihao Wang, Carl Yang, and John D. Owens. 2016b.  A Comparative Study on Exact Triangle Counting Algorithms on the GPU. In Proceedings of the 1st High Performance Graph Processing Workshop (HPGP ’16). 1–8.  DOI:http://dx.doi.org/10.1145/2915516.2915521
  * Wang et al. (2016a) Yangzihao Wang, Andrew Davidson, Yuechao Pan, Yuduo Wu, Andy Riffel, and John D. Owens. 2016a.  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 2016). 11:1–11:12.  DOI:http://dx.doi.org/10.1145/2851141.2851145
  * Wu et al. (2013) Bo Wu, Zhijia Zhao, Eddy Zheng Zhang, Yunlian Jiang, and Xipeng Shen. 2013.  Complexity Analysis and Algorithm Design for Reorganizing Data to Minimize Non-coalesced Memory Accesses on GPU. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’13). ACM, New York, NY, USA, 57–68.  DOI:http://dx.doi.org/10.1145/2442516.2442523
  * Wu et al. (2015) Yuduo Wu, Yangzihao Wang, Yuechao Pan, Carl Yang, and John D. Owens. 2015.  Performance Characterization for High-Level Programming Models for GPU Graph Analytics. In IEEE International Symposium on Workload Characterization (IISWC-2015). 66–75.  DOI:http://dx.doi.org/10.1109/IISWC.2015.13
  * Yang et al. (2015) Carl Yang, Yangzihao Wang, and John D. Owens. 2015\.  Fast Sparse Matrix and Sparse Vector Multiplication Algorithm on the GPU. In Graph Algorithms Building Blocks (GABB 2015). 841–847.  DOI:http://dx.doi.org/10.1109/IPDPSW.2015.77
  * Zhong and He (2014) Jianlong Zhong and Bingsheng He. 2014.  Medusa: Simplified Graph Processing on GPUs.  IEEE Transactions on Parallel and Distributed Systems 25, 6 (June 2014), 1543–1552.  DOI:http://dx.doi.org/10.1109/TPDS.2013.111