Design and Evaluation of Scalable Concurrent Queues for Many-Core Architectures
| dc.contributor.author | Scogland, Thomas R. W. | en |
| dc.contributor.author | Feng, Wu-chun | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2014-08-06T16:28:47Z | en |
| dc.date.available | 2014-08-06T16:28:47Z | en |
| dc.date.issued | 2014-08-06 | en |
| dc.description.abstract | 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 characterization of queue designs in terms of modern multi- and many-core architectures, (2) the design of a high-throughput concurrent FIFO queue for many-core architectures that avoids the bottlenecks 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 insight 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 actually increase throughput. | en |
| dc.identifier.trnumber | TR-14-03 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/49700 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Computer Science Technical Reports | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | Algorithms | en |
| dc.subject | Computer systems | en |
| dc.subject | High performance computing | en |
| dc.subject | Parallel and distributed computing | en |
| dc.title | Design and Evaluation of Scalable Concurrent Queues for Many-Core Architectures | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |