FFQ: A Fast Single-Producer/Multiple-Consumer Concurrent FIFO Queue
| Autor: | Sergei Arnautov, Bohdan Trach, Christof Fetzer, Pascal Felber |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
010302 applied physics
Queueing theory FIFO (computing and electronics) Computer science business.industry Distributed computing 020207 software engineering 02 engineering and technology Thread (computing) 01 natural sciences Synchronization Producer–consumer problem Multithreading 0103 physical sciences Scalability 0202 electrical engineering electronic engineering information engineering Double-ended queue business Queue Throughput (business) Computer network |
| Zdroj: | IPDPS 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
| DOI: | 10.1109/ipdps.2017.41 |
| Popis: | With the spreading of multi-core architectures, operating systems and applications are becoming increasingly more concurrent and their scalability is often limited by the primitives used to synchronize the different hardware threads. In this paper, we address the problem of how to optimize the throughput of a system with multiple producer and consumer threads. Such applications typically synchronize their threads via multi-producer/multi-consumer FIFO queues, but existing solutions have poor scalability, as we could observe when designing a secure application framework that requires high-throughput communication between many concurrent threads. In our target system, however, the items enqueued by different producers do not necessarily need to be FIFO ordered. Hence, we propose a fast FIFO queue, FFQ, that aims at maximizing throughput by specializing the algorithm for single-producer/multiple-consumer settings: each producer has its own queue from which multiple consumers can concurrently dequeue. Furthermore, while we provide a wait-free interface for producers, we limit ourselves to lock-free consumers to eliminate the need for helping. We also propose a multi-producer variant to show which synchronization operations we were able to remove by focusing on a single producer variant. Our evaluation analyses the performance using micro-benchmarks and compares our results with other state-of-the-art solutions: FFQ exhibits excellent performance and scalability. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|