Scalable Concurrent Queues for GPU

arXiv:2606.01693v1 [cs.DC] 1 Jun 2026

Scalable Concurrent Queues for GPU Pratheek Prakash Shetty

Thomas R. W. Scogland

Wu-chun Feng

Department of ECE Virginia Tech Blacksburg, VA, USA [email protected]

Lawrence Livermore National Laboratory Livermore, CA, USA [email protected]

Department of CS and ECE Virginia Tech Blacksburg, VA, USA [email protected]

Abstract—Concurrent queues can significantly impact supercomputing performance by being critical bottlenecks for task distribution, load balancing, or resource utilization. As HPC systems move beyond 10-million processor cores, the ability to rapidly move items between producer and consumer threads without excessive locking is essential for delivering efficient queues (i.e., preventing idle cores and maximizing utilization) and, in turn, achieving high parallel speedup. While concurrent queues are well studied on CPUs, they remain largely unexplored on modern GPUs, where SIMT execution, massive parallelism, and atomic contention reshape the design space. We present three linearizable GPU concurrent queues spanning from lock-free to wait-free guarantees: (1) GWFQ-YMC, an adaptation of Yang and Mellor-Crummey’s waitfree queue using preallocated segments; (2) G-LFQ, a bounded lock-free queue that uses wave-batched fast paths to maximize throughput, and (3) G-WFQ, a bounded wait-free queue that packs shared state into 64-bit compare-and-swap operations while preserving linearizability and bounded memory. Index Terms—concurrent queues, atomic operations, profiling

I. I NTRODUCTION Concurrent queues are a cornerstone of shared-memory processing on CPUs, with decades of research establishing both a rich design space and well-understood notions of correctness and progress guarantees [1]–[9]. This spans lock-free compareand-swap (CAS) based designs, scalable fetch-and-add (FAA) based rings, and practical wait-free constructions showing the diversity and maturity of CPU concurrent queue research. In contrast, the GPU concurrent queue space remains significantly less mature, even though modern exascale systems [10], [11] are overwhelmingly accelerator-driven. For example, the Frontier supercomputer [11] couples each CPU with four AMD MI250X GPUs, while El Capitan’s performance is dominated by the GPU portion of four MI300A APUs per node [10]. Thus, coordination mechanisms that execute on the GPU are essential primitives in today’s heterogeneous machines, yet the GPU concurrent queue space has only a handful of designs [12]–[14] with little attention to formal progress guarantees. Two requirements dominate in concurrent queues: (1) semantics, i.e., FIFO ordering and linearizability [15], so that programs can reason about the order in which work is produced and consumed and (2) progress, i.e., guarantees The work detailed herein has been supported in part by NSF I/UCRC CNS-1822080 via the NSF Center for Space, High-performance, and Resilient Computing (SHREC).

about completion and forward progress under contention. On CPUs, both lock-free and wait-free queue designs have been explored in depth with a well-developed understanding of their correctness, performance, and boundedness [1], [2], [6]– [8]. On GPUs, in contrast, prior work has focused more on practical implementations, blocking designs, linearizability, or throughput-oriented work distribution [12]–[14], with little attention to explicit non-blocking progress guarantees or waitfree semantics. As a result, the field still lacks a GPU-aware wait-free concurrent queue with explicit, theorem-grounded progress guarantees and evaluation across contention regimes and applications. To address this gap, we first adapt Yang and MellorCrummey’s CPU wait-free queue (WFQ) to GPU allocation, synchronization, and memory-ordering constraints, i.e., GWFQ-YMC. Second, we design and implement two GPUaware concurrent queues with strong progress guarantees and then study their behavior on the AMD MI210 GPU and AMD MI300A APU, namely • G-LFQ (GPU Lock-Free Queue). G-LFQ derives from the scalable circular queue (sCQ) [7] ring structure but changes the fast path so that one wavefront1 leader reserves positions for the wave with a batched fetch-andadd (FAA). This yields a lock-free GPU queue without slow-path overhead. • G-WFQ (GPU Wait-Free Queue). G-WFQ extends that structure with head and tail metadata arranged to support a bounded slow path and a wait-free proof argument. GWFQ uses single-width 64-bit compare-and-swap atomics as double-width or (CAS2) atomics are not available to most current GPUs. To understand and validate correctness (i.e., linearizability), we use device-recorded histories checked by Porcupine [16], a linearizability checker, together with targeted tests for FIFO behavior. We then state the assumptions under which our waitfreedom argument holds on GPUs. We evaluate the queues with two fixed-duration throughput micro-benchmarks and two applications. The first microbenchmark is balanced: every thread performs exactly one enqueue followed by one dequeue, so each thread does an equal amount of work. The second is a split micro-benchmark, 1 Throughout this paper we use AMD terminology (i.e., wave or wavefront); wavefront is equivalent to NVIDIA’s warp.

where all threads perform only enqueues or dequeues with varying producer fractions to create an asymmetric load. The two applications are level-synchronous breadth-first search (BFS) and a tile-based wavefront ray tracer. We then analyze micro-benchmark performance using metrics collected with rocprofv2, in particular WAIT/op, the normalized wave stall fraction per successful queue operation, and VALU/op, the number of vector ALU instructions per successful queue operation. Our contributions are as follows. • The first GPU wait-free queue. We present G-WFQ, a bounded GPU-aware wait-free queue with explicit theorem-grounded progress guarantees, and G-LFQ, a bounded GPU lock-free design. • Verifiable correctness with proofs. We prove linearizability and progress properties for G-WFQ and G-LFQ, and validate FIFO behavior using Porcupine-based linearizability checking and device-side tests. • Performance evaluation and analysis of GPU concurrent queues. We evaluate our GPU concurrent queues against the current state of the art, namely SFQ (Scogland-Feng queue for GPU) and G-WFQ-YMC (Yang & Mellor-Crummey wait-free queue for GPU) using fixed-duration micro-benchmarks, level-synchronous BFS, and wavefront ray tracing, and explain the performance trends using hardware profiling metrics. II. R ELATED W ORK A. CPU Concurrent Queues Concurrent queue design on CPUs spans classic algorithms like CAS-based linked queues [1], [2], FAA-based ring queues [6], and wait-free fast-path/slow-path constructions [5]. Michael and Scott’s queue (MSQ) is considered to be the seminal work in the field and still remains the baseline for correctness and portability [1]. The LCRQ explored a fetchand-add (FAA) based queue to reduce contention on shared head and tail updates, but it relies on linked ring segments and (CAS2) synchronization [6], later work also presented a variant that did not use the (CAS2) [17]. Nikolaev introduced a scalable circular queue (sCQ), a bounded lock-free ring design that preserves ordering semantics while avoiding some of LCRQ’s portability and memory-management limitations [7]. CPU queues that achieved wait-free guarantees followed a related but distinct line of work. The first fast-path/slow-path methodology developed to convert lock-free structures into wait-free ones through helping was introduced by Kogan and Petrank [3]. They developed a practical wait-free queue based on the Michael-Scott structure [4], while Yang and MellorCrummey (YMC) later showed that a wait-free queue can be as fast as FAA-based lock-free alternatives by combining an FAA-based fast path with helping through per-thread request records [5]. More recently, Nikolaev and Ravindran, revisited the problem from a bounded-memory perspective, arguing that practical wait-freedom should not rely on unbounded growth or deferred reclamation — a flaw they identified in

YMC’s design — and introduced wCQ, built atop the sCQ structure [8]. Recent work revisited how to make FAA-based synchronization scale better under contention. Aggregating Funnels show that software aggregation can substantially reduce FAA hot-spot pressure and improve queue performance [9]. Our G-LFQ uses this direction as inspiration in its wavefront or wave-batched fast path, but applies it in a bounded GPU ring with explicit correctness arguments. B. GPU Concurrent Queues The GPU queue literature is much sparser than the CPU queue literature. The Scogland-Feng Queue (SFQ) is one of the earliest and most widely cited GPU concurrent queues. It is a bounded, linearizable queue built around ticketing in a fixed-size ring and serves as a standard baseline for GPU queue studies [12]. Scogland and Feng emphasize throughput rather than strong progress guarantees, providing a highthroughput blocking interface together with a separate nonwaiting interface for cases where waiting is undesirable. The Broker Queue explores GPU queuing through a centralized broker that batches and redistributes operations to reduce contention [13]. For applications like work distribution and path-tracing, Kerbl et al. [13] present a faster non-linearizable variant that trades explicit ordering for higher throughput. Since our study is focused on explicit progress guarantees, this distinction is important. C. Queues, Worklists, and Application Context Queues and queue-like worklists appear naturally in irregular GPU applications. Thus, we evaluate our designs against Gunrock for BFS [18], asking whether stronger queue semantics can remain competitive in realistic frontier-management and work-distribution settings. In ray tracing and path tracing, the role of queues is more subtle. Modern GPU ray tracing relies on BVH traversal and specialized traversal engines or software traversal kernels [19]. Our queue-based raytracing benchmark is not intended to replace BVH traversal itself. Rather, the benchmark targets the work-distribution layer around ray generation, staging, and re-enqueueing. This queue-as-work-distribution layer framing is consistent with prior wavefront and compaction-based path-tracing work, where active rays are compacted or reordered between stages to improve efficiency [20]–[23]. We therefore use streamcompaction as a baseline for queue-driven work management, not as a claim that queues replace the full ray-tracing pipeline. Taken together, prior GPU queue work has emphasized practical scalability and work distribution, while explicit strong progress guarantees have remained significantly less explored than in the CPU literature. III. C ONCURRENT Q UEUE D ESIGN ON GPU We study three GPU queue designs. G-WFQ-YMC is our GPU adaptation of Yang and Mellor-Crummey’s wait-free queue [5]. G-LFQ is a bounded lock-free GPU queue derived from an sCQ-like ring structure [7]. G-WFQ extends the same

bounded ring design with a slow path inspired by wCQ [8], adapted to GPUs using native 64-bit atomics in place of 128bit compare-and-swap or (CAS2). The following subsections describe each design in detail. A. G-WFQ-YMC: GPU adaptation of Yang and MellorCrummey’s wait-free queue a) Overview: G-WFQ-YMC is our GPU adaptation of the CPU wait-free queue of Yang and Mellor-Crummey [5], used as a reference wait-free design. The queue keeps the original fast-path/slow-path organization: an operation first attempts a short FAA-based fast path, and if that does not succeed, it publishes a per-thread enqueue or dequeue request that can be completed by helpers. b) GPU adaptation: The CPU implementation grows a linked list of segments dynamically and reclaims retired segments with hazard-pointer-style cleanup. In our GPU adaptation, we instead pre-allocate a segment pool on the device and replace dynamic segment growth during execution with direct arithmetic lookup into the pre-allocated pool. This avoids device-side allocation and reclamation while preserving the logical segment structure of the original design. The queue logic, helping structure, and linearization behavior follow Yang and Mellor-Crummey’s algorithm [5]. We present G-WFQYMC as a GPU-adapted baseline rather than a new queue design. c) Progress and limitation: Under the assumptions of the original work [5], G-WFQ-YMC remains wait-free: once a slow-path request is published, helpers can complete it in bounded algorithmic work. However, as discussed in the bounded-memory critique motivating wCQ [8], the YMC-style queue is not bounded-memory in the strict sense, since the logical structure grows by linked segments [5] rather than operating within a fixed ring. In our GPU experiments, we pre-allocate enough segments ahead of time, but this does not change that underlying distinction. B. G-LFQ: GPU Lock-Free Queue a) Design goal: G-LFQ is the lock-free version of our GPU queue family. It uses the same bounded-ring setting as the sCQ [7] with a ring of size 2n, a threshold check for empty, and an outer indirection layer that moves indices rather than payloads directly. We change how tickets are reserved and how the slot state is packed for GPU execution. G-LFQ replaces the per-thread fetch-and-add on the hot counters with wavebatched reservation and stores each live slot in a single 64bit word. The proof below therefore focuses on the modified ticket-reservation and packed-slot mechanisms and otherwise relies on the arguments made in sCQ [7]. b) Data structure: The inner ring has 2n physical slots and logical capacity n. Each slot is a single 64-bit word. Index is either a payload index ⊥ for an empty slot or ⊥c for a consumed slot. As in sCQ [7], the queue state consists of monotonically increasing Head and Tail counters, a Threshold used by empty dequeues, and the entry array itself.

Fig. 1: Wave-batching reduces atomic contention

c) Wave-batched ticket reservation: A naive FAA-based queue performs one fetch-and-add per active thread on Head or Tail. On a GPU, that needlessly concentrates contention on the same counter word. G-LFQ instead batches reservations within a wavefront. Active lanes first form a mask with a ballot instruction. One leader performs a single fetch-and-add by the number of active lanes, broadcasts the returned base ticket, and each participating lane adds its rank within the mask. The result is a consecutive block of tickets, but only one global atomic is issued for the whole group, as visualized by Fig. 1. For the pseudocode below, let   t mod 2bc . SLOT(t) = (t mod 2n), CYCLE(t) = 2n We denote FAA for fetch-and-add and CAS for compare-andswap. The operation C ONSUME is an atomic update that marks the slot’s index field as ⊥c without changing the other packed fields. d) Linearization points: A successful enqueue linearizes at the successful 64-bit CAS that installs the new entry in its target slot. A successful dequeue linearizes at C ONSUME, which atomically marks that slot as consumed. An empty dequeue linearizes at the first empty observation for its claimed head ticket: either Tail has not advanced beyond h + 1, or the threshold update proves that no reachable element exists for that ticket. Lemma III.1 (WaveFAA preserves ticket order). Within one call to WAVE FAA, the active mask is fixed. The leader performs exactly one fetch-and-add by the number of active lanes, which reserves a contiguous ticket interval. Each active lane adds a distinct prefix rank within that mask, so the returned tickets are pairwise distinct and consecutive. Across different calls, the global counter remains monotonic because fetch-and-add is atomic. Therefore, WAVE FAA produces exactly the same total ticket order as per-thread fetch-and-add; it only changes how that order is obtained 1. Lemma III.2 (Reduced-width cycle tags are sufficient for reachable states). Let R = 2bc be the cycle range. A ticket t maps to slot t mod 2n and cycle ⌊t/(2n)⌋ mod R. Because a physical slot can only be reused after another full wrap of 2n tickets, the queue compares only live cycle states whose

Algorithm 1: G-LFQ fast path function WAVE FAA(C, active): mask ← Ballot(active) 3 if mask = 0 then 4 return ⊥ 5 end 6 count ← Popcount(mask) 7 leader ← FirstSetBit(mask) − 1 8 if lane = leader then 9 base ← FAA(C, count) 10 end 11 base ← Shuffle(base, leader) 12 rank ← Popcount(mask ∩ lower_lanes(lane)) 13 return base + rank 14 function T RY E NQ (x): 15 t ← WAVE FAA(T ail, active) 16 j ← SLOT(t), c ← CYCLE(t) 17 E ← Entry[j] 18 if E.Cycle < c and (E.Safe ∨ Head ≤ t) and E.Index ∈ {⊥, ⊥c } then 19 if CAS(Entry[j], E, ⟨c, 1, x⟩) succeeds then 20 reset Threshold to 3n − 1 21 return SUCCESS 22 end 23 end 24 return RETRY 25 function T RY D EQ (): 26 if T hreshold < 0 then 27 return EMPTY 28 end 29 h ← WAVE FAA(Head, active) 30 j ← SLOT(h), c ← CYCLE(h) 31 E ← Entry[j] 32 if E.Cycle = c and E.Index ∈ / {⊥, ⊥c } then 33 C ONSUME(Entry[j]) 34 return E.Index 35 end 36 if E.Index ∈ {⊥, ⊥c } then 37 try CAS(Entry[j], E, ⟨c, E.Safe, ⊥⟩) 38 end 39 else 40 try CAS(Entry[j], E, ⟨E.Cycle, 0, E.Index⟩) 41 end 42 if T ail ≤ h + 1 then 43 catch up Tail to at least h + 1 44 decrement Threshold and return EMPTY 45 end 46 if decrementing Threshold makes it negative then 47 return EMPTY 48 end 49 return RETRY 1

2

true distance is bounded by the number of outstanding wraps on that slot. Under the paper’s queue configurations, the live skew remains strictly below R/2, so modular comparison agrees with the true cycle order on all reachable fast-path states. Hence, the packed cycle field preserves the slot ordering needed by the sCQ-style ring argument. Theorem III.3 (G-LFQ is linearizable and FIFO). Proof. Apart from the two changes to the ticket reservation, GLFQ follows the same bounded-ring discipline as sCQ [7]. By Lemma III.1, ticket reservation in G-LFQ is observationally

Fig. 2: Entry word for G-WFQ

equivalent to the sequential ticket order assumed by sCQ. By Lemma III.2, the reduced-width cycle field preserves the same live-slot ordering as the unbounded counter view on all reachable states. Since each slot update is performed by a single 64-bit atomic operation, the queue exposes the same slot semantics to concurrent threads as the sCQ ring. Therefore, GLFQ is linearizable and preserves FIFO order. □ Theorem III.4 (G-LFQ is lock-free). Proof. The lock-freedom argument is the same as for sCQ once the ticket correspondence is fixed. If an enqueue or dequeue retries forever, then it must do so because some shared state changed first: another thread claimed the slot, consumed the slot, advanced Head or Tail, or changed the thresholdrelevant state for the observed ticket. Thus infinite retries by one thread imply infinitely many successful state changes by other threads. Therefore, G-LFQ is lock-free, though not waitfree. □ C. G-WFQ: GPU Wait-Free Queue a) Design goal: G-WFQ is our bounded wait-free GPU ring with the same bounded 2n-slot organization as G-LFQ, but adds a cooperative slow path so that an operation that fails repeatedly on the fast path can still complete after bounded helping. At a high level, the design follows the fast-path/slowpath structure of wCQ [8]: retries are bounded on the fast path, requests are published in fixed per-thread records, and helpers cooperate on the same logical round. We use patience constants to bound the number of fast-path retries before an operation publishes a request and enters the cooperative slow path. The help delay D controls how frequently each thread checks for pending peer requests: a thread inspects one peer record every D operations. Together, patience and help delay determine the worst-case bound on slow-path completion. The main difference is architectural. Instead of relying on CAS2style shared state as in the CPU setting, G-WFQ packs the shared queue state into native 64-bit GPU words and uses only pre-allocated device memory. b) Data structure: The inner queue is a bounded ring with 2n physical slots and logical capacity n. Each slot stores all shared entry state in one 64-bit word, as shown in Fig. 2. In the packed entry format, Index is either a payload index, ⊥ (empty), or ⊥c for a consumed slot. As in sCQ and wCQ, the ring uses the same threshold-based empty test and the same bounded-memory setting with fixed capacity [8].

Fig. 3: Global and local Tail/Head word for G-WFQ

The global Head and Tail are packed into one 64bit word, as shown in Fig. 3, where ThrIdx is a helper

Algorithm 2: G-WFQ cooperative slow-path increment function S LOW FAA(G, L, thld): while true do 3 if L has FIN then 4 return false 5 end 6 read G = ⟨c, u⟩ 7 if u ̸= NULL then 8 help the phase-2 request named by u 9 end 10 synchronize L to c using INC 11 publish phase-2 record (L, c) 12 if CAS(G, ⟨c, NULL⟩, ⟨c + 1, tid⟩) succeeds then 13 if thld ̸= ∅ then 14 FAA (thld, −1) 15 end 16 clear INC on L 17 clear ThrIdx in G 18 return true 19 end 20 end 1

2

empty dequeue linearizes at the first threshold observation, proving that no reachable entry exists for the claimed head ticket. Lemma III.5 (Single-word shared-state atomicity). Every shared word that is concurrently modified in G-WFQ is updated with one 64-bit atomic operation: slot entries, global head/tail state, and local head/tail state. Consequently, helpers never observe torn mixed states, such as a new cycle with an old index or a new counter with a stale helper identifier. This is the key invariant that replaces 128-bit compare-and-swap or CAS2-style atomicity from wCQ [8] in our GPU design. Lemma III.6 (Modular cycle correctness). Let R = 2bc be the cycle range. G-WFQ compares cycle tags modulo R and treats a as newer than b when 0 < (a − b) mod R < R/2. For a queue with logical capacity n, k participating threads, and help delay D, the true cycle skew on any one physical slot is bounded by Dk + 5n . 2n Hence modular comparison is sound whenever Smax <

thread identifier or a reserved null value. Each thread owns a fixed record containing the request flags, the initial and local head/tail values, the payload index for enqueue, two sequence fields, and a phase-2 record. Fig. 3 also shows how local head/tail words are packed together. Compared with wCQ [8], the role is the same but adapted using single-word GPU atomics. c) GPU publication discipline: A slow-path request is published in a fixed order. The owner first writes the payload fields (localTail/localHead, initTail/initHead, index, enqueue), then publishes the request with the sequence fields and the pending bit. Helpers accept a request only if the published sequence values match, similar to the request-record discipline used by wCQ [8], but stated in the form needed for our packed 64-bit design. Algorithm 2 shows the cooperative slow-path increment (S LOW FAA) used by both enqueue and dequeue to advance the global counter exactly once per round. d) Slow-path slot actions: T RY E NQ S LOW and T RY DEQ S LOW operate on the slot selected by the current logical ticket. A slow enqueue either installs the current-cycle entry or records (via Note) that a stale slot is no longer a valid candidate for this request. A slow dequeue follows the same pattern: it either completes on the matching current-cycle slot or updates the slot state so that later helpers make the same reuse decision. The slow-path note mechanism mirrors the role of Note in wCQ [8], but here the entire decision state is carried in one packed slot word. e) Linearization points: G-WFQ uses the same fast-path as G-LFQ. On the slow path, a successful enqueue linearizes at the CAS that first installs the current-cycle entry in the target slot. The later Enq-bit update from 0 to 1 does not move the linearization point; it only makes the entry visible to later fast-path dequeues. A successful dequeue linearizes at C ONSUME, which atomically marks the slot consumed. An

Dk + 6. n Under the proof configuration used in this paper (k ≤ n and D = 64), an 8-bit cycle tag (R = 256) is therefore sufficient. Lemma III.7 (One cooperative increment per round). For any published slow-path request, all helpers race on the same global transition R>

⟨c, NULL⟩ → ⟨c + 1, tid⟩. At most one CAS can succeed. The INC bit prevents duplicate local increments for the same round, and the FIN bit terminates further rounds once the request has been resolved. Therefore, each logical slow-path round advances Head or Tail exactly once. For dequeue rounds, the Threshold is decremented at most once. Lemma III.8 (Stale-slot exclusion). If a helper determines that an old-cycle slot is not reusable for the current request, it advances Note to the current cycle. Any later helper for that same request cycle observes the updated note and skips the same slot. Thus, helpers do not diverge by repeatedly reconsidering stale slots that have already been ruled out. Theorem III.9 (G-WFQ is linearizable and FIFO). Proof. By Lemma III.5, all shared-state transitions are atomic at the granularity assumed by the algorithm. By Lemma III.6, reduced-width cycle tags preserve the intended live-slot order. By Lemma III.7, the slow path behaves like one logical fetch-and-add round even when many helpers participate. By Lemma III.8, helpers cannot later reuse a stale slot that has already been ruled out for the same request. Therefore, the slow path preserves the same FIFO order as the fast path, and the two compose correctly. Hence, G-WFQ is linearizable and preserves FIFO order. □

TABLE I: GPUs used in micro-benchmark.

A. Throughput Benchmarks

GPU

Arch

Cache line

Compute Units

Global Mem

MI210 MI300A

CDNA2 CDNA3

64 B 128 B

104 224

64 GB 128 GB

a) Micro-benchmarks: We use two fixed-duration queue micro-benchmarks. The first is a balanced kernel, where each active thread repeatedly performs one enqueue followed by one dequeue. The second benchmark is a split producer/consumer kernel, in which the threads are assigned producer or consumer roles, and the producer fraction is varied to create a load that is asymmetric. We evaluate producer/consumer splits of 25% producer/75% consumers, 50%/50%, 75%/25% which more closely resemble the empty, nominal, and full conditions of the queue. The test measures throughput over a fixed runtime interval intended to measure sustained throughput rather than completion time for a fixed number of operations. b) Throughput metric: We report successful-operation throughput, measured as the number of successful enqueues plus successful dequeues divided by the measurement interval:

Theorem III.10 (GPU-resident wait-freedom of G-WFQ). Assume that the participating thread set remains resident (i.e., all participating blocks remain concurrently resident on the GPU) and that the scheduler provides fair progress among those threads. Under this assumption, G-WFQ is wait-free. Proof. The fast path is bounded by the compile-time patience constants. After that, the operation publishes a fixedsize request record and enters the cooperative slow path. By Lemma III.7, each slow round performs at most one logical increment of the corresponding global counter, and once the request is resolved, FIN is set so that all remaining helpers stop. Since the number of fast attempts is bounded and the work per slow round is bounded under the stated residency assumption, every operation completes in a bounded number of its own steps. Therefore, G-WFQ is wait-free under GPUresident execution. □ IV. C ORRECTNESS CHECKS a) Linearizability via Porcupine: We log concurrent operations with fields proc, op, arg, ret, call, end, where op=0 denotes E NQ and op=1 denotes D EQ. We then feed the log to the standard FIFO model in Porcupine and check linearizability [15], [16].2 b) Device-side FIFO conformance: Independently, we run a GPU check: each producer thread emits tokens tok = (tid << 32) | (seq+1); consumers dequeue until all tokens have been consumed. We verify (i) exactly once (no zeros, no > 1 counts), (ii) no out-of-bounds tokens, and (iii) monotone sequence per-producer. For SFQ’s bounded ring, we cap ops/thread to avoid intentional blocking of producers. c) Result: SFQ, G-WFQ-YMC, G-WFQ, and G-LFQ all passed the Porcupine checks, which returned linearizable, and the device-side checker reported no duplicates or per-producer order violations. Together, these tests support linearizable FIFO semantics. V. E XPERIMENTAL M ETHODOLOGY We isolate queue behavior with two GPU micro-benchmarks before evaluating application workloads. All implementations are compiled with HIP; each variant (SFQ, G-WFQ-YMC, G-LFQ, G-WFQ) plugs into a unified harness that initializes the queues, launches a single kernel, and measures end-to-end kernel time. Kernels are run at a fixed block size. a) Devices: We use the AMD MI300A and MI210 as shown in the hardware specification Table I. To minimize false sharing on lines, we pad cells to a cache-aligned width. 2 We follow Porcupine’s queue example; the model enqueues append to the state list and dequeues must return the head or report empty.

Successful ops = successful enq + successful deq, Successful ops [ops/s]. Throughput = tmeas

(1) (2)

c) Parameters and reporting: We sweep thread counts T ∈ {29 − 215 } with a fixed block size of 256 threads, as that gave us optimal results (we swept block sizes from 64 to 512). Each run includes a warmup interval followed by a measurement interval. Each configuration is run five times; we report the median throughput. For the split kernel, we report results for producer fractions of 25%, 50%, and 75%. B. Application workloads Irregular workloads that exhibit contention-heavy coordination are a natural use case for GPU concurrent queues. We therefore two applications to validate queue behavior beyond synthetic micro-benchmarks. a) Level-synchronous BFS: We evaluate the queues in a level-synchronous BFS over graphs stored in CSR (Compressed Sparse Row) format. At each level, the current frontier is dequeued, outgoing neighbors are examined, and newly visited vertices are marked and are enqueued into the next frontier. We alternate between two queues across BFS levels until the next frontier is empty. We compare against Gunrock’s BFS from the HIP-develop branch, using Gunrock’s default parameters. We report BFS runtime (ms), number of BFS levels, and total edges scanned as we sweep thread counts from 29 to 213 with a block size of 256. b) Tile-based wavefront Ray Tracing: To compare against stream-compaction [21], we evaluate the queues in a tile-based persistent wavefront ray tracer. A W × H image is partitioned into Tx × Ty tiles, and each tile owns its own queue. Primary rays are generated and enqueued per tile, and a persistent tracing kernel repeatedly dequeues work, traces rays, shades hits, and re-enqueues reflective bounces into the same tile queue until no work remains. We report ray-tracing throughput in MRays/s (Millions of Rays per second) and compare each queue against the stream-compaction baseline using relative throughput. The two scenes are: (1) Complex

TABLE II: Base counters sampled with rocprofv2. Short names are used in plots. Short name

ROCm counter (sum over kernel)

WAIT VALU WAVE CYC SUCC

SQ_WAIT_ANY SQ_INSTS_VALU_INT(32|64) SQ_WAVE_CYCLES successful enqueue + dequeue count

TABLE III: Derived metrics used in evaluation. All values are aggregated per kernel and normalized by successful operations. Metric

Definition and interpretation

WAIT/op

= (WAIT/WAVE CYC)/SUCC. Average scheduler wave stall fraction per successful op. High values indicate backpressure, serialization, or prolonged spinning. = VALU/SUCC. Vector ALU instructions executed per successful operation. Captures retry overhead and wasted computation under contention.

VALU/op

Scene, with 100 spheres on a plane and two-bounce reflections, and (2) Cornell-box Scene, with two spheres, four reflections, a plane, and three walls. C. Profiling setup We profile the throughput tests using rocprofv2, focusing on two kernels that stress different contention regimes: balanced kernel (enqueue/dequeue alternation) and split kernel (producers at 25%/50%/75% unless otherwise stated). a) Normalization by successful operations: Raw hardware counters on GPUs primarily reflect execution activity, not algorithmic progress. In contended queues, retries and spinning may lead to a large execution of instructions while making little progress. We normalize all primary metrics we collect as shown in Table II by the number of successful queue operations for the true cost. A successful operation is defined as an enqueue or dequeue that completes and commits its effect to the queue state. We exclude from this: failed retries, speculative attempts, and empty dequeues. This makes comparisons across queue designs and contention regimes more meaningful by converting raw counters into per-operation costs. b) Key metrics: We focus on two normalized metrics as our primary indicators of efficiency and scalability as shown by Table III: • Wait per successful op: captures how much wavefront waiting a queue operation induces. • VALU per successful op: captures how much useful vector computation is expended per completed operation. c) Why wait/op and VALU/op: When using the above metrics, we can distinguish queues that are inefficient, either due to waiting or retrying while trying to make forward progress. Normalizing by successful operations isolates contention (WAIT/op) and computational overhead (VALU/op) as pure per-progress-unit costs.

VI. E VALUATION We evaluate G-WFQ-YMC, G-WFQ, and G-LFQ in two ways: micro-benchmark throughput and performance in two applications, level-synchronous breadth first search and wavefront ray tracing. We then use profiling metrics to explain the throughput trends and compare the application results against Gunrock and a stream-compaction ray tracing baseline. A. Throughput Summary Fig. 4 shows throughput (Mops/s) versus thread count on MI300A and MI210 for balanced kernel (1:1 enqueue/dequeue) and split producer/consumer kernels. Overall, the bounded ring queues dominate throughput. G-LFQ is the strongest design in the balanced kernel test and in the split (producer/consumer) test that keeps it near-balanced, while G-WFQ sustains higher throughput under asymmetric split test (i.e., producer/consumer at 25%/75% or 75%/25%) which places the queue in near-empty or near-full conditions. These performance trends are also sensitive to architecture: on MI210, G-LFQ is strongest whenever the workload remains close to balanced, whereas on MI300A its advantage becomes less evident at the largest thread counts. G-WFQ-YMC remains slower, but becomes more competitive in producerheavy splits on MI300A. SFQ is only competitive in the balanced kernel and throughput declines sharply under split workloads. B. Key Observations 1) Balanced Kernel 1:1 Test: In the balanced kernel, the bounded ring designs clearly separate from the two baselines on MI210/MI300A. G-LFQ delivers the highest throughput, which indicates that its wave-batched fast path is effective when enqueue and dequeue demand are balanced. G-WFQ remains close behind, showing that the added overhead required for wait-freedom does not eliminate the advantages of its wave-batched fast-path and bounded ring structure. By contrast, G-WFQ-YMC carries a higher structural overhead, and SFQ remains limited by its more serialized dequeue behavior. 2) Split (Producer/Consumer) Kernel: Under asymmetric loads or conditions that place the queue at near empty or near full, the advantage shifts from peak throughput to the ability to make progress. On MI210, under the near-empty and nearfull regimes, the G-WFQ outperforms the other queues, while the G-LFQ remains strongest near the even 50% producerconsumer split. On MI300A, the same bounded ring family remains strongest overall, but G-LFQ degrades at the largest thread counts, whereas G-WFQ degrades more gracefully. G-WFQ-YMC is still not the fastest design overall, but it becomes relatively more competitive in producer-heavy splits on MI300A. SFQ performs poorly in all split configurations, which is consistent with a design that is much less tolerant of asymmetric contention. C. Profiling Analysis The profiling figures (Figs. 5a and 5b) explain the throughput ordering in Fig. 4. We use G-LFQ as the reference point

Fig. 4: Fixed-duration successful-operation throughput (Mops/s) across four queue micro-benchmarks on AMD MI210 and MI300A: balanced kernel (1:1 enqueue/dequeue) and split producer/consumer kernels (25%/75%, 50%/50%, and 75%/25%). G-LFQ achieves the highest throughput in most configurations. On MI210, G-WFQ remains closer to G-LFQ under asymmetric producer/consumer splits. On MI300A, G-WFQ’s throughput falls less sharply at high thread counts, while G-LFQ more often peaks earlier and drops under asymmetric splits. G-WFQ-YMC remains slower overall, but still similar to the bounded ring designs in split workloads, especially on MI300A. SFQ is only competitive in the balanced kernel.

because it is the fastest design in the balanced kernel and nearbalanced split tests. a) G-LFQ: has the lowest per-operation cost on MI210, which indicates that wave-batched fetch-and-add is effective when the hardware handles the atomic contention on the shared counters efficiently. On MI300A, the dominant change is not a comparable rise in VALU/op, but a much larger increase in WAIT/op. This indicates that G-LFQ tends to stall on CDNA3, likely due to higher atomic-operation latency on MI300A’s memory subsystem, which explains why it retains strong peak throughput at moderate thread counts, but loses performance as contention increases. b) G-WFQ: remains close to G-LFQ in per-operation cost on both architectures, but shows a smaller WAIT/op penalty on MI300A. That lower WAIT/op growth is consistent with the throughput results: G-WFQ does not always achieve the highest peak throughput, but its throughput degradation is less rapid than G-LFQ in the highest-thread-count and asymmetric regimes (i.e., which put the queues under near empty or near full condition). On MI300A, the higher atomic latency means threads enter the slow path less frequently, reducing slow-path overhead and partially explaining G-WFQ’s more graceful degradation on CDNA3. c) G-WFQ-YMC: incurs a higher instruction cost for every successful queue operation than the bounded ring designs, due to its more complex helping and segment-based structure, which increases instruction cost, especially on queue retries. However, its wait cost tracks the bounded designs more closely on MI300A than on MI210, which explains why it becomes relatively more competitive on CDNA3 even though its absolute per-operation cost remains higher.

TABLE IV: Graph inputs used in the BFS evaluation. Graph ak2010 belgium_osm kron_g500-logn21 delaunay_n21 hollywood-2009 roadNet-CA road_usa europe_osm delaunay_n24

Vertices

Edges

Avg. out-degree

45,292 1,441,295 2,097,152 2,097,152 1,139,905 1,971,281 23,947,347 50,912,018 16,777,216

217,098 3,099,940 182,081,864 12,582,816 112,751,422 5,533,214 57,708,624 108,109,320 100,663,202

4.79 2.15 86.82 6.00 98.91 2.81 2.41 2.12 6.00

d) SFQ: operates in a different regime altogether. Its peroperation cost is dominated by the serialization of its dequeue side, which drives both WAIT/op and VALU/op well above the bounded ring designs. This explains why SFQ remains acceptable only in the balanced kernel and collapses under split producer/consumer workloads. D. Level-Synchronous BFS Performance Table IV summarizes the graph inputs which are taken from the Suitesparse matrix collection [24] used in the BFS evaluation, and Fig. 6 reports each queue’s best runtime across the thread-count sweep relative to Gunrock from 29 to 213 (performance degraded at higher counts for all designs). The main result shows that the bounded ring queues remain competitive against the baseline of the GPU graph framework while providing stronger queue semantics. Across the nine graphs, G-LFQ is the strongest overall design, and G-WFQ remains in a similar performance range on most input graphs. The largest gains appear on several MI210 graphs, whereas on MI300A, the bounded ring queues more often remain close to Gunrock rather than outperforming it. G-WFQ-YMC remains

(a) MI210 Profiling Metrics Per Successful Operation

(b) MI300A Profiling Metrics Per Successful Operation

Fig. 5: Per-operation profiling metrics across four queue micro-benchmarks on AMD MI300A and MI210. Each row shows WAIT/op and VALU/op for the balanced kernel (1:1 enqueue/dequeue) and split producer/consumer kernels (25%/75%, 50%/50%, and 75%/25%). On MI300A, G-WFQ and G-LFQ have similar WAIT/op through much of the thread-count sweep, but G-LFQ’s WAIT/op rises more sharply at the largest thread counts. On MI210, G-WFQ and G-LFQ remain close in WAIT/op, while G-WFQ-YMC incurs higher VALU/op. SFQ has the highest per-operation cost, especially under split workloads.

viable but generally trails the bounded ring designs, which suggests that the efficiency of the bounded ring designs carries over better to the irregular graph frontier management than the segment-based unbounded queue. SFQ, by contrast, is consistently much slower, matching the serialization effects already visible in the micro-benchmarks, Fig. 4. Overall, the BFS results show that concurrent queues with strong progress guarantees can remain practical in graph traversal workloads rather than only in synthetic kernels.

E. Wavefront Ray Tracing with Concurrent Queues Fig. 7 compares queue-driven wavefront ray tracing against stream-compaction [21] across two scenes and thread counts from 29 to 213 . The outcome is strongly architecturedependent. On MI210, G-LFQ is the strongest design and exceeds the compaction baseline across both scenes. G-WFQ remains competitive on the simpler workload but loses ground on the more reflection-heavy scene. G-WFQ-YMC and SFQ

Fig. 6: BFS runtime relative to Gunrock across 9 graphs. G-LFQ consistently beats Gunrock, while G-WFQ is faster on several graphs. G-WFQ-YMC scales well but does not surpass Gunrock, and SFQ is slower by orders of magnitude.

Fig. 7: Ray-tracing throughput relative to stream-compaction across both scenes and GPUs. On MI210, G-LFQ outperforms stream-compaction while G-WFQ approaches parity; on MI300A, all queues fall below compaction, with G-LFQ and G-WFQ the closest.

remain well behind the bounded ring designs throughout. On MI300A, stream compaction beats all the queue designs. Even so, G-LFQ and G-WFQ remain the closest queue-based alternatives, whereas G-WFQ-YMC becomes less reliable at higher thread counts and SFQ remains substantially weaker. Taken together, these results suggest that queue-based wavefront scheduling is most effective when the cost of global synchronization dominates the cost of queue operations. VII. F UTURE W ORK Concurrent queue-driven work distribution is promising especially in irregular GPU pipelines, as indicated by the work in Broker Queue [13]. The next step would be to study and compare queues with progress guarantees against those without relaxed alternatives. We tested Broker Queue’s linearizable variant but it stalled under sustained application pressure in both BFS and ray tracing; the non-linearizable variant completed ray-tracing runs but could not maintain FIFO semantics for BFS frontier management. A controlled comparison of linearizable and relaxed queues across application workloads remains future work. Although the current design preserves the strong progress guarantees, slow-path activation can still impose substantial overhead. Future work should therefore focus on reducing the cost of slow-path publication and completion on GPUs.

VIII. C ONCLUSION This paper presented GPU-aware concurrent queues with strong progress guarantees and bounded memory: the lockfree G-LFQ, the wait-free G-WFQ, and G-WFQ-YMC as an adapted reference baseline. Across fixed-duration microbenchmarks on MI210 and MI300A, the bounded ring designs delivered the strongest overall performance and efficiency. G-LFQ achieved the highest peak throughput in several settings, while G-WFQ was the most robust across architectures and workload mixes, sustaining performance under contention and degrading more gracefully at high thread counts. Profiling showed that these differences are explained largely by the per-operation wait cost and atomic overhead. In level-synchronous BFS, G-LFQ and G-WFQ matched or exceeded Gunrock on several graphs, and in tile-based wavefront ray tracing the queue-driven designs were competitive with stream-compaction. Overall, the results show that linearizable, bounded GPU queues with strong progress guarantees can be both practical and high-performance. IX. ACKNOWLEDGEMENT The manuscript was drafted by the authors. ChatGPT 5.4 and Claude Sonnet 4.6 were used to identify spelling, and tone issues, with all suggestions reviewed and selectively included to improve clarity and polish.

R EFERENCES [1] M. M. Michael and M. L. Scott, “Simple, fast, and practical nonblocking and blocking concurrent queue algorithms,” in Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, ser. PODC ’96. New York, NY, USA: Association for Computing Machinery, 1996, p. 267–275. [Online]. Available: https://doi.org/10.1145/248052.248106 [2] P. Tsigas and Y. Zhang, “A simple, fast and scalable non-blocking concurrent fifo queue for shared memory multiprocessor systems,” in Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, ser. SPAA ’01. New York, NY, USA: Association for Computing Machinery, 2001, p. 134–143. [Online]. Available: https://doi.org/10.1145/378580.378611 [3] A. Kogan and E. Petrank, “A methodology for creating fast wait-free data structures,” SIGPLAN Not., vol. 47, no. 8, p. 141–150, Feb. 2012. [Online]. Available: https://doi.org/10.1145/2370036.2145835 [4] ——, “Wait-free queues with multiple enqueuers and dequeuers,” in Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’11. New York, NY, USA: Association for Computing Machinery, 2011, p. 223–234. [Online]. Available: https://doi.org/10.1145/1941553.1941585 [5] C. Yang and J. Mellor-Crummey, “A wait-free queue as fast as fetch-and-add,” in Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’16. New York, NY, USA: Association for Computing Machinery, 2016. [Online]. Available: https://doi.org/10.1145/2851141.2851168 [6] A. Morrison and Y. Afek, “Fast concurrent queues for x86 processors,” SIGPLAN Not., vol. 48, no. 8, p. 103–112, Feb. 2013. [Online]. Available: https://doi.org/10.1145/2517327.2442527 [7] R. Nikolaev, “A Scalable, Portable, and Memory-Efficient LockFree FIFO Queue,” in 33rd International Symposium on Distributed Computing (DISC 2019), ser. Leibniz International Proceedings in Informatics (LIPIcs), J. Suomela, Ed., vol. 146. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, pp. 28:1– 28:16. [Online]. Available: https://doi.org/10.4230/LIPIcs.DISC.2019.28 [8] R. Nikolaev and B. Ravindran, “wcq: a fast wait-free queue with bounded memory usage,” in Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 461–462. [Online]. Available: https://doi.org/10. 1145/3503221.3508440 [9] Y. Roh, Y. Wei, E. Ruppert, P. Fatourou, S. Jayanti, and J. Shun, “Aggregating funnels for faster fetch&add and queues,” in Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’25. New York, NY, USA: Association for Computing Machinery, 2025, p. 99–114. [Online]. Available: https://doi.org/10.1145/3710848.3710873 [10] A. Smith, G. H. Loh, M. J. Schulte, M. Ignatowski, S. Naffziger, M. Mantor, M. Fowler, N. Kalyanasundharam, V. Alla, N. Malaya, J. L. Greathouse, E. Chapman, and R. Swaminathan, “Realizing the amd exascale heterogeneous processor vision,” in Proceedings of the 51st Annual International Symposium on Computer Architecture, ser. ISCA ’24. IEEE Press, 2025, p. 876–889. [Online]. Available: https://doi.org/10.1109/ISCA59077.2024.00068 [11] S. L. Atchley, C. Zimmer, J. Lange, D. Bernholdt, V. Melesse Vergara, T. Beck, M. Brim, T. Evans, R. Budiardja, S. Chandrasekaran et al., “Frontier: Exploring exascale.” Oak Ridge National Laboratory (ORNL), Oak Ridge, TN (United States), 04 2024. [Online]. Available: https://www.osti.gov/biblio/2438964 [12] T. R. Scogland and W.-c. Feng, “Design and evaluation of scalable concurrent queues for many-core architectures,” in Proceedings

of the 6th ACM/SPEC International Conference on Performance Engineering, ser. ICPE ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 63–74. [Online]. Available: https://doi.org/10.1145/2668930.2688048 [13] B. Kerbl, M. Kenzel, J. H. Mueller, D. Schmalstieg, and M. Steinberger, “The broker queue: A fast, linearizable fifo queue for fine-granular work distribution on the gpu,” in Proceedings of the 2018 International Conference on Supercomputing, ser. ICS ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 76–85. [Online]. Available: https://doi.org/10.1145/3205289.3205291 [14] M. S. H. Polak, D. A. Troendle, and B. Jang, “Boundary-aware concurrent queue: A fast and scalable concurrent fifo queue on gpu environments,” Applied Sciences, vol. 15, no. 4, 2025. [Online]. Available: https://www.mdpi.com/2076-3417/15/4/1834 [15] M. P. Herlihy and J. M. Wing, “Linearizability: a correctness condition for concurrent objects,” ACM Trans. Program. Lang. Syst., vol. 12, no. 3, p. 463–492, Jul. 1990. [Online]. Available: https://doi.org/10.1145/78969.78972 [16] A. Horn and D. Kroening, “Faster linearizability checking via p-compositionality,” in Formal Techniques for Distributed Objects, Components, and Systems, S. Graf and M. Viswanathan, Eds. Cham: Springer International Publishing, 2015, pp. 50–65. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-319-19195-9 4 [17] R. Romanov and N. Koval, “The state-of-the-art lcrq concurrent queue algorithm does not require cas2,” in Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’23. New York, NY, USA: Association for Computing Machinery, 2023, p. 14–26. [Online]. Available: https://doi.org/10.1145/3572848.3577485 [18] Y. Wang, Y. Pan, A. Davidson, Y. Wu, C. Yang, L. Wang, M. Osama, C. Yuan, W. Liu, A. T. Riffel, and J. D. Owens, “Gunrock: Gpu graph analytics,” ACM Trans. Parallel Comput., vol. 4, no. 1, Aug. 2017. [Online]. Available: https://doi.org/10.1145/3108140 [19] S. G. Parker, J. Bigler, A. Dietrich, H. Friedrich, J. Hoberock, D. Luebke, D. McAllister, M. McGuire, K. Morley, A. Robison, and M. Stich, “Optix: a general purpose ray tracing engine,” ACM Trans. Graph., vol. 29, no. 4, Jul. 2010. [Online]. Available: https://doi.org/10.1145/1778765.1778803 [20] S. Laine, T. Karras, and T. Aila, “Megakernels considered harmful: wavefront path tracing on gpus,” in Proceedings of the 5th HighPerformance Graphics Conference, ser. HPG ’13. New York, NY, USA: Association for Computing Machinery, 2013, p. 137–143. [Online]. Available: https://doi.org/10.1145/2492045.2492060 [21] I. Wald, “Active thread compaction for gpu path tracing,” in Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, ser. HPG ’11. New York, NY, USA: Association for Computing Machinery, 2011, p. 51–58. [Online]. Available: https://doi.org/10.1145/2018323.2018331 [22] D. Meister, J. Boksansky, M. Guthe, and J. Bittner, “On ray reordering techniques for faster gpu ray tracing,” in Symposium on Interactive 3D Graphics and Games, ser. I3D ’20. New York, NY, USA: Association for Computing Machinery, 2020. [Online]. Available: https://doi.org/10.1145/3384382.3384534 [23] M. Lee, B. Green, F. Xie, and E. Tabellion, “Vectorized production path tracing,” in Proceedings of High Performance Graphics, ser. HPG ’17. New York, NY, USA: Association for Computing Machinery, 2017. [Online]. Available: https://doi.org/10.1145/3105762.3105768 [24] T. A. Davis and Y. Hu, “The university of florida sparse matrix collection,” ACM Trans. Math. Softw., vol. 38, no. 1, Dec. 2011. [Online]. Available: https://doi.org/10.1145/2049662.2049663