BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20131119T180000Z
DTEND:20131119T183000Z
LOCATION:401/402/403
DESCRIPTION;ENCODING=QUOTED-PRINTABLE: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=0Aseveral 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.
SUMMARY:Scalable Matrix Computations on Large Scale-Free Graphs Using 2D Graph Partitioning
PRIORITY:3
END:VEVENT
END:VCALENDAR