Multithreaded Fine-Grained Asynchronous BSP for Integer Sorting with LCI and OpenMP

Minyu Cheng, Jiakun Yan 1, Marc Snir · 2026

Read Multithreaded Fine-Grained Asynchronous BSP for Integer Sorting with LCI and OpenMP by Minyu Cheng, Jiakun Yan 1, Marc Snir (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25340.txt.

Introduction

Minyu Cheng, Jiakun Yan, and Marc Snir speed up parallel integer sorting for uneven workloads. The classic bulk-synchronous model stalls on irregular work because it forces global communication lockstep. Fine-grained asynchronous variants overlap work better but usually tie one process to each core. The team combines a lightweight communication library with OpenMP threading to exploit every core fully. Tested on the NAS integer-sort benchmark with its original skewed distribution, the multithreaded design beats traditional bulk-synchronous MPI implementations and scales for irregular scientific work.

Catalog record

CREATORMinyu Cheng, Jiakun Yan 1, Marc Snir
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44501
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.25340

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multithreaded Fine-Grained Asynchronous BSP for Integer Sorting with LCI and OpenMP Minyu Cheng, Jiakun Yan 1, 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. I Introduction For decades, the bulk synchronous parallel (BSP) model has been the dominant paradigm in parallel computing, offering a predictable execution model based on lockstep phases of alternating computation and communication. However, as high-performance computing (HPC) applications scale and algorithms become increasingly irregular, the rigidity of BSP becomes a bottleneck. The requirement for global synchronization at barriers results in significant idle time during load imbalances, while its rigid structure prevents effective overlap between computation and communication. To mitigate these issues, models that relax global synchronization have emerged. Task-based systems [ 13 , 12 , 2 ] allow runtimes to manage asynchrony dynamically but often impose heavy runtime overheads and require extensive refactoring of legacy code. Alternatively, the fine-grained asynchronous BSP (FA-BSP) model [ 17 ] offers a middle ground. By retaining the BSP structure while enabling asynchronous communication and finer-grained actor execution, FA-BSP improves computation-communication overlap with minimal code changes. However, current FA-BSP implementations generally rely on a single-threaded, one-process-per-core model. This approach fails to exploit modern multicore architectures effectively, as the resulting proliferation of processes increases pressure on memory subsystems and network interfaces. Furthermore, single-threaded execution cannot leverage shared-memory multithreading to mitigate load imbalances in irregular applications. This reliance on one-process-per-core is largely a historical compromise due to the poor multithreaded performance of traditional communication libraries [ 16 , 23 , 21 ] such as the message passing interface (MPI) [ 15 ] and OpenSHMEM [ 5 ] . With the advent of libraries designed for efficient multithreaded communication, such as the lightweight communication interface (LCI) [ 22 ] , these limitations can now be overcome. This paper explores the potential of multithreaded FA-BSP by presenting a case study of the integer sort (IS) benchmark from the NAS parallel benchmarks (NPB) [ 3 ] . As a building block for particle simulations and graph analytics, IS is an ideal candidate for this evaluation, given its irregular communication patterns and data-dependent load imbalances arising from Gaussian key distributions. We present a multithreaded FA-BSP implementation of Integer Sort using LCI and OpenMP, and compare it with a traditional single-threaded MPI-based BSP implementation. Our evaluation shows that combining multithreading with the FA-BSP model yields significant performance gains. This paper makes the following contributions: 1. An analysis of the inefficiencies inherent in the traditional MPI-based BSP implementation of Integer Sort. 2. The design and implementation of a multithreaded FA-BSP algorithm of Integer Sort utilizing LCI and OpenMP. 3. A detailed performance evaluation on a large-scale HPC system, demonstrating the specific benefits of multithreading and FA-BSP for irregular workloads. 4. A set of controlled experiments to identify the source of performance improvement in the LCI implementation. The rest of the paper is organized as follows. Section II provides background on the HPC programming models and communication libraries relevant to this work and prior work on Integer Sort. Section III introduces LCI and describes its features relevant to this work. Section IV describes the design and implementation of our multithreaded FA-BSP Integer Sort using LCI. Section V presents our performance evaluation and analysis. Finally, Section VI concludes the paper and discusses future work. II Related Work II-A Parallel Models and Communication Runtimes While the BSP model provides structural simplicity, decades of research have focused on addressing its limitations in handling irregular workloads. The partitioned global address space (PGAS) model [ 8 , 5 , 1 ] extends BSP by introducing a global shared memory abstraction and one-sided communication primitives, yet it typically retains the bulk-synchronous execution structure with global barriers. In contrast, the bulk asynchronous parallel (BASP) model [ 6 ] explicitly relaxes these synchronization requirements, allowing processes to proceed immediately once local dependencies are met. More radical departures, such as task-based systems [ 13 , 12 , 2 ] , abandon the superstep structure entirely in favor of dynamic, graph-based execution. FA-BSP [ 17 ] occupies a middle ground by injecting fine-grained actor execution into the standard BSP superstep, aiming to preserve the model’s simplicity while enabling the overlap of communication and computation found in asynchronous models. However, the efficacy of these models is heavily constrained by the underlying communication libraries. Traditional message-passing libraries like MPI [ 15 ] and GASNet-EX [ 4 ] were primarily optimized for single-threaded, process-based parallelism. Consequently, they often incur high lock contention when accessed by multiple threads concurrently. This bottleneck has historically forced FA-BSP implementations to rely on a one-process-per-core configuration, limiting shared-memory load balancing. Our work leverages LCI [ 22 ] , which distinguishes itself from MPI and GASNet-EX by optimizing specifically for multithreaded, fine-grained messaging, thereby enabling the multithreaded FA-BSP approach proposed in this paper. LCI has been used to improve the performance of established task-based systems [ 20 , 14 ] . II-B Prior Work on Integer Sort The NPB IS benchmark [ 3 ] has been widely studied to evaluate programming models and communication substrates. The standard NPB suite provides reference implementations in MPI (distributed memory) and OpenMP (shared memory). Several studies have attempted to optimize IS using alternative models. For example, [ 18 ] evaluated an OpenSHMEM implementation of IS and found it resulting in slightly lower performance compared to the bulk-transfer MPI baseline. Other works have modified the benchmark itself to avoid the load imbalancing issue. The ISx benchmark [ 10 ] provides implementations in MPI, OpenSHMEM, and Chapel. While [ 11 ] demonstrated that OpenSHMEM could outperform MPI on ISx, the benchmark alters the key generation to a uniform distribution. This modification significantly reduces the load imbalance and communication irregularity inherent in the original Gaussian distribution of NPB IS. Similarly, [ 9 ] applied the FA-BSP model to ISx, showing gains over standard MPI and OpenSHMEM. However, because ISx effectively regularizes the workload, these results do not fully capture the challenges of highly irregular applications. In contrast, this work targets the original NPB IS benchmark with its Gaussian key distribution. We directly tackle the pathological load imbalances and irregular communication patterns that multithreaded FA-BSP is theoretically best suited to solve. III LCI Overview Many HPC algorithms are traditionally implemented on top of MPI, which was originally designed around bulk-synchronous execution and relatively coarse-grained communication. While MPI provides strong single-thread performance and portability, its communication model and implementation choices make it less well-suited for algorithms that rely on fine-grained, highly asynchronous communication invoked concurrently by many threads. In such settings, communication progress, synchronization overheads, and contention on shared communication resources

Read the complete text