A cache-friendly concurrent lock-free queue for efficient inter-core communication
Xianghui Meng, Xuewen Zeng, Xiao Chen, Xiaozhou Ye · 2017
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.