Triangle Counting

Problem Description

This benchmark counts the number of triangles in a given undirected graph. It uses a new graph partitioning scheme that avoids communication during triangle counting.


To count the number of triangles in a distributed platform, we use a a novel application-agnostic graph partitioning strategy. The strategy eliminates almost all communication for distributed triangle counting. Each machine in a distributed cluster performs triangle counting independently in its own partition without communicating with other hosts. In the end, the total triangle count is obtained by aggregating the local triangle counts from all machines. More details about the partitioning strategy and the distributed triangle counting can be found in [1].

[1] Loc Hoang, Vishwesh Jatala, Xuhao Chen, Udit Agarwal, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali, DistTC: High Performance Distributed Triangle Counting. In 2019 IEEE High Performance Extreme Computing Conference, HPEC 2019. IEEE, 2019.


The graph below shows the performance of distributed triangle counting (DistTC) on Bridges cluster at the Pittsburgh Supercomputing Center. We used up to 64 NVIDIA Tesla P100 GPUs located on 32 distributed machines with 128GB DRAM each. Each P100 GPU has 16GB of memory. Each node in the cluster has 2 Intel Broadwell E5-2683 v4 CPUs with 16 cores per CPU. The nodes in the cluster are connected through the Intel Omni-Path Architecture. We run on five graphs (friendster, gsh-2015, rmat26, twitter40, and uk2007) on up to 64 GPUs (32 nodes on Bridges). The below table show the properties of the input graph. rmat26 is a synthetic graph generated by an RMAT generator; twitter40, friendster, uk-2007, gsh-2015, and clueweb12 are web crawls. Input graphs are symmetric, have no self-loops, and have no duplicated edges.

Input Properties

GraphVertices Undirected Edges No. of Triangles
friendster 65,608,366 1,806,067,135 4,173,724,142
gsh-2015 988,490,691 25,690,705,118 910,140,734,636
rmat26 67,108,864 1,065,788,093 43,646,321,254
twitter40 41,652,230 1,202,513,046 34,824,916,864
uk2007 105,896,435 3,301,876,564 286,701,284,103

Figure 1: Strong Scaling of Distributed Triangle Counting on Bridges (P100 GPUs).