# Boundary-Aware Concurrent Queue: A Fast and Scalable Concurrent FIFO Queue on GPU Environments
## 1 Introduction  
Designing efficient shared data structures, such as concurrent queues, has gained prominence with the proliferation of many-core architectures like GPUs. Leveraging the massive computational power of modern GPUs as co-processors for computationally intensive tasks introduces significant challenges. Each new generation of GPUs brings more cores and increased threads, demanding greater scalability and more sophisticated control over thread execution order. An example use case where execution order is critical is topological sorting, which orders the vertices of a Directed Acyclic Graph (DAG) such that for every directed edge u\(\rightarrow\)v, vertex u appears before v. Similarly, in graph traversal algorithms, multiple threads may need to traverse different parts of the graph while maintaining a specific order. One of the most prevalent solutions for workloads requiring such order is the specially optimized concurrent first-in first-out (FIFO) queue tailored for massively parallel environments like GPUs. While concurrent queue design has been extensively studied in the context of multi-core architectures [1, 2, 3, 4, 5] for the past few decades, adapting these designs to the single-instruction multiple-threads model (SIMT) of GPUs presents new challenges. On CPUs, lock-free approaches [6, 7] have been favored due to their strong progress guarantees [8] and we hypothesize that the frequent failure of Compare and Swap (CAS) operations couldoutweigh the benefits of lock-free designs. However, on GPUs, the frequent failures of CAS operations can lead to significant performance penalties. When a CAS fails on a GPU, it requires a full round-trip to the CUDA cores, which can interrupt the execution flow and degrade performance. As a result, lock-free designs may not always be ideal for GPUs. Later on, researchers proposed alternative solutions such as blocking queues tailored for GPU environments [9]. While blocking queues mitigate the bottleneck caused by failed CAS operations and preserve linearizability, they introduce scalability limitations. For example, some blocking queues [10] restrict flexibility in handling overflow or underflow scenarios, which are known as boundary conditions. In such cases, the queues may not return control to the calling threads, resulting in stalled execution. Avoiding contention at hot spots or boundary conditions is a fundamental challenge in concurrent algorithms [11]. Although it may be unrealistic to eliminate boundary conditions entirely, minimizing their occurrence is crucial to improving performance in concurrent queue designs. Innovative approaches that limit the frequency of these conditions or reduce the management overhead effectively improve the efficiency of concurrent queues on GPUs. We developed a novel, scalable, and linearizable concurrent queue called BACQ (Boundary-Aware Concurrent Queue) to address these challenges on GPUs. The primary motivation behind BACQ is to make the queue aware of boundary conditions--such as overflow and underflow--before they occur, reducing the impact of these conditions on performance. Importantly, if the queue reaches a boundary, it can return an empty state to the controller, allowing for efficient handling of such scenarios. Our queue makes the following key contributions:  
* BACQ monitors concurrent enqueue and dequeue operations, raising awareness of the queue's proximity to boundary conditions (such as full or empty states). This awareness allows BACQ to adjust its operation priorities dynamically based on the queue's state. Specifically, when the queue is nearing its capacity, BACQ prioritizes dequeue over enqueue operations. * BACQ maintains and preserves the order of incoming requests, maintaining their temporal sequence with minimal access overhead. We achieved this by utilizing a leader thread from each warp, which coordinates operations across threads. * BACQ avoids the overhead of traditional \"inquire-then-update\" operations by incorporating a ticketing system.