| |  | Preface |
| | |
Chapter 1.
Introduction to Parallel Computing |
| |
| |
Section 1.1.
Motivating Parallelism |
| |
| |
Section 1.2.
Scope of Parallel Computing |
| |
| |
Section 1.3.
Organization and Contents of the Text |
| |
| |
Section 1.4.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 2.
Parallel Programming Platforms |
| |
| |
Section 2.1.
Implicit Parallelism: Trends in Microprocessor Architectures* |
| |
| |
Section 2.2.
Limitations of Memory System Performance* |
| |
| |
Section 2.3.
Dichotomy of Parallel Computing Platforms |
| |
| |
Section 2.4.
Physical Organization of Parallel Platforms |
| |
| |
Section 2.5.
Communication Costs in Parallel Machines |
| |
| |
Section 2.6.
Routing Mechanisms for Interconnection Networks |
| |
| |
Section 2.7.
Impact of Process-Processor Mapping and Mapping Techniques |
| |
| |
Section 2.8.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 3.
Principles of Parallel Algorithm Design |
| |
| |
Section 3.1.
Preliminaries |
| |
| |
Section 3.2.
Decomposition Techniques |
| |
| |
Section 3.3.
Characteristics of Tasks and Interactions |
| |
| |
Section 3.4.
Mapping Techniques for Load Balancing |
| |
| |
Section 3.5.
Methods for Containing Interaction Overheads |
| |
| |
Section 3.6.
Parallel Algorithm Models |
| |
| |
Section 3.7.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 4.
Basic Communication Operations |
| |
| |
Section 4.1.
One-to-All Broadcast and All-to-One Reduction |
| |
| |
Section 4.2.
All-to-All Broadcast and Reduction |
| |
| |
Section 4.3.
All-Reduce and Prefix-Sum Operations |
| |
| |
Section 4.4.
Scatter and Gather |
| |
| |
Section 4.5.
All-to-All Personalized Communication |
| |
| |
Section 4.6.
Circular Shift |
| |
| |
Section 4.7.
Improving the Speed of Some Communication Operations |
| |
| |
Section 4.8.
Summary |
| |
| |
Section 4.9.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 5.
Analytical Modeling of Parallel Programs |
| |
| |
Section 5.1.
Sources of Overhead in Parallel Programs |
| |
| |
Section 5.2.
Performance Metrics for Parallel Systems |
| |
| |
Section 5.3.
The Effect of Granularity on Performance |
| |
| |
Section 5.4.
Scalability of Parallel Systems |
| |
| |
Section 5.5.
Minimum Execution Time and Minimum Cost-Optimal Execution Time |
| |
| |
Section 5.6.
Asymptotic Analysis of Parallel Programs |
| |
| |
Section 5.7.
Other Scalability Metrics |
| |
| |
Section 5.8.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 6.
Programming Using the Message-Passing Paradigm |
| |
| |
Section 6.1.
Principles of Message-Passing Programming |
| |
| |
Section 6.2.
The Building Blocks: Send and Receive Operations |
| |
| |
Section 6.3.
MPI: the Message Passing Interface |
| |
| |
Section 6.4.
Topologies and Embedding |
| |
| |
Section 6.5.
Overlapping Communication with Computation |
| |
| |
Section 6.6.
Collective Communication and Computation Operations |
| |
| |
Section 6.7.
Groups and Communicators |
| |
| |
Section 6.8.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 7.
Programming Shared Address Space Platforms |
| |
| |
Section 7.1.
Thread Basics |
| |
| |
Section 7.2.
Why Threads? |
| |
| |
Section 7.3.
The POSIX Thread API |
| |
| |
Section 7.4.
Thread Basics: Creation and Termination |
| |
| |
Section 7.5.
Synchronization Primitives in Pthreads |
| |
| |
Section 7.6.
Controlling Thread and Synchronization Attributes |
| |
| |
Section 7.7.
Thread Cancellation |
| |
| |
Section 7.8.
Composite Synchronization Constructs |
| |
| |
Section 7.9.
Tips for Designing Asynchronous Programs |
| |
| |
Section 7.10.
OpenMP: a Standard for Directive Based Parallel Programming |
| |
| |
Section 7.11.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 8.
Dense Matrix Algorithms |
| |
| |
Section 8.1.
Matrix-Vector Multiplication |
| |
| |
Section 8.2.
Matrix-Matrix Multiplication |
| |
| |
Section 8.3.
Solving a System of Linear Equations |
| |
| |
Section 8.4.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 9.
Sorting |
| |
| |
Section 9.1.
Issues in Sorting on Parallel Computers |
| |
| |
Section 9.2.
Sorting Networks |
| |
| |
Section 9.3.
Bubble Sort and its Variants |
| |
| |
Section 9.4.
Quicksort |
| |
| |
Section 9.5.
Bucket and Sample Sort |
| |
| |
Section 9.6.
Other Sorting Algorithms |
| |
| |
Section 9.7.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 10.
Graph Algorithms |
| |
| |
Section 10.1.
Definitions and Representation |
| |
| |
Section 10.2.
Minimum Spanning Tree: Prim's Algorithm |
| |
| |
Section 10.3.
Single-Source Shortest Paths: Dijkstra's Algorithm |
| |
| |
Section 10.4.
All-Pairs Shortest Paths |
| |
| |
Section 10.5.
Transitive Closure |
| |
| |
Section 10.6.
Connected Components |
| |
| |
Section 10.7.
Algorithms for Sparse Graphs |
| |
| |
Section 10.8.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 11.
Search Algorithms for Discrete Optimization Problems |
| |
| |
Section 11.1.
Definitions and Examples |
| |
| |
Section 11.2.
Sequential Search Algorithms |
| |
| |
Section 11.3.
Search Overhead Factor |
| |
| |
Section 11.4.
Parallel Depth-First Search |
| |
| |
Section 11.5.
Parallel Best-First Search |
| |
| |
Section 11.6.
Speedup Anomalies in Parallel Search Algorithms |
| |
| |
Section 11.7.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 12.
Dynamic Programming |
| |
| |
Section 12.1.
Overview of Dynamic Programming |
| |
| |
Section 12.2.
Serial Monadic DP Formulations |
| |
| |
Section 12.3.
Nonserial Monadic DP Formulations |
| |
| |
Section 12.4.
Serial Polyadic DP Formulations |
| |
| |
Section 12.5.
Nonserial Polyadic DP Formulations |
| |
| |
Section 12.6.
Summary and Discussion |
| |
| |
Section 12.7.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Chapter 13.
Fast Fourier Transform |
| |
| |
Section 13.1.
The Serial Algorithm |
| |
| |
Section 13.2.
The Binary-Exchange Algorithm |
| |
| |
Section 13.3.
The Transpose Algorithm |
| |
| |
Section 13.4.
Bibliographic Remarks |
| |
| | Problems |
|
| | |
Appendix A.
Complexity of Functions and Order Analysis |
| |
| |
Section A.1.
Complexity of Functions |
| |
| |
Section A.2.
Order Analysis of Functions |
|
| | | Bibliography |
