A high-performance N-body gravitational simulation implementing serial, OpenMP, and MPI parallelisation strategies for performance comparison and analysis. Completed as part of High Performance Computing coursework.
This project simulates the gravitational interactions between N bodies in 3D space using Newton's law of universal gravitation. The simulation implements four different approaches:
- Serial implementation: Baseline single-threaded execution for performance benchmarking
- OpenMP implementation: Shared-memory parallelisation using multi-threading
- MPI implementation: Distributed-memory parallelisation across multiple processes
- Visualisation implementation: Real-time graphical display using SFML library
The project was developed as part of a High-Performance Computing (HPC) module to explore and compare different parallelisation paradigms, with an additional visualisation component for educational demonstration.
The simulation uses a direct N-body algorithm where every body interacts with every other body through gravitational forces:
F = G * (m₁ * m₂) / r²
Where:
Gis the gravitational constant (normalised to 1.0)m₁andm₂are the masses of two bodiesris the distance between them
The system evolves using a simple Euler integration scheme with time step dt = 0.1.
The baseline implementation uses a nested loop structure with O(N²) complexity:
- Outer loop: iterates through all bodies
- Inner loop: calculates pairwise forces with remaining bodies
- Newton's third law is exploited to reduce calculations by half
Parallelises the force calculation loop using:
- Thread-local force arrays to avoid race conditions
#pragma omp parallelfor thread creation#pragma omp for schedule(static, 2)for work distribution#pragma omp criticalsection for force accumulation- Configurable thread count (default: 2 threads)
Distributes the computation across multiple processes using:
MPI_InitandMPI_Finalizefor MPI environment setup/teardown- Process-local force arrays for independent computation
- Rank-based work distribution using strided loop iteration (
i = rank; i < N; i += size) MPI_AllreducewithMPI_SUMoperation to combine forces from all processes- Each process computes forces for a subset of bodies based on its rank
- Synchronisation ensures all processes have consistent position and force data
Provides real-time graphical rendering of the N-body simulation using SFML (Simple and Fast Multimedia Library):
- Displays bodies as coloured circles in a 800×600 window
- Uses random red-tinted colours for visual distinction
- Maps 3D positions to 2D screen coordinates (projects x-y plane)
- Smaller time step (
dt = 0.001) for smoother animation - Adjustable animation speed via sleep delay (default: 10ms per frame)
- Implements forward Euler integration with symplectic properties
- Increased body count to 900 for more dramatic visual effects
| Parameter | Value | Description |
|---|---|---|
| N | 840 | Number of bodies |
| T | 2000.0 | Total simulation time |
| dt | 0.1 | Time step size |
| G | 1.0 | Gravitational constant (normalised) |
| Parameter | Value | Description |
|---|---|---|
| N | 900 | Number of bodies |
| T | 2000.0 | Total simulation time |
| dt | 0.001 | Time step size (smaller for smoother animation) |
| G | 1.0 | Gravitational constant (normalised) |
| Window Size | 800×600 | Display resolution |
| Particle Radius | 5 pixels | Visual size of each body |
All quantities are randomly generated from normal distributions:
- Masses: μ = 1.0, σ = 0.0 (uniform mass)
- Positions: μ = 0.0, σ = 1.0 (centred distribution)
- Velocities: μ = 0.0, σ = 1.0 (random initial velocities)
g++ -O3 -o serial serial.cppg++ -O3 -fopenmp -o openmp OpenMP.cppmpic++ -O3 -fopenmp -o mpi MPI.cppg++ -O3 -o visualisation visualisation.cpp -lsfml-graphics -lsfml-window -lsfml-systemNote: SFML library must be installed for the visualisation version. See SFML installation guide
./serial./openmpTo change the number of threads, modify num_threads in the source code or set the environment variable:
export OMP_NUM_THREADS=4
./openmpmpirun -np 4 ./mpi./visualisationThe visualisation window will open automatically. Close the window to terminate the simulation. To adjust animation speed, modify the sleep_for milliseconds value in the source code (line ~145).
The simulation outputs execution time in seconds. Key metrics for comparison:
- Speedup: S(p) = T₁ / Tₚ
- Efficiency: E(p) = S(p) / p
- Parallel Overhead: Communication and synchronisation costs
- Serial: O(N²) per time step, baseline reference
- OpenMP: Scales with thread count, limited by memory bandwidth and critical section overhead
- MPI: Requires substantial communication for position/force data distribution
- Visualisation Performance: The visualisation version is not optimised for performance (single-threaded with rendering overhead)
- 2D Projection: Visualisation only displays x-y coordinates; z-axis depth not represented
- Numerical Integration: Simple Euler method; more accurate schemes (e.g., Verlet, RK4) would improve accuracy
- Collision Handling: No softening parameter or collision detection implemented
- Add Barnes-Hut or Fast Multipole Method for O(N log N) complexity
- Enhance visualisation with 3D rendering (OpenGL/Vulkan)
- Add interactive camera controls and zoom functionality
- Add energy conservation checks for validation
- Implement more sophisticated integration schemes (Verlet, leapfrog, RK4)
- C++11 compatible compiler
- Standard C++ libraries
- OpenMP support (gcc 4.9+, clang 3.8+, or equivalent)
- MPI library (OpenMPI, MPICH, etc.)
- SFML 2.5+ (Simple and Fast Multimedia Library)
- Graphics module
- Window module
- System module