Distributed Queues in Shared Memory - Multicore Performance and Scalability through Quantitative Relaxation

Andreas Haas
Thomas A. Henzinger
Ana Sokolova
Christoph M. Kirsch
Ali Sezgin
Proceedings of the ACM International Conference on Computing Frontiers, ACM, New York, NY, USA(2013), 17:1-17:9


A prominent remedy to multicore scalability issues in concurrent data structure implementations is to relax the sequential specification of the data structure. We present distributed queues (DQ), a new family of relaxed concurrent queue implementations. DQs implement relaxed queues with linearizable emptiness check and either configurable or bounded out-of-order behavior or pool behavior. Our experiments show that DQs outperform and outscale in micro- and macrobenchmarks all strict and relaxed queue as well as pool implementations that we considered.

Research Areas