Parallel programming: techniques and applications using networked workstations and parallel computers

Cover......Page 1
Contents......Page 14
Preface......Page 6
About the Authors......Page 12
PART I: BASIC TECHNIQUES......Page 22
  1.1 The Demand for Computational Speed......Page 24
  1.2 Potential for Increased Computational Speed......Page 27
  1.3 Types of Parallel Computers......Page 34
  1.4 Cluster Computing......Page 47
  Further Reading......Page 59
  Bibliography......Page 60
  Problems......Page 62
  2.1 Basics of Message-Passing Programming......Page 63
  2.2 Using a Cluster of Computers......Page 72
  2.3 Evaluating Parallel Programs......Page 83
  2.4 Debugging and Evaluating Parallel Programs Empirically......Page 91
  Further Reading......Page 96
  Bibliography......Page 97
  Problems......Page 98
  3.1 Ideal Parallel Computation......Page 100
  3.2 Embarrassingly Parallel Examples......Page 102
  3.3 Summary......Page 119
  Bibliography......Page 120
  Problems......Page 121
  4.1 Partitioning......Page 127
  4.2 Partitioning and Divide-and-Conquer Examples......Page 138
  Further Reading......Page 152
  Bibliography......Page 153
  Problems......Page 154
  5.1 Pipeline Technique......Page 161
  5.2 Computing Platform for Pipelined Applications......Page 165
  5.3 Pipeline Program Examples......Page 166
  5.4 Summary......Page 178
  Problems......Page 179
  6.1 Synchronization......Page 184
  6.2 Synchronized Computations......Page 191
  6.3 Synchronous Iteration Program Examples......Page 195
  6.4 Partially Synchronous Methods......Page 212
  Bibliography......Page 214
  Problems......Page 215
  7.1 Load Balancing......Page 222
  7.2 Dynamic Load Balancing......Page 224
  7.3 Distributed Termination Detection Algorithms......Page 231
  7.4 Program Example......Page 235
  Further Reading......Page 244
  Bibliography......Page 245
  Problems......Page 246
  8.1 Shared Memory Multiprocessors......Page 251
  8.2 Constructs for Specifying Parallelism......Page 253
  8.3 Sharing Data......Page 260
  8.4 Parallel Programming Languages and Constructs......Page 268
  8.5 OpenMP......Page 274
  8.6 Performance Issues......Page 279
  8.7 Program Examples......Page 286
  8.8 Summary......Page 292
  Bibliography......Page 293
  Problems......Page 294
  9.1 Distributed Shared Memory......Page 300
  9.2 Implementing Distributed Shared Memory......Page 302
  9.3 Achieving Consistent Memory in a DSM System......Page 305
  9.4 Distributed Shared Memory Programming Primitives......Page 307
  9.5 Distributed Shared Memory Programming......Page 311
  9.6 Implementing a Simple DSM system......Page 312
  Bibliography......Page 318
  Problems......Page 319
PART II: ALGORITHMS AND APPLICATIONS......Page 322
  10.1 General......Page 324
  10.2 Compare-and-Exchange Sorting Algorithms......Page 325
  10.3 Sorting on Specific Networks......Page 341
  10.4 Other Sorting Algorithms......Page 348
  Further Reading......Page 356
  Bibliography......Page 357
  Problems......Page 358
  11.1 Matrices—A Review......Page 361
  11.2 Implementing Matrix Multiplication......Page 363
  11.3 Solving a System of Linear Equations......Page 373
  11.4 Iterative Methods......Page 377
  Bibliography......Page 386
  Problems......Page 387
  12.1 Low-level Image Processing......Page 391
  12.2 Point Processing......Page 393
  12.3 Histogram......Page 394
  12.4 Smoothing, Sharpening, and Noise Reduction......Page 395
  12.5 Edge Detection......Page 400
  12.6 The Hough Transform......Page 404
  12.7 Transformation into the Frequency Domain......Page 408
  12.8 Summary......Page 421
  Bibliography......Page 422
  Problems......Page 424
  13.1 Applications and Techniques......Page 427
  13.2 Branch-and-Bound Search......Page 428
  13.3 Genetic Algorithms......Page 432
  13.4 Successive Refinement......Page 444
  13.5 Hill Climbing......Page 445
  Further Reading......Page 449
  Bibliography......Page 450
  Problems......Page 451
APPENDIX A: BASIC MPI ROUTINES......Page 458
APPENDIX B: BASIC PTHREAD ROUTINES......Page 465
APPENDIX C: OPENMP DIRECTIVES, LIBRARY FUNCTIONS, AND ENVIRONMENT VARIABLES......Page 470
 B......Page 481
 F......Page 482
 J......Page 483
 M......Page 484
 P......Page 485
 S......Page 486
 U......Page 487
 W......Page 488