High-Performance 1D Earth Mover's Distance

A performance engineering project implementing four algorithms — matrix multiplication, N-body simulation, merge sort and 1D Earth Mover's Distance — across up to six parallelization paradigms (sequential, OpenMP, MPI, CUDA, OpenACC, hybrid), benchmarked with real measurements on the University of Basel's SciCORE HPC cluster (NVIDIA L40S / A100 GPUs).

Computing Earth Mover's Distance and similar primitives is common in distribution comparison, but naive sequential implementations do not scale to large inputs. The project set out to characterize how different parallelization strategies affect runtime and energy efficiency in practice, not just in theory.

Completed as the High Performance Computing course project (Spring 2026) at the University of Basel, run on the SciCORE production research cluster via Slurm. Originally a team project; the public repository has been cleaned to present my individual contribution as a solo showcase.

I implemented every version of the EMD algorithm — sequential, OpenMP, MPI, CUDA and hybrid — designed the prefix-scan optimization, and ran the profiling and runtime/energy analysis on the cluster via Slurm.

• Correct sequential baseline implementation of 1D EMD
• Shared-memory parallelization using OpenMP
• Distributed-memory parallelization using MPI
• GPU acceleration using CUDA
• A hybrid parallelization strategy combining multiple models
• Prefix-scan optimization to reduce redundant computation
• Job scheduling and execution on an HPC cluster via Slurm
• Runtime and energy-to-solution profiling across configurations

A shared computational core for 1D EMD accelerated through independent parallel backends (OpenMP for shared memory, MPI for distributed memory, CUDA for GPU execution, and a hybrid MPI+CUDA configuration), orchestrated as Slurm batch jobs on SciCORE with PMT-based energy profiling (RAPL for CPU, NVML for GPU) around each run.

Started from a sequential prefix-scan-optimized implementation of 1D EMD, then built parallel variants: an OpenMP version parallelizing across shared-memory threads, an MPI version distributing work across nodes/ranks, a CUDA version offloading computation to GPU, and a hybrid MPI+CUDA version combining both. All versions were benchmarked on SciCORE using Slurm job scripts, with runtime and energy-to-solution measured across problem sizes and worker counts, and the results published as a live interactive dashboard.

Achieving correct, efficient parallelization of the prefix-scan step — which is inherently sequential in its naive form — across shared-memory, distributed-memory and GPU models was the main technical difficulty, along with fairly comparing runtime and energy efficiency across fundamentally different hardware execution models.

Applied parallel prefix-scan algorithms adapted to each backend's memory model, and standardized the benchmarking methodology (problem sizes, worker counts, Slurm job configuration, PMT energy sampling window) so runtime and energy-to-solution results were directly comparable across implementations.

Matrix multiplication reached a 4,245× speedup over the sequential baseline using MPI+CUDA across 8 GPUs (vs. 9.8× for MPI alone and 545× for CUDA alone at 4096²). 1D EMD hit 73× on a single A100 for the compute phase (100M samples), and N-body simulation reached 35× on GPU. Energy profiling showed OpenMP using roughly 91× less energy than MPI for merge sort at N=1M, since MPI's scatter/gather overhead dominates at that problem size — a case where the fastest wall-clock method was not the most energy-efficient one. Full results, methodology and interactive charts for all four algorithms are on the live dashboard linked above.

Implementing the same class of algorithm across four distinct parallel programming models made the practical trade-offs between shared-memory, distributed-memory and GPU execution concrete — including that GPU setup/transfer overhead can make an objectively faster compute kernel slower end-to-end for one-shot workloads.

• Extend the approach to higher-dimensional Earth Mover's Distance
• Explore multi-GPU and multi-node CUDA-aware MPI configurations
• Auto-tune parallelization strategy selection based on input size