Synthesis of Parallel Algorithms

This landmark collaboration will enhance the knowledge and abilities of anyone interested in parallel algorithms and in developing programs for parallel computers. Many problems currently solved with sequential algorithms are themselves highly parallelizable when designers use the powerful parallel techniques now available. These thorough but introductory presentations demonstrate the most important algorithmic techniques and their use in exposing the hidden parallelism within problems. Beginning with familiar sequential algorithms, the authors provide a careful description of the fundamental problem, its solution, and analysis--complete with examples and exercises. Each of the 22 chapters then synthesizes a more sophisticated parallel algorithm using the simpler sequential and parallel techniques used to introduce the problem. The PRAM shared-memory model of computing provides a unifying framework. This model has been used extensively for designing parallel algorithms and can be efficiently simulated on many of the parallel architectures now in use. Applying the methods in this book will offer designers a substantial advantage when solving problems for parallel computation.

Table of Contents:
Introduction John H. Reif Part I Fundamental Parallel Graph Algorithms 1. Prefix Sums and Their Applications Guy Blelloch 2. List Ranking and Parallel Tree Contraction Margaret Reid-Miller, Gary Miller, Francesmary Modugno 3. Introduction to Parallel Connectivity, List Ranking, and Euler Tour Techniques Sara Baase Part II Advanced Parallel Graph Algorithms 4. Advanced Parallel Prefix-sums, List Ranking and Connectivity Uzi Vishkin 5. Randomized Parallel Connectivity Hillel Gazit 6. Parallel Lowest Common Ancestor Computation Baruch Schieber 7. Parallel Open Ear Decomposition with Applications to Graph Biconnectivity and Triconnectivity Vijaya Ramachandran 8. Parallel Graph Matching Vijay Vazirani Part III Parallel Sorting and Computational Geometry 9. Parallel Algorithms for Chordal Graphs Philip Klein 10. Dynamic Parallel Evaluation of Computation DAGs Erich Kaltofen 11. Parallel Evaluation of Logic Queries Jeffrey Ullman Part IV Fundamental Parallel Algebraic Algorithms 12. Parallel Merge Sort Richard Cole 13. Deterministic Parallel Computational Geometry Mikhail Atallah and Michael Goodrich Part V Advanced Parallel Algebraic Algorithms 14. Random Sampling Techniques and Parallel Algorithms Design Sanguthevar Rajasekaran and Sandeep Sen 15. Parallel Solution of Sparse Linear and Path Systems Victor Pan Part VI Extensions of Parallel Tree Contraction to Algebraic and Logical Problems 16. Parallel Algorithms for Network Flow Problems Andrew Goldberg 17. Newton Iteration and Integer Design Stephen Tate Part VII Parallel Combinatorial Optimization 18. Parallel Linear Algebra Joachim von zur Gathen 19. Parallel Resultant Computation Doug Ierardi and Dexter Kozen Part VIII Inherent Limitations of Parallel Computations 20. Polynomial Completeness and Parallel Computation Raymond Greenlaw 21. The Complexity of Computation on the Parallel Random Access Machine Faith Fich Part IX Asynchronous Parallel Computation 22. Asynchronous PRAM Algorithms Phillip Gibbons