| |
| |
Preface | |
| |
| |
| |
Motivation and History | |
| |
| |
| |
Introduction | |
| |
| |
| |
Modern Scientific Method | |
| |
| |
| |
Evolution of Supercomputing | |
| |
| |
| |
Modern Parallel Computers | |
| |
| |
| |
Seeking Concurrency | |
| |
| |
| |
Data Clustering | |
| |
| |
| |
Programming Parallel Computers | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Architectures | |
| |
| |
| |
Introduction | |
| |
| |
| |
Interconnection Networks | |
| |
| |
| |
Processor Arrays | |
| |
| |
| |
Multiprocessors | |
| |
| |
| |
Multicomputers | |
| |
| |
| |
Flynn's Taxonomy | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Parallel Algorithm Design | |
| |
| |
| |
Introduction | |
| |
| |
| |
The Task/Channel Model | |
| |
| |
| |
Foster's Design Methodology | |
| |
| |
| |
Boundary Value Problem | |
| |
| |
| |
Finding the Maximum | |
| |
| |
| |
The n-Body Problem | |
| |
| |
| |
Adding Data Input | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Message-Passing Programming | |
| |
| |
| |
Introduction | |
| |
| |
| |
The Message-Passing Model | |
| |
| |
| |
The Message-Passing Interface | |
| |
| |
| |
Circuit Satisfiability | |
| |
| |
| |
Introducing Collective Communication | |
| |
| |
| |
Benchmarking Parallel Performance | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Sieve of Eratosthenes | |
| |
| |
| |
Introduction | |
| |
| |
| |
Sequential Algorithm | |
| |
| |
| |
Sources of Parallelism | |
| |
| |
| |
Data Decomposition Options | |
| |
| |
| |
Developing the Parallel Algorithm | |
| |
| |
| |
Analysis of Parallel Sieve Algorithm | |
| |
| |
| |
Documenting the Parallel Program | |
| |
| |
| |
Benchmarking | |
| |
| |
| |
Improvements | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Floyd's Algorithm | |
| |
| |
| |
Introduction | |
| |
| |
| |
The All-Pairs Shortest-Path Problem | |
| |
| |
| |
Creating Arrays at Run Time | |
| |
| |
| |
Designing the Parallel Algorithm | |
| |
| |
| |
Point-to-Point Communication | |
| |
| |
| |
Documenting the Parallel Program | |
| |
| |
| |
Analysis and Benchmarking | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Performance Analysis | |
| |
| |
| |
Introduction | |
| |
| |
| |
Speedup and Efficiency | |
| |
| |
| |
Amdahl's Law | |
| |
| |
| |
Gustafson-Barsis's Law | |
| |
| |
| |
The Karp-Flatt Metric | |
| |
| |
| |
The Isoefficiency Metric | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Matrix-Vector Multiplication | |
| |
| |
| |
Introduction | |
| |
| |
| |
Sequential Algorithm | |
| |
| |
| |
Data Decomposition Options | |
| |
| |
| |
Rowwise Block-Striped Decomposition | |
| |
| |
| |
Columnwise Block-Striped Decomposition | |
| |
| |
| |
Checkerboard Block Decomposition | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Document Classification | |
| |
| |
| |
Introduction | |
| |
| |
| |
Parallel Algorithm Design | |
| |
| |
| |
Nonblocking Communications | |
| |
| |
| |
Documenting the Parallel Program | |
| |
| |
| |
Enhancements | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Monte Carlo Methods | |
| |
| |
| |
Introduction | |
| |
| |
| |
Sequential Random Number Generators | |
| |
| |
| |
Parallel Random Number Generators | |
| |
| |
| |
Other Random Number Distributions | |
| |
| |
| |
Case Studies | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Matrix Multiplication | |
| |
| |
| |
Introduction | |
| |
| |
| |
Sequential Matrix Multiplication | |
| |
| |
| |
Rowwise Block-Striped Parallel Algorithm | |
| |
| |
| |
Cannon's Algorithm | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Solving Linear Systems | |
| |
| |
| |
Introduction | |
| |
| |
| |
Terminology | |
| |
| |
| |
Back Substitution | |
| |
| |
| |
Gaussian Elimination | |
| |
| |
| |
Iterative Methods | |
| |
| |
| |
The Conjugate Gradient Method | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Finite Difference Methods | |
| |
| |
| |
Introduction | |
| |
| |
| |
Partial Differential Equations | |
| |
| |
| |
Vibrating String | |
| |
| |
| |
Steady-State Heat Distribution | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Sorting | |
| |
| |
| |
Introduction | |
| |
| |
| |
Quicksort | |
| |
| |
| |
A Parallel Quicksort Algorithm | |
| |
| |
| |
Hyperquicksort | |
| |
| |
| |
Parallel Sorting by Regular Sampling | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
The Fast Fourier Transform | |
| |
| |
| |
Introduction | |
| |
| |
| |
Fourier Analysis | |
| |
| |
| |
The Discrete Fourier Transform | |
| |
| |
| |
The Fast Fourier Transform | |
| |
| |
| |
Parallel Program Design | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Combinatorial Search | |
| |
| |
| |
Introduction | |
| |
| |
| |
Divide and Conquer | |
| |
| |
| |
Backtrack Search | |
| |
| |
| |
Parallel Backtrack Search | |
| |
| |
| |
Distributed Termination Detection | |
| |
| |
| |
Branch and Bound | |
| |
| |
| |
Parallel Branch and Bound | |
| |
| |
| |
Searching Game Trees | |
| |
| |
| |
Parallel Alpha-Beta Search | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Shared-Memory Programming | |
| |
| |
| |
Introduction | |
| |
| |
| |
The Shared-Memory Model | |
| |
| |
| |
Parallel for Loops | |
| |
| |
| |
Declaring Private Variables | |
| |
| |
| |
Critical Sections | |
| |
| |
| |
Reductions | |
| |
| |
| |
Performance Improvements | |
| |
| |
| |
More General Data Parallelism | |
| |
| |
| |
Functional Parallelism | |
| |
| |
| |
Summary | |
| |
| |
| |
Key Terms | |
| |
| |
| |
Bibliographic Notes | |
| |
| |
| |
Exercises | |
| |
| |
| |
Combining MPI and OpenMP | |
| |
| |
| |
Introduction | |
| |
| |
| |
Conjugate Gradient Method | |
| |
| |
| |
Jacobi Method | |
| |
| |
| |
Summary | |
| |
| |
| |
Exercises | |
| |
| |
| |
MPI Functions | |
| |
| |
| |
Utility Functions | |
| |
| |
| |
Header File MyMPI.h | |
| |
| |
| |
Source File MyMPI.c | |
| |
| |
| |
Debugging MPI Programs | |
| |
| |
| |
Introduction | |
| |
| |
| |
Typical Bugs in MPI Programs | |
| |
| |
| |
Practical Debugging Strategies | |
| |
| |
| |
Review of Complex Numbers | |
| |
| |
| |
OpenMP Functions | |
| |
| |
Bibliography | |
| |
| |
Author Index | |
| |
| |
Subject Index | |