ISBN 1-55860-253-4 Morgan Kaufmann Publishers, Inc. 1994 ordering information

What is Contained in Parallel Computing Works?

We briefly describe the contents of this book

Applications

The heart of this work is a set of applications largely developed at Caltech from 1985-1990 by the Caltech Concurrent Computation Group. These are linked to a set of tables and Glossaries

• Application Paradigms in High Performance Fortran
• Algorithms and Applications in High Performance Fortran
• Petaflop Application Categories developed at a workshop.
• A table developed by Fox in 1991-1993 to categorize New York State Industrial Applications of HPCC

Applications are classified into 5 problem classes:

Synchronous Applications, more in I and II

Such applications tend to be regular and characterised by algorithms employing simultaneous identical updates to a set of points, more in I and II

Loosely Synchronous Applications

Such applications are iterative or time-stepped but unlike the synchronous case, employ different evolution(update) procedures which synchronize macroscopically, , more in I , II and III

Embarrassingly Parallel Applications

Such applications can employ complex algorithms but can be parallelized because the evolution of different points is largely independent

Asynchronous Problems

These are hard to parallelize problems with no natural algorithmic synchronization between the evolution of linked irregular data points, more in I

Metaproblems

Such problems are hybrid integration of several subproblems of the other four basic application classes

Overview

This collection of over 40 succesful parallel applications is woven into a discussion of other key features of HPCC

• History of Parallel Computing as in pertained to work at Caltech
• A survey of the evolution of parallel machines
• Computer Architecture is not discussed in Parallel Computing Works
• Education was an interesting feature of the Caltech work as it showed the relevance of interdisciplinary education of the type now called computational science
• Software Systems and Approachs described later
• Algorithmic Technologies described later

Software Systems and Tools

• Operating Systems
• Parallel Computing Programming Paradigms
• Message Passing Software and its use in applications
• Data Parallel Programmimg model. This approach advanced rapidly in the last 5 years and Parallel Computing Works has been kept uptodate in areas such as High Performance Fortran and High Performance Fortran Forum
• Shared Memory Programming Model
• Cache Management on sequential machines and its relation to parallel computing where both cache and parallelism demand data locality.
• Software Tools is an important area but covered incompletely in Parallel Computing works
• Asynchronous Software i.e. what is needed for asynchronous problems includingEvent Driven Simulations
• Metasoftware which integrates the components of metaproblems

Algorithmic Technologies

Major topics include:

• Full Matrix Algorithms
• The harder Sparse matrix algorithms
• Load Balancing or automatic data decomposition
• Grid Generation for partial differential equations
• Optimization
• Simulated Annealing
• Sorting
• Branch and Bound

• Contents
• Foreword
• 1 Introduction
  • 1.1 Introduction
  • 1.2 The National Vision for ParallelComputation
  • 1.3 Caltech Concurrent Computation Program
  • 1.4 How Parallel Computing Works
• 2 Technical Backdrop
  • 2.1 Introduction
  • 2.2 Hardware Trends
    • 2.2.1 Parallel Scientific Computers Before 1980
    • 2.2.2 Early 1980s
    • 2.2.3 Birth of the Hypercube
    • 2.2.4 Mid-1980s
    • 2.2.5 Late 1980s
    • 2.2.6 Parallel Systems-1992
  • 2.3 Software
    • 2.3.1 Languages and Compilers
    • 2.3.2 Tools
  • 2.4 Summary
• 3 A Methodology for Computation
  • 3.1 Introduction
  • 3.2 The Process of Computation and ComplexSystems
  • 3.3 Examples of Complex Systems and TheirSpace-Time Structure
  • 3.4 The Temporal Properties of ComplexSystems
  • 3.5 Spatial Properties of Complex Systems
  • 3.6 Compound Complex Systems
  • 3.7 Mapping Complex Systems
  • 3.8 Parallel Computing Works?
• 4 Synchronous Applications I
  • 4.1 QCD and the Beginning of CP
  • 4.2 Synchronous Applications
  • 4.3 Quantum Chromodynamics
    • 4.3.1 Introduction
    • 4.3.2 Monte Carlo
    • 4.3.3 QCD
    • 4.3.4 Lattice QCD
    • 4.3.5 Concurrent QCD Machines
    • 4.3.6 QCD on the Caltech Hypercubes
    • 4.3.7 QCD on the Connection Machine
    • 4.3.8 Status and Prospects
  • 4.4 Spin Models
    • 4.4.1 Introduction
    • 4.4.2 Ising Model
    • 4.4.3 Potts Model
    • 4.4.4 XY Model
    • 4.4.5 O(3) Model
  • 4.5 An Automata Model of Granular Materials
    • 4.5.1 Introduction
    • 4.5.2 Comparison to Particle Dynamics Models
    • 4.5.3 Comparison to Lattice Gas Models
    • 4.5.4 The Rules for the Lattice Grain Model
    • 4.5.5 Implementation on a Parallel Computer
    • 4.5.6 Simulations
    • 4.5.7 Conclusion
• 5 Express and CrOS - Loosely Synchronous Message Passing
  • 5.1 Multicomputer Operating Systems
  • 5.2 A ``Packet'' History of Message-passingSystems
    • 5.2.1 Prehistory
    • 5.2.2 Application-driven Development
    • 5.2.3 Collective Communication
    • 5.2.4 Automated Decomposition-whoami
    • 5.2.5 ``Melting''-a Non-crystalline Problem
    • 5.2.6 The Mark III
    • 5.2.7 Host Programs
    • 5.2.8 A Ray Tracer-and an ``Operating System''
    • 5.2.9 The Crystal Router
    • 5.2.10 Portability
    • 5.2.11 Express
    • 5.2.12 Other Message-passing Systems
    • 5.2.13 What Did We Learn?
    • 5.2.14 Conclusions
  • 5.3 Parallel Debugging
    • 5.3.1 Introduction and History
    • 5.3.2 Designing a Parallel Debugger
    • 5.3.3 Conclusions
  • 5.4 Parallel Profiling
    • 5.4.1 Missing a Point
    • 5.4.2 Visualization
    • 5.4.3 Goals in Performance Analysis
    • 5.4.4 Overhead Analysis
    • 5.4.5 Event Tracing
    • 5.4.6 Data Distribution Analysis
    • 5.4.7 CPU Usage Analysis
    • 5.4.8 Why So Many Separate Tools?
    • 5.4.9 Conclusions
• 6 Synchronous Applications II
  • 6.1 Computational Issues in SynchronousProblems
  • 6.2 Convectively-Dominated Flows and theFlux-Corrected Transport Technique
    • 6.2.1 An Overview of the FCT Technique
    • 6.2.2 Mathematics and the FCT Algorithm
    • 6.2.3 Parallel Issues
    • 6.2.4 Example Problem
    • 6.2.5 Performance and Results
    • 6.2.6 Summary
  • 6.3 Magnetism in the High-TemperatureSuperconductor Materials
    • 6.3.1 Introduction
    • 6.3.2 The Computational Algorithm
    • 6.3.3 Parallel Implementation and Performance
    • 6.3.4 Physics Results
    • 6.3.5 Conclusions
  • 6.4 Phase Transitions in Two-dimensionalQuantum Spin Systems
    • 6.4.1 The case of : Antiferromagnetic Transitions
      • Origin of the Interaction
      • Simulation Results
      • Theoretical Interpretation
      • Comparison with Experiments
    • 6.4.2 The Case of : Quantum XY Model and theTopological Transition
      • A Brief History
      • Evidence for the Transition
      • Implications
  • 6.5 A Hierarchical Scheme for SurfaceReconstruction and Discontinuity Detection
    • 6.5.1 Multigrid Method with Discontinuities
    • 6.5.2 Interacting Line Processes
    • 6.5.3 Generic Look-up Table and Specific Parametrization
    • 6.5.4 Pyramid on a Two-Dimensional Mesh of Processors
    • 6.5.5 Results for Orientation Constraints
    • 6.5.6 Results for Depth Constraints
    • 6.5.7 Conclusions
  • 6.6 Character Recognition by Neural Nets
    • 6.6.1 MLP in General
    • 6.6.2 Character Recognition using MLP
    • 6.6.3 The Multiscale Technique
    • 6.6.4 Results
    • 6.6.5 Comments and Variants on the Method
  • 6.7 An Adaptive Multiscale Scheme for Real-Time Motion Field Estimation
    • 6.7.1 Errors in Computing the Motion Field
    • 6.7.2 Adaptive Multiscale Scheme on a Multicomputer
    • 6.7.3 Conclusions
  • 6.8 Collective Stereopsis
• 7 Independent Parallelism
  • 7.1 Embarrassingly Parallel Problem Structure
  • 7.2 Dynamically Triangulated Random Surfaces
    • 7.2.1 Introduction
    • 7.2.2 Discretized Strings
    • 7.2.3 Computational Aspects
    • 7.2.4 Performance of String Program
    • 7.2.5 Conclusion
  • 7.3 Numerical Study of High-T Spin Systems
  • 7.4 Statistical Gravitational Lensing
  • 7.5 Parallel Random Number Generators
  • 7.6 Parallel Computing in Neurobiology: The GENESIS Project
    • 7.6.1 What Is Computational Neurobiology?
    • 7.6.2 Parallel Computers?
    • 7.6.3 Problems with Most Present Day Parallel Computers
    • 7.6.4 What is GENESIS?
    • 7.6.5 Task Farming
    • 7.6.6 Distributed Modelling via the Postmaster Element
• 8 Full Matrix Algorithms and Their Applications
  • 8.1 Full and Banded Matrix Algorithms
    • 8.1.1 Matrix Decomposition
    • 8.1.2 Basic Matrix Arithmetic
    • 8.1.3 Matrix Multiplication for Banded Matrices
    • 8.1.4 Systems of Linear Equations
    • 8.1.5 The Gauss-Jordan Method
    • 8.1.6 Other Matrix Algorithms
    • 8.1.7 Concurrent Linear Algebra Libraries
    • 8.1.8 Problem Structure
    • 8.1.9 Conclusions
  • 8.2 Quantum Mechanical Reactive ScatteringUsing a High-Performance ParallelComputer
    • 8.2.1 Introduction
    • 8.2.2 Methodology
    • 8.2.3 Parallel Algorithm
    • 8.2.4 Results and Discussion
  • 8.3 Studies of Electron-Molecule Collisions onDistributed-Memory Parallel Computers
    • 8.3.1 Introduction
    • 8.3.2 The SMC Method and Its Implementation
    • 8.3.3 Parallel Implementation
    • 8.3.4 Performance
      • Mark IIIfp
      • Intel Machines
    • 8.3.5 Selected Results
    • 8.3.6 Conclusion
• 9 Loosely Synchronous Problems
  • 9.1 Problem Structure
  • 9.2 Geomorphology by Micromechanical Simulations
  • 9.3 Plasma Particle-in-Cell Simulation of anElectron Beam Plasma Instability
    • 9.3.1 Introduction
    • 9.3.2 GCPIC Algorithm
    • 9.3.3 Electron Beam Plasma Instability
    • 9.3.4 Performance Results for One-DimensionalElectrostatic Code
    • 9.3.5 One-Dimensional Electromagnetic Code
    • 9.3.6 Dynamic Load Balancing
    • 9.3.7 Summary
  • 9.4 Computational Electromagnetics
  • 9.5 LU Factorization of Sparse, Unsymmetric Jacobian Matrices
    • 9.5.1 Introduction
    • 9.5.2 Design Overview
    • 9.5.3 Reduced-Communication Pivoting
    • 9.5.4 New Data Distributions
    • 9.5.5 Performance Versus Scattering
    • 9.5.6 Performance
      • Order 13040 Example
      • Order 2500 Example
    • 9.5.7 Conclusions
  • 9.6 Concurrent DASSL Applied to Dynamic Distillation Column Simulation
    • 9.6.1 Introduction
    • 9.6.2 Mathematical Formulation
    • 9.6.3 proto-Cdyn - Simulation Layer
      • Template Structure
      • Problem Preformulation
    • 9.6.4 Concurrent Formulation
      • Overview
      • Single Integration Step
    • 9.6.5 Chemical Engineering Example
    • 9.6.6 Conclusions
  • 9.7 Adaptive Multigrid
    • 9.7.1 Introduction
    • 9.7.2 The Basic Algorithm
    • 9.7.3 The Adaptive Algorithm
    • 9.7.4 The Concurrent Algorithm
    • 9.7.5 Summary
  • 9.8 Munkres Algorithm for Assignment
    • 9.8.1 Introduction
    • 9.8.2 The Sequential Algorithm
    • 9.8.3 The Concurrent Algorithm
  • 9.9 Optimization Methods for Neural Nets:Automatic Parameter Tuning and FasterConvergence
    • 9.9.1 Deficiencies of Steepest Descent
    • 9.9.2 The ``Bold Driver'' Network
    • 9.9.3 The Broyden-Fletcher-Goldfarb-Shanno One-StepMemoryless Quasi-Newton Method
    • 9.9.4 Parallel Optimization
    • 9.9.5 Experiment: the Dichotomy Problem
    • 9.9.6 Experiment: Time Series Prediction
    • 9.9.7 Summary
• 10 DIME Programming Environment
  • 10.1 DIME: Portable Software for IrregularMeshes for Parallel or SequentialComputers
    • 10.1.1 Applications and Extensions
    • 10.1.2 The Components of DIME
    • 10.1.3 Domain Definition
    • 10.1.4 Mesh Structure
    • 10.1.5 Refinement
    • 10.1.6 Load Balancing
    • 10.1.7 Summary
  • 10.2 DIMEFEM: High-level Portable Irregular-Mesh Finite-Element Solver
    • 10.2.1 Memory Allocation
    • 10.2.2 Operations and Elements
    • 10.2.3 Navier-Stokes Solver
    • 10.2.4 Results
    • 10.2.5 Summary
• 11 Load Balancing and Optimization
  • 11.1 Load Balancing as an Optimization Problem
    • 11.1.1 Load Balancing a Finite-Element Mesh
    • 11.1.2 The Optimization Problem and Physical Analogy
    • 11.1.3 Algorithms for Load Balancing
    • 11.1.4 Simulated Annealing
    • 11.1.5 Recursive Bisection
    • 11.1.6 Eigenvalue Recursive Bisection
    • 11.1.7 Testing Procedure
    • 11.1.8 Test Results
    • 11.1.9 Conclusions
  • 11.2 Applications and Extensions of the Physical Analogy
  • 11.3 Physical Optimization
  • 11.3.1 An Improved Method for the Travelling Salesman Problem
    • 11.4.1 Background on Local Search Heuristics
    • 11.4.2 Background on Markov Chains and SimulatedAnnealing
    • 11.4.3 The New Algorithm-Large-Step Markov Chains
    • 11.4.4 Results
• 12 Irregular Loosely Synchronous Problems
  • 12.1 Irregular Loosely Synchronous Problems Are Hard
  • 12.2 Simulation of the Electrosensory System of the Fish Gnathonemus petersii
    • 12.2.1 Physical Model
    • 12.2.2 Mathematical Theory
    • 12.2.3 Results
    • 12.2.4 Summary
  • 12.3 Transonic Flow
    • 12.3.1 Compressible Flow Algorithm
    • 12.3.2 Adaptive Refinement
    • 12.3.3 Examples
    • 12.3.4 Performance
    • 12.3.5 Summary
  • 12.4 Tree Codes for N-body Simulations
    • 12.4.1 Oct-Trees
    • 12.4.2 Computing Forces
    • 12.4.3 Parallelism in Tree Codes
    • 12.4.4 Acquiring Locally Essential Data
    • 12.4.5 Comments on Performance
  • 12.5 Fast Vortex Algorithm and ParallelComputing
    • 12.5.1 Vortex Methods
    • 12.5.2 Fast Algorithms
    • 12.5.3 Hypercube Implementation
    • 12.5.4 Efficiency of Parallel Implementation
    • 12.5.5 Results
  • 12.6 Cluster Algorithms for Spin Models
    • 12.6.1 Monte Carlo Calculations of Spin Models
    • 12.6.2 Cluster Algorithms
    • 12.6.3 Parallel Cluster Algorithms
    • 12.6.4 Self-labelling
    • 12.6.5 Global Equivalencing
    • 12.6.6 Other Algorithms
    • 12.6.7 Summary
  • 12.7 Sorting
    • 12.7.1 The Merge Strategy
    • 12.7.2 The Bitonic Algorithm
    • 12.7.3 Shellsort or Diminishing Increment Algorithm
    • 12.7.4 Quicksort or Samplesort Algorithm
  • 12.8 Hierarchical Tree-Structures as Adaptive Meshes
    • 12.8.1 Introduction
    • 12.8.2 Adaptive Structures
    • 12.8.3 Tree as Grid
    • 12.8.4 Conclusion
• 13 Data Parallel C and Fortran
  • 13.1 High-Level Languages
    • 13.1.1 High Performance Fortran Perspective
    • 13.1.2 Problem Architecture and Message-Passing Fortran
    • 13.1.3 Problem Architecture and Fortran 77
  • 13.2 A Software Tool for Data Partitioning and Distribution
    • 13.2.1 Is Any Assistance Really Needed?
    • 13.2.2 Overview of the Tool
    • 13.2.3 Dependence-based Data Partitioning
    • 13.2.4 Mapping Data to Processors
    • 13.2.5 Communication Analysis and Performance Improvement Transformations
    • 13.2.6 Communication Analysis Algorithm
    • 13.2.7 Static Performance Estimator
    • 13.2.8 Conclusion
  • 13.3 Fortran 90 Experiments
  • 13.4 Optimizing Compilers by Neural Networks
  • 13.5 ASPAR
    • 13.5.1 Degrees of Difficulty
    • 13.5.2 Various Parallelizing Technologies
    • 13.5.3 The Local View
    • 13.5.4 The ``Global'' View
    • 13.5.5 Global Strategies
    • 13.5.6 Dynamic Data Distribution
    • 13.5.7 Conclusions
  • 13.6 Coherent Parallel C
  • 13.7 Hierarchical Memory
• 14 Asynchronous Applications
  • 14.1 Asynchronous Problems and a Summary of Basic Problem Classes
  • 14.2 Melting in Two Dimensions
    • 14.2.1 Problem Description
    • 14.2.2 Solution Method
    • 14.2.3 Concurrent Update Procedure
    • 14.2.4 Performance Analysis
  • 14.3 Computer Chess
    • 14.3.1 Sequential Computer Chess
      • The Evaluation Function
      • Quiescence Searching
      • Iterative Deepening
      • The Hash Table
      • The Opening
      • The Endgame
    • 14.3.2 Parallel Computer Chess: The Hardware
    • 14.3.3 Parallel Alpha-Beta Pruning
      • Analysis of Alpha-Beta Pruning
      • Global Hash Table
    • 14.3.4 Load Balancing
    • 14.3.5 Speedup Measurements
    • 14.3.6 Real-time Graphical Performance Monitoring
    • 14.3.7 Speculation
    • 14.3.8 Summary
• 15 High-Level Asynchronous Software Systems
  • 15.1 Asynchronous Software Paradigms
  • 15.2 MOOS II: An Operating System forDynamic Load Balancing on the iPSC/1
    • 15.2.1 Design of MOOSE
    • 15.2.2 Dynamic Load-Balancing Support
    • 15.2.3 What We Learned
  • 15.3 Time Warp
• 16 The Zipcode Message-Passing System
  • 16.1 Overview of Zipcode
  • 16.2 Low-Level Primitives
    • 16.2.1 CE/RK Overview
    • 16.2.2 Interface with the CE/RK system
    • 16.2.3 CE Functions
      • CE Programs
    • 16.2.4 RK Calls
    • 16.2.5 Zipcode Calls
      • Zipcode Class-Independent Calls
      • Mailer Creation
      • Predefined Mailer Classes
      • Letter-Generating Primitives
      • Letter-Consuming Primitives
  • 16.3 High-Level Primitives
    • 16.3.1 Invoices
    • 16.3.2 Packing and Unpacking
    • 16.3.3 The Packed-Message Functions
    • 16.3.4 Fortran Interface
  • 16.4 Details of Execution
    • 16.4.1 Initialization/Termination
    • 16.4.2 Process Creation/Destruction
  • 16.5 Conclusions
• 17 MOVIE - Multitasking Object-oriented Visual Interactive Environment
  • 17.1 Introduction
    • 17.1.1 The Beginning
    • 17.1.2 Towards the MOVIE System
    • 17.1.3 Current Status and Outlook
  • 17.2 System Overview
    • 17.2.1 The MOVIE System in a Nutshell
    • 17.2.2 MovieScript as Virtual Machine Language
    • 17.2.3 Data-Parallel Computing
    • 17.2.4 Model for MIMD-parallelism
    • 17.2.5 Distributed Computing
    • 17.2.6 Object Orientation
    • 17.2.7 Integrated Visualization Model
      • DPS/NeWS
      • X/Motif/OpenLook
      • AVS/Explorer
      • 3D MOVIE
      • Integration
    • 17.2.8 ``In Large'' Extensibility Model
    • 17.2.9 CASE Tools
      • MetaDictionary
      • C Language Naming Conventions
      • MetaIndex
      • Makefile Model
      • Documentation Model
    • 17.2.10 Planned MOVIE Applications
      • Machine Vision
      • Neural Networks
      • Databases
      • Global Change
      • High Energy Physics Data Analysis
      • Expert Systems
      • Command and Control
      • Virtual Reality
  • 17.3 Map Separates
    • 17.3.1 Problem Specification
    • 17.3.2 Test Case
    • 17.3.3 Segmentation via RGB Clustering
    • 17.3.4 Comparison with JPL Neural Net Results
    • 17.3.5 Edge Detection via Zero Crossing
    • 17.3.6 Towards the Map Expert System
    • 17.3.7 Summary
  • 17.4 The Ultimate User Interface: VirtualReality
    • 17.4.1 Overall Assessment
    • 17.4.2 Markets and Application Areas
    • 17.4.3 VR at Syracuse University
    • 17.4.4 MOVIE as VR Operating Shell
• 18 Complex System Simulation and Analysis
  • 18.1 MetaProblems and MetaSoftware
    • 18.1.1 Applications
    • 18.1.2 Asynchronous versus Loosely Synchronous?
    • 18.1.3 Software for Compound Problems
  • 18.2 ISIS: An Interactive Seismic ImagingSystem
    • 18.2.1 Introduction
    • 18.2.2 Concepts of Interactive Imaging
    • 18.2.3 Geologist-As-Analyst
    • 18.2.4 Why Interactive Imaging?
    • 18.2.5 System Design
    • 18.2.6 Performance Considerations
    • 18.2.7 Trace Manager
    • 18.2.8 Display Manager
    • 18.2.9 User Interface
    • 18.2.10 Computation
    • 18.2.11 Prototype System
    • 18.2.12 Conclusions
  • 18.3 Parallel Simulations that Emulate Function
    • 18.3.1 The Basic Simulation Structure
    • 18.3.2 The Run-Time Environment-the Centaur Operating System
    • 18.3.3 SDI Simulation Evolution
    • 18.4 Simulation Framework and Synchronization Control
  • 18.4 Multitarget Tracking
    • 18.4.1 Nature of the Problem
    • 18.4.2 Tracking Techniques
      • Single-Target Tracking
      • Multitarget Tracking
    • 18.4.3 Algorithm Overview
    • 18.4.4 Two-dimensional Mono Tracking
      • Two-dimensional Track Extensions
      • Two-dimensional Report Formation
      • Track Initialization
    • 18.4.5 Three-dimensional Tracking
      • Track Extension Associations
• 19 Parallel Computing in Industry
  • 19.1 Motivation
  • 19.2 Examples of Industrial Applications
• 20 Computational Science
  • 20.1 Lessons
  • 20.2 Computational Science
• A Selected Biographic Information
• B References
• Index
• About this document ...