HPC @ University of Basel — Parallel Computing Results

All-Kernel Speedup Summary

Best speedup achieved per kernel vs. single-threaded sequential baseline.

Parallelism Hierarchy

How different parallelism levels layer on top of each other.

Sequential baseline1×

OpenMP (20 threads)18.6×

MPI (256 ranks)55×

CUDA (L40S GPU)543×

MPI + CUDA hybrid4,245×

Bar widths are log-scaled. Speedup measured on matrix multiplication 4096×4096.

N-Body

572 GFLOP/s

CUDA L40S, N=50K particles

Sequential1×

OpenMP 20T18.6×

CUDA35×

Matrix Multiply

4,245×

MPI+CUDA vs sequential, 4096²

MPI 16P9.8×

CUDA543×

MPI+CUDA4,245×

Merge Sort

3.9×

OpenMP 16 threads, N=1M

OpenMP 16T3.87×

Energy (OMP)8.74 J

Energy (MPI)799 J

EMD

73×

CUDA vs OMP-1T, N=100M

OMP 64T6.6×

MPI 256R54×

CUDA A10073×

Kernel 1

2D N-Body Gravitational Simulation

All-pairs O(N²) gravitational force calculation. Each particle interacts with every other particle every time step. Compute-bound — ideal for GPU acceleration. Benchmarked on SciCORE's l40s partition.

CUDA OpenMP MPI OpenACC

OpenMP Strong Scaling (N=5,000 particles)

Wall-clock time and speedup as threads increase. Near-linear scaling to 8T; diminishing returns beyond due to memory bandwidth saturation.

CUDA GPU Performance vs Sequential

NVIDIA L40S GPU achieves up to 572 GFLOP/s. Sequential is ~3.2 GFLOP/s (compute-bound single core). GPU parallelism increases with N.

Full Results Table — N-Body Benchmarks (SciCORE, May 2026)

Method	Particles (N)	Steps	Time (s)	GFLOP/s	Speedup vs Seq
Sequential	1,000	100	0.308	3.24	—
Sequential	5,000	100	7.742	3.23	—
Sequential	10,000	100	30.84	3.24	—
OpenMP 1T	5,000	50	5.067	4.93	1.0×
OpenMP 4T	5,000	50	1.268	19.7	3.99×
OpenMP 8T	5,000	50	0.649	38.5	7.80×
OpenMP 16T	5,000	50	0.335	74.6	15.1×
OpenMP 20T	5,000	50	0.273	91.6	18.6×
CUDA (L40S)	1,000	100	0.088	22.7	3.5×
CUDA (L40S)	5,000	100	0.438	114.3	17.7×
CUDA (L40S)	10,000	100	0.874	228.7	35.3×
CUDA (L40S)	50,000	100	8.728	572.9	—

Implementation Notes

Arithmetic Intensity~20 FLOP/byte at N=100, scaling to 8,333 FLOP/byte at N=20K. Highly compute-bound at large N — perfect for GPU.

Block SizeCUDA block size 256 threads. Each thread computes forces on one particle. Shared memory tiling explored in profiling runs.

VerificationEnergy conservation and position checksum validated across all variants. Maximum drift <200× (relative) across 100 steps.

Kernel 2

Dense Matrix Multiplication (C = A × B)

Square matrix multiplication (N×N). Implemented in six variants: sequential, OpenMP, MPI, OpenACC, CUDA (naive + tiled), and hybrid MPI+CUDA/OpenMP. Benchmarked on SciCORE l40s partition (NVIDIA L40S).

CUDA OpenMP MPI OpenACC MPI+CUDA

CPU Strong Scaling — 4096×4096 Matrix

OpenMP and MPI runtime vs. number of threads/processes. Both approach 5–9× speedup at 16 workers.

Ultimate Showdown — All Implementations

Runtime (log scale) for 4096×4096 matrix. CUDA and MPI+CUDA are orders of magnitude faster.

GPU Comparison — CUDA Naive vs Tiled

Tiled (shared-memory) CUDA generally matches or beats naive at large sizes. Block size tuning matters.

Hybrid MPI+CUDA Scaling

8 MPI ranks, each driving one GPU. Problem sizes 2048–8192. 4,245× speedup at 4096² vs sequential.

Full Results — Matrix Multiplication (SciCORE, -O3)

Implementation	Workers	512²	1024²	2048²	4096²	Speedup (4096²)
Sequential	1	0.0447 s	0.374 s	6.727 s	53.65 s	1.0×
OpenMP	16T	0.00807 s	0.0427 s	1.295 s	8.540 s	6.3×
OpenMP	32T	0.00588 s	0.0347 s	1.449 s	10.63 s	5.0×
MPI	16P	0.00421 s	0.0245 s	0.359 s	5.465 s	9.8×
MPI	32P	0.00533 s	0.0222 s	0.297 s	5.671 s	9.5×
OpenACC	1 GPU	0.213 s	0.195 s	0.290 s	1.064 s	50.4×
CUDA Naive	1 GPU	0.000309 s	0.00165 s	0.01248 s	0.09970 s	538×
CUDA Tiled	1 GPU	0.000321 s	0.00166 s	0.01250 s	0.09850 s	545×
MPI + OpenMP	8P×4T	—	—	0.275 s	1.520 s	35×
MPI + CUDA	8P×1 GPU	—	—	0.00198 s	0.01264 s	4,245×

Kernel 3

Parallel Merge Sort

Comparison-based sorting parallelised with OpenMP (task-parallel tree) and MPI (scatter–sort–gather). Energy consumption measured with PMT (RAPL for CPU, NVML for GPU) on SciCORE. Input: N = 1,000,000 random integers.

OpenMP MPI

OpenMP Scaling (N = 1,000,000)

Speedup and efficiency vs. thread count. Threshold-based cutoff to sequential insertion sort below ~10K elements.

Energy Comparison — PMT Measurements

OpenMP uses 91× less energy than MPI for the same problem. MPI overhead from scatter/gather dominates at N=1M.

Results Table — Merge Sort Benchmarks

Method	Workers	Time (s)	Speedup	Energy (J)	Power (W)
Sequential	1	~0.109	1.0×	—	—
OpenMP	2T	0.0679	1.61×	—	—
OpenMP	4T	0.0600	1.82×	—	—
OpenMP	8T	0.0489	2.24×	—	—
OpenMP	16T	0.0283	3.87×	8.74	121.5
MPI	8P	0.131	0.83×	798.6	240.0

MPI energy measured over the full 3.33 s wall-clock window (job setup + sort). OpenMP measured over 0.072 s window. MPI's energy cost is dominated by OS/framework overhead at this small problem size.

Key Insights

OpenMP is well-suited for sorting Task parallelism maps naturally onto merge sort's divide-and-conquer tree. Each subtask can be spawned with #pragma omp task. Threshold prevents over-spawning for small subproblems.

MPI overhead dominates at N=1M Scatter/gather communication costs O(N) data movement. At N=1M, MPI is actually slower than sequential (0.83× speedup). MPI shines at much larger N or when data is already distributed.

Kernel 4

Earth Mover's Distance (EMD / Wasserstein-1)

1D EMD between two distributions of N=100,000,000 samples. Consists of a sort + prefix-sum + linear scan. The compute phase is highly parallelisable; the setup (sort) dominates at large N.

CUDA (A100) OpenMP MPI MPI+CUDA

Compute Speedup vs OMP-1T (N=100M)

Speedup of the compute phase only (excludes setup/sort). CUDA is 73× faster than single-threaded OMP on compute.

MPI Strong Scaling (compute phase)

MPI scales near-linearly up to 128 ranks (32.5×), then plateaus as communication overhead grows relative to the shrinking per-rank workload.

Results Table — EMD N=100,000,000 (SciCORE)

Method	Workers	Setup (s)	Compute (s)	End-to-End (s)	Compute Speedup
Sequential	1	0.473	0.086	0.559	—
OpenMP	1T	0.492	0.172	0.665	1.0×
OpenMP	16T	0.105	0.036	0.141	4.8×
OpenMP	64T	0.144	0.026	0.173	6.6×
MPI	1R	0.483	0.178	0.661	1.0×
MPI	128R	0.012	0.0053	0.016	33.6×
MPI	256R	0.005	0.0032	0.009	54×
CUDA (A100)	1 GPU	1.662	0.00235	1.664	73×
MPI+CUDA	2R×1GPU	—	—	~1.3	—
MPI+CUDA	4R×1GPU	—	—	~1.2	—

Analysis: When CUDA Loses End-to-End

Setup dominates CUDA end-to-end CUDA compute is 73× faster, but GPU setup (data transfer + sort on GPU) takes 1.66 s vs OMP setup of 0.49 s. End-to-end CUDA (1.66 s) is actually slower than OMP 16T (0.14 s). GPU is only worthwhile when the same data is processed many times.

MPI wins end-to-end at 128+ ranks MPI at 256 ranks completes end-to-end in 0.009 s — the fastest wall-clock time overall. MPI parallelises the setup phase too (each rank sorts its own partition), whereas GPU setup is serial on the host side.

Infrastructure

SciCORE — University of Basel HPC Cluster

SciCORE is the scientific computing centre of the University of Basel. All benchmarks in this project were run as Slurm batch jobs on SciCORE's compute nodes.

🖥️

CPU Nodes

Partition: scicore
AMD EPYC / Intel Xeon
Up to 256 cores per node
Used for OpenMP + MPI jobs

⚡

GPU Nodes — L40S

Partition: l40s, QoS: l40s-30min
NVIDIA L40S (Ada Lovelace, SM 8.9)
142 SMs, 44.4 GB VRAM
Used for CUDA + OpenACC jobs

🚀

GPU Nodes — A100

Partition: a100, QoS: a100-30min
NVIDIA A100 (Ampere, SM 8.0)
80 GB HBM2e, 2 TB/s bandwidth
Used for EMD CUDA jobs

Software Environment

Modules loaded for GPU jobs:

module --force purge
module load GCC/13.3.0
module load OpenMPI/5.0.7-GCC-13.3.0
module load CUDA/12.6.0   # L40S jobs
# CUDA/13.1.0             # matmul jobs
# arch=sm_89 (L40S) / sm_80 (A100)

Job submission workflow:

sbatch jobs/job_cuda.sh     # GPU benchmark
sbatch jobs/job_omp.sh      # OpenMP scaling
sbatch jobs/job_mpi.sh      # MPI scaling
sbatch jobs/job_hybrid.sh   # MPI+OpenMP
squeue -u $USER             # monitor jobs

Slurm Job Scripts

N-Body CUDA job (nbody/jobs/job_cuda.sh)

#!/bin/bash
#SBATCH --job-name=nbody_cuda
#SBATCH --output=../results/cuda_%j.out
#SBATCH --error=../results/cuda_%j.err
#SBATCH --time=00:30:00
#SBATCH --mem=8G
#SBATCH --ntasks=1
#SBATCH --cpus-per-task=2
#SBATCH --partition=l40s
#SBATCH --qos=l40s-30min
#SBATCH --gres=gpu:1

module --force purge
module load CUDA/12.6.0

nvidia-smi --query-gpu=name,memory.total,driver_version \
  --format=csv,noheader

for N in 1000 2000 5000 10000 20000 50000; do
  ./bin/nbody_cuda -n $N -s 100 -dt 0.01
done

MatMul MPI+CUDA job (hpc_matmul/scripts/run_hybrid.sh)

#!/bin/bash
#SBATCH --job-name=matmul_hybrid
#SBATCH --output=../results/hybrid_output_%j.txt
#SBATCH --time=01:00:00
#SBATCH --nodes=1
#SBATCH --ntasks=8
#SBATCH --cpus-per-task=4
#SBATCH --mem=64G
#SBATCH --partition=l40s
#SBATCH --gres=gpu:8

module load GCC/13.3.0 OpenMPI/5.0.7-GCC-13.3.0
module load CUDA/13.1.0

SIZES=(2048 4096 8192)
for size in "${SIZES[@]}"; do
  mpirun -np 8 ./bin/hybrid_cuda_matmul $size
done

EMD CUDA job (kernel4_emd_final/jobs/cuda.job)

#!/bin/bash
#SBATCH --job-name=emd-cuda
#SBATCH --partition=a100
#SBATCH --qos=a100-30min
#SBATCH --time=00:20:00
#SBATCH --nodes=1
#SBATCH --ntasks-per-node=1
#SBATCH --cpus-per-task=8
#SBATCH --gres=gpu:a100:1
#SBATCH --output=logs/emd_cuda_%j.out

ml intel/2024a
ml CUDA/12.6.0

# sm_80 = A100; sm_89 = L40S; sm_90 = H100
nvcc -O3 -std=c++17 -arch=sm_80 -o emd_cuda emd_cuda.cu

srun ./emd_cuda ${N} ${REPS}

N-Body Hybrid MPI+OpenMP (nbody/jobs/job_hybrid.sh)

#!/bin/bash
#SBATCH --job-name=nbody_hybrid
#SBATCH --time=02:00:00
#SBATCH --ntasks=16
#SBATCH --cpus-per-task=4
#SBATCH --nodes=2-4
#SBATCH --partition=scicore
#SBATCH --exclusive

module load GCC/13.3.0
module load OpenMPI/5.0.7-GCC-13.3.0

N=5000; STEPS=50

# Sweep MPI × OMP configurations
for NP in 1 2 4 8; do
  for T in 2 4; do
    export OMP_NUM_THREADS=$T
    mpirun --oversubscribe -np $NP \
      --bind-to none \
      ./bin/nbody_hybrid -n $N -s $STEPS -dt 0.01
  done
done

Reproducibility

Run Locally — CPU Fallback + Docker

No SciCORE account required. The Docker container runs the N-Body and matrix multiplication benchmarks using OpenMP on your CPU. Results will differ from SciCORE numbers (different hardware) but the code is identical.

Quick Start with Docker

# Clone the repo
git clone https://github.com/Denxhinjo/hpc-parallel-computing-unibasel
cd hpc-parallel-computing-unibasel

# Build and run the demo container
docker compose up --build

# Or manually:
docker build -t hpc-demo ./docker
docker run --rm -e OMP_NUM_THREADS=4 hpc-demo

The container runs matrix multiplication (512², 1024², 2048²) in sequential and OpenMP modes and prints a speedup table.

Build Natively (Linux / WSL2)

# Requirements: GCC ≥ 11, OpenMPI ≥ 4, (optionally CUDA)
sudo apt install -y build-essential libopenmpi-dev

# Matrix Multiplication
cd src/matmul
make all   # builds seq, omp, mpi targets
./run_local.sh

# Merge Sort
cd src/merge_sort
make all
./merge_sort_omp 1000000 16   # N=1M, 16 threads

# N-Body
cd src/nbody
make seq omp
./nbody_omp -n 5000 -s 100 -dt 0.01

Dockerfile

FROM ubuntu:22.04
ENV DEBIAN_FRONTEND=noninteractive

RUN apt-get update && apt-get install -y \
    build-essential g++ libgomp1 \
    libopenmpi-dev openmpi-bin \
    python3 python3-pip && \
    pip3 install numpy matplotlib && \
    rm -rf /var/lib/apt/lists/*

WORKDIR /app
COPY docker/cpu_demo.cpp .
RUN g++ -O3 -fopenmp -o cpu_demo cpu_demo.cpp

ENV OMP_NUM_THREADS=4
CMD ["./cpu_demo"]

Expected Output (4 CPU threads, laptop)

=== HPC Matrix Multiplication Demo ===
Platform: CPU (OpenMP, 4 threads)
Note: SciCORE used NVIDIA L40S GPU — CPU results will be slower

Matrix 512×512
  Sequential:  0.047 s
  OpenMP 4T:   0.014 s   speedup: 3.36×

Matrix 1024×1024
  Sequential:  0.389 s
  OpenMP 4T:   0.108 s   speedup: 3.60×

Matrix 2048×2048
  Sequential:  6.82 s
  OpenMP 4T:   1.93 s    speedup: 3.54×

On SciCORE (CUDA L40S, 4096²): 0.099 s  →  543× vs sequential
======================================

Parallel Computing Results Dashboard