The Parallel BGL project began in June 2004. The first prototype algorithms were breadth-first search and Dijkstra's algorithm, both of which were implemented using a new set of distributed data structures. These data structures mimic the interfaces of their sequential counterparts in the Boost Graph Library well enough that the existing sequential implementations of these algorithms could be reused as distributed algorithms. Other algorithms followed, and as of February 2005 the Parallel BGL contains several of the core graph theoretic algorithms for distributed graphs. In January 2005 we initiated work on shared-memory, thread-based parallelism in the Parallel BGL, focusing again on core algorithms and retaining the highest level of compatibility with the Boost Graph Library as is possible for a parallel library.
The Parallel BGL is intended both as a research project, to determine how best to develop generic, parallel libraries, and as a platform for applying graph algorithms to interesting problems in other areas. Its primary goals are:
- Provide a flexible, efficient library of parallel and distributed graph algorithms and data structures.
Support different models of parallelism, such as shared-memory, distributed memory, and non-uniform memory access, for various parallel APIs (such as MPI or POSIX threads).
Allow sequential programs using the BGL to be transformed into parallel programs without a great deal of effort and provide guidance.
Understand how generic programming interacts with parallel programming.
- Build a comprehensive concept taxonomy for parallel processing.
- Set the stage for additional parallel generic libraries.
- Understand how to relate sequential and parallel versions of the same algorithm and how to parallelize generic sequential algorithms.
The Parallel BGL is currently undergoing a major rewrite. You can continue to find Parallel BGL "classic" in the Boost releases. Parallel BGL "2.0" as we're currently referring to it is no longer interface compatible with sequential BGL or Parallel BGL classic. We have restructured the algorithms into stateful objects suitable for fine-grained parallelization via threads and possibly (eventually) accelerators of various types. We have also replaced the process group abstraction with an active message library of our own design: AM++. More info about AM++ is available in our publications.