MapGraph
Authors:
Open Access
- 22 June 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-6
Abstract
High performance graph analytics are critical for a long list of application domains. In recent years, the rapid advancement of many-core processors, in particular graphical processing units (GPUs), has sparked a broad interest in developing high performance parallel graph programs on these architectures. However, the SIMT architecture used in GPUs places particular constraints on both the design and implementation of the algorithms and data structures, making the development of such programs difficult and time-consuming. We present MapGraph, a high performance parallel graph programming framework that delivers up to 3 billion Traversed Edges Per Second (TEPS) on a GPU. MapGraph provides a high-level abstraction that makes it easy to write graph programs and obtain good parallel speedups on GPUs. To deliver high performance, MapGraph dynamically chooses among different scheduling strategies depending on the size of the frontier and the size of the adjacency lists for the vertices in the frontier. In addition, a Structure Of Arrays (SOA) pattern is used to ensure coalesced memory access. Our experiments show that, for many graph analytics algorithms, an implementation, with our abstraction, is up to two orders of magnitude faster than a parallel CPU implementation and is comparable to state-of-the-art, manually optimized GPU implementations. In addition, with our abstraction, new graph analytics can be developed with relatively little effort.Keywords
This publication has 6 references indexed in Scilit:
- Medusa: Simplified Graph Processing on GPUsIEEE Transactions on Parallel and Distributed Systems, 2013
- Green-Marl2012
- Scalable GPU graph traversal2012
- Parallel PageRank computation using GPUs2012
- SOME GPU ALGORITHMS FOR GRAPH CONNECTED COMPONENTS AND SPANNING TREEParallel Processing Letters, 2010
- Pregel2010