Parallel Computing Works! (eBook)

Front Cover 1
Parallel Computing Works! 4
Copyright Page 5
Table of Contents 6
Color Plates 514
Preface 18
Chapter 1. Introduction 20
1.1 Introduction 20
1.2 The National Vision for Parallel Computation 21
1.3 Caltech Concurrent Computation Program 24
1.4 How Parallel Computing Works 28
Chapter 2. Technical Backdrop 32
2.1 Introduction 32
2.2 Hardware Trends 33
2.3 Software 46
2.4 Summary 50
Chapter 3. A Methodology for Computation 52
3.1 Introduction 52
3.2 The Process of Computation and Complex Systems 55
3.3 Examples of Complex Systems and Their Space-Time Structure 61
3.4 The Temporal Properties of Complex Systems 64
3.5 Spatial Properties of Complex Systems 69
3.6 Compound Complex Systems 74
3.7 Mapping Complex Systems 77
3.8 Parallel Computing Works? 78
Chapter 4. Synchronous Applications 84
4.1 QCD and the Beginning of C3P 84
4.2 Synchronous Applications 92
4.3 Quantum Chromodynamics 99
4.4 Spin Models 118
4.5 An Automata Model of Granular Materials 139
Chapter 5. Express and CrOS — 
150 
5.1 Multicomputer Operating Systems 150
5.2 A "Packet" History of Message-passing Systems 152
5.3 Parallel Debugging 172
5.4 Parallel Profiling 186
Chapter 6. Synchronous Applications II 198
6.1 Computational Issues in Synchronous Problems 198
6.2 Convectively-Dominated Flows and the 
202 
6.3 Magnetism in the High-Temperature 
208 
6.4 Phase Transitions in Two-dimensional 
222 
6.5 A Hierarchical Scheme for Surface 
234 
6.6 Character Recognition by Neural Nets 250
6.7 An Adaptive Multiscale Scheme for 
263 
6.8 Collective Stereopsis 269
Chapter 7. Independent Parallelism 276
7.1 Embarrassingly Parallel Problem Structure 276
7.2 Dynamically Triangulated Random Surfaces 278
7.3 Numerical Study of High-Tc Spin Systems 290
7.4 Statistical Gravitational Lensing 293
7.5 Parallel Random Number Generators 297
7.6 Parallel Computing in Neurobiology: The GENESIS Project 298
Chapter 8. Full Matrix Algorithms and 
308 
8.1 Full and Banded Matrix Algorithms 308
8.2 Quantum Mechanical Reactive Scattering Using a High-Performance Parallel Computer 327
8.3 Studies of Electron-Molecule Collisions on Distributed-Memory Parallel Computers 339
Chapter 9. Loosely Synchronous Problems 352
9.1 Problem Structure 352
9.2 Geomorphology by Micromechanical Simulations 357
9.3 Plasma Particle-in-Cell Simulation of an 
360 
9.4 Computational Electromagnetics 368
9.5 LU Factorization of Sparse, Unsymmetric Jacobian Matrices 373
9.6 Concurrent DASSL Applied to Dynamic 
392 
9.7 Adaptive Multigrid 409
9.8 Munkres Algorithm for Assignment 414
9.9 Optimization Methods for Neural Nets: Automatic Parameter Tuning and Faster 
426 
Chapter 10. DIME Programming Environment 434
10.1 DIME Portable Software for Irregular 
 
434 
10.2 DIMEFEM: High-level Portable Irregular-Mesh Finite-Element Solver 444
Chapter 11. Load Balancing and Optimization 450
11.1 Load Balancing as an Optimization Problem 450
11.2 Applications and Extensions of the Physical Analogy 487
11.3 Physical Optimization 490
11.4 An Improved Method for the Travelling Salesman Problem 492
Chapter 12. Irregular Loosely 
500 
12.1 Irregular Loosely Synchronous Problems Are Hard 500
12.2 Simulation of the Electrosensory System of the Fish Gnathonemus petersii 502
12.3 Transonic Flow 508
12.4 Tree Codes for N-body Simulations 513
12.5 Fast Vortex Algorithm and Parallel 
542 
12.6 Cluster Algorithms for Spin Models 551
12.7 Sorting 557
12.8 Hierarchical Tree-Structures as Adaptive Meshes 569
Chapter 13. Data Parallel C and Fortran 580
13.1 High-Level Languages 580
13.2 A Software Tool for Data Partitioning and Distribution 591
13.3 Fortran 90 Experiments 610
13.4 Optimizing Compilers by Neural Networks 611
13.5 ASPAR 615
13.6 Coherent Parallel C 628
13.7 Hierarchical Memory 630
Chapter 14. Asynchronous Applications 638
14.1 Asynchronous Problems and a Summary of Basic Problem Classes 638
14.2 Melting in Two Dimensions 646
14.3 Computer Chess 651
Chapter 15. High-Level Asynchronous Software Systems 670
15.1 Asynchronous Software Paradigms 670
15.2 MOOS II: An Operating System for 
673 
15.3 Time Warp 677
Chapter 16. The Zipcode Message-Passing System 682
16.1 Overview of Zipcode 682
16.2 Low-Level Primitives 687
16.3 High-Level Primitives 695
16.4 Details of Execution 703
16.5 Conclusions 705
Chapter 17. MOVIE—Multitasking 
706 
17.1 Introduction 706
17.2 System Overview 710
17.3 Map Separates 746
17.4 The Ultimate User Interface: Virtual 
764 
Chapter 18. Complex System Simulation 
774 
18.1 MetaProblems and MetaSoftware 774
18.2 ISIS: An Interactive Seismic Imaging System 783
18.3 Parallel Simulations that Emulate Function 794
18.4 Multitarget Tracking 805
Chapter 19. Parallel Computing in Industry 822
19.1 Motivation 822
19.2 Examples of Industrial Applications 824
Chapter 20. Computational Science 830
20.1 Lessons 830
20.2 Computational Science 831
Appendices 17
Appendix A: C3P Reports 838
Appendix B: Selected Biographic Information 888
Bibliography 912
Index 1006