News Archives

[Colloquium] The Parallel BGL: A High-Performance Parallel Graph Algorithms Library

February 24, 2011

Watch Colloquium: 


  • Date: Thursday, February 24, 2011 
  • Time: 11:00 am — 11:50 am 
  • Place: Mechanical Engineering 218

Andrew Lumsdaine
Professor of Computer Science
Computer Science Department, Indiana University

Graphs and graph algorithms have long been a fundamental abstraction in computer science and many types of data-driven applications – the emerging “fourth pillar” of science – depend on graph computations. The resource requirements for graph computations can be quite large, however, running graph algorithms on today’s HPC systems presents a number of challenges – the paradigms, software, and hardware that have worked well for mainstream scientific applications are not well matched to large-scale graph problems.

In this talk we present the design and implementation of the Parallel Boost Graph Library, a library of reusable high-performance software components for large-scale graph computation. Like the sequential Boost Graph Library (BGL) upon which it is based, the Parallel BGL applies the paradigm of generic programming to the domain of graph computations. To illustrate how the Parallel BGL was built from the sequential BGL, we revisit the abstractions comprising the BGL and lift away the implicit requirements of sequential execution and a single shared address space. This process allows us to create generic algorithms having sequential expression and requiring only the introduction of parallel data structures for parallel execution. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms implemented in the open-source Parallel Boost Graph Library. We conclude by discussing on-going and future work, most notably the new active-message system being incorporated into PBGL to enable efficient execution on multi-core, hybrid, and exascale architectures.

Bio: Andrew Lumsdaine obtained his Ph.D. in Electrical Engineering and Computer Science at Massachusetts Institute of Technology in 1992. His research interests include: * Compilers * Computational Photography * Computational Science and Engineering * Computer Networks * Cyberinfrastructure and e-Science * Generic Programming * High Performance Computing * Mathematical Software * Numerical Analysis * Parallel and Distributed Computing * Programming Languages * Software Engineering * Software and Systems * Visualization, Computer Vision, and Graphics.