Triangle Counting

Application Description

This benchmark counts the number of triangles in an undirected graph.

Algorithm

The algorithm is called extend-reduce. A initial worklist contains initial embedding (single edge). It computes the common neighbors of the two endpoints of each edge using set intersection, and accumulates the count to the global counter (total number) of triangles.

Performance

We present timing on NVIDIA V100 GPU (32G memory)

Graph	Time (s)
mico	0.001
patent_citations	0.01

Please read the following paper for detailed performance evaluation:

(VLDB 2020) [PDF] [Code]
Xuhao Chen, Roshan Dathathri, Gurbinder Gill, Keshav Pingali,
Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU,
PVLDB, 13(8): 1190-1205, 2020