Full HTML for

Scripted foilset Overview of Monte Carlo Case Study

Given by Geoffrey C. Fox, Paul Coddington at CPSP713 on Autumn Semester 1994. Foils prepared 15 March 1996
Outside Index Summary of Material

CFD (Computational Fluid Dynamics) and NR (Numerical Relativity) both involve the solution of second order partial differential equations (PDE's) describing physical phenomena.
This case study will study both applications and then look at the computer science (computational) issues which are both common and distinct.
This will allow us to study the requirements of a computational toolkit for general solution of second order PDE's.
These two applications are by no means the only applications but they cover a broad range of issues.
CFD can be defined narrowly as confined to aerodynamic flow around vehicles but it can be generalized to include as well such areas as weather and climate simulation, flow of pollutants in the earth, and flow of liquids in oil fields (reservoir modelling).

Table of Contents for full HTML of Overview of Monte Carlo Case Study

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 CPS 713--Case study II
August to December1994 - Case Studies in Computational Science
-- Overview of Second Case Study
CFD and Numerical Relativity
2 Abstract for CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity
3 Further Remarks on CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity
4 Overview of Topics in CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity
5 CPS713 Case Study II)CFD+NNR -- Motivation of The NAS Benchmarks
6 CPS713 Case Study II) --Use of The NAS Benchmarks
7 CPS713 Case Study II) -- Overview of Computational Toolkit Issues
8 CPS713 Case Study II) -- Remainder of Basic Module (What will be in The Long Discussion of Subject after one lecture Overview)
9 CPS713 Case Study II) Overview Features of Numerical Relativity
10 CPS713 Case Study II) Comparison of Numerical Relativity with Maxwell's Equations
11 CPS713 Case Study II) Computational Features of Numerical Relativity
12 CPS713 Case Study II) Computational Features of Numerical Relativity (Contd) -- Singularity Structure
13 CPS713 Case Study II) Computational Features of Numerical Relativity (Contd) -- Black Hole Boundary Condition
14 CPS713 Case Study II) Computational Needs for CFD and Numerical Relativity
15 CPS713 Case Study II) Some Common Issues between CFD and Numerical Relativity
16 CPS713 Case Study II) Computer Science Support for CFD and NR -- Portable Scalable Software Tools
17 CPS713 Case Study II) Further Computer Science Issues for CFD and NR Computational Toolkit
18 CPS713 Case Study II) Specific Toolkit Modules Needed
19 CPS713 Case Study II) Specific Toolkit Modules Needed -- Parallel Grid Generation

Outside Index Summary of Material

HTML version of Scripted Foils prepared 15 March 1996

Foil 1 CPS 713--Case study II
August to December1994 - Case Studies in Computational Science
-- Overview of Second Case Study
CFD and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Geoffrey Fox
NPAC
Syracuse University
Syracuse NY 13244-4100
HTML version of Scripted Foils prepared 15 March 1996

Foil 2 Abstract for CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
CFD (Computational Fluid Dynamics) and NR (Numerical Relativity) both involve the solution of second order partial differential equations (PDE's) describing physical phenomena.
This case study will study both applications and then look at the computer science (computational) issues which are both common and distinct.
This will allow us to study the requirements of a computational toolkit for general solution of second order PDE's.
These two applications are by no means the only applications but they cover a broad range of issues.
CFD can be defined narrowly as confined to aerodynamic flow around vehicles but it can be generalized to include as well such areas as weather and climate simulation, flow of pollutants in the earth, and flow of liquids in oil fields (reservoir modelling).
HTML version of Scripted Foils prepared 15 March 1996

Foil 3 Further Remarks on CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Our numerical relativity example will be the collision of two black holes which is focus of a major NSF Grand Challenge involving NPAC with seven other institutions in a collaboration led by Richard Matzner at Texas.
Note that Numerical Relativity involves solution of Einstein's equations which include as a special case Maxwell's equations used to describe electromagnetic phenomena.
Thus issues of relevance to computational electromagnetics (used in study of antennas and radar cross-sections of military aircraft) are implicitly included in this case study.
Nearly all partial differential equations which are commonly encountered can be found by choosing parameters or limits in CFD or NR.
HTML version of Scripted Foils prepared 15 March 1996

Foil 4 Overview of Topics in CPS713 Case Study II) Computational Fluid Dynamics and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Motivation for CFD -- why we need Teraflop and Petaflop performance to design new aircraft and model oil reservoirs and polluted chemical dump sites
Introduction to NAS benchmarks and remarks on performance of today's machines.
Motivation of Numerical Relativity with Collision of two black holes as expected signature for LIGO gravitational wave detector -- expected need for Teraflop performance
General Discussion of Continuum Physics as a model for Nature
The Navier Stokes Equation -- Basic equations of CFD
General discussion of Computational Issues for CFD
Introduction to Numerical formulation of Einstein's Equations
General discussion of computational issues for Numerical Relativity
Comparison of Similarities and differences between CFD and NR
HTML version of Scripted Foils prepared 15 March 1996

Foil 5 CPS713 Case Study II)CFD+NNR -- Motivation of The NAS Benchmarks

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
The NAS benchmarks were introduced by a group at NASA Ames as a novel approach to benchmarking high performance machines.
Most benchmarks (call these software benchmarks) are presented as specific pieces of software which must be run on a target machine to measure its performance
  • Software benchmarks involve both the computer and the compiler (assuming benchmark in a language such as Fortran C C++ ADA). Further they implement a particular algorithm to solve the problem.
  • Particular high performance computers may need different algorithms and or different language to achieve good performance
    • For instance High Performance Fortran would be needed on a parallel machine instead of simple Fortran77
    • The benchmark code may implement in a high level language a basic algorithm such as FFT or matrix solve while any practical code would use the optimized (assembly language) subroutines.
    • The basic algorithm might need to be changed due to architecture of machine e.g. SIMD or vector architectures typically need different optimal algorithms from MIMD machines.
  • The innovation in NAS benchmarks was "pencil and paper" (i.e. mathematical) definition of benchmark so each implementation could be optimized (with certain rules) for target computer as appropriate.
HTML version of Scripted Foils prepared 15 March 1996

Foil 6 CPS713 Case Study II) --Use of The NAS Benchmarks

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
The NAS Benchmarks are described in a basic document:
  • "NAS Parallel Benchmarks" RNR-94-007, March 1994 by D.Bailey et al. updating original 1991 document.
  • "NAS Parallel Benchmark Results 3-94", RNR-94-006 by D.Bailey, E. Barszcz, L.Dagum, and H.D. Simon
  • contain latest but obviously ephemeral results.
  • See also http://www.nas.nasa.gov/RNR/Parallel/NPB/NPBindex.html.
The material used in class selects results from 4 benchmarks described in detail in above citations:
  • EP: Embarrassingly parallel -- no communication -- tests node performance
  • The remaining three benchmarks involve significant communication.
  • CG: Conjugate Gradient -- basic PDE Solution method discussed in CPS615
  • SP: Pentadiagonal Solver -- model of a full CFD solver
  • BT: Block Tridiagonal PDE Iterative solver -- another model of a full CFD solver
There are several striking results in NAS results with SGI Power Challenge and IBM SP2 leading the way in performance per node. Full document discusses performance per dollar and the full set of benchmarks.
We will later use mathematical definition of CFD contained in BT and SP benchmarks as a way of indicating key computer science issues in CFD. We will generalize this approach and try to specify numerical relatively in a similar fashion.
HTML version of Scripted Foils prepared 15 March 1996

Foil 7 CPS713 Case Study II) -- Overview of Computational Toolkit Issues

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
We will use AIAA-94-2249 "Computational Toolkit for Colliding Black Holes and CFD" by N.P. Chrisochoides, G.C. Fox and T. Haupt as an overview of issues that need to be studied in producing a PDE (CFD and NR) Computational toolkit
  • Example of multidisciplinary design as a metaproblem needing integration of many disparate software modules (sec. 1)
  • Study of ELLPACK and issues in modular programming for PDE solution. Relevance of domain specific interfaces built using Mathematica or similar package (sec. 2)
  • Software Integration issues needed in metaproblems (sec. 3)
  • Review of programming paradigms (sec. 4.1)
  • High Performance Fortran for individual modules (Sec 4.2)
  • Runtime Support from libraries, message passing to programming environment (Sec. 5)
  • Parallel Grid Generation for Structured (NR) and Unstructured (CFD) meshs (Sec. 6)
HTML version of Scripted Foils prepared 15 March 1996

Foil 8 CPS713 Case Study II) -- Remainder of Basic Module (What will be in The Long Discussion of Subject after one lecture Overview)

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Relate CFD to NAS benchmark discussion
Review of various PDE solution methods and their parallel implementations
Discuss in detail numerics and parallel implementation of NAS CFD model problems
Present NR in NAS benchmark form
Discuss model problems from wave equation to simple realistic NR problem
Return to general toolkit Issues:
  • Current status of MPI and PVM -- standard message passing systems
  • Comparison with thread based approaches (PORTS Collaboration)
  • Irregular adaptive Compiler (High Performance Fortran) Language and runtime support
  • Parallel Grid Generation -- Integration with HPF and HPC++
  • Software Integration with AVS and Fortran-M (CC++)
HTML version of Scripted Foils prepared 15 March 1996

Foil 9 CPS713 Case Study II) Overview Features of Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Numerical Relativity is a coupled set of partial differential equations
  • Direct formulation has 10 independent equations
  • Some implementations have up to 50 coupled functions
Equations can be divided into two classes
  • 4 Elliptic (Laplace equation-like) constraint equations which must be satisfied at each time
  • 6 coupled Hyperbolic (Wave equation like) equations describing time evolution
For CFD, the "physics" determines computational issues
  • e.g. a shock represents a rapidly varying solution which requires typically an adaptive irregular mesh and finite element solution method
For Numerical relativity, one can change the nature of solution by changing "space itself"
  • This is called choosing the Gauge
  • One gauge could have rapidly varying fields and require adaptive finite elements
  • Another Gauge could have slowly varying fields and be soluble with finite difference.
HTML version of Scripted Foils prepared 15 March 1996

Foil 10 CPS713 Case Study II) Comparison of Numerical Relativity with Maxwell's Equations

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
The Magnetic Field is given in terms of vector potential by
Components of vector potential are not independent as expressed by gauge transformation
  • for any field
Choosing implies choosing gauge
The Constraint equations are:
The evolution Equations are:
These give waves at infinity
HTML version of Scripted Foils prepared 15 March 1996

Foil 11 CPS713 Case Study II) Computational Features of Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
The theory is very nonlinear:
  • For instance one of the elliptic constraints can be written:
  • CFD is also nonlinear as have terms such as
Boundary Conditions at Infinity are those of computational electromagnetics (CEM)
  • Not those familiar from CFD
  • One needs to look for wave solutions and these waves are precisely what LIGO experiment will detect
  • Curiously I see that methods used in CEM such as method of moments are not being used in Numerical Relativity
    • NR solves evolution equations and identifies oscillatory wave solution
    • Waves very sensitive to numerics -- small numerical errors can be amplified as wave propagates
    • Numerical approximation can introduce an effective dissipative term which has small coefficient but enhanced by large propagation distance
HTML version of Scripted Foils prepared 15 March 1996

Foil 12 CPS713 Case Study II) Computational Features of Numerical Relativity (Contd) -- Singularity Structure

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
There are no small coefficients of second order derivative terms
  • In CFD small coefficient proportional to viscosity led to rapidly varying fields so product of viscosity times second derivative was comparable in size to other terms in CFD equations
  • This leads to shocks, boundary layers, turbulent flow in CFD i.e.
    • CFD has singularities which are lower dimension than solution space
Numerical Relativity has the world's most significant singularity -- Black Holes
  • Otherwise singularities are volume based and not like shocks
  • Correspondingly Numerical Relativity can use finite difference methods
    • One does need adaptive block structured meshs but probably not unstructured meshs
    • Can use Finite Elements (FEM) and may be preferable -- CFD is more or less required to use FEM
HTML version of Scripted Foils prepared 15 March 1996

Foil 13 CPS713 Case Study II) Computational Features of Numerical Relativity (Contd) -- Black Hole Boundary Condition

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Boundary conditions at Black Holes involve physics and numerics
Certainly finite difference mesh needs some sort of special treatment
Physics says that any information inside black hole is irrelevant
  • It cannot get out and so cannot affect solution outside hole
However we don't know where Black Hole is until we get full solution!
This issue is "Show-Stopper". It may be that difficulties in this area will prevent reliable solutions without a major algorithmic breakthrough or new physics insight
  • Other NR issues are hard but no reason why we shouldn't solve reasonably well
HTML version of Scripted Foils prepared 15 March 1996

Foil 14 CPS713 Case Study II) Computational Needs for CFD and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
It is possible that a teraflop computer may be sufficient to "solve" the collision of two black holes
  • Solution defined as producing a catalog of wave forms which can be used in analysis of initial LIGO data
  • This is not of course only important issue and other studies may require more or less computer time
NASA has documented carefully estimates of computer needs for various CFD approaches.
  • Although not entirely clear what CFD approaches are actually relevant to design new aircraft or cars.
    • Better -- this would mean using more accurate solutions to full equations
    • Faster -- This is perhaps more promising and requires Integration of several distinct simulations in full design cycle
    • This Multidisciplinary analysis and design underlies agile manufacturing or concurrent engineering
Snapshot results are:
  • Petaflop performance needed for full Navier Stokes equations for full aircraft
  • Teraflop performance needed for Multidisciplinary Analysis using Reynolds averaged approximations with turbulence models
HTML version of Scripted Foils prepared 15 March 1996

Foil 15 CPS713 Case Study II) Some Common Issues between CFD and Numerical Relativity

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Both problems are coupled systems of second order partial differential equations
Both can involve solution of metaproblems -- coupling between different systems of equations
  • In CFD, Metaproblems seen in Multidisciplinary Analysis and Design
  • in NR, Metaproblem seen in coupling of constraint and evolution equations
Both problems require numerical experimentation to develop working codes
  • Many unsolved issues requiring new physics insight implemented well numerically
  • One cannot specify today the "right" approach to CFD or NR
Both problems have elliptic and hyperbolic equations
Similarities suggest we develop a toolkit applicable for either or both applications
HTML version of Scripted Foils prepared 15 March 1996

Foil 16 CPS713 Case Study II) Computer Science Support for CFD and NR -- Portable Scalable Software Tools

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Portable means runs on (nearly) all of today's high performance (parallel) computers
Scalable means code written today will run on future high performance machines
  • These current and future machines include networks of workstations as well as integrated massively parallel machines
High Performance Fortran and C++ ; scalable data parallel support
Fortran-M and CC++ ; scalable support of task parallelism
AVS ; industry standard for visualization and software integration
PVM and MPI ; standard message passing support
ADIFOR ; differentiate Fortran code ; critical tool for optimization problems
Prototyping Software ; needs development of Interpreters and other tools
HTML version of Scripted Foils prepared 15 March 1996

Foil 17 CPS713 Case Study II) Further Computer Science Issues for CFD and NR Computational Toolkit

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Domain Specific Software where user interfaces at level of mathematical equations -- not C++ or Fortran
  • Can build with Computer algebra tools such as Maple or Mathematica which then must be taught to generate efficient High Performance Fortran , Fortran77 + MPI or equivalent.
    • SINAPSE -- built from Mathematica at Schlumberger research
    • ELLPACK -- one of first and best PDE toolkits (for ELLiptic equations)
Runtime support and libraries
  • Schedulers and data decomposition tools
  • Scientific Libraries such as SCALAPACK which can be used directly to solve matrices coming from computational electromagnetics formulated with the method of moments
  • Parallel Compiler Runtime Consortium
    • Integrated support for many languages on many computers
    • Can mix programming paradigms such as
    • HPC++ for convenience and elegance with Fortran77 + MPI for efficiency
HTML version of Scripted Foils prepared 15 March 1996

Foil 18 CPS713 Case Study II) Specific Toolkit Modules Needed

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
PDE Solvers for both Elliptic, Hyperbolic and mixed equations
Geometry packages to define solution space (mainly for CFD used in design of real vehicles)
Visualization including Virtual Reality (VR)
  • VR used by Boeing today to study if a particular design can be serviced
  • VR study of CFD or NR solution may lead to new physics insight
Optimization needed for Multidisciplinary Analysis and Design
Boundary Conditions can be application specific as sensitive to physical system
  • Fluid -- Vehicle Boundary
  • NR Infinity boundary condition of waves
  • NR Black Hole event horizon (guaranteed to be inside true black hole surface) boundary condition
HTML version of Scripted Foils prepared 15 March 1996

Foil 19 CPS713 Case Study II) Specific Toolkit Modules Needed -- Parallel Grid Generation

From Overview of Monte Carlo Case Study CPSP713 -- Autumn Semester 1994. *
Full HTML Index
Grid Generation has several important characteristics:
  • Adaptive Block Structured for CFD and NR
  • Adaptive Unstructured for CFD
  • Should be consistent with multigrid and domain decomposition solution methods
  • Should be integrated with High Level Language or Domain Specific Interface
  • Should be linkable between different sets of equations
    • For instance mesh used to simulate structure of airframe must be consistent with volume mesh needed for CFD study of airflow around aircraft
  • Must be able to generate and adapt "in place" and "in parallel" on parallel machine
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun Feb 22 1998