MPI Allgather+Merge on a Cluster
Bruck vs Circulant
Implemented and benchmarked 3 Allgather+merge variants up to 640 ranks; parallel variants delivered ~1.5×–2× average speedup, with Circulant typically 10–30% faster than Bruck.
Built a sequential baseline (MPI_Allgather + p-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.
Highlights
- Replaced a k-way merge using a heap with a tournament loser-tree (~3.52× 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–30% faster than Bruck in results.
- Ran Hydra benchmarks up to 640 ranks with 30-run averages across multiple message sizes and input distributions.
What I did
- 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.
Stack
- C/C++
- MPI (OpenMPI)
- Linux
- Cluster Benchmarking