HW5 N-body Simulation (CUDA)

# HW5 N-body Simulation (CUDA) Due: Mon, 2022/5/31 23:59 Slide: https://docs.google.com/presentation/d/1YrModN2q3REyAPNeJinDfzcetjSHN0HB2z-b5akrEns/edit?usp=sharing [TOC] ## Changelog 2022/5/28: Update missile cost error tolarance. 2022/5/26: Update the formula of the missile cost. 2022/5/18: We update the formula of the missile cost and fix a bug in the judger. 2022/6/9: Update problem description. ## Introduction * Simulation of a dynamical system of particles Under the influence of gravity * The dataset is an imitation of our Milky Way galaxy In this homework, your are asked to use CUDA with 2 GPUs to perform the simulation. ## Problem Description Please refer to the homework slides for problem description. You should implement the parallel code with brute force algorithm. No need to implement Barnes-Hut Algorithm. ## Formulas & Parameters ### Gravity Simulation 1. Calculating the force vector on body $i$ cuased by body $j$: $$f_{ij} = \frac{Gm_im_j}{||q_j - q_i||^2} \cdot \frac{q_j - q_i}{||q_j - q_i||} = \frac{Gm_im_j(q_j - q_i)}{||q_j - q_i||^3}$$ 2. Calculating total force vector on body $i$ caused by other $N - 1$ bodies: $$F_i = \sum_{j \neq i} f_{ij} = \sum_{j \neq i} \frac{Gm_im_j(q_j - q_i)}{||q_j - q_i||^3}$$ 3. To avoid the gravitational force growing indefinitely in situation when two bodies com too close, we add a softening factor $\varepsilon$: $$F_i \approx \sum_{j \neq i} f_{ij} = \sum_{j \neq i} \frac{Gm_im_j(q_j - q_i)}{(||q_j - q_i||^2 + \varepsilon^2)^{ \frac{3}{2}}}$$ 5. Update velocities by: $$v_i(t) = v_i(t-\Delta t) + a_i(t) \cdot \Delta t$$ 6. Update position by: $$q_i(t) = q_i(t - \Delta t) + v_i(t) \cdot \Delta t$$ ## Parameters * Simulation steps: 200000 * Time difference between each time step(sec): $\Delta t = 60$ * Softening factor(m): $\varepsilon = 10^{-3}$ * Gravity constant($m^3kg^{-1}s^{-2}$): $G = 6.674 * 10^{-11}$ * Gravity devices’ mass (kg): $m(t) = m(0) + 0.5 \cdot m(0) \cdot |\sin{\frac{t}{6000}}|$ * The asteroid hits the planet if their distance at a time step is below(m):$10^7$ * Missile traveling speed($m/s$): $10^6$ * Missile cost: $10^5 + (step+1)*\Delta t*10^3$ where $t$ is the time the missile reach the asteroid. **All the units given above are SI units, so you don’t need to do conversion. (If you find otherwise, it’s a bug! Please let the TAs know)** ## I/O ### Compilation We will compile your program with a command equivalent to: ```bash make ``` ### Command Line Format Your program will be tested with a command equivalent to: ```bash srun -pipc22 -c2 --gres=gpu:2 ./hw5 input_file output_file ``` ### Input Format The input is a text file looking like this: ``` N planet-id asteroid-id qx0 qy0 qz0 vx0 vy0 vz0 m0 type0 qx1 qy1 qz1 vx1 vy1 vz1 m1 type1 qx2 qy2 qz2 vx2 vy2 vz2 m2 type2 ... ``` The first line of the input file contains three integers, which are: 1. $N$, the number of celestial bodies. 2. $ID_{planet}$ the (0-indexed ) ID of the planet. 3. $ID_{asteroid}$, the ID of the asteroid. Then there are N lines following, each contains 8 values: 1. $q_{xi}(0), q_{yi}(0), q_{zi}(0)$: the initial position of the i-th body, ```double```. 2. $v_{xi}(0), v_{yi}(0), v_{zi}(0)$: the initial velocity of the i-th body, ```double```. 3. $m_{i}(0)$: the initial mass of the body, ```double```. 4. $type_i$: the type of the body,```string```. ### Output Format The output is a text file looking like this: ``` min-dist hit-time-step gravity-device-id missile-cost ``` * The first line is the minimal distance between the asteroid and the planet if there were no gravity devices. This value is considered correct if the relative error is within $10^{-8}$. * The second line is the time step that the asteroid hit the planet. If the asteroid did not hit the planet, output -2. This value is considered correct if the absolute error is within $\pm 1$ . * The third line contains two numbers. ```gravity-device-id``` is the ID of the gravity device that we want to destroy, ```missile-cost``` is the cost of the missile. If there is no need to destroy the gravity devices, output -1 0. If destroying one gravity device couldn’t prevent the asteroid hitting the planet, output -1 0 as well. missile-cost is considered correct if the absolute error is within $6*10^{4}$. ## Report Answer the following questions, in either English or Traditional Chinese. 1. What is your parallelism strategy? 2. If there are 4 GPUs instead of 2, what would you do to maximize the performance? 3. If there are 5 gravity devices, is it necessary to simulate 5 n-body simulations independently for this problem? 4. (Optional) Any suggestions or feedback for the homework are welcome. ## Submission Upload these files to eeclass: * ```hw5.cu``` – the source code of your implementation. * ```Makefile``` – optional. Submit this file if you want to change the build command. If you didn’t submit this file, ```/home/ipc22/share/hw5/sample/Makefile``` will be used. * ```report.pdf``` – your report. Please follow the naming listed above carefully. Failing to adhere to the names above will result to points deduction. ## Grading 1. (40%) Correctness. 2. (40%) Performance. Based on the total time you solve all the test cases. 3. (20%) Report. ## Resources Refer to ```/home/ipc22/share/hw5/``` on hades for sample test cases, source codes and tools. ## Judge The `hw5-judge` command can be used to automatically judge your code against all sample test cases, it also submits your execution time to the scoreboard so you can compare your performance with others. Scoreboard: https://apollo.cs.nthu.edu.tw/ipc22/scoreboard/hw5/). To use it, run ```hw5-judge``` in the directory that contains your code ```hw5.cu```. It will automatically search for ```Makefile``` and use it to compile your code, or fallback to the TA provided ```/home/ipc22/share/hw5/sample/Makefile``` otherwise. If code compiliation is successful, it will then run all the sample test cases, show you the results as well as update the scoreboard. ## Judge Verdict Table |Verdict | Explaination| |------- | ------------| |internal error| there is a bug in your code | |time limited exceeded+|execution time > time limit + 10 seconds| |time limited exceeded|execution time > time limit| |runtime error|your program didn’t return 0 or is terminated by a signal| |no output|your program did not produce an output| |wrong answer|your output is incorrect| |accepted|you passed the test case|