18183

A Comparative Study on Exact Triangle Counting Algorithms on the GPU

Leyuan Wang, Yangzihao Wang, Carl Yang, John D. Owens
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}

}

Download Download (PDF)   View View   Source Source   

515

views

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.
Rating: 3.0/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: