# Boundary-Aware Concurrent Queue: A Fast and Scalable Concurrent FIFO Queue on GPU Environments
## 3 BACQ Proposal
### Establishing Priority with Low Access Overhead  
Enqueue and dequeue must insert and remove items from the supporting data structure in a strict FIFO order to ensure correctness. We refer to this as establishing priority. They must publish (i.e., synchronize) their changes to all threads with minimal overhead. In an enqueue operation, threads must determine the correct priority order and efficiently publish that information to all threads. Ideally, from the client's perspective, priority should be assigned immediately upon entering the enqueue. Delays risk lower priority enqueues cutting in front of a higher priority enqueue. Thus, an enqueue operation should increment the global tail pointer immediately upon starting the transaction (Listing 2 Line 14). Dequeues have a slightly different perspective. Threads complete for access to the head of the queue, which points to the oldest and, thus, the next dequeued item. So, dequeue operations should increment the global head pointer immediately upon starting, thus ensuring the thread accesses the oldest item in the queue (Listing 3 Line 14). The latest Ada Lovelace GPU architecture divides each streaming multiprocessor (SM) into four processing blocks called partitions. Each partition contains a dedicated warp scheduler and a dispatch unit capable of dispatching one 32-thread warp per clock cycle. As a result, four warps can run independently from each SM in parallel at any given moment (see Figure 2) [18]. This characteristic of SIMT execution presents an opportunity to reduce the contention on global atomic counters. Notably, the parallelism within warps can be leveraged to reduce pressure on shared counters by coagulating these requests, ultimately improving performance. The BACQ algorithm introduces a _leader thread_ for each warp to handle the atomic increments of the global head and tail counters, as shown in Figure 3. Instead of having every thread participate in incrementing these counters, only the designated leader thread performs the atomic increment for all threads within its warp. Since all threads in a warp start from the same program address and execute concurrently in lock-step, this aggregation ensures that the correct temporal order is established for each warp thread immediately upon making their request. This method significantly reduces atomic overhead because it avoids having each thread individually interact with the global counters. Once the leader thread increments the counters, it then broadcasts the old head and tail addresses to the rest of the warp. However, warps can branch and execute independently in practice, leading to warp divergence. Warp divergence occurs when threads within the same warp take different execution paths due to conditional statement statements. At each instruction issue time, the instruction unit selects a ready warp to execute and dispatches the next instruction to its active threads [19]. On concurrent queues, a warp with a mix of enqueue and dequeue requests may encounter warp divergence, as shown in the code snippet in Listing 4. As a result of independent branching, any given warp may have active and inactive threads. To address the challenge of warp divergence, we propose electing a leader thread only from the set of active threads in the warp (Listing 2 Line 8 and Listing 3 Line 8) as visualized in Figure 4. This ensures that even in the presence of divergence, the leader thread--chosen from the currently active threads in the warp--can still manage the atomic increments for the global head and tail counters. The leader thread's primary responsibility is incrementing the two highly contended hotspots of the queue atomically. They are the global head and tail pointers. In concurrent queues, atomic operations typically rely on primitives like compare-and-swap (CAS) and fetch-and-add (FAA) [9]. CAS provides a strong progress guarantee, ensuring that at least one transaction makes progress.