Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

159.341 – 2023 Semester 1

Assignment 3

Deadline:

Hand in by 5pm on Friday 2nd June 2023

Evaluation:

15 marks which is 15% of your final grade

Late Submission:

1 mark off per day late

Work:

This assignment is to be done individually your submission may be checked for plagiarism  against  other  assignments  and  against  Internet repositories.  If you adapt material from the internet you must acknowledge your source.

Purpose:

Parallelise an existing program

Problem to solve:

A sequential implementation of an n-body simulator is available on the course stream site. This program simulates the motion of a number of bodies (planets, particles etc) with an attractive force between  each  pair  of  particles.  Your  task  is  to  convert  this  program  to  a  multi-threaded implementation with the purpose of improving performance.

Description:

You may use whichever multi-threading library/API you choose to convert the simulator to a multi- threaded implementation  intended  for  a multi-core PC.  The  current  implementation  is written  in C/C++ but you may write your new implementation in a different programming language if you so choose.

You are free to re-arrange the computation however you see fit but the simulator must compute the force  between  each  pair  of particles  (n2   operations)  and  perform  the  calculations  using  double precision floating-point values. Do not attempt to convert the program to an nlog(n) algorithm or similar method.

The state of a body in an n-body simulation consists of a position, velocity, mass and radius.

struct body {

vec2 pos;

vec2 vel;

double mass;

double radius;

}; ...

The force between each pair of bodies can be calculated by iterating through every pair.

// for each body

for(int i = 0; i < N; ++i) {

// for each following body

for(int j = i+1; j < N; ++j) {

// Calculate force between bodies

...

}

}

The force between two bodies is calculated from their relative positions and masses and accumulated in an array of accelerations.

vec2 dx = bodies[i].pos - bodies[j].pos;

vec2 u = normalise(dx);

double d2 = length2(dx);

if(d2 > min2) {

// Difference in position

// Normalised difference in position

// Distance squared

// If greater than minimum distance

double f = -G*bodies[i].mass*bodies[j].mass / d2; // Force

acc[i] += (u * f / bodies[i].mass);               // Accumulate acceleration

acc[j] -= (u * f / bodies[j].mass);               // Accumulate acceleration

}

Finally, the new state (position and velocity) of each body can be calculated from the old state, the accumulated acceleration and the timestep dt.

// For each body

for(int i = 0; i < N; ++i) {

bodies[i].pos += bodies[i].vel * dt; // Update Position

bodies[i].vel += acc[i] * dt;        // Update Velocity

}

Details:

The sequential implementation can be compiled into an executable that has a real-time graphics         display or a version with no real-time graphics but that writes the final positions and an image to file. The real-time graphics version can be compiled by including the flag -DGRAPHICS and linking to   the SFML libraries (available here https://www.sfml-dev.org/).

Requirements:

•   You must provide full details of the language and multi-threaded API you used to develop the implementation (including any version information and any specific flags).

•   Your  submission  will  be  ranked  based  on  its  performance.  The  performance  will  be benchmarked on a lab machine with a large number of particles (>= 5000).

•   The particle positions produced by your implementation (written to output.dat) should be almost  the  same  as  the  original  sequential  version.  Be  aware  that  there  may  be  slight differences due to floating-point errors (you should expect that at least the first 6 decimal places should be identical).

You must follow the next two specifications in each and every assignment for this course

1.   Place the following comments at the top of your program code and provide the  appropriate information:

/* Family Name, Given Name, Student ID, Assignment number, 159.341

*/

/* explain what the program is doing . . . */

2.   Ensure that your main function uses printf to print this information to the console.  You might use code like:

int main( int argc, char * argv[] ){

printf( "----------------------------------------" );

printf( "  159.341 Assignment 3 Semester 1 2023  " );

printf( "  Submitted by: Rick Deckard, 20191187  " );

printf( "----------------------------------------" );

}  ...

Hand-in: Submit your program and documentation (a zip file is acceptable) electronically through the form on the stream site.

Marks  will  be  allocated  for:  correctness,  fitness  of purpose,  sensible  use  of data  structures  and algorithms,  utility,  style,  use  of sensible  comments  and  program  documentation,  and  general elegance. Good comments will help me to award you marks even if your code is not quite perfect.

If you have any questions about this assignment, please ask the lecturer.