SCHEDULE: NOV 16-22, 2013

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.

On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs

SESSION: Sorting and Graph Algorithms

EVENT TYPE: Papers

TIME: 2:00PM - 2:30PM

SESSION CHAIR: Karen Devine

AUTHOR(S):Sungpack Hong, Nicole C. Rodia, Kunle Olukotun

ROOM:205/207

ABSTRACT:
Detecting strongly connected components (SCCs) in a directed graph is a fundamental graph analysis algorithm that is used in many science and engineering domains. Traditional approaches in parallel SCC detection, however, show limited performance and poor scaling behavior when applied to large real-world graph instances. In this paper, we investigate the shortcomings of the conventional approach and propose a series of extensions that consider the fundamental properties of real-world graphs, e.g. the small-world property. Our scalable implementation offers excellent performance on diverse, small-world graphs resulting in a 5.01x to 29.41x parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads.

Chair/Author Details:

Karen Devine (Chair) - Sandia National Laboratories

Sungpack Hong - Oracle Corporation

Nicole C. Rodia - Stanford University

Kunle Olukotun - Stanford University

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library