|
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.
|
