When the Oracle Cannot Trust Lockstep

FuzzGPU's second design problem begins after a structured program has finally reached deep GPU execution. This chapter focuses on how the framework decides whether a device-under-test result is wrong when writebacks arrive out of order, barriers make progress depend on several warps, and memory operations can have more than one legal outcome. The useful judgment is not “did the hardware and reference model produce identical events?” but “did the observed execution violate a rule that applies to this target?”

Why lockstep fails at the boundary

Differential testing compares a device under test, or DUT, with a golden reference model, or GRM. The appeal is straightforward: run the same program in both places and look for a difference. For a sequential processor, a checker can often advance the reference model as hardware instructions commit. That lockstep picture becomes unreliable when the hardware's physical event order is not the program's architectural order.

FuzzGPU's generator has already made this problem visible. Different warps can be ready at different times. A load can wait on a cache while an arithmetic operation proceeds. A barrier can stop one warp until other participants arrive. The GPU can then write back results out of order while preserving the per-warp issue order that gives the program its architectural meaning. If a checker compares each writeback as soon as it appears, it may compare the right value with the wrong point in the reference execution.

The error is not merely a timing inconvenience. A GPU core can lack the CPU-style reorder buffer and precise in-order commit behavior that would make an intermediate register file an obvious architectural checkpoint. A register value visible on a cycle boundary may be a transient consequence of latency hiding. Comparing it directly with a GRM that has advanced through a sequential instruction stream can create a false mismatch even when the design is behaving within its intended execution rules.

Synchronization creates a second failure in lockstep. Consider two warps that meet at a shared barrier. In the DUT, the first warp reaches the barrier and is marked inactive while it waits. When the second warp arrives, the hardware can release both. A GRM that simply steps the first warp past the barrier before it has observed the second warp's arrival may construct a different state. When the second arrival is processed, the model is no longer at the same synchronization point. The resulting mismatch is an artifact of the checker’s schedule, not evidence that the DUT violated the barrier.

FuzzGPU repairs these two ordering problems separately. At issue time, the harness assigns each instruction a globally unique identifier and carries that identifier into the writeback trace. Each writeback records enough context to identify the program event: its program counter, thread mask, destination register, and written value. The harness then maintains a completion queue for each warp. An instruction may complete physically out of order, but the GRM advances only when the head event in the relevant queue is complete.

This does not pretend that all warps form one universal sequence. The queues preserve the order that matters inside each warp while allowing the hardware to overlap work across warps.