🚀 go-pugleaf

Title: The Design and Analysis of Parallel Algorithms
Author: Justin R. Smith
Publisher: Oxford University Press

Availability date: December, 1992

522 pp, 131 figures.

Table of Contents:

List of Figures
Preface 
Acknowledgements
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
     2. The Discrete Fourier Transform
        2.1. Background
        2.2. Definition and basic properties
        2.3. The Fast Fourier Transform Algorithm
        2.4. Eigenvalues of cyclic matrices
     3. Wavelets
        3.1. Background
        3.2. Discrete Wavelet Transforms
        3.3. Discussion and Further reading
     4. Numerical Evaluation of Definite Integrals
        4.1. The one-dimensional case
        4.2. Higher-dimensional integrals
        4.3. Discussion and Further reading
     5. Partial Differential Equations 
        5.1. Elliptic Differential Equations
             5.1.1. Basic concepts
             5.1.2. Self-adjoint equations
             5.1.3. Rate of convergence
        5.2. Parabolic Differential Equations
             5.2.1. Basic Methods
             5.2.2. Error Analysis
             5.2.3. Implicit Methods
             5.2.4. Error Analysis
        5.3. Hyperbolic Differential Equations
             5.3.1. Background
             5.3.2. Finite differences
        5.4. Further reading
VI. A Survey of Symbolic Algorithms
     1. Doubling Algorithms
        1.1. General Principles
        1.2. Recurrence Relations
        1.3. Deterministic Finite Automata
     2. Graph Algorithms
        2.1. The Euler Tour Algorithm
        2.2. Parallel Tree Contractions
        2.3. Shortest Paths
        2.4. Connected Components
             2.4.1. Algorithm for a CREW Computer
             2.4.2. Algorithm for a CRCW computer
        2.5. Spanning Trees and Forests
             2.5.1. An algorithm for an inverted spanning forest
        2.6. Minimal Spanning Trees and Forests
        2.7. Cycles in a Graph
             2.7.1. Definitions
             2.7.2. A simple algorithm for a cycle basis
             2.7.3. Lowest Common Ancestors
        2.8. Further Reading
     3. Parsing and the Evaluation of arithmetic expressions
        3.1. Introduction
        3.2. An algorithm for building syntax-trees
        3.3. An algorithm for evaluating a syntax tree
        3.4. Discussion and Further Reading
        3.5. Appendix: Parenthesis-matching algorithm
     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
 A. Answers to selected exercises
 B. Index of notation
 Bibliography
-- 
Justin R. Smith
Department of Mathematics and Computer Science
Drexel University
Philadelphia, PA 19104                    (215) 895-1847