CHAPTER 1 Introduction to Parallel Computing

1.1 Motivating Parallelism

1.1.1 The Computational Power Argument-from Transistors to FLOPS

1.1.2 The Memory/Disk Speed Argument

1.1.3 The Data Communication Argument

1.2 Scope of Parallel Computing

1.2.1 Applications in Engineering and Design

1.2.2 Scientific Applications

1.2.3 Commercial Applications

1.2.4 Applications in Computer Systems

1.3 Organization and Contents of the Text

1.4 Bibliographic Remarks

Problems

CHAPTER 2 Parallel Progrmming Platforms

2.1.1 Pipelining and Superscalar Execution

2.1 Implicit parallelism:Trends in Microprocessor Architectures

2.1.2 Very Long Instruction Word Processors

2.2 Limitations of Memory System Performance

2.2.1 Improving Effective Memory Latency Using Caches

2.2.2 Impact of Memory Bandwidth

2.2.3 Alternate Approaches for Hiding Memory Latency

2.2.4 Tradeoffs of Multithreading and Prefetching

2.3 Dichotomy of Parallel Computing Platforms

2.3.1 Control Structure of parallel Platforms

2.3.2 Communication Model of Parallel Platforms

2.4 Physical Organization of Parallel Platforms

2.4.1 Architecture of an Ideal Parallel Computer

2.4.2 Interconnection Networks for Parallel Computers

2.4.3 Network Topologies

2.4.4 Evaluating Static Interconnection Networks

2.4.5 Evaluating Dynamic Interconnection Networks

2.4.6 Cache Coherence in Multiprocessor Systems

2.5.1 Message Passing Costs in Parallel Computers

2.5 Communication Costs in Parallel Machines

2.5.2 Communication Costs in Shared-Address-Space Machines

2.6 Routing Mechanisms for Interconnection Networks

2.7 Impact of Process-Processor Mapping and Mapping Techniques

2.7.1 Mapping Techniques for Graphs

2.7.2 Cost-Performance Tradeoffs

2.8 Bibliographic Remarks

Problems

CHAPTER 3 Principles of Parallel Algorithm Design

3.1 Preliminaries

3.1.1 Decomposition,Tasks,and Dependency Graphs

3.1.2 Granularity,Concurrency,and Task-Interaction

3.1.3 Processes and Mapping

3.1.4 Processes versus Processors

3.2 Decomposition Techniques

3.2.1 Recursive Decomposition

3.2.2 Data Decomposition

3.2.3 Exploratory Decomposition

3.2.4 Speculative Decomposition

3.2.5 Hybrid Decompositions

3.3 Characteristics of Tasks and Interactions

3.3.1 Characteristics of Tasks

3.3.2 Characteristics of Inter-Task Interactions

3.4 Mapping Techniques for Load Balancing

3.4.1 Schemes for Static Mapping

3.4.2 Schemes for Dynamic Mapping

3.5.1 Maximizing Data Locality

3.5 Methods for Containing Interaction Overheads

3.5.2 Minimizing Contention and Hot Spots

3.5.3 Overlapping Computations with Interactions

3.5.4 Replicating Data or Computations

3.5.5 Using Optimized Collective Interaction Operations

3.5.6 Overlapping Interactions with Other Interactions

3.6 Parallel Algorithm Models

3.6.1 The Data-Parallel Model

3.6.3 Tht Work Pool Model

3.6.2 The Task Graph Model

3.6.4 The Master-Slave Model

3.6.5 The Pipeline or Producer-Consumer Model

3.6.6 Hybrid Models

3.7 Bibliographic Remarks

Problems

CHAPTER 4 Basic Communication Operations

4.1 One-to-All Broadcast and All-to-One Reduction

4.1.1 Ring or Linear Array

4.1.2 Mesh

4.1.3 Hypercube

4.1.4 Balanced Binary Tree

4.1.5 Detailed Algorithms

4.1.6 Cost Analysis

4.2 All-to-All Broadcast and Reduction

4.2.1 Linear Array and Ring

4.2.2 Mesh

4.2.3 Hypercube

4.2.4 Cost Analysis

4.3 All-Reduce and Prefix-Sum Operations

4.4 Scatter and Gather

4.5 All-to-All Personalized Communication

4.5.1 Ring

4.5.2 Mesh

4.5.3 Hypercube

4.6.1 Mesh

4.6 Circular Shift

4.6.2 Hypercube

4.7 Improving the Speed of Some Communication Operations

4.7.1 Splitting and Routing Messages in Parts

4.7.2 All-Port Communication

4.8 Summary

4.9 Bibliographic Remarks

Problems

5.1 Sources of Overhead in Parallel Programs

CHAPTER 5 Analytical Modeling of Parallel Programs

5.2 Performance Metrics for Parallel Systems

5.2.1 Execution Time

5.2.2 Total Parallel Overhead

5.2.3 Speedup

5.2.4 Efficiency

5.2.5 Cost

5.3 The Effect of Granularity on Performance

5.4 Scalability of Parallel Systems

5.4.1 Scaling Characteristics of Parallel Programs

5.4.2 The Isoefficiency Metric of Scalability

5.4.3 Cost-Optimality and the Isoefficiency Function

5.4.4 A Lower Bound on the Isoefficiency Function

5.4.5 The Degree of Concurrency and the Isoefficiency Function

5.5 Minimum Execution Time and Minimum Cost-Optimal Execution Time

5.6 Asymptotic Analysis of Parallel Programs

5.7 Other Scalability Metrics

5.8 Bibliographic Remarks

Problems

CHAPTER 6 Programming Using the Message-Passing Paradigm

6.1 Principles of Message-Passing Programming

6.2 The Building Blocks:Send and Receive Operations

6.2.1 Blocking Message Passing Operations

6.2.2 Non-Blocking Message Passing Operations

6.3 MPI:the Message Passing Interface

6.3.2 Communicators

6.3.1 Starting and Terminating the MPI Library

6.2.3 Getting Information

6.3.4 Sending and Receiving Messages

6.3.5 Example:Odd-Even Sort

6.4 Topologies and Embedding

6.4.1 Creating and Using Cartesian Topologies

6.4.2 Example:Cannon s Matrix-Matrix Multiplication

6.5 Overlapping Communication with Computation

6.5.1 Non-Blocking Communication Operations

6.6.2 Broadcast

6.6.1 Barrier

6.6 Collective Communication and Computation Operations

6.6.3 Reduction

6.6.4 Prefix

6.6.5 Gather

6.6.6 Scatter

6.6.7 All-to-All

6.6.8 Example:One-Dimensional Matrix-Vector Multiplication

6.6.9 Example:Single-Source Shortest-Path

6.6.10 Example:Sample Sort

6.7 Groups and Communicators

6.7.1 Example:Two-Dimensional Matrix-Vector Multiplication

6.8 Bibliographic Remarks

Problems

CHAPTER 7 Programming Shared Address Space Platforms

7.1 Thread Basics

7.2 Why Threads?

7.4 Thread Basics:Creation and Termination

7.3 The POSIX Thread API

7.5 Synchronization Primitives in Pthreads

7.5.1 Mutual Exclusion for Shared Variables

7.5.2 Condition Variables for Synchronization

7.6 Controlling Thread and Synchronization Attributes

7.6.1 Attributes Objects for Threads

7.6.2 Attributes Objects for Mutexes

7.7 Thread Cancellation

7.8.1 Read-Write Locks

7.8 Composite Synchronization Constructs

7.8.2 Barriers

7.9 Tips for Designing Asynchronous Programs

7.10 OpenMP:a Standard for Directive Based Parallel Programming

7.10.1 The OpenMP Programming Model

7.10.2 Specifying Concurrent Tasks in OpenMP

7.10.3 Synchronization Constructs in OpenMP

7.10.4 Data Handling in OpenMP

7.10.5 OpenMP Library Functions

7.10.6 Environment Variables in OpenMP

7.10.7 Explicit Threads versus OpenMP Based Programming

7.11 Bibliographic Remarks

Problems

CHAPTER 8 Dense Matrix Algorithms

8.1 Matrix-Vector Multiplication

8.1.1 Rowwise 1-D Partitioning

8.1.2 2-D Partitioning

8.2 Matrix-Matrix Multiplication

8.2.1 A Simple Parallel Algorithm

8.2.2 Cannon s Algorithm

8.2.3 The DNS Algorithm

8.3 Solving a System of Linear Equations

8.3.1 A Simple Gaussian Elimination Algorithm

8.3.2 Gaussian Elimination with Partial Pivoting

8.3.3 Solving a Triangular System:Back-Substitution

8.3.4 Numerical Considerations in Solving Systems of Linear Equations

8.4 Bibliographic Remarks

Problems

CHAPTER 9 Sorting

9.1 Issues in Sorting on Parallel Computers

9.1.1 Where the Input and Output Sequences are Stored

9.1.2 How Comparisons are Performed

9.2 Sorting Networks

9.2.1 Bitonic Sort

9.2.2 Mapping Bitonic Sort to a Hypercube and a Mesh

9.3 Bubble Sort and its Variants

9.3.1 Odd-Even Transposition

9.3.2 Shellsort

9.4 Quicksort

9.4.1 Parallelizing Quicksort

9.4.2 Parallel Formulation for a CRCW PRAM

9.4.3 Parallel Formulation for Practical Architectures

9.4.4 Pivot Selection

9.5 Bucket and Sample Sort

9.6.1 Enumeration Sort

9.6 Other Sorting Algorithms

9.6.2 Radix Sort

9.7 Bibliographic Remarks

Problems

CHAPTER 10 Graph Algorithms

10.1 Definitions and Representation

10.2 Minimum Spanning Tree:Prim s Algorithm

10.3 Single-Source Shortest Paths:Dijkstra s Algorithm

10.4 All-Pairs Shortest Paths

10.4.1 Dijkstra s Algorithm

10.4.2 Floyd s Algorithm

10.4.3 Performance Comparisons

10.5 Transitive Closure

10.6 Connected Components

10.6.1 A Depth-First Search Based Algorithm

10.7 Algorithms for Sparse Graphs

10.7.1 Finding a Maximal Independent Set

10.7.2 Single-Source Shortest Paths

10.8 Bibliographic Remarks

Problems

CHAPTER 11 Search Algorithms for Discrete Optimization Problems

11.1 Definitions and Examples

11.2 Sequential Search Algorithms

11.2.1 Depth-First Search Algorithms

11.2.2 Best-First Search Algorithms

11.3 Search Overhead Factor

11.4 Parallel Depth-First Search

11.4.1 Important Parameters of Parallel DFS

11.4.2 A General Framework for Analysis of Parallel DFS

11.4.3 Analvsis of Load-Balancing Schemes

11.4.4 Termination Detection

11.4.5 Experimental Results

11.4.6 Parallel Formulations of Depth-First Branch-and-Bound Search

11.4.7 Parallel Formulations of IDA

11.5 Parallel Best-First Search

11.6 Speedup Anomalies in Parallel Search Algorithms

11.6.1 Analysis of Average Speedup in Parallel DFS

11.7 Bibliographic Remarks

Problems

CHAPTER 12 Dynamic Programming

12.1 Overview of Dynamic Programming

12.2 Serial Monadic DP Formulations

12.2.1 The Shortest-Path Problem

12.2.2 The O/I Knapsack Problem

12.3 Nonserial Monadic DP Formulations

12.3.1 The Longest-Common-Subsequence Problem

12.4 Serial Polyadic DP Formulations

12.4 1 Floyd s All-Pairs Shortest-Paths Algorithm

12.5 Nonserial Polyadic DP Formulations

12.5.1 The Optimal Matrix-Parenthesization Problem

12.6 Summary and Discussion

12.7 Bibliographic Remarks

Problems

CHAPTER 13 Fast Fourier Transform

13.1 The Serial Algorithm

13.2 The Binary-Exchange Algorithm

13.2.1 A Full Bandwidth Network

13.2.2 Limited Bandwidth Network

13.2.3 Extra Computations in Parallel FFT

13.3 The Transpose Algorithm

13.3.1 Two-Dimensional Transpose Algorithm

13.3.2 The Generalized Transpose Algorithm

13.4 Bibliographic Remarks

Problems

APPENDIX A Complexity of Functions and Order Analytsis

A.1 Complexity of Functions

A.2 Order Analysis of Functions

Bibliography

Author Index

Subject Index