Flat Combining

Flat Combining and the Synchronization-Parallelism Tradeoff

Ben-Gurion University
 Itai Incze 
Tel-Aviv University
Tel-Aviv University
Tel-Aviv Universiy

Traditional data-structure designs, whether lock-based or lock-free, provide parallelism via fine grained synchronization among threads. We introduce a new synchronization paradigm based on coarse locking, which we call flat-combining. The cost of synchronization in flat-combining is so low, that having a single thread holding a lock perform the combined access requests of all others, delivers, up to a certain non-negligible concurrency level, better performance than the most effec
tive parallel finely synchronized implementations. We use flat-combining to devise, among other structures, new linearizable stack, queue, and priority queue algorithms that greatly out perform all prior algorithms.
Subpages (1): Download