Multithreaded Fine-Grained Asynchronous BSP for Integer Sorting with LCI and OpenMP
2026-05-25 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors show that a common way to run big programs at the same time on many processors (called BSP) doesn't work well when tasks are uneven or irregular. They suggest a new method that uses threads and special communication tools (LCI and OpenMP) to better use many cores in a processor. By testing this on a sorting benchmark with uneven tasks, they find their method runs faster and scales better than the old way that uses strict synchronized communication. This means their approach can handle irregular programs more efficiently.
Bulk Synchronous Parallel (BSP)Fine-grained Asynchronous BSP (FA-BSP)Lightweight Communication Interface (LCI)OpenMPMPI collectivesmultithreadingload balancingirregular workloadsNAS Parallel BenchmarkInteger Sort (IS)
Authors
Minyu Cheng, Jiakun Yan, Marc Snir
Abstract
The bulk synchronous parallel (BSP) model struggles with irregular workloads due to rigid global communication. While fine-grained asynchronous BSP (FA-BSP) improves overlap, existing implementations typically rely on a limiting one-process-per-core model. This paper proposes a multithreaded FA-BSP approach combining Lightweight Communication Interface (LCI) and OpenMP to fully exploit multicore architectures. We evaluate this design using the NAS Parallel Benchmark Integer Sort (IS), retaining the original irregular Gaussian distribution to rigorously test load balancing. By replacing synchronous MPI collectives with OpenMP multithreading and LCI's fine-grained, zero-copy active messages, we enable efficient computation-communication overlap. Our evaluation demonstrates that multithreaded FA-BSP significantly outperforms traditional bulk-synchronous MPI implementations, offering a scalable solution for irregular scientific applications.