A Comparative Study on Exact Triangle Counting Algorithms on the GPU
University of California, Davis
arXiv:1804.06926 [cs.DC], (18 Apr 2018)
@article{wang2018comparative,
title={A Comparative Study on Exact Triangle Counting Algorithms on the GPU},
author={Wang, Leyuan and Wang, Yangzihao and Yang, Carl and Owens, John D.},
year={2018},
month={apr},
archivePrefix={"arXiv"},
primaryClass={cs.DC},
doi={10.1145/2915516.2915521}
}
We implement exact triangle counting in graphs on the GPU using three different methodologies: subgraph matching to a triangle pattern; programmable graph analytics, with a set-intersection approach; and a matrix formulation based on sparse matrix-matrix multiplies. All three deliver best-of-class performance over CPU implementations and over comparable GPU implementations, with the graph-analytic approach achieving the best performance due to its ability to exploit efficient filtering steps to remove unnecessary work and its high-performance set-intersection core.
April 28, 2018 by hgpu
