This project contains several C implementations capable of parallelizing the n-body problem. The project was made by students for a Multicore Programming course within a BSc degree program in Computer Science.
Two algorithms were used to experiment:
- A trivial direct sum algorithm with time complexity:
$O(n^3)$ - The Barnes-Hut algorithm with time complexity:
$O(n \log n)$
Both algorithms have been parallelized and compared.
A single process version and two multicore versions are provided for both algorithms:
- One with distributed memory, implemented using the MPI library.
- One with shared memory, implemented using the OpenMP library.
In this repository you will find:
- Various versions of optimization procedures done on the initial code.
- A detailed report explaining the various optimizations and the reason behind the choices made.
- Some utility Python scripts that are able to:
- Carry out performance tests
- Generate input files with random bodies
- Render the output file and have a graph of the bodies
- Test the similarity between the outputs of the different implementations
- The data used for performance analysis, including pre-populated input csv files end some expected results.
To run the codes correctly you need to install the libraries:
- open-mpi (C)
- omp (C)
- mathplot (Python, only to render the results)
First, clone this repository. In each subfolder there is a makefile that automatically compiles the associated version. Set the current working directory to the desired folder and run make.
- exhaustive sequential version
.\<name_of_executable> <input_file> <simulation_steps>- Barnes Hut sequential version
.\<name_of_executable> <input_file> <simulation_steps> <approx_threshold>- exhaustive mpi version
mpirun -n <number_of_cores> <name_of_executable> <input_file> <simulation_steps>- Barnes Hut mpi version
mpirun -n <number_of_cores> <name_of_executable> <input_file> <simulation_steps> <approx_threshold>- exhaustive omp version
.\<name_of_executable> <input_file> <simulation_steps> <thread_count>- Barnes Hut omp
.\<name_of_executable> <input_file> <simulation_steps> <approx_threshold> <thread_count>The output file will be written to the current directory with the name output.csv