Flat combining and the synchronization-parallelism tradeoff

By Danny Hendler, Itai Incze, Nir Shavit, Moran Tzafrir. ACM Symposium on Parallelism in Algorithms and Architectures, 2010

354 citations recorded by the source corpus.

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 effective parallel finely synchronized implementations. We use flat-combining to devise, among other structures, new linearizable stack, queue, and priority queue algorithms that greatly outperform all prior algorithms.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/4a3ffcaeaadda240da787b6bd8deaa387817f336