The Design and Analysis of Parallel Algorithms

This text for students and professionals in computer science provides a valuable overview of current knowledge concerning parallel algorithms. These computer operations have recently acquired increased importance due to their ability to enhance the power of computers by permitting multiple processors to work on different parts of a problem independently and simultaneously. This approach has led to solutions of difficult problems in a number of vital fields, including artificial intelligence, image processing, and differential equations. As the first up-to-date summary of the topic, this book will be sought after by researchers, computer science professionals, and advanced students involved in parallel computing and parallel algorithms. I. Basic Concepts -- 1. Introduction -- Ii. Models Of Parallel Computation. 1. Generalities. 2. The Pram Model And A Sorting Algorithm. 3. Bitonic Sorting Algorithm. 4. Appendix: Proof Of The 0-1 Principal. 5. Relations Between Pram Models. 6. Theoretical Issues. 6.1. Complexity Classes And The Parallel Processing Thesis. 6.2. P-completeness And Inherently Sequential Problems. 6.3. Further Reading. 7. General Principles Of Parallel Algorithm Design. 7.1. Brent's Theorem. 7.2. Simd Algorithms. 7.2.1. Doubling Algorithms. 7.2.2. The Brent Scheduling Principle. 7.2.3. Pipelining. 7.2.4. Divide And Conquer. 7.3. Mimd Algorithms. 7.3.1. Generalities. 7.3.2. Race-conditions. 7.3.3. Optimization Of Loops. 7.3.4. Deadlocks. 7.4. Comparison Of The Simd And Mimd Models Of Computation -- Iii. Distributed-memory Models. 1. Introduction. 2. Generic Parallel Algorithms. 3. The Butterfly Network. 3.1. Discussion And Further Reading. 4. The Hypercube Architecture. 4.1. Description. 5. The Shuffle-exchange Network. 5.1. Discussion And Further Reading. 6. Cube-connected Cycles. 7. Dataflow Computers. 8. The Granularity Problem -- Iv. Examples Of Existing Parallel Computers. 1. Asynchronous Parallel Programming. 1.1. Portable Programming Packages. 2. Simd Programming: The Connection Machine. 2.1. Generalities. 2.2. Algorithm-design Considerations. 2.3. The C* Programming Language. 2.3.1. Running A C* Program. 2.4. Semantics Of C*. 2.4.1. Shapes And Parallel Allocation Of Data. 2.4.2. Action Of The With-statement. 2.4.3. Action Of The Where-statement. 2.4.4. Parallel Types And Procedures. 2.4.5. Special Parallel Operators. 2.4.6. Sample Programs. 2.4.7. Pointers. 2.4.8. Subtleties Of Communication. 2.4.9. Collisions. 2.5. A Critique Of C*. 3. Programming A Mimd-simd Hybrid Computer: Modula*. 3.1. Introduction. 3.2. Data Declaration. 3.2.1. Elementary Data Types. 3.2.2. Parallel Data Types. 3.3. The Forall Statement. 3.3.1. The Asynchronous Case. 3.3.2. The Synchronous Case. 3.4. Sample Programs. 3.5. A Critique Of Modula* -- V. Numerical Algorithms. 1. Linear Algebra. 1.1. Matrix-multiplication. 1.2. Systems Of Linear Equations. 1.2.1. Generalities On Vectors And Matrices. 1.2.2. The Jacobi Method. 1.2.3. The Jor Method. 1.2.4. The Sor And Consistently Ordered Methods. 1.2.5. Discussion. 1.3. Power-series Methods: The Pan-reif Algorithm. 1.3.1. Introduction. 1.3.2. The Main Algorithm. 1.3.3. Proof Of The Main Result. 1.4. Nonlinear Problems. 1.5. A Parallel Algorithm For Computing Determinants. 1.6. Further Reading. 4. Searching And Sorting. 4.1. Parallel Searching. 4.2. Sorting Algorithms For A Pram Computer. 4.2.1. The Cole Sorting Algorithm -- Crew Version. 4.2.2. Example. 4.2.3. The Cole Sorting Algorithm -- Erew Version. 4.3. The Ajtai, Komlos, Szemeredi Sorting Network. 4.4. Detailed Proof Of The Correctness Of The Algorithm. 4.5. Expander Graphs. 5. Computer Algebra. 5.1. Introduction. 5.2. Number-theoretic Considerations -- Vii. Probabilistic Algorithms. 1. Introduction And Basic Definitions. 1.1. Numerical Algorithms. 1.1.1. Monte Carlo Integration. 1.2. Monte Carlo Algorithms. 1.3. Las Vegas Algorithms. 2. The Class Rnc. 2.1. Work-efficient Parallel Prefix Computation. 2.2. The Valiant And Brebner Sorting Algorithm. 2.3. Maximal Matchings In Graphs. 2.3.1. A Partitioning Lemma. 2.3.2. Perfect Matchings. 2.3.3. The General Case. 2.4. The Maximal Independent-set Problem. 2.4.1. Definition And Statement Of Results. 2.4.2. Proof Of The Main Results. 3. Further Reading. Justin R. Smith. Includes Bibliographical References (p. 495-501) And Index. Parallel algorithms - computer operations designed to be performed independently - make parallel processing possible. This study provides an overview of their current potential.