Basic IMAGE version of Foils prepared 20 October 1997

Foil 27 Representing the Message Parallel N-Body problem

From Fox Presentation Fall 1995 CPS615 Basic Simulation Track for Computational Science -- Fall Semester 97. by Geoffrey C. Fox
(0 to 5):

© 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 Mon Apr 12 1999

Table of Contents for N Body Problems using Message Parallel Approach

CPS 615 Lectures 1998 Fall Semester -- Message Parallel N Body
1 CPS 615 -- Computational Science in
Simulation Track
Message Parallel Module on ODE's and Particle Dynamics
October 20, 1997
2 Abstract of Message Parallel ODE and Particle Dynamics
Particle Dynamics as applications
3 Particle (N-Body) Applications and Ordinary Differential Equations (ODE's)
4 Particle Applications - Ordinary Differential Equations (ODE's)
5 Particle Applications - the N-body problem
6 Newton's First Law -- The Gravitational Force on a Particle
7 Equations of Motion -- Newton's Second Law
ODE Solution Techniques
8 Numerical techniques for solving ODE's
9 Second and Higher Order Equations
10 Basic Discretization of Single First Order Equation
11 Errors in numerical approximations
12 Runge-Kutta Methods: Euler's method
13 Estimate of Error in Euler's method
14 Relationship of Error to Computation
15 Example using Euler's method from the CSEP book
16 Approximate solutions at t=1,using Euler's method with different values of h
17 Runge-Kutta Methods: Modified Euler's method
18 Approximate solutions of the ODE for et at t=1, using modified Euler's method with different values of h
19 The Classical Runge-Kutta -- In Words
20 The Classical Runge-Kutta -- Formally
21 The Classical Runge-Kutta Pictorially
22 Predictor / Corrector Methods
23 Definition of Multi-step methods
24 Features of Multi-Step Methods
25 Comparison of Explicit and Implicit Methods
Setup of N Body Problem
26 Solving the N-body equations of motion
27 Representing the Message Parallel N-Body problem
28 Form of the Computation -- Message Parallel
29 Summary of Parallel N-Body Programming Methods and Algorithms
30 Status of Parallelism in Various N Body Cases
31 Other N-Body Like Problems - I
32 Other N-Body Like Problems - II
Message Parallel Approach
33 Essential Structure of Message Parallel O(N2) Algorithm - I
34 Essential Structure of Message Parallel O(N2) Algorithm - II
35 Structure of Runge Kutta Phases
36 The 9 Fortran Phases in Runge Kutta Update
37 Features of Message Parallel Computation
38 Message Parallel Force Computation MPGrav
3 Message Parallel Methods
39 Very Bad Naive Message Parallel Algorithm
40 Features of Very Bad Naive Message Parallel Algorithm
41 Much Better Message Parallel Algorithm
42 Blocking of Messages
43 Compilers, Caches and Data Locality
44 Communication and Computation Complexity
One Dimensional System Dimension
45 N-body Problem is a one dimensional Algorithm
46 Factor of Two in the Parallel O(N2) Algorithm
47 Best Message Parallel N Body Algorithm - I
48 Best Message Parallel N Body Algorithm - II
Decomposition Approaches Block Cyclic Scattered
49 Choice of Place to Compute Fi,j
50 The Two Basic Distributions in HPF
51 The Example of Matrix Inversion
52 Example of Graphics Rendering
Pipeline Approach
53 Final Remarks on Best Algorithm
54 Better Data Parallel Pipeline Algorithm for Computation of Accelerations,
taking 1/2 the time for iterations over force computation
55 Pipeline Algorithm in detail
56 Basic Message Parallel pipeline operation
57 Examples of Message Parallel Pipeline Algorithm
References
58 Notes and References
Click outside pointer rectangle to move pointer
Click on Pointer to Hide
Click on Pointer + ALT to toggle message hiding
Click on Pointer + CNTL to abolish pointer
Click on Pointer + Shift to cycle families
Click outside + Alt is Change Image
Click outside + Control is Double Size
Click outside + Shift is Halve Size
Right Mouse Down on Pointer Toggles Index
Shift Right Mouse aligns top with scrolled Page
While With Mouse Down on Current Pointer
h hides This Message while m restores
i Toggles Index Aligned with Page Top
j Toggles Index Aligned with Scrolled View Top
a Abolishes Pointer while CNTL-Click restores
f cycles through pointer families
c cycles through members of a family
u increases Size Up and d decreases Down
Mouse Up-Down between changes of
Pointer to process new option