Colloquium Details
The Parallel BGL: A High-Performance Parallel Graph Algorithms Library
| Author: | Andrew Lumsdaine Indiana University |
|---|---|
| Date: | January 10, 2013 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
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.
Biography
Andrew Lumsdaine is a Professor of Computer Science in the School of Informatics & Computing at Indiana University and Director of the Center for Research in Extreme Scale Technologies (CREST) at the Pervasive Technology Institute. Lumsdaine received his Ph.D. from MIT in 1992. Prior to coming to IU, he was a faculty member in the Department of Computer Science and Engineering at the University of Notre Dame. His research interests include high-performance computing, programming languages, parallel and distributed computing, and computational photography. He is a member of ACM, IEEE, and SIAM, as well as the MPI Forum, and the ISO C++ standards committee.