Abstract
In the VAMP (verified architecture microprocessor) project, we have designed, functionally verified, and synthesized a processor with a full DLX instruction set, delayed branch, Tomasulo scheduler, maskable nested precise interrupts, pipelined fully IEEE-compatible dual-precision floating-point unit with variable latency, and separate instruction and data caches. The verification was carried out in the theorem proving system PVS. The processor has been implemented on a Xilinx FPGA.
Introduction
Microprocessor verification has historically faced a "complexity wall." To maintain formal proof manageability, researchers often relied on significant abstractions, such as simplified instruction sets, infinite resources (e.g., infinite tags for instruction tracking), or component isolation. The VAMP project addresses these limitations by verifying a system that includes complex real-world features like byte-level memory access, precise nested interrupts, and a coherent memory system with split caches, all within a synthesizable design.
System Architecture
The VAMP processor is a complex out-of-order machine implementing the DLX Instruction Set Architecture (ISA). Its design incorporates a Tomasulo scheduler to manage instruction execution across multiple functional units, including a pipelined, IEEE 754-compliant floating-point unit (FPU).
Verification Methodology
The verification was conducted using the Prototype Verification System (PVS). The team employed several innovative strategies to bridge the gap between abstract architectural specifications and gate-level implementation:
- Scheduling Functions: Mathematical functions were used to map out-of-order hardware cycles and pipeline stages back to a sequential instruction sequence.
- Hierarchical Memory Modeling: The processor was first verified against an ideal dual-ported memory, followed by a separate proof that the actual split-cache and burst-mode bus protocol system behaves identically to that ideal model.
- Formal Synthesis: Hardware descriptions were written directly in PVS and translated into synthesizable Verilog HDL using a custom
pvs2hdltool. - Uninterpreted Functions: Functional units were initially modeled as "black boxes" to simplify the scheduler proof, then later instantiated with verified logic for the FPU and ALU.
One critical aspect of the verification involved the "PC environment," which manages program counters and handles the complexities of delayed branches and precise interrupts.
Key Insights and Results
The VAMP project yielded several significant findings:
- Integration Complexity: Integrating verified components (like the FPU and scheduler) required an entire person-year, highlighting that interfaces are a primary source of subtle bugs.
- Standard Compliance: Verification against the IEEE 754 standard revealed that commercial hardware, such as the Pentium II, deviated from the standard in specific edge cases involving denormal numbers.
- Finite Resource Proofs: The authors proved that the finite tags used in physical hardware are logically equivalent to the infinite tags used in theoretical models, provided tag reuse is correctly managed.
In terms of scale, the VAMP processor occupies approximately 18,000 slices on a Xilinx FPGA (roughly 1.5 million gates). The verification effort spanned 8 person-years, involving 2,548 lemmas and over 88,000 proof steps.
Conclusion and Future Work
The VAMP project demonstrates that "no-compromise" formal verification of realistic, synthesizable hardware is achievable. However, limitations remain, such as the current lack of a store buffer and Memory Management Unit (MMU). Future efforts will focus on improving memory performance and exploring the combination of theorem proving with automated model checking to reduce the significant manual effort required for such large-scale formal proofs.
Summary updated