SentryWard: Formal Verification of Warp-Specialized GPU Kernels
For a long time, GPU kernels were uniform data-parallel programs: every thread in a block ran the same code on its own part of the data. On modern architectures such as NVIDIA’s Hopper and Blackwell, matrix multip…
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
For a long time, GPU kernels were uniform data-parallel programs: every thread in a block ran the same code on its own part of the data. On modern architectures such as NVIDIA’s Hopper and Blackwell, matrix multiplication and data movement run on specialized units, the tensor cores and the Tensor Memory Accelerator (TMA), and these units work asynchronously: a thread only starts an operation, and the unit finishes it later.
To reach peak performance, a kernel must keep these units busy at the same time, loading the next tile while computing on the current one. High-performance kernels therefore give different warps different roles, such as loading, computing, and storing results. This style is called warp specialization, and the warps coordinate through barriers that wait for asynchronous operations to finish.
Such a kernel is a concurrent program, and its behavior can differ across schedules. A synchronization error may corrupt the output only under particular schedules, and random testing, which samples only the schedules that occur at run time, may miss it. Moreover, even with correct synchronization, a kernel can compute the wrong function because of a logic error.
SentryWard is a verifier for warp-specialized GPU kernels. Given a kernel’s PTX, a launch configuration, and an optional PyTorch reference, it can establish the following properties for that configuration and within its model:
SentryWard found issues in popular kernel libraries; we describe three of them below. Across 44 kernels, removing synchronization that it shows to be redundant cuts kernel time by a median of 3–7.5%, depending on the input size. In this post, we look at how warp-specialized kernels synchronize, what can go wrong, and how SentryWard checks them.
A block-wide barrier such as __syncthreads() makes all threads of a block wait for each other, but it does not wait for asynchronous copies or matrix multiplications to finish. Warp-specialized kernels therefore synchronize through mbarriers, barrier objects in shared memory with two counters: the pending arrivals and the pending bytes that the barrier still expects. Threads arrive on the barrier, and asynchronous copies report the bytes they deliver. When both counters reach zero, the current phase completes: the threads waiting for it proceed, and the barrier starts the next phase with its counters reset. We write a barrier’s state as (pending arrivals, pending bytes). For example, a barrier that expects one arrival starts at (1, 0); after a thread announces 32 KB and arrives, it is at (0, 32 KB), and once copies have delivered all 32 KB, it reaches (0, 0) and the phase completes.
The table below specifies each operation in our pseudocode, writing (p) for the phase number, (n) for the expected arrivals per phase, (a) for the pending arrivals, and (b) for the pending bytes (announced minus completed). It follows NVIDIA’s mbarrier, TMA copy, and tcgen05.commit specifications, without scope qualifiers and fences.
Our running example is a small warp-specialized kernel on a Blackwell GPU that computes one tile of a matrix multiplication (C = AB). A large matrix multiplication is usually split into such tiles, one per thread block. Each thread block computes its (M \times N) tile of (C) in a loop over the shared dimension (K), multiplying a block of (A) by a block of (B) in each iteration. The loop is software-pipelined: while the tensor core operates on the current blocks, the TMA prefetches those for subsequent iterations. After the loop, the epilogue stores the accumulated tile to (C) in global memory. Our example runs a single iteration, with (M = N = 128) and (K = 64); with 16-bit elements, each input tile is 16 KB.
The kernel runs 128 threads in four warps. Warp 0 loads the input tiles, and warp 1 issues the matrix multiply-accumulate (MMA) instruction. Running the two jobs in separate warps allows them to overlap. All four warps then run the epilogue. We call the three roles the producer, the consumer, and the epilogue. A single thread issues each copy or MMA. First, thread 0 (warp 0) asks the TMA to copy the input tiles into the shared-memory buffers sA and sB. When both copies have landed, the barrier full completes, and thread 32 (warp 1) issues the MMA; the tensor core executes it and writes the product to acc in tensor memory. When the product is ready, the barrier mma_done completes, and all 128 threads copy acc to (C) in global memory, one row per thread.
// 128 threads (4 warps), thread index t. if t == 0: init(full, 1) init(mma_done, 1) syncthreads()
// Main loop: a real kernel repeats it for every block of K; // here K is a single block, so it runs once. if t == 0: // producer arrive.expect_tx(full, 32 KB) 1 tma_load(sA ← A, full) 2 3 tma_load(sB ← B, full) 2 3
if t == 32: // consumer wait(full, 0) 4 tcgen05.mma(acc ← sA * sB) 5 tcgen05.commit(mma_done) 6
// Epilogue wait(mma_done, 0) 7 r = tcgen05.ld(acc[t, :]) 8 tcgen05.wait::ld() st.global(C[t, :] ← r) 8
Pseudocode of the running example; step numbers match Figure 1. Hover over or tap an operation to see what it does.
Figure 1: The running example. Threads only start the copies and the multiplication, and the TMA and the tensor core complete them asynchronously. The two barriers keep every step from using data before it is ready. Step numbers match the code.
The kernel is correct only because of the order its barriers enforce: step 4 keeps the multiplication from reading sA and sB too early, and step 7 keeps the threads from loading the accumulator too early.
Now suppose the epilogue forgets its wait, step 7:
wait(mma_done, 0) // epilogue (buggy) r = tcgen05.ld(acc[t, :]) tcgen05.wait::ld() st.global(C[t, :] ← r)
Both barriers still count exactly as before: the copies complete phase 0 of full, and the commit’s arrival completes phase 0 of mma_done. But nothing orders the epilogue’s loads after the multiplication any more. Whether the epilogue reads acc before or after the tensor core writes it depends on the schedule:
In this small kernel, the missing wait is easy to spot. In real kernels, with many more roles, pipeline stages, and asynchronous operations, it is not. The results below include a closely related missing wait in CUTLASS.
A test observes only the schedules that happen to occur, and so does a dynamic race detector such as Compute Sanitizer. Enumerating all schedules quickly becomes infeasible, since their number grows exponentially with the number of threads and asynchronous operations. We need an argument that covers every schedule without exhaustively enumerating them.
To prove a kernel correct, SentryWard checks three properties in turn: that the barriers behave the same way in every schedule, that no schedule has a data race or uses a resource after it is freed, and that the kernel computes the same function as the reference. The first property is well-synchronization, introduced for named barriers [1] and implemented in the WEFT verifier; SentryWard extends the definition and its algorithms to mbarriers. Each check relies on the guarantee of the one before it, and every guarantee covers all schedules of the configured launch under the modeled semantics. When a check identifies a violation, SentryWard reports a witness, such as the two unordered accesses of a race.
SentryWard analyzes kernels with static control flow: their branches and loop bounds may depend on the launch configuration, but not on the data. It first specializes the kernel for the launch configuration: it resolves branches and unrolls loops, so that each thread executes a finite sequence of instructions. It then records the program in two views: the event view, a graph of events, and the value view, which records what each thread loads, stores, and computes. An instruction that takes effect at once, such as a store or a barrier update, is a single event. An asynchronous instruction starts with an issue event, after which the hardware performs the rest. Program-order edges record the order that each thread’s code imposes.
Program order covers each thread on its own; across threads, the order comes from barriers. An mbarrier goes through a sequence of phases. During each phase, it counts pending arrivals and pending bytes: arrive decrements the pending-arrival count, expect_tx announces bytes, and a TMA copy subtracts its bytes when its transfer completes. When both counters reach zero, the phase completes, and the next phase starts with the counters reset. A thread waits for a phase to complete with wait; in our example, every wait is for phase 0.
Which updates does a wait observe? Those of the phase it waits for. But the schedule can change which phase an update joins. In one schedule, an update happens before phase 0 completes, so it joins phase 0. In another schedule, phase 0 completes first, so the same update joins phase 1. SentryWard focuses on kernels in which the schedule never changes what a wait observes. Formally, it requires the kernel to be well-synchronized: every barrier update and every wait belongs to the same phase in every execution.
Caveat. Some correct kernels are not well-synchronized, so they are outside SentryWard’s scope. Programmers, however, usually intend each wait to observe one particular phase, and in practice we find this scope sufficient: only one kernel in our benchmark fails SentryWard’s well-synchronization check.
Following WEFT, SentryWard first simulates one trace of the kernel, along any schedule that completes, and records the phase of every barrier update and every wait. From this trace it builds a candidate graph with a completion vertex for each phase. It then certifies that every schedule agrees with the trace. WEFT does this by checking that every update comes after the previous phase of its barrier completes. If certification succeeds, the candidate graph is the kernel’s happens-before graph: its orderings hold in every execution, and no execution deadlocks.
The hard part is the byte counter, for which WEFT’s check is not enough. A named barrier counts only arrivals, so a phase cannot complete before its last arrival. Pending bytes, however, go up as well as down, so a phase can reach (0, 0) before all of its updates have happened. It then completes early: the threads waiting for it proceed without the remaining updates, which join the next phase instead. To see this, consider a different mistake from the one above: the producer announces each tile’s 16 KB separately, just before starting its copy.
if t == 0: // producer (another bug) arrive.expect_tx(full, 16 KB) tma_load(sA ← A, full) expect_tx(full, 16 KB) tma_load(sB ← B, full)
If copy A lands before the second announcement, phase 0 completes early, and the second announcement joins phase 1. Unlike the missing wait, this kernel is not well-synchronized: the phase that the second announcement joins depends on the schedule. To catch such kernels, SentryWard checks that no phase can complete early. It looks for updates that can happen before the rest of their phase and already bring both counters to zero, like the first announcement and copy A here.
The buggy kernel with the missing wait passes the well-synchronization check, since its barriers count exactly as in the correct kernel. But without the epilogue’s wait, its happens-before graph has no path from the MMA’s execution to the epilogue’s loads (see the “Buggy kernel” tab in Figure 5).
With the happens-before graph, checking races becomes a question about paths. Two accesses conflict if their footprints may overlap and at least one of them writes, and SentryWard requires every conflicting pair to be ordered. Footprints follow exact layouts, including swizzled shared-memory tiles, and an SMT solver decides overlap when addresses a
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。