N Body Gravitational Problem

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

Recently Viewed Presentations

  • A JOURNEY THROUGH HELL Enter by the narrow

    A JOURNEY THROUGH HELL Enter by the narrow

    HELL IS REAL. Matthew 7:13-14 "Enter by the narrow gate; for wide is the gate and broad is the way that leads to destruction, and there are many who go in by it. 14 Because narrow is the gate and...
  • Topic 7: Economic Performance and Challenges

    Topic 7: Economic Performance and Challenges

    Inflation Rate: the percentage rate of change in price level over time. Core Inflation Rate: rate of inflation excluding effects of food and energy prices. In order to study long term trends in the inflation rate, economists set aside temporary...
  • Silkscreen Printing - SJA Art

    Silkscreen Printing - SJA Art

    In the 1930's it became popular as a means to make commercial prints in vivid opaque colour Silkscreen printing has been used to document life during the Depression, or used for propaganda purposes by various governments The technique was popularized...
  • Overview of Injury Research - Penn Engineering

    Overview of Injury Research - Penn Engineering

    All of the samples will be tested, each to a different cyclic load. Review the video to identify the failure cycle and to identify any pre-failure deformation. Statistical analysis of the populations of two stitch types. The stress-strain curve for...
  • Open Office.Org

    Open Office.Org

    Open Office.Org What is the Open Office.org Source Project? Open source project through which Sun Microsystems is releasing the technology for the popular Star Office(tm) productivity suite. Name of the overall project and is being hosted by CollabNet.
  • Data and Computer Communications

    Data and Computer Communications

    There is a simple relationship between the two sine waves, one in time and one in space. ... The bandwidth of the transmitted signal as constrained by the transmitter and the nature of the transmission medium, expressed in cycles per...
  • The Body of a News Story - College of Charleston

    The Body of a News Story - College of Charleston

    The Body of a News Story Chapter 9 Storytelling Styles Organizing the Story (Four Styles) Inverted pyramid—summary lead then information in descending order of importance (dates back to the American Civil War) Hour glass style—starts with inverted pyramid, then has...
  • Finding a model to suit South Africa Dr

    Finding a model to suit South Africa Dr

    Finding a model to suit South Africa Dr Japie du Toit Healthcare Advisor PricewaterhouseCoopers