# Boundary-Aware Concurrent Queue: A Fast and Scalable Concurrent FIFO Queue on GPU Environments
## 2 Related Works  
Concurrent first-in first-out (FIFO) queues have recently become a significant focus in research, particularly for optimizing performance on multi-core and many-core architectures, such as CPUs and GPUs. These queues are especially well suited for applications like real-time data processing engines, machine learning frameworks (e.g., TensorFlow and PyTorch), CUDA streams, and algorithms for shortest path finding. Despite their broad applicability, the specific implementations of concurrent queue structures used in commercial products remain proprietary and are not publicly disclosed.  
[PERSON] and [PERSON] [3] (TZQ), [PERSON] [12] (CGQ) and [PERSON] [13] (SHQ) introduced a concurrent queue design that performs enqueues and dequeues on a local shared cyclic array before committing to a global queue. While it avoids inconsistent head and tail states through compare-and-swap (CAS) operations, the reliance on retry CAS creates significant performance bottlenecks.  
In 1983, [PERSON] et al. [14] introduced an array-based queue (GQ), utilizing a ring buffer structure and fine-grained locking on each location for concurrency. However, the design faced performance challenges due to contention caused by a pair of index counters, leading to non-linearizable behavior.  
In 2013, [PERSON] et al. [15] published the Linked Concurrent Ring Queue (LCRQ), which consists of multiple linked arrays and retains lock-freedom while avoiding CAS operations by relying on Atomic Fetch Add (AFA). Despite its advantages, LCRQ relies on double-wide CAS (only available on x86) and incurred costly allocations and initializations of new CRQs after a certain number of operations or retries. In 2023, [PERSON] and [PERSON] eliminated the usage of CAS2 while maintaining the same performance. They published a new queue called LPRQ but did not handle the garbage of queues created by overlapping requests. Its heavy usage of memory allocation for new CRQs makes it unsuitable for GPU as they transfer all memory from the host side to the client on a single kernel launch [16].  
[PERSON] et al. [10] introduced the circular buffer queue (CBQ) specifically for many-core architectures, utilizing two counters for enqueue and dequeue operations. However, CBQ blocks the entire queue during these operations, impacting performance. Additionally, CBQ fails to address boundary conditions, restricting enqueue to non-full queues and dequeue to non-empty queues. [PERSON] et al. proposed a High-Throughput Queue (HTQ) as an alternative, overcoming CBQ limitations but retaining the flawed two-counter approach from the Gottlieb queue.  
In 2017, [PERSON] and [PERSON] [9] presented the Scalable Fine-grained Queue (SFQ), an extension of CBQ with a closing mechanism to mitigate blocking waits. SFQ employs a buffer queue and a ticketing system in many-core architectures, limiting communication to one thread per warp, leading to performance degradation. Later on, [PERSON] et al. [17] presented the broker queue, designed for fine-grained parallel work distribution on GPUs. The broker queue uses a ring buffer with a ticketing system but has performance issues with divergent enqueue and dequeue operations. Additionally, an explicit counter and blocking mechanism are required to prevent boundary condition issues and catch enqueue or dequeue in flight. Table 1 summarizes the properties of the queues discussed in this section.