News Archives

[Colloquium] Massive Multithreading for Unstructured Graph Problems

October 20, 2006

Watch Colloquium: 

Note: Approximately 15 minutes at the beginning of this colloquia were lost due to an issue with the recording media. Additionally, there is a short amount of time at the end of the question and answer session not recorded.

Quicktime version (116 Meg)|
AVI version (345 Meg)


  • Date: Friday, October 20, 2006 
  • Time: 1 pm — 2:15 pm 
  • Place: ME 218

Jon Berry
Sandia National Lab

Abstract Traditional distributed memory clusters are effective platforms for problems such as meshing, in which physical locality implies that an appropriate partitioning of the work is possible. However, in applications such as social network analysis, there may be no effective partitioning. Clusters also struggle with computations that get broken down into subproblems via divide-and-conquer or branch-and-bound algorithms, such that the subproblems themselves can be too large to store in local memory. The architectural paradigm of massive multithreading is an appealing alternative for large discrete problems without locality.

Sandia National Laboratories has been exploring massive multithreading as a solution technology for such problems. We will present an overview of this work in three parts: an introduction to the Cray MTA-2, the most mature existing instance of this paradigm, an introduction to the programming model for the MTA-2, and an introduction to algorithm design for massively multithreaded computers.

More specifically, we will present our work on the “MultiThreaded Graph Library (MTGL)” for graph query, and two multithreaded graph algorithms: a simple algorithm for connected components and a simple heuristic for subgraph isomorphism. These algorithms scale almost perfectly on the MTA-2 for randomized power-law graph instances. We will conclude with a discussion of future work in multithreaded algorithms and of the next-generation massively multithreaded computers under development.

Bio Jon Berry got his PhD in computer science from Rensselaer Polytechnic Institute, did a postdoc at DIMACS, the Center for Theoretical Computer Science and Discrete Mathematics based at Rutgers University, then spent 8 years teaching computer science at Elon University in North Carolina and Lafayette College in Easton, PA. In 2004 he moved to Sandia National Laboratories, where he is a now a member of the technical staff. This talk concerns one of his current research interests: to explore the intersection between graph algorithms and high-performance computing architectures.