Parallel Computations

Parallel Computations focuses on parallel computation, with emphasis on algorithms used in a variety of numerical and physical applications and for many different types of parallel computers. Topics covered range from vectorization of fast Fourier transforms (FFTs) and of the incomplete Cholesky conjugate gradient (ICCG) algorithm on the Cray-1 to calculation of table lookups and piecewise functions. Single tridiagonal linear systems and vectorized computation of reactive flow are also discussed.

Comprised of 13 chapters, this volume begins by classifying parallel computers and describing techniques for performing matrix operations on them. The reader is then introduced to FFTs and the tridiagonal linear system as well as the ICCG method. Different versions of the conjugate gradient method for solving the time-dependent diffusion equation are considered. Subsequent chapters deal with two- and three-dimensional fluid flow calculations, paying particular attention to the principal issues in designing efficient numerical methods for hydrodynamic calculations; the decisions that a numerical modeler must make to optimize chemically reactive flow simulations; and how to handle disk-to-core data transfer and storage allocation for the solution of the implicit equations for three-dimensional flows. The book also describes the time-split finite difference scheme for solving the two-dimensional Navier-Stokes equation for flows through slotted nozzles. Finally, the large-scale stimulation of plasmas, as carried out on a small computer with an array processor, is discussed.

This monograph should be of interest to specialists in computer science.

Contenu

List of Contributors
Preface
A Guide to Parallel Computation and Some Cray-1 Experiences
I. Introduction
II. Hardware
III. Theoretical Considerations
IV. Applications
Appendix A. A Register Assignment for Sparse-Banded Matrix Multiply
Appendix B. Factor and Forward Substitution
Appendix C. Backward Substitution
Appendix D. Factorization Only
References
Vectorizing the FFTs
I. Introduction
II. Preliminaries
III. The Complex FFT Algorithms
IV. Vectorizing Multiple Transforms
V. Transforming Real Sequences
VI. The Symmetric Transforms
VII. Software and Summary
References
Solution of Single Tridiagonal Linear Systems and Vectorization of the ICCG Algorithm on the Cray-1
I. A Vector Algorithm for Tridiagonal Linear Systems
II. An Incomplete Cholesky Conjugate Gradient (ICCG) Algorithm for the Cray-1 Computer
III. Cyclic Reduction on Future Machines
References
An Implicit Numerical Solution of the Two-Dimensional Diffusion Equation and Vectorization Experiments
I. Introduction
II. Spatial Differencing
III. Matrix Formulation
IV. Properties of the Matrix A
V. Method of Lines
VI. The Generalized Conjugate Gradient Algorithm
VII. Computational Example
VIII. Comments and Conclusions
References
Swimming Upstream: Calculating Table Lookups and Piecewise Functions
I. Introduction to Table Lookup
II. Evaluating Algorithms on Vector Processors
III. Basic Processes on Vector Processors
IV. One-Dimensional Problems
V. Two-Dimensional Problems: Equations of State
References
Trade-Offs in Designing Explicit Hydrodynamical Schemes for Vector Computers
I. Introduction
II. Why Vectorization of Explicit Hydrodynamical Schemes Should Be Easy
III. Why Vectorization of Explicit Hydrodynamical Schemes Can Be Difficult
IV. Alternative Approaches and Their Costs on Vector Computers 160
V. The Example of the Interaction of Two Blast Waves
VI. Conclusions
References
Vectorized Computation of Reactive Flow
I. Introduction and Statement of the Problem
II. Vectorization and Optimization
III. Techniques for Modeling Fast Time Scales
IV. Techniques for Modeling Short Space Scales
V. Techniques for Dealing with Physical and Geometric Complexity
VI. Programming Guidelines and Summary of Parallelism Principles
References
A Fully Implicit, Factored Code for Computing Three-Dimensional Flows on the ILLIAC IV
I. Introduction
II. Basic Equations
III. ILLIAC Architecture
IV. Data-Base Considerations
V. The ILLIAC Code ARC3
VI. Results
VII. Concluding Remarks
References
A Time-Split Difference Scheme for the Compressible Navier-Stokes Equations with Applications to Flows in Slotted Nozzles
I. Introduction
II. The Difference Scheme
III. The Application
IV. The Implementation
V. Results
Appendix. Numerical Grid Generation
References
Geophysical Fluid Simulation on a Parallel Computer
I. Introduction
II. The Salient Characteristics of the ASC
III. The FORTRAN Compiler on the ASC
IV. The Physical Processes of a Model
V. Estimating Parallelism in Models
VI. Conclusion
Experiences with a Floating Point Systems Array Processor
I. Introduction
II. Scientific Computing beyond the CDC 7600
III. The AP-190L Installation at Cornell
IV. FPS Array Processors and Parallel Computing
V. Examples of Optimal Programming for the AP
VI. The Two-Machine Environment
VII. Practical Problems of AP Ownership
VIII. Conclusions
References
A Case Study in the Application of a Tightly Coupled Multiprocessor to Scientific Computations
I. Introduction
II. Tightly Coupled Multiprocessors
III. Case Studies
IV. Conclusions
Appendix. Implementing Parallel Algorithms
References
Computer Modeling in Plasma Physics on the Parallel-Architecture CHI Computer
I. Introduction
II. Formulation of the Simulation Problems
III. Design of the Computer System
IV. Programming for Efficiency
V. Observations and Speculations
References
Index