SC14 New Orleans, LA

The International Conference for High Performance Computing, Networking, Storage and Analysis

Parallel Clustering Coefficient Computation Using GPUs.


Authors: Tahsin Reza (University of British Columbia), Tanuj Kr Aasawat (Jadavpur University), Matei Ripeanu (University of British Columbia)

Abstract: Clustering coefficient is the measure of how tightly vertices are bounded in a network. The Triangle Counting problem is at the core of clustering coefficient computation. We present a new technique for implementing clustering coefficient algorithm on GPUs. It relies on neighbour list being sorted with respect to vertex ID. The algorithm can process very large graphs not seen in the literature for single-node in-memory systems before. Our technique is able to compute clustering coefficient of each vertex in power-law graphs with up to 512M edges on a single GPU. Our GPU implementation offers 7x speedup over the best known work for the same graph. For the CPU implementation, we present results for graphs with up to 4B edges. We also investigate performance bottleneck of power-law graphs with skewed vertex degree distribution by analyzing performance counter outputs and interpreting them in terms of GPU memory and thread characteristics.

Poster: pdf
Two-page extended abstract: pdf


Poster Index