CHAPTER 1 Motivation and History

1.1 Introduction

1.2 Modern Scientific Method

1.3 Evolution of Supercomputing

1.4 Modern Parallel Computers

1.4.1 The Cosmic Cube

1.4.2 Commercial Parallel Computers

1.4.3 Beowulf

1.4.4 Advanced Strategic Computing Initiative

1.5 Seeking Concurrency

1.5.1 Data Dependence Graphs

1.5.2 Data Parallelism

1.5.3 Functional Parallelism

1.5.4 Pipelining

1.5.5 Size Considerations

1.6 Data Clustering

CONTENTS

Preface

1.7 Programming Parallel Computers

1.7.1 Extend a Compiler

1.7.2 Extend a Sequential Programming Language

1.7.3 Add a Parallel Programming Layer

1.7.4 Create a Parallel Language

1.7.5 Current Status

1.8 Summary

1.9 KeyTerms

1.10 Bibliographic Notes

1.11 Exercises

CHAPTER 2 Parallel Architectures

2.1 Introduction

2.2 Interconnection Networks

2.2.1 Shared versus Switched Media

2.2.2 Switch Network Topologies

2.2.3 2-D Mesh Network

2.2.4 Binary Tree Network

2.2.5 Hypertree Network

2.2.6 Butterfty Network

2.2.7 Hypercube Network

2.2.8 Shuffle-exchange Network

2.2.9 Summary

2.3.1 Architecture and Data-parallel Operations

2.3 Processor Arrays

2.3.2 Processor Array Performance

2.3.3 Processor Interconnection Network

2.3.4 Enabling and Disabling Processors

2.3.5 Additional Architectural Features

2.3.6 Shortcomings of Processor Arrays

2.4 Multiprocessors

2.4.1 Centralized Multiprocessors

2.4.2 Distributed Multiprocessors

2.5 Multicomputers

2.5.1 Asymmetrical Multicomputers

2.5.2 Symmetrical Multicomputers

2.5.3 Which Model Is Best for a Commodity Cluster？

2.5.4 Differences between Clusters and Networks of Workstations

2.6.1 SISD

2.6 Flynn's Taxonomy

2.6.2 SIMD

2.6.3 MISD

2.6.4 MIMD

2.7 Summary

2.8 Key Terms

2.9 Bibliographic Notes

2.10 Exercises

CHAPTER 3 Parallel Algorithm Design

3.1 Introduction

3.2 The Task/Channel Model

3.3 Foster's Design Methodology

3.3.1 Partitioning

3.3.2 Communication

3.3.3 Agglomeration

3.3.4 Mapping

3.4 Boundary Value Problem

3.4.1 Introduction

3.4.2 Partitioning

3.4.3 Communication

3.4.4 Agglomeration and Mapping

3.4.5 Analysis

3.5 Finding the Maximum

3.5.1 Introduction

3.5.2 Partitioning

3.5.3 Communication

3.5.4 Agglomeration and Mapping

3.6.1 Introduction

3.5.5 Analysis

3.6 The n-Body Problem

3.6.2 Partitioning

3.6.3 Communication

3.6.4 Agglomeration and Mapping

3.6.5 Analysis

3.7 Adding Data Input

3.7.1 Introduction

3.7.2 Communication

3.7.3 Analysis

3.8 Summary

3.10 Bibliographic Notes

3.11 Exercises

3.9 Key Terms

CHAPTER 4 Message-Passing Programming

4.1 Introduction

4.2 The Message-Passing Model

4.3 The Message-Passing Interface

4.4 Circuit Satisfiability

4.4.1 Function MPI_Init

4.4.2 Functions MPI_Comm_rank and MPI_Comm_size

4.4.3 Function MPI_Finalize

4.4.4 Compiling MPI Programs

4.4.5 Running MPI Programs

4.5 Introducing Collective Communication

4.5.1 Function MPI_Reduce

4.6.2 Function MPI_Barrier

4.6 Benchmarking Parallel Performance

4.6.1 Functions MPI_Wtime and MPI_Wtick

4.7 Summary

4.8 Key Terms

4.9 Bibliographic Notes

4.10 Exercises

CHAPTER 5 The Sieve of Eratosthenes

5.1 Introduction

5.2 Sequential Algorithm

5.3 Sources of Parallelism

5.4 Data Decomposition Options

5.4.1 Interleaved Data Decomposition

5.4.2 Block Data Decomposition

5.4.4 Local Index versus Global Index

5.4.3 Block Decomposition Macros

5.4.5 Ramifications of Block Decomposition

5.5 Developing the Parallel Algorithm

5.5.1 Function MPI_Bcast

5.6 Analysis of Parallel Sieve Algorithm

5.7 Documenting the Parallel Program

5.8 Benchmarking

5.9 Improvements

5.9.1 Delete Even Integers

5.9.2 Eliminate Broadcast

5.9.3 Reorganize Loops

5.9.4 Benchmarking

5.10 Summary

5.13 Exercises

5.11 Key Terms

5.12 Bibliographic Notes

CHAPTER 6 Floyd's Algorithm

6.1 Introduction

6.2 The All-Pairs Shortest-Path Problem

6.3 Creating Arrays at Run Time

6.4 Designing the Parallel Algorithm

6.4.1 Partitioning

6.4.2 Communication

6.4.3 Agglomeration and Mapping

6.4.4 Matrix Input/Output

6.5 Point-to-Point Communication

6.5.1 Function MPI_Send

6.5.2 Function MPI_Recv

6.5.3 Deadlock

6.6 Documenting the Parallel Program

6.7 Analysis and Benchmarking

6.8 Summary

6.9 KeyTerms

6.10 Bibliographic Notes

6.11 Exercises

CHAPTER 7 Performance Analysis

7.1 Introduction

7.2 Speedup and Efficiency

7.3 Amdahl's Law

7.3.2 The Amdahl Effect

7.4 Gustafson-Barsis's Law

7.3.1 Limitations of Amdahl's Law

7.5 The Karp-Flatt Metric

7.6 The Isoefficiency Metric

7.7 Summary

7.8 Key Terms

7.9 Bibliographic Notes

7.10 Exercises

CHAPTER 8 Matrix-Vector Multiplication

8.1 Introduction

8.2 Sequential Algorithm

8.3 Data Decomposition Options

8.4 Rowwise Block-Striped Decomposition

8.4.1 Design and Analysis

8.4.2 Replicating a Block-Mapped Vector

8.4.3 Function MPI_Allgatherv

8.4.4 Replicated Vector Input/Output

8.4.5 Documenting the Parallel Program

8.4.6 Benchmarking

8.5 Columnwise Block-Striped Decomposition

8.5.1 Design and Analysis

8.5.2 Reading a Columnwise Block-Striped Matrix

8.5.3 Function MPI_Scatterv

8.5.4 Printing a Columnwise Block-Striped Matrix

8.5.5 Function MPI_Gatherv

8.5.6 Distributing Partial Results

8.5.7 Function MPI_Alltoallv

8.5.8 Documenting the Parallel Program

8.5.9 Benchmarking

8.6.1 Design and Analysis

8.6 Checkerboard Block Decomposition

8.6.2 Creating a Communicator

8.6.3 Function MPI_Dims_create

8.6.4 Function MPI_Cart_create

8.6.5 Reading a Checkerboard Matrix

8.6.6 Function MPI_Cart_rank

8.6.7 Function MPI_Cart_coords

8.6.8 Function MPI_Comm_split

8.6.9 Benchmarking

8.7 Summary

8.9 Bibliographic Notes

8.10 Exercises

8.8 Key Terms

CHAPTER 9 Document Classlflcation

9.1 Introduction

9.2 Parallel Algorithm Design

9.2.1 Partitioning and Communication

9.2.2 Agglomeration and Mapping

9.2.3 Manager/Worker Paradigm

9.2.4 Manager Process

9.2.5 Function MPI_Abort

9.2.6 Worker Process

9.2.7 Creating a Workers-only Communicator

9.3 Nonblocking Communications

9.3.1 Manager's Communication

9.3.2 Function MPI_Irecv

9.3.6 Function MPI_Probe

9.3.5 Function MPI_Isend

9.3.3 Function MPI_Wait

9.3.4 Workers'Communications

9.3.7 Function MPI_Get_count

9.4 Documenting the Parallel Program

9.5 Enhancements

9.5.1 Assigning Groups of Documents

9.5.2 Pipelining

9.5.3 Function MPI_Testsome

9.6 Summary

9.7 Key Terms

9.8 Bibliographic Notes

9.9 Exercises

10.1 Introduction

CHAPTER 10 Monte Carlo Methods

10.1.1 Why Monte Carlo Work

10.1.2 Monte Carlo and Parallel Computing

10.2 Sequential Random Number Generators

10.2.1 Linear Congruential

10.2.2 Lagged Fibonacci

10.3 Parallel Random Number Generators

10.3.1 Manager-Worker Method

10.3.2 Leapfrog Method

10.3.3 Sequence Splitting

10.3.4 Parameterization

10.4 Other Random Number Distributions

10.4.1 Inverse Cumulative Distribution Function Transformation

10.4.2 Box-Muller Transformation

10.4.3 The Rejection Method

10.5.1 Neutron Transport

10.5 Case Studies

10.5.2 Temperature at a Point Inside a 2-D Plate

10.5.3 Two-Dimensional Ising Model

10.5.4 Room Assignment Problem

10.5.5 Parking Garage

10.5.6 Traffic Circle

10.6 Summary

10.7 Key Terms

10.8 Bibliographic Notes

10.9 Exercises

CHAPTER 11 Matrix Multipllcation

11.1 Introduction

11.2.1 Iterative,Row-Oriented Algorithm

11.2 Sequential Matrix Multiplication

11.2.2 Recursive,Block-Oriented Algorithm

11.3 Rowwise Block-Striped Parallel Algorithm

11.3.1 Identifying Primitive Tasks

11.3.2 Agglomeration

11.3.3 Communication and Further Agglomeration

11.3.4 Analysis

11.4 Cannon's Algorithm

11.4.1 Agglomeration

11.4.2 Communication

11.4.3 Analysis

11.5 Summary

11.8 Exercises

11.7 Bibliographic Notes

11.6 Key Terms

CHAPTER 12 Solving Linear Systems

12.1 Introduction

12.2 Terminology

12.3 Back Substitution

12.3.1 Sequential Algorithm

12.3.2 Row-Oriented Parallel Algorithm

12.3.3 Column-Oriented Parallel Algorithm

12.3.4 Comparison

12.4 Gaussian Elimination

12.4.1 Sequential Algorithm

12.4.2 Parallel Algorithms

12.4.3 Row-Oriented Algorithm

12.4.5 Comparison

12.4.4 Column-Oriented Algorithm

12.4.6 Pipelined,Row-Oriented Algorithm

12.5 Iterative Methods

12.6 The Conjugate Gradient Method

12.6.1 Sequential Algorithm

12.6.2 Parallel Implementation

12.7 Summary

12.8 Key Terms

12.9 Bibliographic Notes

12.10 Exercises

CHAPTER 13 Finite Difference Methods

13.1 Introduction

13.2.1 Categorizing PDEs

13.2 Partial Differential Equations

13.2.2 Difference Quotients

13.3 Vibrating String

13.3.1 Deriving Equations

13.3.2 Deriving the Sequential Program

13.3.3 Parallel Program Design

13.3.4 Isoefficiency Analysis

13.3.5 Replicating Computations

13.4 Steady-State Heat Distribution

13.4.1 Deriving Equations

13.4.2 Deriving the Sequential Program

13.4.3 Parallel Program Design

13.4.4 Isoefficiency Analysis

13.5 Summary

13.4.5 Implementation Details

13.6 Key Terms

13.7 Bibliographic Notes

13.8 Exercises

CHAPTER 14 Sorting

14.1 Introduction

14.2 Quicksort

14.3 A Parallel Quicksort Algorithm

14.3.1 Definition of Sorted

14.3.2 Algorithm Development

14.3.3 Analysis

14.4 Hyperquicksort

14.4.1 Algorithm Description

14.4.2 lsoefficiency Analysis

14.5 Parallel Sorting by Regular Sampling

14.5.1 Algorithm Description

14.5.2 Isoefficiency Analsis

14.6 Summary

14.7 Key Terms

14.8 Bibliographic Notes

14.9 Exercises

CHAPTER 15 The Fast Fourler Transform

15.1 Introduction

15.2 Fourier Analysis

15.3 The Discrete Fourier Transform

15.3.2 Sample Application:Polynomial Multiplication

15.3.1 Inverse Discrete Fourier Transform

15.4 The Fast Fourier Transform

15.5 Parallel Program Design

15.5.1 Partitioning and Communication

15.5.2 Agglomeration and Mapping

15.5.3 Isoefficiency Analysis

15.6 Summary

15.7 Key Terms

15.8 Bibliographic Notes

15.9 Exercises

CHAPTER 16 Comblnatorlal Search

16.1 Introduction

16.2 Divide and Conquer

16.3.1 Example

16.3 Backtrack Search

16.3.2 Time and Space Complexity

16.4 Parallel Backtrack Search

16.5 Distributed Termination Detection

16.6 Branch and Bound

16.6.1 Example

16.6.2 Sequential Algorithm

16.6.3 Analysis

16.7 Parallel Branch and Bound

16.7.1 Storing and Sharing Unexamined Subproblems

16.7.2 Efficiency

16.7.3 Halting Conditions

16.8.1 Minimax Algorithm

16.8 Searching Game Trees

16.8.2 Alpha-Beta Pruning

16.8.3 Enhancements to Alpha-Beta Pruning

16.9 Parallel Alpha-Beta Search

16.9.1 Parallel Aspiration Search

16.9.2 Parallel Subtree Evaluation

16.9.3 Distributed Tree Search

16.10 Summary

16.11 Key Terms

16.12 Bibliographic Notes

16.13 Exercises

CHAPTER 17 Shared-Memory Programming

17.1 Introduction

17.2 The Shared-Memory Model

17.3 Parallel for Loops

17.3.1 parallel for Pragma

17.3.2 Function omp_get_ num_procs

17.3.3 Function omp_set_ num_threads

17.4 Declaring Private Variables

17.4.1 private Clause

17.4.2 firstprivate Clause

17.4.3 lastprivate Clause

17.5 Critical Sections

17.5.1 critical Pragma

17.6 Reductions

17.7 Performance Improvements

17.7.1 Inverting Loops

17.7.2 Conditionally Executing Loops

17.7.3 Scheduling Loops

17.8 More General Data Parallelism

17.8.1 parallel Pragma

17.8.2 Function omp_get_ thread_num

17.8.3 Function omp_get_ num_threads

17.8.4 for Pragma

17.8.5 single Pragma

17.8.6 nowait Clause

17.9 Functional Parallelism

17.9.1 parallel sections Pragma

17.9.2 section Pragma

17.9.3 sections Pragma

17.10 Summary

17.11 Key Terms

17.12 Bibliographic Notes

17.13 Exercises

CHAPTER 18 Combining MPI and OpenMP

18.1 Introduction

18.2 Conjugate Gradient Method

18.2.1 MPI Program

18.2.2 Functional Profiling

18.2.3 Parallelizing Function matrix_vector_product

18.2.4 Benchmarking

18.3 Jacobi Method

18.3.1 Profiling MPI Program

18.3.2 Parallelizing Function find_steady_state

18.3.3 Benchmarking

18.4 Summary

18.5 Exercises

APPENDIX A MPI Functions

APPENDIX B Utility Functions

B.1 Header File MyMPI.h

B.2 Source File MyMPI.c

APPENDIX C Debugging MPI Programs

C.1 Introduction

C.2 Typical Bugs in MPI Programs

C.2.1 Bugs Resulting in Deadlock

C.2.2 Bugs Resulting in Incorrect Results

C.2.3 Advantages of Collective Communications

C.3 Practical Debugging Strategies

APPENDIX D Review of Complex Numbers

APPENDIX E OpenMP Functions

Bibliography