2012 ScalableGPUGraphTraversal

• (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. ISBN:978-1-4503-1160-1 doi:10.1145/2370036.2145832

Subject Headings: Graph Analysis Algorithm; Graph Diameter.

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Scalable+GPU+Graph+Traversal
• http://dl.acm.org/citation.cfm?id=2370036.2145832&preflayout=flat#citedby

Quotes

Abstract

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 non-trivial diameter.

We present a BFS parallelization focused on fine-grained task management constructed from efficient prefix sum that achieves an asymptotically optimal O (|V|+|E|) 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 both CPU and GPU platforms.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 ScalableGPUGraphTraversal	Duane Merrill Michael Garland Andrew Grimshaw			Scalable GPU Graph Traversal				10.1145/2370036.2145832		2012