2025 · HPC / Parallel Software Engineer

MPI Allgather+Merge on a Cluster (Bruck vs Circulant)

Implemented and benchmarked 3 Allgather+merge variants up to 640 ranks; parallel variants delivered $\approx 1.5\times\text{–}2\times$ average speedup, with Circulant typically $10\text{–}30\%$ faster than Bruck.

Results

Replaced a $k\text{-way}$ merge using a heap with a tournament loser-tree ( $\approx 3.52\times$ faster merge).
Generalized Bruck for non-power-of-two process counts via source-rank tagging + last-round filtering.
Circulant implementation with non-blocking comms + chunked pipelining; typically $10\text{–}30\%$ faster than Bruck in results.
Ran Hydra benchmarks up to 640 ranks with 30-run averages across multiple message sizes and input distributions.

Overview

Built a sequential baseline (MPI_Allgather + $p\text{-way}$ merge) and two allgather-merge algorithms (generalized Bruck and Circulant).

Optimized merge and memory traffic (loser-tree merge, SoA layout, ping-pong buffers), implemented non-blocking and pipelined communication, and analyzed scaling limits (eager threshold/rendezvous handshakes, synchronization walls) on the Hydra cluster at TUW over multiple node/process configurations and message sizes.

My work

Implemented baseline Allgather+merge and optimized the local merge using a loser-tree and SoA memory layout.
Implemented Bruck and Circulant allgather-merge variants, including non-blocking Isend/Irecv and pipelined chunking.
Built a benchmark runner (multiple configs/message sizes/input types) and produced comparative performance analysis.
Diagnosed performance walls (communication handshakes, synchronization effects) and documented trade-offs vs baseline.

Technologies

C/C++
MPI (OpenMPI)
Linux
Cluster Benchmarking

Source material

HPC Project Report (PDF) ↗