TY - GEN
T1 - wCQ
T2 - 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022
AU - Nikolaev, Ruslan
AU - Ravindran, Binoy
N1 - Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/7/11
Y1 - 2022/7/11
N2 - The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, only a fraction of them have high performance. In addition, many queue designs, such as LCRQ, trade memory usage for better performance. The recently proposed SCQ design achieves both memory efficiency as well as excellent performance. Unfortunately, both LCRQ and SCQ are only lock-free. On the other hand, existing wait-free queues are either not very performant or suffer from potentially unbounded memory usage. Strictly described, the latter queues, such as Yang & Mellor-Crummey's (YMC) queue, forfeit wait-freedom as they are blocking when memory is exhausted. We present a wait-free queue, called wCQ. wCQ is based on SCQ and uses its own variation of fast-path-slow-path methodology to attain wait-freedom and bound memory usage. Our experimental studies on x86 and PowerPC architectures validate wCQ's great performance and memory efficiency. They also show that wCQ's performance is often on par with the best known concurrent queue designs.
AB - The concurrency literature presents a number of approaches for building non-blocking, FIFO, multiple-producer and multiple-consumer (MPMC) queues. However, only a fraction of them have high performance. In addition, many queue designs, such as LCRQ, trade memory usage for better performance. The recently proposed SCQ design achieves both memory efficiency as well as excellent performance. Unfortunately, both LCRQ and SCQ are only lock-free. On the other hand, existing wait-free queues are either not very performant or suffer from potentially unbounded memory usage. Strictly described, the latter queues, such as Yang & Mellor-Crummey's (YMC) queue, forfeit wait-freedom as they are blocking when memory is exhausted. We present a wait-free queue, called wCQ. wCQ is based on SCQ and uses its own variation of fast-path-slow-path methodology to attain wait-freedom and bound memory usage. Our experimental studies on x86 and PowerPC architectures validate wCQ's great performance and memory efficiency. They also show that wCQ's performance is often on par with the best known concurrent queue designs.
UR - http://www.scopus.com/inward/record.url?scp=85134405479&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134405479&partnerID=8YFLogxK
U2 - 10.1145/3490148.3538572
DO - 10.1145/3490148.3538572
M3 - Conference contribution
AN - SCOPUS:85134405479
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 307
EP - 319
BT - SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
Y2 - 11 July 2022 through 14 July 2022
ER -