Skip to content

Latest commit

 

History

History
63 lines (54 loc) · 2.73 KB

README.md

File metadata and controls

63 lines (54 loc) · 2.73 KB
Raw

N-Body Problem Parallelization

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.

♟️ Algorithms

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.

👾 Implementations

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

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.

📚 Libs

To run the codes correctly you need to install the libraries:

  • open-mpi (C)
  • omp (C)
  • mathplot (Python, only to render the results)

💻 Usage

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.

To run the code:

  • 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