Parallel Programming : Techniques and Applications Using Networked Workstations and Parallel Computers

by Wilkinson, Barry; Allen, Michael

• ISBN13: 9780136717102
• ISBN10: 0136717101
• Edition: 2nd
• Format: Paperback
• Copyright: 2005-01-01
• Publisher: Prentice Hall

Summary

Designed for undergraduate level parallel programming courses. This nontheoretical, highly accessible textwhich is linked to real parallel programming softwarecovers the techniques of parallel programming in a practical manner that enables students to write and evaluate their parallel programs. Supported by the National Science Foundation and exhaustively class-tested, it is the first text of its kind that does not require access to a special multiprocessor system, concentrating instead only on parallel programs that can be executed on networked workstations using freely available parallel software tools.

Table of Contents

Preface	v	(3)
About the Authors	viii
PART I BASIC TECHNIQUES	1	(264)
CHAPTER 1 PARALLEL COMPUTERS	3	(35)
1.1 The Demand for Computational Speed	3	(3)
1.2 Types of Parallel Computers	6	(5)
Shared Memory Multiprocessor System	6	(1)
Message-Passing Multicomputer	7	(2)
Distributed Shared Memory	9	(1)
MIMD and SIMD Classifications	10	(1)
1.3 Architectural Features of Message-Passing Multicomputers	11	(11)
Static Network Message-Passing Multicomputers	11	(5)
Embedding	16	(2)
Communication Methods	18	(4)
Input/Output	22	(1)
1.4 Networked Computers as a Multicomputer Platform	22	(4)
1.5 Potential for Increased Computational Speed	26	(6)
1.6 Summary	32	(1)
Further Reading	32	(1)
Bibliography	33	(3)
Problems	36	(2)
CHAPTER 2 MESSAGE-PASSING COMPUTING	38	(44)
2.1 Basics of Message-Passing Programming	38	(8)
Programming Options	38	(1)
Process Creation	39	(2)
Message-Passing Routines	41	(5)
2.2 Using Workstation Clusters	46	(15)
Software Tools	46	(1)
PVM	47	(4)
MPI	51	(8)
Pseudocode Constructs	59	(2)
2.3 Evaluating Parallel Programs	61	(10)
Parallel Execution Time	61	(3)
Time Complexity	64	(3)
Comments on Asymptotic Analysis	67	(1)
Time Complexity of Broadcast/Gather	68	(3)
2.4 Debugging and Evaluating Parallel Programs	71	(6)
Low-Level Debugging	71	(1)
Visualization Tools	72	(1)
Debugging Strategies	73	(1)
Evaluating Programs Empirically	74	(2)
Comments on Optimizing the Parallel Code	76	(1)
2.5 Summary	77	(1)
Further Reading	77	(1)
Bibliography	78	(2)
Problems	80	(2)
CHAPTER 3 EMBARRASSINGLY PARALLEL COMPUTATIONS	82	(25)
3.1 Ideal Parallel Computation	82	(2)
3.2 Embarrassingly Parallel Examples	84	(16)
Geometrical Transformations of Images	84	(5)
Mandelbrot Set	89	(6)
Monte Carlo Methods	95	(5)
3.3 Summary	100	(1)
Further Reading	100	(1)
Bibliography	101	(1)
Problems	102	(5)
CHAPTER 4 PARTITIONING AND DIVIDE-AND-CONQUER STRATEGIES	107	(32)
4.1 Partitioning	107	(11)
Partitioning Strategies	107	(4)
Divide and Conquer	111	(6)
M-ary Divide and Conquer	117	(1)
4.2 Divide-and-Conquer Examples	118	(13)
Sorting Using Bucket Sort	118	(4)
Numerical Integration	122	(4)
N-Body Problem	126	(5)
4.3 Summary	131	(1)
Further Reading	131	(1)
Bibliography	132	(1)
Problems	133	(6)
CHAPTER 5 PIPELINED COMPUTATIONS	139	(23)
5.1 Pipeline Technique	139	(4)
5.2 Computing Platform for Pipelined Applications	143	(1)
5.3 Pipeline Program Examples	144	(12)
Adding Numbers	144	(3)
Sorting Numbers	147	(4)
Prime Number Generation	151	(2)
Solving a System of Linear Equations--Special Case	153	(3)
5.4 Summary	156	(1)
Further Reading	157	(1)
Bibliography	157	(1)
Problems	158	(4)
CHAPTER 6 SYNCHRONOUS COMPUTATIONS	162	(36)
6.1 Synchronization	162	(7)
Barrier	162	(2)
Counter Implementation	164	(2)
Tree Implementation	166	(1)
Butterfly Barrier	166	(2)
Local Synchronization	168	(1)
Deadlock	168	(1)
6.2 Synchronized Computations	169	(4)
Data Parallel Computations	169	(3)
Synchronous Iteration	172	(1)
6.3 Synchronous Iteration Program Examples	173	(16)
Solving a System of Linear Equations by Iteration	173	(6)
Heat Distribution Problem	179	(9)
Cellular Automata	188	(1)
6.4 Summary	189	(1)
Further Reading	190	(1)
Bibliography	190	(1)
Problems	191	(7)
CHAPTER 7 LOAD BALANCING AND TERMINATION DETECTION	198	(29)
7.1 Load Balancing	198	(2)
7.2 Dynamic Load Balancing	200	(7)
Centralized Dynamic Load Balancing	201	(1)
Decentralized Dynamic Load Balancing	202	(2)
Load Balancing Using a Line Structure	204	(3)
7.3 Distributed Termination Detection Algorithms	207	(4)
Termination Conditions	207	(1)
Using Acknowledgment Messages	208	(1)
Ring Termination Algorithms	209	(2)
Fixed Energy Distributed Termination Algorithm	211	(1)
7.4 Program Example	211	(9)
Shortest Path Problem	211	(1)
Graph Representation	212	(2)
Searching a Graph	214	(6)
7.5 Summary	220	(1)
Further Reading	220	(1)
Bibliography	221	(1)
Problems	222	(5)
CHAPTER 8 PROGRAMMING WITH SHARED MEMORY	227	(38)
8.1 Shared Memory Multiprocessors	227	(3)
8.2 Constructs for Specifying Parallelism	230	(6)
Creating Concurrent Processes	230	(1)
Threads	231	(5)
8.3 Sharing Data	236	(14)
Creating Shared Data	236	(1)
Accessing Shared Data	236	(8)
Language Constructs for Parallelism	244	(1)
Dependency Analysis	245	(3)
Shared Data in Systems with Caches	248	(2)
8.4 Program Examples	250	(7)
UNIX Processes	251	(3)
Pthreads Example	254	(2)
Java Example	256	(1)
8.5 Summary	257	(1)
Further Reading	258	(1)
Bibliography	258	(1)
Problems	259	(6)
PART II ALGORITHMS AND APPLICATIONS	265	(133)
CHAPTER 9 SORTING ALGORITHMS	267	(34)
9.1 General	267	(3)
Sorting	267	(1)
Potential Speedup	268	(1)
Rank Sort	268	(2)
9.2 Compare-and-Exchange Sorting Algorithms	270	(25)
Compare and Exchange	270	(3)
Bubble Sort and Odd-Even Transposition Sort	273	(4)
Two-Dimensional Sorting	277	(3)
Mergesort	280	(2)
Quicksort	282	(2)
Quicksort on a Hypercube	284	(6)
Odd-Even Mergesort	290	(1)
Bitonic Mergesort	291	(4)
9.3 Summary	295	(1)
Further Reading	295	(1)
Bibliography	296	(1)
Problems	297	(4)
CHAPTER 10 NUMERICAL ALGORITHMS	301	(30)
10.1 Matrices--A Review	301	(2)
Matrix Addition	301	(1)
Matrix Multiplication	302	(1)
Matrix-Vector Multiplication	302	(1)
Relationship of Matrices to Linear Equations	303	(1)
10.2 Implementing Matrix Multiplication	303	(10)
Algorithm	303	(1)
Direct Implementation	304	(3)
Recursive Implementation	307	(2)
Mesh Implementation	309	(4)
Other Matrix Multiplication Methods	313	(1)
10.3 Solving a System of Linear Equations	313	(4)
Linear Equations	313	(1)
Gaussian Elimination	314	(1)
Parallel Implementation	315	(2)
10.4 Iterative Methods	317	(9)
Jacobi Iteration	318	(3)
Faster Convergence Methods	321	(5)
10.5 Summary	326	(1)
Further Reading	326	(1)
Bibliography	326	(1)
Problems	327	(4)
CHAPTER 11 IMAGE PROCESSING	331	(36)
11.1 Low-Level Image Processing	331	(2)
11.2 Point Processing	333	(1)
11.3 Histogram	334	(1)
11.4 Smoothing, Sharpening, and Noise Reduction	335	(5)
Mean	335	(1)
Median	336	(2)
Weighted Masks	338	(2)
11.5 Edge Detection	340	(4)
Gradient and Magnitude	340	(1)
Edge Detection Masks	341	(3)
11.6 The Hough Transform	344	(4)
11.7 Transformation into the Frequency Domain	348	(13)
Fourier Series	348	(1)
Fourier Transform	349	(1)
Fourier Transforms in Image Processing	350	(2)
Parallelizing the Discrete Fourier Transform Algorithm	352	(4)
Fast Fourier Transform	356	(5)
11.8 Summary	361	(1)
Further Reading	362	(1)
Bibliography	362	(2)
Problems	364	(3)
CHAPTER 12 SEARCHING AND OPTIMIZATION	367	(31)
12.1 Applications and Techniques	367	(1)
12.2 Branch-and-Bound Search	368	(4)
Sequential Branch and Bound	368	(2)
Parallel Branch and Bound	370	(2)
12.3 Genetic Algorithms	372	(12)
Evolution and Genetic Algorithms	372	(2)
Sequential Genetic Algorithms	374	(1)
Initial Population	374	(2)
Selection Process	376	(1)
Offspring Production	377	(2)
Variations	379	(1)
Termination Conditions	379	(1)
Parallel Genetic Algorithms	380	(4)
12.4 Successive Refinement	384	(1)
12.5 Hill Climbing	385	(4)
Banking Application	386	(2)
Hill Climbing in a Banking Application	388	(1)
Parallelization	389	(1)
12.6 Summary	389	(1)
Further Reading	389	(1)
Bibliography	390	(1)
Problems	391	(7)
APPENDIX A BASIC PVM ROUTINES	398	(6)
APPENDIX B BASIC MPI ROUTINES	404	(6)
APPENDIX C BASIC PTHREAD ROUTINES	410	(5)
APPENDIX D PARALLEL COMPUTATION MODELS	415	(11)
INDEX	426