Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs

Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs

Haicheng Wu, Daniel Zinn, Molham Aref, and Sudhakar Yalamanchili. “Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs.” International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures (ADMS). September 2014.

Abstract

Recent work has demonstrated that the use of programmable GPUs can be advantageous during relational query processing on analytical workloads. In this paper, we take a closer look at graph problems such as finding all triangles and all four-cliques of a graph. In particular, we present two different join algorithms for the GPU. The first is an implementation of Leapfrog-Triejoin (LFTJ), a recently presented worst-case optimal multi-predicate join algorithm. The second is a novel approach, inspired by the former but more suitable for GPU architectures. Our preliminary performance benchmarks show that for both approaches using GPUs is cost-effective. (the GPU implementation outperforms respective CPU variants). While the second algorithm is faster overall, it comes with increased implementation complexity and storage requirements for intermediary results. Furthermore, both our algorithms are competitive with the hand-written C++ implementation for finding triangles and four-cliques in the graph-processing system GraphLab executing on a multi-core CPU.

Download

Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs [PDF]

Citation

@inproceedings{Wu:2014:LFTJ,
author = {Wu, Haicheng and Zinn, Daniel and Aref, Molham and Yalamanchili, Sudhakar},
title = {Multipredicate Join Algorithms for Accelerating Relational Graph Processing on GPUs},
booktitle = {International Workshop on Accelerating Data Management Systems Using Modern Processor and Storage Architectures},
series = {ADMS ’14},
year = {2014},
location = {Hangzhou, China},
pages = {1–12},
numpages = {12},
}