SCHEDULE: NOV 10-16, 2012
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.
Breaking the Speed and Scalability Barriers for Graph Exploration on Distributed-Memory Machines
SESSION: Breadth First Search
EVENT TYPE: Papers
TIME: 11:00AM - 11:30AM
SESSION CHAIR: Umit Catalyurek
AUTHOR(S):Fabio Checconi, Fabrizio Petrini, Jeremiah Willcock, Andrew Lumsdaine, Yogish Sabharwal, Anamitra Choudhury
In this paper, we describe the challenges involved in designing a family of highly-efficient Breadth-First Search (BFS) algorithms and in optimizing these algorithms on the latest two generations of Blue Gene machines, Blue Gene/P and Blue Gene/Q. With our recent winning Graph 500 submissions in November 2010, June 2011, and November 2011, we have achieved unprecedented scalability results in both space and size. On Blue Gene/P, we have been able to parallelize the largest BFS search presented in the literature, running a scale 38 problem with 238 vertices and 242 edges on 131,072 processing cores. Using only four racks of an experimental configuration of Blue Gene/Q, we have achieved the fastest processing rate reported to date on a BFS search, 254 billion edges per second on 65,536 processing cores. This paper describes the algorithmic design and the main classes of optimizations that we have used to achieve these results.
Umit Catalyurek (Chair) - Ohio State University
Fabio Checconi - IBM T.J. Watson Research Center
Fabrizio Petrini - IBM T.J. Watson Research Center
Jeremiah Willcock - Indiana University
Andrew Lumsdaine - Indiana University
Yogish Sabharwal - IBM India
Anamitra Choudhury - IBM India