Douglas Gregor
ABSTRACT
This paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed with parallelism in mind. In this paper, we revisit the abstractions comprising the BGL in the context of distributed-memory parallelism, lifting away the implicit requirements of sequential execution and a single shared address space. We illustrate our approach by describing the process as applied to one of the core algorithms in the BGL, breadth-first search. The result is a generic algorithm that is unchanged from the sequential algorithm, requiring only the introduction of external (distributed) data structures for parallel execution. More importantly, the generic implementation retains its interface and semantics, such that other distributed algorithms can be built upon it, just as algorithms are layered in the sequential case. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic, object-oriented parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms.
- P. An, A. Jula, S. Rus, S. Saunders, T. Smith, G. Tanase, N. Thomas, N. Amato, and L. Rauchwerger. STAPL: A standard template adaptive parallel C++ library. In Int. Wkshp on Adv. Compiler Technology for High Perf. and Embedded Processors, page 10, July 2001.]]Google Scholar
- Guy E. Blelloch. NESL: A nested data-parallel language. Technical Report CMU-CS-93-129, April 1993.]] Google ScholarDigital Library
- Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw H. Gebremedhin, and Fredrik Manne. A scalable parallel graph coloring algorithm for distributed memory computers. Preprint.]]Google Scholar
- Boost. Boost C++ Libraries. http://www.boost.org/.]]Google Scholar
- Peter N. Brown and Alan C. Hindmarsh. Matrix-free methods for stiff systems of ODE's. SIAM J. Numer. Anal., 23(3):610--638, June 1986.]] Google ScholarDigital Library
- Bradford L. Chamberlain, Sung-Eun Choi, E. Christopher Lewis, Calvin Lin, Lawrence Snyder, and Derrick Weathersby. ZPL: A machine independent programming language for parallel computers. Software Engineering, 26(3):197--211, 2000.]] Google ScholarDigital Library
- Albert Chan and Frank Dehne. CGMgraph/CGMlib: Implementing and testing CGM graph algorithms on PC clusters. In PVM/MPI, pages 117--125, 2003.]]Google Scholar
- Albert Chan and Frank Dehne. cgmLIB: A library for coarse-grained parallel computing. http://lib.cgmlab.org/, 2004 December.]]Google Scholar
- Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A parallelization of dijkstra's shortest path algorithm. In Lubos Brim, Jozef Gruska, and Jirí Zlatuska, editors, Mathematical Foundations of Computer Science (MFCS), volume 1450 of Lecture Notes in Computer Science, pages 722--731. Springer, 1998.]] Google ScholarDigital Library
- Frank Dehne, Andreas Fabri, and Andrew Rau-Chaplin. Scalable parallel geometric algorithms for coarse grained multicomputers. In Proceedings of the ninth annual symposium on Computational geometry, pages 298--307. ACM Press, 1993.]] Google ScholarDigital Library
- Frank Dehne and Silvia Götz. Practical parallel algorithms for minimum spanning trees. In Symposium on Reliable Distributed Systems, pages 366--371, 1998.]] Google ScholarDigital Library
- Al Geist, Adam Beguelin, Jack Dongarra, Weicheng Jiang, Robert Manchek, and Vaidyalingam S. Sunderam. PVM: A Parallel Virtual Machine. Scientific and Engineering Computation Series. MIT Press, 1994.]]Google ScholarCross Ref
- Steve Goddard, Subodh Kumar, and Jan F. Prins. Connected components algorithms for mesh connected parallel computers. In Sandeep N. Bhatt, editor, Parallel Algorithms, volume 30 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 43--58. American Mathematical Society, 1997.]]Google Scholar
- Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar. Introduction to Parallel Computing, Second Edition. Addison-Wesley, 2003.]]Google Scholar
- W. D. Gropp and B. Smith. PETSc: Portable extensible tools for scientific computation. Technical report, Argonne National Laboratory, Argonne, IL, 1994.]]Google Scholar
- Florian Hielscher and Peter Gottschling. ParGraph. http://pargraph.sourceforge.net/, 2004.]]Google Scholar
- J.-M. Jézéquel. EPEE: an Eiffel environment to program distributed memory parallel computers. Journal of Object Oriented Programming, 1993.]]Google Scholar
- J.-M. Jézéquel. Transparent parallelisation through reuse: Between a compiler and a library approach. In O. M. Nierstrasz, editor, ECOOP'93 proceedings, number 707 in Lecture Notes in Computer Science, pages 384--405. Springer Verlag, July 1993.]] Google ScholarDigital Library
- Donald B. Johnson and Panagiotis Takis Metaxas. A parallel algorithm for computing minimum spanning trees. In ACM Symposium on Parallel Algorithms and Architectures, pages 363--372, 1992.]] Google ScholarDigital Library
- Elizabeth Johnson and Dennis Gannon. HPC++: Experiments with the Parallel Standard Template Library. In International Conference on Supercomputing, pages 124--131, 1997.]] Google ScholarDigital Library
- Lie-Quan Lee, Lixin Ge, Marc Kowalski, Zenghai Li, Cho-Kuen Ng, Greg Schussman, Michael Wolf, and Kwok Ko. Solving large sparse linear systems in end-to-end accelerator structure simulations. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04), 2004.]]Google ScholarCross Ref
- Lie-Quan Lee and Andrew Lumsdaine. Generic programming for high performance scientific applications. In Proceedings of the 2002 Joint ACM Java Grande -- ISCOPE Conference, pages 112--121. ACM Press, 2002.]] Google ScholarDigital Library
- Lie-Quan Lee, Jeremy Siek, and Andrew Lumsdaine. The Generic Graph Component Library. In Proceedings of OOPSLA'99, 1999.]] Google ScholarDigital Library
- Calvin Lin and Lawrence Snyder. ZPL: An array sublanguage. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and Compilers for Parallel Computing, pages 96--114, 1993. ftp://ftp.cs.washington.edu/pub/orca/papers/lcpc93.ps.]] Google ScholarDigital Library
- Message Passing Interface Forum. MPI: A Message Passing Interface. In Proc. of Supercomputing '93, pages 878--883. IEEE Computer Society Press, November 1993.]] Google ScholarDigital Library
- Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel single source shortest path algorithm. In ESA '98: Proceedings of the 6th Annual European Symposium on Algorithms, pages 393--404. Springer-Verlag, 1998.]] Google ScholarDigital Library
- David R. Musser and Alexander A. Stepanov. Generic programming. In P. (Patrizia) Gianni, editor, Symbolic and algebraic computation: ISSAC '88, Rome, Italy, July 4--8, 1988: Proceedings, volume 358 of Lecture Notes in Computer Science, pages 13--25, Berlin, 1989. Springer Verlag.]] Google ScholarDigital Library
- Thomas Nitsche. Lifting sequential functions to parallel skeletons. Parallel Processing Letters, 12(2):267--284, June 2002.]]Google ScholarCross Ref
- Christopher R. Palmer and J. Gregory Steffan. Generating network topologies that obey power laws. In Proceedings of GLOBECOM '2000, November 2000.]]Google ScholarCross Ref
- Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2002.]] Google ScholarDigital Library
- Jeremy Siek and Andrew Lumsdaine. The Matrix Template Library: A generic programming approach to high performance numerical linear algebra. In International Symposium on Computing in Object-Oriented Parallel Environments, 1998.]] Google ScholarDigital Library
- Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. Generic programming for high performance numerical linear algebra. In Proceedings of the SIAM Workshop on Object Oriented Methods for Inter-operable Scientific and Engineering Computing (OO'98). SIAM Press, 1998.]]Google Scholar
- Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. Boost Graph Library. Boost, 2001. http://www.boost.org/libs/graph/doc/index.html.]]Google Scholar
- Alexander A. Stepanov and Meng Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, ISO Programming Language C++ Project, May 1994.]]Google Scholar
- Y. H. Tsin. Some remarks on distributed depth-first search. Information Processing Letters, 82(4):173--178, 2002.]] Google ScholarDigital Library
- Leslie G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103--111, 1990.]] Google ScholarDigital Library
Index Terms
- Lifting sequential graph algorithms for distributed-memory parallel computation
Recommendations
Lifting sequential graph algorithms for distributed-memory parallel computation
Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applicationsThis paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed ...
Implementation of parallel graph algorithms on a massively parallel SIMD computer with virtual processing
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingWe describe our implementation, with virtual processing, of several parallel graph algorithms on a 16,384-processor MasPar MP-1. We present extensive test data on our code.
Portable and Efficient Parallel Computing Using the BSP Model
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software ...
Comments