SOFTQOLB: An Ultra-Efficient Synchronization Primitive for Clusters of Commodity Workstations

Efficient synchronization can dramatically improve the performance of shared-memory parallel programs. Past work has proposed pairwise synchronization primitives---such as Queue-on-Lock-Bit (QOLB) [6, 5] and the transactional memory model [7, 26]---that offer higher performance than currently widely used primitives--- such as MCS locks [16]. QOLB and the transactional memory model, as originally conceived, require modifications to commodity processors, and thus have not yet been implemented. In this report, we present an implementation of QOLB, called SOFTQOLB, that runs entirely in software, and can thus run on unmodified commodity workstation clusters. We describe our implementation in detail and present an evaluation of its performance using a microbenchmark. We show that the SOFTQOLB primitive consistently outperforms MCS when there is high contention (SOFTQOLB is in these cases at least 5 times as fast as MCS) and the performance of these two primitives is comparable under low-co..