Changes

The program I found is an n-body simulation using a brute force algorithm. It essentially does an n-body simulation of O(n^2) efficiency and displays the visual output onto the screen. For testing purposes-as well as for compatibility issues-I disabled the visual output and redirected the graphics libraryfunction call, vga_setmode, to text mode (0)). '''Testing Environment:''' *Operating System: Ubuntu 12.10, 32-bit *Compiler: GNU C++, version 4:4.7.2-1ubuntu2 *Processor: Intel(c) Core(tm) i5 CPU M 480 @ 2.67GHz x 4 *Graphics Card: Intel(c) HD Graphics 2000 *Memory: 5.7GB '''How to Setup (on Linux machines with admin priveleges only):'''* Download source file: [http://sourceforge.net/projects/nbodysim01/files/nbodysim01/C%2B%2B_code/galaxy_0.1.cpp.gz/download | n-body-simulation]* Install required libraries/utils:<refpre>ysudo apt-get install g++ sudo apt-get install libsvgal-dev</refpre>* Compile and run:<pre> g++ galaxy_0.1.cpp -lvga -pgsudo ./a.out</pre>  '''Analysis:''' The program contains 1 main function that takes up 90% of the execution time: Calculate_Gravity(). The reason being that the function has 3 for loops. 1 for loop to text mode)reinitialize the bodies' locations. The other 2 for loops are nested and is what does the main calculations of the simulation. <pre> for (i=0; i<=NumP-1; i++) { xa[i]=0; ya[i]= Assignment 2 0; za[i]=0; }for (i=0; i<=NumP-1; i++){ for (j=i+1; j<=NumP-1; j++) { // calculating statements </pre> Another hot spot in the code was the function planet::Interact(...) because it had to do a lot of calculations for each body <pre>for (i= Assignment 3 0;i<=NumP-1;i++) if (P[i].exist) P[i].Interact(xa[i],ya[i],za[i],swx,swy,swz);</pre> and then update the visual of each position. <pre>if (ins){ vga_setcolor(colr); vga_drawpixel (xpos,ypos); if (prj) Projection(7,sc);}</pre> Right now, the functions are running once at a time, making the program run slower. If both Calculate_Gravity() and planet::Interact(...)'s for loops were parallelized, there would be a significant speedup. Using Amdahl's Law: <pre> S1344 =1 / ( 1 - 0.9982 + 0.9982 / 1344) =393.28</pre> A ~393 times speedup would make a function that took 24.16 seconds to execute, only 0.06 seconds. '''Flat Profiles''' [http://zenit.senecac.on.ca/wiki/imgs/Dps915_neil_flat_profiles.pdf Flat Profiles for 100,500,1000,5000,10000 bodies]  '''Calculate_Gravity() Excel Charts:'''<gallery>File:Dps915_neil_exec_calc.png|Execution TimeFile:Dps915_neil_self_calc.png|Self SecondsFile:Dps915_neil_calls_calc.png|Self Calls</gallery>  '''Difficulties Met:''' The main difficulty was trying to find and install the library that would let the code compile. The library that the program uses, svgalibs, is an old library meant for displaying images on linux machines. This means that the program itself would try and access the /dev/tty of the linux system-this is also why you needed admin privileges to run the program.  Another difficulty was the initial reading of the code and trying to understand it. After a couple more reading, it becomes easier to understand and it looks like it could be improved much more by changing the graphics used and the structure of the code. If we end up choosing this, the difficulty might light in the fact that we have to update the technologies used (graphics library), restructure the code, and possibly change the algorithm to Barnes-hut.  '''Summary:'''* Algorithm used: Brute force O(n^2), is way too ineffecient for high numbers of n** Can be improved upto O(n log n) through use of Barnes-hut algorithm* Main function to parallelize: Calculate_Gravity(), due to these for loops: <pre>

=== Resources Assignment 2 ===<references/>=== Assignment 3 ===