SCHEDULE: NOV 16-21, 2014

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Parallel Clustering Coefficient Computation Using GPUs

SESSION: Poster Reception

EVENT TYPE: Posters

TIME: 5:15PM - 7:00PM

AUTHOR(S):Tahsin Reza, Tanuj Kr Aasawat, Matei Ripeanu

ROOM:New Orleans Theater Lobby

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.

Chair/Author Details:

Tahsin Reza - University of British Columbia

Tanuj Kr Aasawat - Jadavpur University

Matei Ripeanu - University of British Columbia

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar