The Execution Model That Makes GPU Tests Different
FuzzGPU's central design problem is to make Vortex and OpenGPGPU execute programs that are both complicated and interpretable. This chapter focuses on the execution model that stands between an instruction stream and a useful GPU test: how work is grouped, how threads split and rejoin, how warps wait for one another, and how hardware resources complete operations. Following that path gives us a concrete way to predict where a CPU-style test will stall or where a hardware observation may not represent the program's architectural result.
From a kernel launch to a shared instruction stream
A GPU does not receive one long list of independent instructions and distribute them arbitrarily. A host CPU launches a kernel, and the GPU organizes that kernel as a grid of Cooperative Thread Arrays, or CTAs. A CTA is a package of work whose warps may need to cooperate, so the scheduler assigns the whole unit to a Streaming Multiprocessor, commonly called an SM. Each CTA contains multiple warps, and each warp is the unit that the scheduler moves through the machine.
That assignment creates the first important boundary in the system. The host defines the work to launch, but the GPU decides when a CTA enters an SM and which ready warp gets an opportunity to issue. A CTA may be waiting for memory while another warp on the same SM uses the available execution units. The machine gains performance from this overlap, but the overlap also means that two instructions near each other in a program need not be near each other in the hardware's event history. A test generator and an oracle both have to preserve the relationship between the work the host requested and the many partial activities the SM performs.
A warp follows one common instruction stream across a group of threads. The paper describes a warp as typically containing 32 threads, but that number is a description of the studied execution model, not a rule that applies to every GPU. Each thread maintains its own register context. A predicate, or active-thread, mask says which threads participate in the current instruction. This combination is what the paper calls Single-Instruction, Multiple-Thread (SIMT) execution: the instruction stream is shared, while participation and data remain partly per-thread.
That distinction changes the meaning of a branch. On a scalar CPU, a conditional branch selects one next program counter for one running context. In a SIMT warp, different threads can evaluate the condition differently. The machine then has to execute the taken path for one subset of threads and the other path for the rest. It records the active mask for each path and the point at which the paths can rejoin. When both paths reach that reconvergence point, the warp can resume with a combined mask.
The paper uses the idea of a SIMT stack to describe this bookkeeping. The stack records an active thread mask and a reconvergence program counter for a deferred path. It is not just an optimization detail. It is part of what makes a program with divergent control flow meaningful: without it, the machine would not know which threads belong on the next path or when inactive threads may participate again.
A simple example shows why this matters to testing. Suppose eight threads in a warp reach a branch, and three take the branch while five fall through. The hardware must run the first path with a three-thread mask, preserve the five-thread path, then run the second path and eventually restore the full group. An input generator that emits instructions for only one path may leave the other threads permanently inactive. A generator that emits both paths but cannot preserve their join can produce instructions that are legal in isolation yet unreachable in the intended execution. In either case, the test's apparent length exaggerates the amount of behavior that the hardware actually exercised.
Synchronization adds a relationship that reaches beyond one warp. A barrier tells participating warps to stop until all members of a defined group have arrived at the matching point. The group might be a CTA or, on a target that supports it, a broader collection of warps. The important state belongs to the group, not to one instruction stream. A warp that reaches the barrier early is not free to continue simply because its own next instruction is available.
The barrier's scope is part of its meaning. A CTA-scoped barrier should coordinate the warps assigned to that cooperative array; a wider scope can impose a dependency across more work. The instruction is therefore not fully described by its opcode. Its identifier, its participant set, and its position relative to other barriers determine which arrivals can release which waiting warps. Leaving any of those relationships implicit is enough to turn a legal-looking sequence into a liveness failure.
That makes progress collective. A test can have no infinite loop in any individual warp and still fail to finish because the warps disagree about which barrier comes next. Conversely, a branch that leaves some threads inactive can change whether a later synchronization operation is reached with the required participants. Control flow and synchronization are therefore not independent instruction categories; they shape one another's reachability.
The diagram's hierarchy is useful because it shows where state is owned. The host launches the grid. The scheduler assigns a CTA to an SM. The warp carries the shared instruction stream, while the thread mask determines participation. A branch changes the active subsets and the SIMT bookkeeping. A barrier then applies a condition to a group of warps before work can proceed. These boundaries are the reason FuzzGPU cannot treat a GPU program as a flat sequence of independent CPU instructions.
Why the hardware state is not one simple timeline
The execution hierarchy sits on top of a collection of resources that hide latency and create additional ordering questions. The representative GPU microarchitecture in the paper contains several SMs, private level-one caches, shared memory, processing blocks, a warp scheduler, register banks, load/store units, and functional units. A CTA scheduler distributes work to the SMs; within an SM, the scheduler selects ready warps while the processing blocks decode and execute their instructions.
A scoreboard tracks pending register writes so that a dependent instruction does not read a value before the producing operation is ready. This is one of the mechanisms that lets a GPU keep many operations in flight. A load may wait on memory while a functional-unit operation from another warp continues. The warp scheduler can use that independence to hide latency. Within a warp, instructions remain in issue order, but the work of different warps can be interleaved, and results can return through different units at different times.
The scoreboard is a useful example of state ownership. It does not replace the register file or the program's architectural rules; it records which physical results are still pending so the front end can make a safe scheduling decision. The cache and memory system owns other delays, while the warp scheduler decides which ready work to present to the execution units. A differential checker that sees only the final register values loses the path through these boundaries. A checker that samples every physical event without understanding them can mistake normal latency hiding for disorder. The relevant question is always which hardware event is evidence about the program and which is only an intermediate implementation step.
The paper emphasizes a consequence that is easy to miss if we import CPU assumptions. These GPU cores use out-of-order writeback to conceal load/store and functional-unit latency. They also do not rely on a CPU-style reorder buffer to provide in-order commit and precise exceptions in the same way. A register value observed at an arbitrary clock cycle can therefore be a transient value associated with an operation that has completed locally but is not the architectural state a reference model would choose to compare.
The distinction is between the history of physical events and the program-level state that the instruction set promises. The physical design may fetch, issue, execute, and write back several instructions in an order that is good for performance. A reference model, by contrast, usually advances through an architectural sequence. If a checker compares an intermediate register file to that architectural sequence without reconstructing the relationship between events, it can report a mismatch caused by observation timing rather than by incorrect computation.
Memory introduces another form of timing dependence. A private cache, shared memory, and lower-level memory system can determine when a store becomes visible to another thread. If different warps access the same address without a synchronization rule that fixes their order, the value seen by a load may depend on propagation and arbitration. That behavior is not necessarily a violation. It may be one of several outcomes allowed by the target's memory model.
For example, let one warp read address A while two other warps store different values to A. Program order may tell us when each warp issued its own operation, but it may not impose one global visibility order on all three operations. A golden reference model that selects one serialization can be useful for deterministic cases, yet it cannot call every other legal read value wrong. The hardware's cache state and interconnect timing are part of the observed behavior, even though an ISA-level model may intentionally abstract them away. This is the point at which a test oracle needs a model of permitted relations, not just a single expected answer.
This is where the execution model separates two questions that are often collapsed. The first is whether a program can make progress under the target's control-flow and synchronization rules. The second is whether a particular value or writeback event is the only value or event that the architecture permits. FuzzGPU must eventually answer both, but they require different evidence. Completion depends on masks, paths, barriers, and resource readiness. Correctness depends on understanding which observations are architectural, which are transient, and which memory outcomes are legally variable.
Barriers provide a concrete liveness failure. Imagine warp 0 reaching barrier B1 while warp 1 reaches barrier B2. If each barrier requires the other warp to participate, warp 0 waits for warp 1 at B1 and warp 1 waits for warp 0 at B2. Neither warp is executing an infinite loop, yet the combined system is stuck in a circular dependency. A random instruction generator can create this situation even if every barrier instruction is individually valid.
FuzzGPU's paper models these dependencies with program order within each warp and a group-barrier happens-before relation across participants. The exact proof belongs to the generator design, but the execution lesson is already visible here: a synchronization instruction has meaning only in relation to the other warps that share its scope and order. A test generator that chooses barriers independently is making a global scheduling decision without the information needed to make it safely.
The same reasoning explains the paper's observations about CPU-fuzzer ports. When Cascade and DiveFuzz were adapted to form multi-thread and multi-warp GPU programs, many tests stopped early. Restricting those generators to one thread or one warp restored high median completion rates. The instruction encodings were not the whole problem; the missing relationships among masks, paths, barriers, and shared state were. Some rejected tests were legal according to the instruction set, but they were not useful probes because they could not sustain execution long enough to reach the deeper machinery.
The practical boundary is important. This chapter's model is a representation of the two open-source targets and the paper's representative GPU organization, not a claim that all GPUs share identical warp sizes, barrier scopes, cache behavior, or retirement rules. What does generalize is the dependency: wherever multiple threads share control flow and resources, a fuzzing input must preserve the target's conditions for progress, and a checker must know which part of the observed timeline is authoritative.
That dependency turns the next design question into a precise one. If FuzzGPU must exercise divergence, synchronization, and memory interaction without creating mostly dead or stalled tests, how can it construct programs that are intricate by design yet valid for the machine that will execute them? The answer begins with treating validity not as a preliminary filter, but as a way to buy more meaningful execution from every test.