SC|05 SC|05 Gateway to Discovery
About Interactive Schedule Programs Registration Exhibits Initiatives & Challenges News & Press Hotel & Travel

You currently have 0 events on your schedule.

Schedule: November 12-18th 2005
Entire WeekSaturdaySundayMondayTuesdayWednesdayThursdayFriday

A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L

Session: System Performance Evaluation

Event Type: Paper, Gordon Bell Finalist

Time: 10:30am - 11:00am

Session Chair: Jeffrey Vetter

Speaker(s): Andy Yoo, Edmond Chow, Keith Henderson, William McLendon, Bruce Hendrickson, Umit Catalyurek

Location: 602-604


Many emerging large-scale data science applications require searching large graphs distributed across multiple memories and processors. This paper presents a distributed breadth-first search (BFS) scheme that scales for random graphs with up to three billion vertices and 30 billion edges. Scalability was tested on IBM BlueGene/L with 32,768 nodes at the Lawrence Livermore National Laboratory. Scalability was obtained through a series of optimizations, in particular, those that ensure scalable use of memory. We use 2D (edge) partitioning of the graph instead of conventional 1D (vertex) partitioning to reduce communication overhead. For Poisson random graphs, we show that the expected size of the messages is scalable for both 2D and 1D partitionings. Finally, we have developed efficient collective communication functions for the 3D torus architecture of BlueGene/L that also take advantage of the structure in the problem. The performance and characteristics of the algorithm are measured and reported.

This paper can be found in the ACM and IEEE Digital Libaries
Click here for ACM
Click here for IEEE

Chair/Speaker Details:

Jeffrey Vetter (Chair)
Oak Ridge National Lab

Andy Yoo
Lawrence Livermore National Laboratory

Edmond Chow
DE Shaw Research and Development

Keith Henderson
Lawrence Livermore National Laboratory

William McLendon
Sandia National Laboratories

Bruce Hendrickson
Sandia National Laboratories

Umit Catalyurek
Ohio State University