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

Graph	Time (s)
mico	0.02
patent_citations	0.1

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

Machine Description

Performance numbers are collected on a 4 package (14 cores per package) Intel(R) Xeon(R) Gold 5120 CPU machine at 2.20GHz from 1 thread to 56 threads in increments of 7 threads. The machine has 192GB of RAM. The operating system is CentOS Linux release 7.5.1804. All runs of the Galois benchmarks used gcc/g++ 7.2 to compile.