BQ: A Lock-Free Queue with Batching.
SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures Vienna Austria July, 2018(2018)
摘要
Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this paper we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates a significant performance improvement of up to 16x (depending on batch lengths), compared to previous queue implementations.
更多查看译文
关键词
Concurrent Algorithms,Concurrent Data Structures,Lock-Freedom,Linearizability,FIFO Queue
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要