SC13 Home > SC13 Schedule > SC13 Presentation - Scalable Parallel Graph Partitioning

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.

Scalable Parallel Graph Partitioning

SESSION: Graph Partitioning and Data Clustering

EVENT TYPE: Papers, Awards, Best Student Paper Finalists

TIME: 11:30AM - 12:00PM

SESSION CHAIR: Chung-Hsing Hsu

AUTHOR(S):Shad Kirmani, Padma Raghavan


We consider partitioning a graph in parallel using a large number of processors. Parallel multilevel partitioners, such as Pt-Scotch and ParMetis, produce good quality partitions but their performance scales poorly. Coordinate bisection schemes such as those in Zoltan, which can be applied only to graphs with coordinates, scale well but partition quality is often compromised. We seek to address this gap by developing a scalable parallel scheme which imparts coordinates to a graph through a lattice-based multilevel embedding. Partitions are computed with a parallel formulation of a geometric scheme that has been shown to provide provably good cuts on certain classes of graphs. We analyze the parallel complexity of our scheme and we observe speed-ups and cut-sizes on large graphs. Our results indicate that our method is substantially faster than ParMetis and Pt-Scotch for hundreds to thousands of processors, while producing high quality cuts.

Chair/Author Details:

Chung-Hsing Hsu (Chair) - Oak Ridge National Laboratory

Shad Kirmani - Pennsylvania State University

Padma Raghavan - Pennsylvania State University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library