Design and Evaluation of Scalable Concurrent Queues for Many-Core Architectures
Authors:
Open Access
- 31 January 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 63-74
Abstract
As core counts increase and as heterogeneity becomes more common in parallel computing, we face the prospect of programming 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 characterization 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 common in modern queue designs, and (3) a thorough evaluation of concurrent queue throughput across CPU, GPU, and co-processor devices. Our evaluation shows that focusing on throughput, rather than progress guarantees, allows our queue to scale to as much as three orders of magnitude (1000x) faster than lock-free and combining queues on GPU platforms and two times (2x) faster on CPU devices. 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.Keywords
Funding Information
- National Science Foundation (CNS-0960081)
- Air Force Office of Scientific Research (FA9550-12-1-044)
This publication has 15 references indexed in Scilit:
- Fast concurrent queues for x86 processors2013
- Fast and Scalable, Lock-Free k-FIFO QueuesLecture Notes in Computer Science, 2013
- A methodology for creating fast wait-free data structures2012
- Toward high-throughput algorithms on many-core architecturesACM Transactions on Architecture and Code Optimization, 2012
- Understanding the Performance of Concurrent Data Structures on Graphics ProcessorsLecture Notes in Computer Science, 2012
- Wait-free queues with multiple enqueuers and dequeuersACM SIGPLAN Notices, 2011
- Scalable Room SynchronizationsTheory of Computing Systems, 2003
- A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems2001
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential ProcessorsACM Transactions on Programming Languages and Systems, 1983