Full HTML for

Basic foilset Earthquake Prediction as Example of N Body Computations

Given by Geoffrey C. Fox at CPS615 INtroduction to Computational Science on Fall Semester 1998. Foils prepared 5 October 98
Outside Index Summary of Material

We briefly discuss why GEM is interesting
We state the computational problem for GEM and analyze parallel computing issues for key steps
We map into a particle dynamics analogy using Green's function formalism and consider O(N2) cut-off O(N) and fast multipole methods
We go in detail through the fast multipole method
We expect object oriented approaches to be very important booth at language level and in using technologies like CORBA to integrate world-wide collaboration, simulations and experiments.

Table of Contents for full HTML of Earthquake Prediction as Example of N Body Computations

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Computational Science and N Body algorithms Illustrated by GEM: General Earthquake Simulation Project CPS615 Introduction to Computational Science October 98
2 Abstract of GEM Analysis for Computational Science
3 Earthquakes are Worldwide
4 Northridge Earthquake 1994 (Southern California)
5 Southern California Earthquake Activity
6 We need to predict earthquakes!
7 Possible Special Features of Earthquake Simulation
8 Basic Computational Structure - I
9 Basic Computational Structure - II
10 Analysis of Computational Structure
11 First two Solutions of O(N2) Computational Complexity
12 Second two Solutions of O(N2) Computational Complexity
13 Basic Idea of Fast Multipole Algorithm
14 Intermediate results of a computation of 322 million particles on ASCI Red
15 Intermediate results of a computation of 9.7 million particles on PC Cluster loki
16 Some Performance Results of Interest from Salmon and Warren
17 Hierarchical Breakup of 2D Space
18 Simple Illustration of Tree Data Structure
19 Tree Structure for 10,000 bodies centrally clustered in a disk
20 Generation of Tree for a small number of particles
21 3 Approximations to Force on a Particle in Fast Multipole Approach
22 Parallelism in O(N2) N Body Approach I
23 Parallelism in O(N2) N Body Approach II
24 Parallelism in Cut Off Force Approach
25 Problems in Cut off Force Parallelism
26 Cyclic and Block Decomposition for Graphics Ray Tracing
27 Generation of Keys in Salmon Warren Method
28 Generation of 3D Key for Salmon Warren
29 Parallelism in Salmon Warren Approach
30 Two Space Filling Curves
31 Morton Curve split up into 8 processors represented by different gray levels
32 Space Filling Curve chopped up into equal length parts
33 Parallel Algorithm in Fast Multipole I
34 Locally essential Data for Processor in Bottom Left Hand Corner of Processor Array
35 Parallel Algorithm in Fast Multipole II
36 Scaling Ideas in GEM
37 Different Physical Scales in GEM
38 Lessons from Other Fields

Outside Index Summary of Material

HTML version of Basic Foils prepared 5 October 98

Foil 1 Computational Science and N Body algorithms Illustrated by GEM: General Earthquake Simulation Project CPS615 Introduction to Computational Science October 98

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Geoffrey Fox
Syracuse University
NPAC
111 College Place Syracuse NY 13244 4100
3154432163
HTML version of Basic Foils prepared 5 October 98

Foil 2 Abstract of GEM Analysis for Computational Science

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
We briefly discuss why GEM is interesting
We state the computational problem for GEM and analyze parallel computing issues for key steps
We map into a particle dynamics analogy using Green's function formalism and consider O(N2) cut-off O(N) and fast multipole methods
We go in detail through the fast multipole method
We expect object oriented approaches to be very important booth at language level and in using technologies like CORBA to integrate world-wide collaboration, simulations and experiments.
HTML version of Basic Foils prepared 5 October 98

Foil 3 Earthquakes are Worldwide

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Many of billions of dollars of damage
Tens of thousands of casualties
Current predictions are probabilistic
GEM is trying to predict in greater detail from "basic" physics
HTML version of Basic Foils prepared 5 October 98

Foil 4 Northridge Earthquake 1994 (Southern California)

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 5 Southern California Earthquake Activity

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 6 We need to predict earthquakes!

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
This is a simulation from group in Queensland Australia
HTML version of Basic Foils prepared 5 October 98

Foil 7 Possible Special Features of Earthquake Simulation

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Link of geographically distributed observations and computation
  • Seismic sensors, SAR etc.
Special Purpose Computers for O(N2) particle dynamics that is used in some approaches to some parts of problem
Less legacy code than other application areas
  • So can adopt more easily modern technology such as Java(Web) and CORBA
HTML version of Basic Foils prepared 5 October 98

Foil 8 Basic Computational Structure - I

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Green's Functions Relate Stress and Deformation to Integrals over slip deficit f(x,t) = slip(x,t)-V*t
After discretization, Green's function integrals become sums with
  • deformationi and stressi = Sj Green(i,j,t) fj(t)
with indices i and j running over fault segments
The friction law then determines if there is an "earthquake" which is a correlated change in the slip deficit
HTML version of Basic Foils prepared 5 October 98

Foil 9 Basic Computational Structure - II

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
The Green's Function is in first approximation independent of time and time only enters through time dependence of slip deficit
We are evolving a set of N differential equations -- think of each fault segment "i"as a particle -and can do this either as either
  • deterministic "particle" dynamics
  • Monte Carlo
These are two standard choices in "ordinary" particle dynamics
After each time/Monte Carlo step one needs to see if a slip will occur using friction law
HTML version of Basic Foils prepared 5 October 98

Foil 10 Analysis of Computational Structure

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
So basic computation is "long range" and O(N2) for N fault segments
We can compare with other classic long range force problems such as particle dynamics (chemistry, astrophysics) and vortex method in CFD
  • This problem is linear in independent variables fi(t)
  • The position of fault segments is irregular but roughly fixed
  • Force law is that of a "double-couple" (equal and opposite dipoles)
But we have the same essential computational feature that O(N2) terms will lead to high computational load which needs to be addressed somehow.
HTML version of Basic Foils prepared 5 October 98

Foil 11 First two Solutions of O(N2) Computational Complexity

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
1) Ignore it and implement straightforwardly on a conventional computer
2) Note that one can build special purpose parallel machines as need less communication bandwidth (and just one dimensional pipeline) and much less memory per CPU power than for general purpose (parallel) computer
  • parallel algorithm described in course incredibly efficient and can use inexpensive low bandwidth communication channels
  • This is approach of GRAPE (Gravity Pipeline) machine which could be about a factor of 100 more cost effective for astrophysics on large problems
  • Note memory is a major cost on most general purpose machines and needed ratio of memory to CPU much smaller for GRAPE than general purpose machine.
  • GRAPE uses same parallel algorithm we described in course
HTML version of Basic Foils prepared 5 October 98

Foil 12 Second two Solutions of O(N2) Computational Complexity

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
3) Cutoff long range forces (common strategy in chemistry where Forces fall off faster (E.g. 1/r5) than in gravity)
  • This leads to a classic nearest neighbor O(N) algorithm with irregular geometry causes minor implementation issues
Use the new "fast multipole" algorithms which have been very successful in other related areas
  • Astrophysics
  • Computational Electromagnetic
  • Vortex approach to CFD
Instead of zeroing out contributions of far away particles, these methods do an ingenious multipole expansion of the contributions of far away regions
HTML version of Basic Foils prepared 5 October 98

Foil 13 Basic Idea of Fast Multipole Algorithm

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
These ideas came from many people: Appel, Barnes-Hut, Greengard and Rokhlin
Salmon (Caltech) and Warren(Los Alamos) implemented very well for astrophysics with upto 108 particles
Instead of summing over the M stars in a far away cluster, "just" replace by the contribution of the centroid
Fast Multipole "just" applies this idea recursively with a sum over multipoles extending simple centroid formula.
HTML version of Basic Foils prepared 5 October 98

Foil 14 Intermediate results of a computation of 322 million particles on ASCI Red

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 15 Intermediate results of a computation of 9.7 million particles on PC Cluster loki

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 16 Some Performance Results of Interest from Salmon and Warren

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
16 Pentium Pro's in a cluster (cost $30K today) reach about 1 gigaflop on a tree code with 107 particles
6800 Pentium Pro's (ASCI Sandia machine) with around 300 million particles
  • 600 gigaflops with simple O(N2) code
  • 400 gigaflops with tree code
But tree code is 105 times as efficient as O(N2) code on this problem
  • i.e if Execution Time(naïve code) is c . N2
  • then Time (tree code) is 3000 c N
  • and tree code is more efficient than O(N2) code for more than 3000 particles
HTML version of Basic Foils prepared 5 October 98

Foil 17 Hierarchical Breakup of 2D Space

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Real astrophysics is 3D but illustrate for 2D case
Chop space recursively into square cells so that at most one (or some specified number) of particles is in each "leaf" cell
HTML version of Basic Foils prepared 5 October 98

Foil 18 Simple Illustration of Tree Data Structure

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
We show this recursive break-up in a simple case
Note refinement depends on number of particle density
HTML version of Basic Foils prepared 5 October 98

Foil 19 Tree Structure for 10,000 bodies centrally clustered in a disk

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 20 Generation of Tree for a small number of particles

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 21 3 Approximations to Force on a Particle in Fast Multipole Approach

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
1)Simple Direct Sum over all particles in region
2)Just Single Centroid Contribution
3)Open up region into 8 cells and use centroid of each cell
HTML version of Basic Foils prepared 5 October 98

Foil 22 Parallelism in O(N2) N Body Approach I

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
O(N2) Algorithms are extremely efficient on parallel machines as
  • Load balancing guaranteed with equal numbers of particles in each node
  • Communication overhead goes like 1/(grain size n = number of particles in node) . Typical time to communicate word/ typical time to do floating computation) ~ 0.25(from algorithm details) . 10( = tcomm/tfloat)/n
  • So very efficient along as around 50 particles or more per processor
HTML version of Basic Foils prepared 5 October 98

Foil 23 Parallelism in O(N2) N Body Approach II

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
This type of performance should be compared with classic grid problems in d dimensions where overhead proportional to edge over area and goes like 1/n1/d
So that grain size in 3D local problems is "cube" of that needed in O(N2) problem
Of course reason that communication overhead is so small is that computation is exceptionally large!
  • Every silver lining has a cloud
Note can "understand" 1/n dependence as write formula as Sj Si Force on i = function(i and j) --
important that outer sum is j not i!
Each j is communicated to each node and is then used to increment force on n/2 (divided by two due to Newton's law of action and reaction) particles in given node
HTML version of Basic Foils prepared 5 October 98

Foil 24 Parallelism in Cut Off Force Approach

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
This is classic "nearest neighbor" problem where one uses "domain decomposition and communicates particles around edge of domain of each processor.
  • Computation a n
  • Communication a n(1-1/d) in d dimensions
Calculation 4 n tcalc
Communication 4 ?n tcomm
Calculation 9 n tcalc
Communication 8 ?n tcomm
2 dimensional examples -- communication and computation both grow as you increase grain size n
Processor Boundary
HTML version of Basic Foils prepared 5 October 98

Foil 25 Problems in Cut off Force Parallelism

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Earthquakes cause load imbalance as "action" concentrated in processors where quake occurs
Can be addressed at cost of increasing communication by using "block-cyclic" decomposition so each processor gets part of action
Problem particularly bad for Monte Carlo as similar to classic "clustering algorithms" needed near critical points to get good performance. We know these have poor parallel performance
Long range versions of Monte Carlo will perform satisfactorily as can parallelize over long range force part of computation
Cyclic Decomposition
Each color is area assigned to particular 1 of 4 processors. Star signifies Earthquake
HTML version of Basic Foils prepared 5 October 98

Foil 26 Cyclic and Block Decomposition for Graphics Ray Tracing

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
One needs to load balance (ensure all processors get an equal amount of work) but preserve domain decomposition which says nearby pixels are in same processor (minimize communication)
Cyclic Decomposition Block Decomposition
HTML version of Basic Foils prepared 5 October 98

Foil 27 Generation of Keys in Salmon Warren Method

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
In 2(3) dimensions add 2(3) binary bits at each step down tree
HTML version of Basic Foils prepared 5 October 98

Foil 28 Generation of 3D Key for Salmon Warren

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Each time one goes down one level of tree, add X Y Z bit
64 bit key supports 21 levels
HTML version of Basic Foils prepared 5 October 98

Foil 29 Parallelism in Salmon Warren Approach

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
First you must decompose cells among processors which is nontrivial as irregular dynamic (maybe not in GEM) tree like structure
Originally used orthogonal recursive bisection chopping space succesively in 2 in different dimensions
However better to run "a space filling curve" through the cells and divide curve into chunks of equal work (which NOT equal numbers of particles as more computation in dense areas of particles)
  • Note fast multipole essentially adds in nearby particles using "direct computation approach"
Simplest is to sort keys and divide up this sorted list (Morton curve)
HTML version of Basic Foils prepared 5 October 98

Foil 30 Two Space Filling Curves

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 31 Morton Curve split up into 8 processors represented by different gray levels

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 32 Space Filling Curve chopped up into equal length parts

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 33 Parallel Algorithm in Fast Multipole I

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Parallelism is clear -- update particles in parallel but what about communication?
It requires a thoughtful algorithm but can efficiently fetch information needed.
  • Fetch all the information needed by ANY particle in a given processor as multipole approach implies that particles tend to need same long range components if nearby
  • call this "locally essential" data
  • cf. O(N) multipole-multipole approach
Effectively top of tree replicated in all processors and they just differ near bottom which is expanded in a way that depends on where processor is
HTML version of Basic Foils prepared 5 October 98

Foil 34 Locally essential Data for Processor in Bottom Left Hand Corner of Processor Array

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
HTML version of Basic Foils prepared 5 October 98

Foil 35 Parallel Algorithm in Fast Multipole II

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Having fetched all needed data, can update all particles in processors with high efficiency seen in O(N2) problem.
  • Namely communicated data is re-used many times as needed by many particles in processor
  • In practice have some 10,000 or more particles per processor
In astrophysics, also need to construct tree and rebalance load at essentially each time step
  • not needed in GEM
There is a straightforward parallel tree building algorithm
These methods outperform O(N2) when more than a few thousand particles (unless problem very inhomogeneous)
HTML version of Basic Foils prepared 5 October 98

Foil 36 Scaling Ideas in GEM

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Note that tree codes are a simple example of general need in GEM to have technologies that bridge different physical scales
  • This is well known for multigrid approach to elliptic partial differential equation solvers
Information travels in O(1 or log K) steps and not K steps for a grid of size K
  • Multipole method implements this type of fast traversal of multiple scales with its variable grid size. A uniform grid is dominated by small distances even if irrelevant
HTML version of Basic Foils prepared 5 October 98

Foil 37 Different Physical Scales in GEM

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
Each Physical layer abstracts layer at finer scale in terms of phenomenological/ averaging parameters
GEM Sweet Spot
HTML version of Basic Foils prepared 5 October 98

Foil 38 Lessons from Other Fields

From Earthquake Prediction as Example of N Body Computations CPS615 INtroduction to Computational Science -- Fall Semester 1998. *
Full HTML Index
If we look at
Computational Fluid Dynamics
Global Climate or Weather Simulations
Flow in Porous Media
Study of Phase Transitions
We see as in GEM, uncertainties in some of critical basic physics but these fields have made clear progress even with a mix of phenomenology (turbulence models) and fundamental equations (e.g. Navier Stokes equations)
© 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 Sat Nov 28 1998