Efficient Synchronization: Let Them Eat QOLB’

EjFcient synchronization primitives are essential for achieving high performance in he-grain, shared-memory parallel pro-grams. One function of synchronization primitives is to enable exclusive access to shared data and cn’tical sections of code. This paper makes three contributions. (1) We enumerate thej?ve sources of overhead that locking synchronization primitives can incul: (2) We describe four mechanisms (local spinning, queue-based lock-ing, collocation, and synchronizedprefetch) that reduce these syn-chronization overheads. (3) u”ith detailed simulations, we show the extent to which these four mechanisms can improve the perfor-mance of shared-memory programs. We evaluate the space of these mechanisms using seventeen synchronization constructs, which are formed from six base types of locks (T.!?.YT&Sn, Ti?iT&TEsrdiSR; MCS, LH, M, and QoD). We show that large performance gains (speedups of more than 1.5 for three ofjive benchmarks) can be achieved ifat least three optimizing mechanisms are used simulta-neously. We jnd that QOL & which incorporates all four mecha-nisms, outperforms all other primitives (including reactive synchronization) in all cases. Finally, we demonstrate the superior performance of a low-cost implementation of Qom, which runs on an unmodified cluster of commodiry workstations.