Design and Evaluation of Scalable Concurrent Queues for Many-Core Architectures ∗

As core counts increase and as heterogeneity becomes more common in parallel computing, we face the prospect of pro-gramming hundreds or even thousands of concurrent threads in a single shared-memory system. At these scales, even highly-efficient concurrent algorithms and data structures can become bottlenecks, unless they are designed from the ground up with throughput as their primary goal. In this paper, we present three contributions: (1) a char-acterization of queue designs in terms of modern multi- and many-core architectures, (2) the design of a high-throughput, linearizable, blocking, concurrent FIFO queue for many-core architectures that avoids the bottlenecks and pitfalls com-mon in modern queue designs, and (3) a thorough evalu-ation of concurrent queue throughput across CPU, GPU, and co-processor devices. Our evaluation shows that focus-ing on throughput, rather than progress guarantees, allows our queue to scale to as much as three orders of magni-tude (1000×) faster than lock-free and combining queues on GPU platforms and two times (2×) faster on CPU de-vices. These results deliver critical insights into the design of data structures for highly concurrent systems: (1) progress guarantees do not guarantee scalability, and (2) allowing an algorithm to block can increase throughput. 1