# N Body Gravitational Problem N BODY GRAVITATIONAL PROBLEM Seminar By Srinivasan Manoharan PROBLE M 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 Fii=G*mii*((mjjrijij)/rijij33) 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 ,ai aibody =G*((m jrij)/

(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 . F1 1 F1 2 F1j F1 n 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 Fij Fin

Fnj Fnn Fi2 F1 3 Fi3 F1 4 Fi4 F1 5 Fi5 F1 6 Fi6 Fn1 Fn2 Fn3 Fn4 Fn5 Fn6 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 N 2 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 By Varying By varying By varying the the the the number number number number of

of of of bodies N interacting iterations. threads per block. 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) 12000 10000 10 8 2 Iteration 16 Iteration 128 iterations 6 4 8000

6000 4000 2000 2 0 0 Time in milli seconds Time in Milli Seconds 12 5000 10000 15000 20000 Number of Bodies 0 0 20 00 40 00 60 00 80 00 10 00 0 12 00 0 14 00 0

16 00 0 18 00 0 14 Time Vs N(Sequential) Time vs N (Parallel) Number of Bodies (N) PERFORMANCE (TIME VS PROCESSORS) Time Vs Number of Nodes 70 60 Time in Milli sec 50 40 128 iterations 30 20 10 0 1 2 3 4 5

6 7 Number of Processors 8 9 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