A cache-friendly concurrent lock-free queue for efficient inter-core communication
A cache-friendly concurrent lock-free queue for efficient inter-core communication
复制标题
缓存友好的并发无锁队列，可实现高效的核心间通信
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Xiaozhou Ye
中科院分区：
文献类型：
--
作者：
Xianghui Meng;Xuewen Zeng;Xiao Chen;Xiaozhou Ye
基于流水线并行的缓冲区共享对核间通信开销非常敏感。现有的并发无锁队列算法没有充分利用CPU的缓存特性来提高性能。为了实现一种快速的单生产者单消费者（SPSC）缓冲区调度队列，提出了一种缓存友好的CLF队列调度算法（CFCLF）. CFCLF创新性地采用矩阵（2D数组）代替一维数组来设计共享队列结构，使得CFCLF具有良好的缓存行为，从而避免了缓存错误共享，以及缓存一致性问题。此外，该算法有效地实现了批处理，以提高吞吐量。提出了一种死锁预防方法。实验结果表明，在Intel Xeon和Cavium OCTEON上，CFCLF算法的性能优于当前最先进的并发无锁队列B-Queue算法，最高可达25.5%，且CFCLF算法的稳定性优于其他算法。
Buffer sharing based on pipeline parallelism is quite susceptible to inter-core communication overhead. Existing work on concurrent lock-free (CLF) queue algorithm did not take full advantage of CPU cache features to improve performance. In order to implement a fast single-producer-single-consumer (SPSC) buffer scheduling queue, this paper proposes a cache-friendly CLF queue scheduling algorithm (CFCLF), which concentrates on cache-level optimization and minimizing inter-core communication overheads in pipeline parallelism. CFCLF innovatively employs a matrix (2D array), instead of one-dimensional array to design the shared queue structure, making CFCLF has a good cache behavior so as to avoid cache false sharing, and cache consistency problem. Besides, the algorithm implements batch processing efficiently to improve throughput. A deadlock prevention method is also proposed. Experimental results show that on Intel Xeon and Cavium OCTEON, CFCLF outperforms B-Queue which is the state-of-the-art concurrent lock-free queue, by up to 25.5%, and CFCLF is more stable than other algorithms.