Synchronization without contention
John Mellor‐Crummey, Michael Lee Scott · 1991
Conventional wisdom holds that contention due to busy-wait synchronization is a major obstacle to scalability and acceptable performance in large shared-memory multiprocessors. We argue the contrary, and present fast, simple algorithms for contention-free mutual exclusion, reader-writer control, and barrier synchronization. These algorithms, based on widely available fetch-and-@ instructions, exploit local access to shared memory to avoid contention. We compare our algorithms to previous approaches in both qualitative and quantitative terms, presenting their performance on the Sequent Symmetry and BBN Butterfly multiprocessors. Our results highlight the importance of local access to shared memory, provide a case against the construction of so-called dance hall machines, and suggest that special-purpose hardware support for synchronization is unlikely to be cost effective on machines with sequentially consistent memory.
Cited by 141 works. doi:10.1145/106972.106999
Authors
References
- Concurrent control with “readers” and “writers”
- The NYU Ultracomputer—Designing an MIMD Shared Memory Parallel Computer
- The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture.
- Memory consistency and event ordering in scalable shared-memory multiprocessors
- “Hot spot” contention and combining in multistage interconnection networks
- Dynamic decentralized cache schemes for mimd parallel processors
- The performance of spin lock alternatives for shared-memory multiprocessors
- Weak ordering—a new definition
- Efficient synchronization primitives for large-scale cache-coherent multiprocessors
- Synchronization with eventcounts and sequencers