Toward Concurrent Lock-Free Queues on GPUs

Xiangyu ZHANG  Yangdong DENG  Shuai MU  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.7   pp.1901-1904
Publication Date: 2014/07/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E97.D.1901
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
FIFO queue,  concurrent,  lock-free,  GPU,  

Full Text: PDF>>
Buy this Article

General purpose computing on GPU (GPGPU) has become a popular computing model for high-performance, data-intensive applications. Accordingly, there is a strong need to develop highly efficient data structures to ease the development of GPGPU applications. In this work, we proposed an efficient concurrent queue data structure for GPU computing. The GPU based provably correct, lock-free FIFO queue allows a massive number of concurrent producers and consumers. Warp-centric en-queue and de-queue procedures are introduced to better match the underlying Single-Instruction, Multiple-Thread execution model of modern GPUs. It outperforms the best previous GPU queues by up to 40 fold. The correctness of the proposed queue operations is formally validated by linearizability criteria.