HW5 N-body Simulation (CUDA)

Due: Tue, 2023/05/16 23:59

• HW5 N-body Simulation (CUDA)
  • Introduction
  • Problem Description
  • Formulas & Parameters
    • Gravity Simulation
  • Parameters
  • I/O
    • Compilation
    • Command Line Format
    • Input Format
    • Output Format
  • Report
  • Submission
  • Grading
  • Resources
  • Judge
  • Judge Verdict Table

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 come 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 use NCHC container for this homework.

We will compile your program with a command equivalent to:

make

Command Line Format

Your program will be tested with a command equivalent to:

./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, /tmp/dataset-nthu-ipc23/share/hw5/samples/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. (50%) Correctness.
2. (20%) Performance. Based on the total time you solve all the test cases.
3. (30%) Report.

Resources

Refer to /tmp/dataset-nthu-ipc23/share/hw5 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/ipc23/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 /tmp/dataset-nthu-ipc23/share/hw5/samples/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

tags: spec