Transcript N Body Gravitational Problem

N BODY GRAVITATIONAL
PROBLEM
Seminar
By Srinivasan Manoharan
PROBLEM




To compute the position of N bodies over a set of Iterations
by using the forces that exists between the other bodies.
A big mathematical conundrum
I chose this problem because of the huge amount of
computation involved in this problem.
Mathematical Problem:Consider n point masses in three dimensional space
 Assumption :- Force experienced between them is Newtonian.
 Then, if the initial positions in space and initial velocities are
specified for every particle at some present instant t0,
determine the position of each particle at every future (or
past) moment of time

PROBLEM(CONTD..)






The All Pairs Approach is a brute force technique which
evaluates the interactions between all the pairs of the N
bodies.
The problem with this approach is that the worst case
computational complexity is O(N2).
The all pair approach is used for evaluating bodies that are
interacting very closely.
So the all pairs method is combined with a more efficient
method ,far field approximation of long range forces(Barnes
Hut method).
This far field method is only valid when the two bodies are
well separated.
The all pairs method requires substantial time to compute
and an area where acceleration can be used.
CALCULATION

Force Between two bodies with a distance r is
Fij=G*(mi*mj)/rij2

The total Force on the Body i is the summation of the all the forces other
than i. i.e
Fi=∑Fij
Fi=G*mi*∑((mjrij)/rij3)
where j is 1 to N and not equal to j.

Due to approximation, softening factor is included and Force = mass *
Acceleration.
Fi=G*mi*∑((mjrij)/(rij2+ε2)3/2).

Acceleration of the body ,ai
ai=G*∑((mjrij)/(rij2+ε2)3/2).
CALCULATION (CONTD..)


With acceleration calculated , we can get the velocity v and
the distance x for the body to move .
We can calculate all Fij in a grid of size N * N .
F11 F12 F13 F14 F15 F16
F1j
F1n
F21
F22
F23
F24
F25
F26
F2j
F2n
F31
F32
F33
F34
F35
F36
F3j
F3n
F41
F42
F43
F44
F45
F46
F4j
F4n
Fi1
Fi2
Fi3
Fi4
Fi5
Fi6
Fij
Fin
Fn5 Fn6
Fnj
Fnn
Fn1 Fn2 Fn3 Fn4
STRATEGY





First we randomly position the bodies in the 3 dimensional
space.
Then we calculate the force exerted in all the axis using the
formula.
We calculate the acceleration by dividing the force by mass
We calculate the velocity by multiplying the acceleration
with delta time.
Then finally we calculate the new position by multiplying
the velocity with delta time.
STRATEGY




Each entry in the Grid can be calculated independently ,
therefore there is N2 parallelism.
But Since the memory is limited, we cannot use N2 threads
each computing the force in the grid.
So we can calculate the forces in a row to be calculated in
sequential order .
And parallelize the columns as each thread can calculate
the Force and acceleration of the body .
ANALYSIS

We need to obtain the performance by
By varying the number of bodies N interacting
 By Varying the number of iterations.
 By varying the number of threads per block.
 By varying the number of processors.


The number of threads per block can also be
varied ,but the performance was better when I
used p= 256 i.e 256 threads per block.
Number of Blocks = Number of Bodies / Number of threads
TABLE (N & NUMBER OF ITERATIONS)-SEQUENTIAL
N - Number of Bodies
2 Iteration
16 Iteration
128 iterations
2
0.017
0.027
0.097
4
0.023
0.052
0.281
8
0.042
0.245
1.45
16
0.108
0.501
3.652
32
0.364
0.623
20.34
64
1.352
7.421
52.469
128
5.235
49.456
120.23
256
20.697
74.89
234.56
512
72.85
202.441
404.57
1024
185
499.772
613.42
2048
230.24
770.268
1,271.87
4096
264.123
1087.857
2,157.59
8192
834.123
3050.968
6,775.38
16384
3238.89
8459.216
10,345.23
TABLE (N & NUMBER OF ITERATIONS)-PARALLEL
N - Number of Bodies
Time for 2 Iteration in Milli sec 16 Iteration
128 iterations
2
0.733
0.837
2.818
4
0.736
0.874
3.204
8
0.762
1.039
3.456
16
0.773
1.054
3.531
32
0.78
1.074
3.653
64
0.801
1.097
3.698
128
0.874
1.06
3.768
256
0.895
1.168
3.897
512
0.981
1.288
4.034
1024
1.117
1.321
4.245
2048
1.527
2.676
4.438
4096
2.45
3.549
4.772
8192
3.214
4.292
6.351
16384
6.21
8.23
11.774
PERFORMANCE(TIME VS N)
Time Vs N(Sequential)
Time vs N (Parallel)
12000
14
10000
10
8
2 Iteration
6
16 Iteration
128 iterations
4
Time in milli seconds
Time in Milli Seconds
12
8000
6000
4000
2000
2
0
0
0
10000
20000
Number of Bodies
0
5000
10000
15000
Number of Bodies (N)
20000
PERFORMANCE (TIME VS PROCESSORS)
Time Vs Number of Nodes
70
60

Time in Milli sec
50
40
128 iterations
30
20
10
0
0
2
4
6
8
Number of Processors
10
As the number of
Nodes increases ,
the performance is
better .
ANALYSIS & INFERENCE
The number of calculations involved is
34357641220 and computed in 11.4 milli seconds.
 Each calculation involves 14 operations.
 When the number of computation is less the
processors are underutilized.
 But when the calculations increase the
performance is far better than the sequential
code.
 When the number of bodies is 32 the
performance is better in parallel .i.e 126976
calculations.

QUESTIONS
Thank You