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 Matrix Computations on Large Scale-Free Graphs Using 2D Graph Partitioning

SESSION: Graph Partitioning and Data Clustering

EVENT TYPE: Papers

TIME: 11:00AM - 11:30AM

SESSION CHAIR: Chung-Hsing Hsu

AUTHOR(S):Erik G. Boman, Karen D. Devine, Sivasankaran Rajamanickam

ROOM:401/402/403

ABSTRACT:
Scalable parallel computing is essential for processing large scale-free (power-law) graphs. The data distribution becomes important on distributed-memory computers with thousands of cores. Recently, it has been shown that 2D layouts (edge partitions) have significant advantages over traditional 1D layouts. However, the simple 2D block distribution does not use the structure of the graph, and more advanced 2D partitioning methods are too expensive for large graphs. We propose a new partitioning algorithm that combines graph partitioning with the 2D block distribution. The cost is essentially the same as 1D graph partitioning. We study the performance of sparse matrix-vector multiplication for large scale-free graphs from, e.g., social networks using several partitioners and data layouts, both 1D and 2D. We demonstrate that our new 2D method consistently outperforms the other methods considered, both for SpMV and an eigensolver, on matrices up to 1.6 billion non-zeros and up to 16,384 cores.

Chair/Author Details:

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

Erik G. Boman - Sandia National Laboratories

Karen D. Devine - Sandia National Laboratories

Sivasankaran Rajamanickam - Sandia National Laboratories

  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