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
ROOM:401/402/403
ABSTRACT:
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
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