Search papers, labs, and topics across Lattice.
This paper presents the first formal verification of an out-of-order multiprocessor against an in-order weak-memory ISA, addressing the challenges posed by unrestricted inter-core interleaving and intra-core out-of-order execution. The authors introduce a novel core specification that encapsulates excess executions in a streamlined instruction list, enabling a two-step proof process that includes core refinement and system inclusion. Mechanized in Rocq and aided by large language model agents, the verification process effectively manages complex microarchitectural states while ensuring compliance with the ISA.
The verification framework reveals that excess out-of-order executions can be systematically managed, paving the way for robust multiprocessor designs.
Out-of-order multiprocessor is a critical piece of modern hardware, and their verification must solve the following challenges. First, inter-core interleaving, in which the order their reads and writes reach shared memory is unrestricted. Second, intra-core out-of-order execution, in which instructions fire out of program order. The combination of the two yields weak outcomes, which no sequential execution explains, and modern ISA allows such behaviors to account for them. However, the microarchitecture even exhibits excess out-of-order executions, temporarily entering states forbidden by the ISA. While discarded later, such states complicate reasoning about the core in full-system verification. Prior works verify a range of processor designs, while none have performed unbounded verification for out-of-order multiprocessor exhibiting such weak outcomes. We present the first formal verification of an out-of-order multiprocessor against an in-order, weak-memory ISA. Our key idea is a well-designed core specification, which captures the essence of excess executions in a single list of instructions. Building upon this, we decompose the proof into two steps. The first is a core refinement, proving a core implementation against this specification, abstracting away every microarchitectural state except those necessary to reason about excess executions and the core interface. The second is a system inclusion, serializing the out-of-order memory executions and inter-core interleaving into the ISA, easily removing excess executions thanks to the core specification. All of our proofs are mechanized in Rocq, heavily utilizing large language model (LLM) agents to write proofs automatically.
