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

SCHEDULE: NOV 13-19, 2010

Scalable Graph Exploration on Multicore Processors

SESSION: Graph Algorithms


TIME: 11:30AM - 12:00PM


AUTHOR(S):Fabrizio Petrini, Virat Agarwal, Davide Pasetto, David Bader


Many important problems in computational sciences, social network analysis, security, and business analytics, are data-intensive and lend themselves to graph-theoretical analyses. In this paper we investigate the challenges involved in exploring very large graphs by designing a breadth-first search (BFS) algorithm for advanced multi-core processors that are likely to become the building blocks of future exascale systems. Our new methodology for large-scale graph analytics combines a high-level algorithmic design that captures the machine-independent aspects, to guarantee portability with performance to future processors, with an implementation that embeds processor-specific optimizations. We present an experimental study that uses state-of-the-art Intel Nehalem EP and EX processors and up to 64 threads in a single system. Our performance on several benchmark problems representative of the power-law graphs found in real-world problems reaches processing rates that are competitive with supercomputing results in the recent literature.

Chair/Author Details:

George Biros (Chair) - Georgia Institute of Technology

Fabrizio Petrini - IBM T.J. Watson Research Center

Virat Agarwal - IBM T.J. Watson Research Center

Davide Pasetto - IBM Ireland

David Bader - Georgia Institute of Technology

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