Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
summary
The gist
Formal verification of an out-of-order multiprocessor against an in-order weak-memory ISA presents a novel approach to solving challenges arising from inter-core interleaving and intra-core…
In short
The research presents a novel formal verification of an out-of-order multiprocessor against an in-order weak-memory instruction set architecture (ISA). It solves challenges from inter-core interleaving and intra-core out-of-order execution by using a core specification that captures excess executions. This allows for unbounded verification, proving the system's correctness across multiple cores.
Key concepts
- Core Specification
- A well-designed specification that captures the essential behavior of an out-of-order core. It models all instructions as a single program order list, which simplifies resolving 'excess executions'—unintended behaviors arising from out-of-order execution—by allowing them to be dropped simply by ignoring instructions after the violating one.
- Modular Refinement
- A proof technique where related states are shown to be indistinguishable through a defined interface. The authors extended this using an 'option' encoding for preconditions, which allows them to prove complex rules while handling precondition violations by setting the internal state to None without increasing the complexity of the metatheory.
- System Inclusion
- The final step in verification that proves how individual core behaviors combine correctly into a multiprocessor system. This is achieved through three sequential steps: merging refinement, threading inclusion, and certification inclusion. It ensures that memory operations and inter-core communication are handled consistently according to the ISA.
- Excess Execution
- Unintended execution paths in an out-of-order system that violate expected coherence or ordering rules. The paper addresses two main types: excess from incoherent out-of-order loads (e.g., reading stale data) and excess from branch misspeculation, which the core specification is designed to resolve.
Terminology used across episodes
This episode discusses
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA · Paper Radio
- CCR 2.0: High-level Reasoning for Conditional Refinements
The paper
Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA · Read on arXiv
KAIST · FuriosaAI
Out-of-order multiprocessors are critical components of modern hardware, and their verification is desirable as they are difficult to correct once shipped. Existing literature simplifies and improves instruction set architectures (ISAs) for such processors, but they assume the processor correctly implements the ISA rather than proving it. We present the first formal verification of an out-of-order multiprocessor Core Impl against an in-order, weak-memory RISC-V ISA, RISC-V prom. Our central component is Core InO, an in-order one-instruction at a time core specification, enabling us to confine out-of-order reasoning to a single core. We decompose the main proof into two refinements. The core refinement proves that Core InO is a correct specification for Core Impl. The system refinement shows that RISC-V prom is a correct specification for multiple Core InO connected with shared memory, leveraging the simplicity of Core InO in the proof. All of our proofs are mechanized in Rocq, with large language model agents heavily used to automate proof writing. We synthesized Core Impl into the Bluespec hardware description language, and validated it produces the intended weak behaviors and adheres to the official RISC-V test suite.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA".
Jane: Here's the gist of the paper. Formal verification of an out-of-order multiprocessor against an in-order weak-memory ISA presents a novel approach to solving challenges arising from inter-core interleaving and intra-core out-of-order execution The authors present the first formal verification of such a system, which is significant because it addresses designs that exhibit weak outcomes not explained by sequential execution, covering multiple cores and intra-core out-of-order execution with unbounded verification The Core Verification Strategy The key idea presented is a well-designed core specification that captures the essence of excess executions in a single list of instructions This specification is used to decompose the proof into two steps: a core refinement and a system inclusion The first step, core refinement, proves a core implementation against this specification by abstracting away every microarchitectural state except those necessary to reason about excess executions and the core interface The second step, system inclusion, serializes the out-of-order memory executions and inter-core interleaving into the ISA, easily removing excess executions thanks to the core specification Taming Excess Execution The paper identifies two primary sources of excess execution that challenge formal verification: excess by incoherent out-of-order loads and excess by branch misspeculation For example, in the distinct-address case, the ISA allows an outcome where a load reads a stale initial value while another load reads a newer one, which is forbidden under coherence requirements The core specification Cores achieves this by merging all instruction information into a single program order list, allowing excess behavior to be resolved simply by dropping all instructions after the violating instruction Modular Refinement Techniques The proof relies on modular refinement, which is defined as a relation where related states are indistinguishable through the method interface and every method and rule of one module preserves this relation The authors developed a lightweight encoding for extending this framework with preconditions by lifting the specification state to option, allowing violations of preconditions to update the internal state to None This technique allows obtaining preconditions at zero additional metatheory cost by wrapping the specification state in option Mechanization and Automation The end-to-end refinement of Theorem 1, from the multiprocessor implementation to ISA, is fully mechanized in Rocq using large language model (LLM) agents as the proof workhorse The agents wrote the large majority of the mechanized proofs, with human authors designing initial specifications and invariants This automation resulted in a proof effort where LLM agents completed the system inclusion nearly autonomously, consulting humans only when a proof attempt grew outsized System Inclusion Steps The system inclusion is proven through three sequential steps: the merging refinement, the threading inclusion, and the certification inclusion The merging refinement removes request transitions and bookkeeping by ensuring that conditions under which a core made a request still hold at response time The threading inclusion proves that the execution is reproduced by showing trace inclusion directly instead of refinement The certification inclusion restores the certification requirement by reusing proofs from Pulte et al.
24: Detailed Component Specifications The paper details the specifications for several complex modules, including the Reorder Buffer (ROB), Arithmetic Unit (ALU), Load-Store Queue (LSQ), and Store Buffer (StB) The LSQ specification is particularly intricate, managing in-flight memory operations with a per-address load bag and a list of retired writes The simulation relation for the folding refinement uses two position maps to translate instruction indices between the memory unit and the core specification The proof for LSQ-DeqSt keeps a committed store in the implementation LSQ while the specification dequeues it into retire The simulation for eager retirement uses an eager closure function to compute the retireable prefix of Cores f's flight The proof for MemUnit relies on an invariant that the specification’s retire equals the StB’s appended with the LSQ The simulation for Corei to Coresf uses a translation function tau to relate instruction indices between MemUnit and Cores The proof for System Inclusion details how the implementation coalesces buffered writes into a single memory write, agreeing observably with TopMod The simulation for TopMod to ISA includes the threading inclusion which resolves inter-core interleaving and residual out-of-order execution Future Extensions Future work plans include extending the design to incorporate features commonly found in out-of-order processors, such as register renaming and superscalar execution The authors also plan to synthesize their design and evaluate its performance against unverified cores Additionally, they intend to add more features to the core, such as exceptions and virtualization, which will require extending the ISA The work provides a new lower bound for existing literature on weak memory semantics The paper also discusses compiler correctness proofs and program logics that bridge until software weak memory models Related Work Context Existing verification methods are categorized into model checking processors, which bound guarantees to fixed parameters, and formally verified processors, which are limited to single cores or sequential consistency semantics The authors position their work as a new lower bound for existing literature on weak memory semantics Their core specification is simpler and more precise than Pulte et al.'s Cores because it models instructions as a single list rather than trees, making it easier for usage in verifications The work builds upon prior research by providing a new lower bound for existing literature on weak memory semantics The authors show that their core specification Cores shares the philosophy of Pulte et al.
Paper summary: Tom: So we’ve seen that the paper, "Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA," is tackling two main hurdles: intercore interleaving and intra-core out of order execution.
Jane: The core claim is that they present the first formal verification for this specific combination, which is significant because it addresses designs with weak outcomes that sequential execution doesn't explain, covering multiple cores and out of order execution within a single core.
Lu: They use a well designed core specification as their key idea to decompose the proof into two steps: a core refinement and a system inclusion.
Meng: The goal of the system inclusion step is essentially to serialize those out-of-order memory executions and intercore interleaving into the instruction set architecture itself, allowing excess execution to be easily removed by that core specification.
Tom: They specifically identify two major sources of this excess execution that challenge verification: excess by incoherent out-of-order loads and excess by branch misspeculation.
Jane: An example they give is the distinct address case where the ISA lets a load read a stale initial value while another load reads a newer one, which violates coherence requirements.
Lu: The core specification Cores solves this by merging all instruction information into a single program order list, meaning excess behavior is resolved simply by dropping instructions after the violating instruction.
Meng: So they are essentially saying that if things fire out of order in a way that breaks rules, you can just cut off the rest of the sequence to fix it.
Tom: They also rely on modular refinement techniques, which lets them extend their framework with preconditions by lifting the specification state to option without adding extra metatheory cost.
Jane: That sounds like they’re making sure that even if a precondition isn't met, the system can gracefully update its internal state to none instead of crashing the proof.
Lu: The entire end-to-end refinement process is mechanized in Rocq using large language model agents as the proof workhorse, which means human authors design the initial specs and invariants.
Meng: It sounds like this automation allows them to handle a massive amount of proof work that would otherwise be impossible for humans alone.
Conclusion: Tom: So we’ve walked through how this paper tackles the verification challenge for out-of-order multiprocessors with weak memory models. The authors are Janggun Lee and Jeehoon Kang, from KAIST and FuriosaAI, respectively.
Jane: Essentially, they’re saying they found a way to formally verify these complex designs by creating a core specification that handles instruction ordering as a single list instead of a tree structure.
Lu: That simplification is what makes their core specification Cores easier to use in verification because it allows them to model
More episodes
- 2403.18642-Collective schedules: axioms and algorithms
- 2411.16152-Optimizing Winograd Convolution on ARMv8 processors
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback