Find this at
http://www.npac.syr.edu/users/gcf/cps615nbody97/
N Body Problems using Message Parallel Approach
Given by Geoffrey C. Fox at CPS615 Basic Simulation Track for Computational Science on Fall Semester 97. Foils prepared 20 October 1997
|
This uses the simple O(N2) Particle Dynamics Problem as a motivator to discuss solution of ordinary differential equations
|
|
We discuss Euler, Runge Kutta and predictor corrector methods
|
|
Various Message parallel O(N2) algorithms are described with performance comments
|
|
There is a related data parallel module sharing the same initial foils
|
This mixed presentation uses parts of the following base foilsets which can also
be looked at on their own!
CPS615-95E CPS615 Foils -- set E: ODE's and Particle
Dynamics
CPS615F90HPF96 Overview of Fortran 90 and HPF Fall 96
CPS 615 Lectures 1998 Fall Semester -- Message Parallel N Body
CPS615-95E 051 001 CPS 615 -- Computational Science in
Simulation Track
Message Parallel Module on ODE's and
Particle Dynamics
October 20, 1997
CPS615-95E 052 002 Abstract of Message Parallel ODE and
Particle Dynamics
Particle Dynamics as applications
CPS615-95E 003 003 Particle (N-Body) Applications and
Ordinary Differential Equations
(ODE's)
CPS615-95E 004 004 Particle Applications - Ordinary
Differential Equations (ODE's)
CPS615-95E 005 005 Particle Applications - the N-body
problem
CPS615-95E 006 006 Newton's First Law -- The
Gravitational Force on a Particle
CPS615-95E 007 007 Equations of Motion -- Newton's
Second Law
ODE Solution Techniques
CPS615-95E 008 008 Numerical techniques for solving
ODE's
CPS615-95E 009 009 Second and Higher Order Equations
CPS615-95E 010 010 Basic Discretization of Single First
Order Equation
CPS615-95E 011 011 Errors in numerical approximations
CPS615-95E 012 012 Runge-Kutta Methods: Euler's method
CPS615-95E 013 013 Estimate of Error in Euler's method
CPS615-95E 014 014 Relationship of Error to Computation
CPS615-95E 015 015 Example using Euler's method from
the CSEP book
CPS615-95E 016 016 Approximate solutions at t=1,using
Euler's method with different values
of h
CPS615-95E 017 017 Runge-Kutta Methods: Modified
Euler's method
CPS615-95E 018 018 Approximate solutions of the ODE for
et at t=1, using modified Euler's
method with different values of h
CPS615-95E 019 019 The Classical Runge-Kutta -- In
Words
CPS615-95E 020 020 The Classical Runge-Kutta --
Formally
CPS615-95E 021 021 The Classical Runge-Kutta
Pictorially
CPS615-95E 022 022 Predictor / Corrector Methods
CPS615-95E 023 023 Definition of Multi-step methods
CPS615-95E 024 024 Features of Multi-Step Methods
CPS615-95E 025 025 Comparison of Explicit and Implicit
Methods
Setup of N Body Problem
CPS615-95E 026 026 Solving the N-body equations of
motion
CPS615-95E 075 027 Representing the Message Parallel
N-Body problem
CPS615-95E 076 028 Form of the Computation -- Message
Parallel
CPS615-95E 053 029 Summary of Parallel N-Body
Programming Methods and Algorithms
CPS615-95E 054 030 Status of Parallelism in Various N
Body Cases
CPS615-95E 055 031 Other N-Body Like Problems - I
CPS615-95E 056 032 Other N-Body Like Problems - II
Message Parallel Approach
CPS615-95E 057 033 Essential Structure of Message
Parallel O(N2) Algorithm - I
CPS615-95E 058 034 Essential Structure of Message
Parallel O(N2) Algorithm - II
CPS615-95E 059 035 Structure of Runge Kutta Phases
CPS615-95E 060 036 The 9 Fortran Phases in Runge Kutta
Update
CPS615-95E 061 037 Features of Message Parallel
Computation
CPS615-95E 062 038 Message Parallel Force Computation
MPGrav
3 Message Parallel Methods
CPS615-95E 063 039 Very Bad Naive Message Parallel
Algorithm
CPS615-95E 064 040 Features of Very Bad Naive Message
Parallel Algorithm
CPS615-95E 065 041 Much Better Message Parallel
Algorithm
CPS615-95E 066 042 Blocking of Messages
CPS615-95E 067 043 Compilers, Caches and Data Locality
CPS615-95E 068 044 Communication and Computation
Complexity
One Dimensional System Dimension
CPS615-95E 046 045 N-body Problem is a one dimensional
Algorithm
CPS615-95E 080 046 Factor of Two in the Parallel O(N2)
Algorithm
CPS615-95E 069 047 Best Message Parallel N Body
Algorithm - I
CPS615-95E 070 048 Best Message Parallel N Body
Algorithm - II
Decomposition Approaches Block Cyclic Scattered
CPS615-95E 071 049 Choice of Place to Compute Fi,j
CPS615F90HPF96 041 050 The Two Basic Distributions in HPF
CPS615F90HPF96 042 051 The Example of Matrix Inversion
CPS615F90HPF96 043 052 Example of Graphics Rendering
Pipeline Approach
CPS615-95E 072 053 Final Remarks on Best Algorithm
CPS615-95E 036 054 Better Data Parallel Pipeline
Algorithm for Computation of
Accelerations,
taking 1/2 the time for iterations
over force computation
CPS615-95E 077 055 Pipeline Algorithm in detail
CPS615-95E 078 056 Basic Message Parallel pipeline
operation
CPS615-95E 079 057 Examples of Message Parallel
Pipeline Algorithm
References
CPS615-95E 050 058 Notes and References
List of Foils Used as they occur
CPS615-95E CPS615 Foils -- set E: ODE's and Particle
Dynamics
51 52 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 75 76 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 46 80 69 70 71 72 36 77 78 79 50
CPS615F90HPF96 Overview of Fortran 90 and HPF Fall 96
41 42 43
Sorted List of Foils Used
CPS615-95E CPS615 Foils -- set E: ODE's and Particle
Dynamics
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 36 46 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 75 76 77 78 79 80
CPS615F90HPF96 Overview of Fortran 90 and HPF Fall 96
41 42 43
© 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 Fri Oct 2 1998