SC is the International Conference for
 High Performnance Computing, Networking, Storage and Analysis

SCHEDULE: NOV 13-19, 2010

Fast PGAS Implementation of Distributed Graph Algorithms

SESSION: Graph Algorithms

EVENT TYPE: Paper

TIME: 10:30AM - 11:00AM

SESSION CHAIR: George Biros

AUTHOR(S):Guojing Cong, George Almasi, Vijay Saraswat

ROOM:393

ABSTRACT:
Due to the memory intensive workload and the erratic access pattern, irregular graph algorithms are notoriously hard to implement and optimize for high performance on distributed-memory systems. Although the PGAS paradigm proposed recently improves ease of programming, no high performance PGAS implementation of large-scale graph analysis is known. We present the first fast PGAS implementation of graph algorithms for the connected components and minimum spanning tree problems. By improving memory access locality, compared with the naive implementation, our implementation exhibits much better communication efficiency and cache performance on a cluster of SMPs. With additional algorithmic and PGAS-specific optimizations, our implementation achieves significant speedups over both the best sequential implementation and the best single-node SMP implementation for large, sparse graphs with more than a billion edges.

Chair/Author Details:

George Biros (Chair) - Georgia Institute of Technology

Guojing Cong - IBM Research

George Almasi - IBM Research

Vijay Saraswat - IBM Research

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 and IEEE Computer Society

   Sponsors    IEEE    ACM