You are here: Home › projects › flat-combining

Flat Combining and the Synchronization-Parallelism Tradeoff

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 out perform all prior algorithms.

Publications

Scalable Flat-Combining Based Synchronous Queues.  Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir.  DISC 2010.

Flat Combining and the Synchronization-Parallelism Tradeoff.  Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir.  SPAA 2010.

Source Code

  • FC C++ code is available here.
  • FC Java queue is available here.
  • FC synchronous queue benchmark package is here.  See README.txt for more details and instructions.  A standalone implementation of the unfair synchronous queues, using a single combiner and parallel combiners, can be downloaded from here.