SC16 Salt Lake City, UT

29. GPU Accelerated Graph Analytics Using Abstract Sparse Linear Algebra

Authors: Stephen T. Kozacik (EM Photonics Inc)Aaron L. Paolini (EM Photonics Inc)Paul Fox (EM Photonics Inc)James L. Bonnett (EM Photonics Inc)Evenie M. Chao (EM Photonics Inc)Eric Kelmelis (EM Photonics Inc)Dennis W. Prather (University of Delaware)

Abstract: Large-scale graph analytics using conventional processing systems often involves prohibitively excessive runtimes. Phrasing graph operations as abstract linear algebra operations offers potential for leveraging backend processing engines that scale better on modern heterogeneous computing platforms. To achieve this goal, we present a language for graph analytics that allows users to write in a familiar, vertex-centric API while leveraging the computational power of many-core accelerators. Our prototype toolchain automatically employs abstract sparse linear algebra (ASLA) operations using custom semi-rings in order to maximize performance. We use a C++ EDSL to map the user’s algorithm to efficient, fused ASLA operations at compile time with no runtime overhead. Using this technique, we have implemented several algorithms, including single-source shortest path, PageRank and single-source widest path. With a GPU-accelerated linear algebra backend, we can achieve better than 500% speedup over a multi-core ASLA library, using real and synthetic datasets.

Poster: pdf
Two-page extended abstract: pdf

Poster Index