Newsgroups: comp.parallel From: jsmith%king.mcs.drexel.edu%gatech@uunet.UU.NET (Justin Smith) Subject: The Design and Analysis of Parallel Algorithms Book Organization: Drexel University Date: Sun, 29 May 1994 17:19:12 GMT Here's a description of a book that covers SIMD computers in a fair amount of detail: (Most of the algorithms from chapter V on are SIMD algorithms). Title: The Design and Analysis of Parallel Algorithms Author: Justin R. Smith Publisher: Oxford University Press ISBN: 0-19-507881-0 Table of Contents: Chapter I Basic Concepts 1 Introduction 1 Chapter II Models of parallel computation 13 1 Generalities 13 2 The PRAM model and a sorting algorithm 18 3 Bitonic Sorting Algorithm 20 4 Appendix: Proof of the 0-1 Principal 25 5 Relations between PRAM models 27 6 Theoretical Issues 31 6.1 Complexity Classes and the Parallel Processing Thesis 31 6.2 P-Completeness and Inherently Sequential Problems 40 6.3 Further reading 45 7 General Principles of Parallel Algorithm Design 45 7.1 Brent's Theorem 45 7.2 SIMD Algorithms 48 7.2.1 Doubling Algorithms 48 7.2.2 The Brent Scheduling Principle 49 7.2.3 Pipelining 50 7.2.4 Divide and Conquer 50 7.3 MIMD Algorithms 50 7.3.1 Generalities 50 7.3.2 Race-conditions 52 7.3.3 Optimization of loops 57 7.3.4 Deadlocks 58 7.4 Comparison of the SIMD and MIMD models of computation 59 Chapter III Distributed-Memory Models 63 1 Introduction 63 2 Generic Parallel Algorithms 63 3 The Butterfly Network 68 3.1 Discussion and further reading 74 4 The Hypercube Architecture 74 4.1 Description 74 5 The Shuffle-Exchange Network 79 5.1 Discussion and further reading 84 6 Cube-Connected Cycles 85 7 Dataflow Computers 93 8 The Granularity Problem 94 Chapter IV Examples of Existing Parallel Computers 105 1 Asynchronous Parallel Programming 105 1.1 Portable programming packages 105 2 SIMD Programming: the Connection Machine 110 2.1 Generalities 110 2.2 Algorithm-Design Considerations 113 2.3 The C* Programming Language 113 2.3.1 Running a C* program 120 2.4 Semantics of C* 120 2.4.1 Shapes and parallel allocation of data 120 2.4.2 Action of the with-statement 121 2.4.3 Action of the where-statement 123 2.4.4 Parallel Types and Procedures 127 2.4.5 Special Parallel Operators 129 2.4.6 Sample programs 130 2.4.7 Pointers 134 2.4.8 Subtleties of Communication 135 2.4.9 Collisions 137 2.5 A Critique of C* 141 3 Programming a MIMD-SIMD Hybrid Computer: Modula* 143 3.1 Introduction 143 3.2 Data declaration 143 3.2.1 Elementary data types 143 3.2.2 Parallel data types 144 3.3 The FORALL Statement 145 3.3.1 The asynchronous case 146 3.3.2 The synchronous case 146 3.4 Sample Programs 150 3.5 A Critique of Modula* 150 Chapter V Numerical Algorithms 153 1 Linear algebra 153 1.1 Matrix-multiplication 153 1.2 Systems of linear equations 154 1.2.1 Generalities on vectors and matrices 154 1.2.2 The Jacobi Method 163 1.2.3 The JOR method 167 1.2.4 The SOR and Consistently Ordered Methods 169 1.2.5 Discussion 176 1.3 Power-series methods: the Pan-Reif Algorithm 178 1.3.1 Introduction 178 1.3.2 The main algorithm 181 1.3.3 Proof of the main result 184 1.4 Nonlinear Problems 187 1.5 A Parallel Algorithm for Computing Determinants 189 1.6 Further reading 192 2 The Discrete Fourier Transform 194 2.1 Background 194 2.2 Definition and basic properties 197 2.3 The Fast Fourier Transform Algorithm 201 2.4 Eigenvalues of cyclic matrices 214 3 Wavelets 218 3.1 Background 218 3.2 Discrete Wavelet Transforms 225 3.3 Discussion and Further reading 238 4 Numerical Evaluation of Definite Integrals 241 4.1 The one-dimensional case 241 4.2 Higher-dimensional integrals 247 4.3 Discussion and Further reading 249 5 Partial Differential Equations 252 5.1 Elliptic Differential Equations 253 5.1.1 Basic concepts 253 5.1.2 Self-adjoint equations 268 5.1.3 Rate of convergence 271 5.2 Parabolic Differential Equations 278 5.2.1 Basic Methods 278 5.2.2 Error Analysis 283 5.2.3 Implicit Methods 286 5.2.4 Error Analysis 289 5.3 Hyperbolic Differential Equations 292 5.3.1 Background 293 5.3.2 Finite differences 294 5.4 Further reading 299 Chapter VI A Survey of Symbolic Algorithms 301 1 Doubling Algorithms 301 1.1 General Principles 301 1.2 Recurrence Relations 304 1.3 Deterministic Finite Automata 306 2 Graph Algorithms 309 2.1 The Euler Tour Algorithm 309 2.2 Parallel Tree Contractions 316 2.3 Shortest Paths 318 2.4 Connected Components 321 2.4.1 Algorithm for a CREW Computer 321 2.4.2 Algorithm for a CRCW computer 329 2.5 Spanning Trees and Forests 334 2.5.1 An algorithm for an inverted spanning forest 340 2.6 Minimal Spanning Trees and Forests 346 2.7 Cycles in a Graph 359 2.7.1 Definitions 359 2.7.2 A simple algorithm for a cycle basis 360 2.7.3 Lowest Common Ancestors 361 2.8 Further Reading 363 3 Parsing and the Evaluation of arithmetic expressions 365 3.1 Introduction 365 3.2 An algorithm for building syntax-trees 366 3.3 An algorithm for evaluating a syntax tree 369 3.4 Discussion and Further Reading 377 3.5 Appendix: Parenthesis-matching algorithm 379 4 Searching and Sorting 379 4.1 Parallel searching 380 4.2 Sorting Algorithms for a PRAM computer 380 4.2.1 The Cole Sorting Algorithm --- CREW version 381 4.2.2 Example 388 4.2.3 The Cole Sorting Algorithm --- EREW version 390 4.3 The Ajtai, Komlos, Szemeredi Sorting Network 398 4.4 Detailed proof of the correctness of the algorithm 410 4.5 Expander Graphs 413 5 Computer Algebra 417 5.1 Introduction 417 5.2 Number-Theoretic Considerations 418 Chapter VII Probabilistic Algorithms 437 1 Introduction and basic definitions 437 1.1 Numerical algorithms 437 1.1.1 Monte Carlo Integration 438 1.2 Monte Carlo algorithms 439 1.3 Las Vegas algorithms 441 2 The class RNC 442 2.1 Work-efficient parallel prefix computation 443 2.2 The Valiant and Brebner Sorting Algorithm 446 2.3 Maximal Matchings in Graphs 447 2.3.1 A Partitioning Lemma 449 2.3.2 Perfect Matchings 450 2.3.3 The General Case 453 2.4 The Maximal Independent-Set Problem 455 2.4.1 Definition and statement of results 456 2.4.2 Proof of the main results 461 3 Further reading 467 A Answers to selected exercises 469 B Index of notation 487 Bibliography 491 -- ______________________________________________________________________ | I sit in silent reverie | Justin R. Smith Awaiting a late messenger: | Department of Mathematics and Time's most refined apparition. | Computer Science Of possibilities yet to be, | Drexel University A subtle, silent harbinger. | Philadelphia, PA 19104 Not a commonplace tradition. | Office: (215) 895-1847 | c Justin R. Smith, May 22, 1994 | Fax: (215) 895-2070