Parallel Computing is a compelling vision of how computation can seamlessly scale from a single processor to virtually limitless computing power. Unfortunately, the scaling of application performance has not matched peak speed, and the programming burden for these machines remains heavy. The applications must be programmed to exploit parallelism in the most efficient way possible. Today, the responsibility for achieving the vision of scalable parallelism remains in the hands of the application developer.
This book represents the collected knowledge and experience of over 60 leading parallel computing researchers. They offer students, scientists and engineers a complete sourcebook with solid coverage of parallel computing hardware, programming considerations, algorithms, software and enabling technologies, as well as several parallel application case studies. The Sourcebook of Parallel Computing offers extensive tutorials and detailed documentation of the advanced strategies produced by research over the last two decades application case studies. The Sourcebook of Parallel Computing offers extensive tutorials and detailed documentation of the advanced strategies produced by research over the last two decades * Provides a solid background in parallel computing technologies * Examines the technologies available and teaches students and practitioners how to select and apply them * Presents case studies in a range of application areas including Chemistry, Image Processing, Data Mining, Ocean Modeling and Earthquake Simulation * Considers the future development of parallel computing technologies and the kinds of applications they will support
Author(s): Jack Dongarra, Ian Foster, Geoffrey C. Fox, William Gropp, Ken Kennedy, Linda Torczon, Andy White
Series: The Morgan Kaufmann Series in Computer Architecture and Design
Publisher: Morgan Kaufmann
Year: 2003
Language: English
Pages: 852
Cover......Page 1
PREFACE......Page 4
Using This Book......Page 5
Acknowledgments......Page 6
Contents......Page 8
Parallelism......Page 23
Introduction......Page 24
1.1 Parallel Computing Hardware......Page 25
1.2 What Have We Learned from Applications?......Page 29
1.3 Software and Algorithms......Page 32
1.4 Toward a Science of Parallel Computation......Page 34
Parallel Computer Architectures......Page 36
2.1 Uniprocessor Architecture......Page 37
2.2 Parallel Architectures......Page 47
2.3 Future Directions for Parallel Architectures......Page 61
2.4 Conclusion......Page 62
Parallel Programming Considerations......Page 64
3.1 Architectural Considerations......Page 66
3.2 Decomposing Programs for Parallelism......Page 70
3.3 Enhancing Parallel Performance......Page 77
3.4 Memory- Hierarchy Management......Page 84
3.5 Parallel Debugging......Page 87
3.6 Performance Analysis and Tuning......Page 88
3.7 Parallel Input/ Output......Page 90
Further Reading......Page 91
Applications......Page 93
4.1 Application Characteristics in a Simple Example......Page 95
Poisson s Equation......Page 99
4.3 Communication Overhead for More General Update Stencils......Page 102
4.4 Applications as Basic Complex Systems......Page 104
4.5 Time- Stepped and Event- Driven Simulations......Page 107
4.6 Temporal Structure of Applications......Page 108
4.7 Summary of Parallelization of Basic Complex Systems......Page 109
4.8 Meta- Problems......Page 110
4.9 Conclusion......Page 111
Parallel Computing in Computational Fluid Dynamics......Page 113
5.1 Introduction to Computational Fluid Dynamics......Page 114
5.2 Incompressible Flows......Page 118
5.3 Compressible Flows......Page 152
5.4 Conclusion......Page 164
Parallel Computing in Environment and Energy......Page 165
6.1 Subsurface- Flow Modeling......Page 166
6.2 IPARS and Grid Computing by NetSolve......Page 172
6.3 Tracking and Interactive Simulation in IPARS......Page 175
6.4 Surface- Water Simulation......Page 179
6.5 A Coupled Simulation of Flow and Transport with ADR......Page 182
6.6 Conclusion......Page 185
Parallel Computational Chemistry: An Overview of NWChem......Page 186
7.1 Molecular Quantum Chemistry......Page 187
7.2 The NWChem Architecture......Page 190
7.3 NWChem Parallel Computing Support......Page 193
7.4 NWChem Chemistry Modules......Page 197
Community......Page 205
Computational Chemistry Algorithms......Page 207
7.7 Conclusion......Page 211
8.1 Numerical ( General) Relativity......Page 214
8.2 Numerical Simulations in Lattice Quantum Chromodynamics......Page 218
8.3 Ocean Modeling......Page 226
8.4 Simulations of Earthquakes......Page 231
8.5 Cosmological Structure Formation......Page 238
8.6 Computational Electromagnetics......Page 246
8.7 Parallel Algorithms in Data Mining......Page 251
8.8 High- Performance Computing in Signal and Image Processing......Page 262
8.9 Deterministic Monte Carlo Methods and Parallelism......Page 268
at Photon Sources......Page 277
for Forces Modeling and Simulation......Page 284
8.12 Computational Structure of Applications......Page 299
8.13 Conclusion......Page 309
Software Technologies......Page 310
Software Technologies......Page 312
9.1 Selecting a Parallel Program Technology......Page 313
9.2 Achieving Correct and Ef cient Execution......Page 327
9.3 Conclusion......Page 329
Message Passing and Threads......Page 332
10.1 Message- Passing Programming Model......Page 333
10.2 Multithreaded Programming......Page 342
10.3 Conclusion......Page 348
Parallel I/ O......Page 349
11.1 Parallel I/ O Infrastructure......Page 351
11.2 Overview of MPI- IO......Page 357
11.3 Parallel I/ O Optimizations......Page 362
11.4 How Can Users Achieve High I/ O Performance?......Page 366
11.5 Conclusion......Page 373
Languages and Compilers......Page 374
12.1 Automatic Parallelization......Page 376
12.2 Data- Parallel Programming in High Performance Fortran......Page 378
12.3 Shared- Memory Parallel Programming in OpenMP......Page 383
Co- Array Fortran......Page 388
12.5 Supporting Technologies......Page 394
12.6 Future Trends......Page 395
12.7 Conclusion......Page 396
Further Reading......Page 397
Parallel Object- Oriented Libraries......Page 399
13.1 Object- Oriented Parallel Libraries......Page 400
13.2 Object- Oriented Parallel Programming in Java......Page 407
13.3 Multithreaded Computation in C+ +......Page 412
13.4 Remote Function Calls, Global Pointers, and Java RMI......Page 417
13.5 Component- Based Software Design......Page 419
13.6 Conclusion......Page 422
Problem- Solving Environments......Page 424
14.1 NetSolve: Network- Enabled Solvers......Page 426
14.2 WebFlow- Object Web Computing......Page 433
14.3 WebPDELab......Page 444
14.4 Other Grid- Computing Environments......Page 455
14.5 Conclusion......Page 457
Tools for Performance Tuning and Debugging......Page 458
15.1 Correctness and Performance Monitoring Basics......Page 459
15.2 Measurement and Debugging Implementation Challenges......Page 466
15.3 Deep Compiler Integration......Page 468
15.4 Software Tool Interfaces and Usability......Page 471
15.5 Software Tool Examples......Page 474
15.7 Conclusion......Page 481
15.8 Further Reading......Page 482
16.1 The Mathematical Model......Page 484
16.3 Parallel Solution of Poisson s Equation......Page 485
16.4 Adding Global Operations......Page 492
Enabling Technologies and Algorithms......Page 496
17.1 Templates: Design Patterns for Parallel Software......Page 498
17.2 Communicators and Data Structure Neutrality......Page 499
17.3 Standard Libraries and Components......Page 500
17.4 Automatic Differentiation......Page 501
17.5 Templates and Numerical Linear Algebra......Page 502
17.6 Conclusion......Page 504
Graph Partitioning for High-Performance......Page 506
18.1 Modeling Mesh- Based Computations as Graphs......Page 508
18.2 Static Graph- Partitioning Techniques......Page 510
18.3 Load Balancing of Adaptive Computations......Page 531
18.4 Parallel Graph Partitioning......Page 540
18.5 Multiconstraint, Multiobjective Graph Partitioning......Page 541
18.6 Conclusion......Page 553
Mesh Generation......Page 557
19.1 Mesh- Generation Strategies and Techniques......Page 558
19.2 Mesh- Generation Process and Geometry Preparation......Page 564
19.3 Adaptive Mesh Generation......Page 566
19.4 Parallel Mesh Generation......Page 574
19.5 Mesh Software......Page 575
19.6 Mesh Con gurations......Page 578
19.7 Mesh Web Sites......Page 581
19.8 The Pacing Obstacle: Geometry/ Mesh Generation......Page 583
19.9 Desiderata......Page 585
19.10 Conclusion......Page 586
Templates and Numerical Linear Algebra......Page 588
20.1 Dense Linear Algebra Algorithms......Page 589
20.2 The In uence of Computer Architecture on Performance......Page 593
20.3 Dense Linear Algebra Libraries......Page 596
20.4 Sparse Linear Algebra Methods......Page 603
20.5 Direct Solution Methods......Page 604
20.6 Iterative Solution Methods......Page 609
20.7 Sparse Eigenvalue Problems......Page 616
20.8 Conclusion......Page 632
Software for the Scalable Solution of Partial Differential Equations......Page 634
21.1 PDE Background......Page 635
21.2 Challenges in Parallel PDE Computations......Page 636
21.3 Parallel Solution Strategies......Page 640
21.4 PETSc Approach to Parallel Software for PDEs......Page 641
21.5 Software for PDEs......Page 658
21.6 Conclusion......Page 660
Parallel Continuous Optimization......Page 661
22.1 Local Optimization......Page 663
22.2 Global Optimization......Page 665
22.3 Direct Search Methods......Page 671
22.4 Optimization of Linked Subsystems......Page 675
22.5 Variable and Constraint Distribution......Page 678
22.6 Conclusion......Page 681
Path Following in Scientific Computing and Its Implementation in AUTO......Page 683
23.1 Local Continuation......Page 685
23.2 Global Continuation and Degree Theory......Page 687
23.3 Folds and Bifurcations......Page 689
23.4 Practical Path Following......Page 691
23.5 Branch Switching at Bifurcations......Page 695
23.6 Computational Examples: AUTO......Page 698
23.7 Parallel AUTO......Page 706
23.8 Conclusion......Page 711
Automatic Differentiation......Page 713
24.1 Overview of Automatic Differentiation......Page 715
24.2 Automatic- Differentiation Implementation Techniques......Page 719
24.3 Automatic- Differentiation Software......Page 721
24.4 Automatic Differentiation of Message- Passing Parallel Codes......Page 723
24.5 Advanced Use of Automatic Differentiation......Page 726
24.6 Conclusion......Page 731
Conclusion......Page 732
25.1 Computational Resources......Page 734
25.2 Applications......Page 735
25.3 Software......Page 736
25.5 Signposts......Page 738
REFERENCES......Page 740
INDEX......Page 801
ABOUT THE AUTHORS......Page 843
