PolyMiR: Polynomial Formal Verification of the MicroRV32 Processor
Open Access
- 18 December 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-6
Abstract
Formal verification techniques ensure completeness as opposed to simulation-based techniques. In general, the process of formal verification is computationally complex, and it is difficult to quantify the exact time and space complexities. Some of the recent works have shown that it is possible to achieve polynomial space and time complexities for verifying specific designs, like arithmetic circuits. However, this cannot be directly extended to complex circuits, like processors. A recent work has reported a formal verification method for the RISC-V processor with polynomial complexity, where only single-cycle instruction execution was considered and it was computation intensive. This method cannot be directly extended to multi-cycle operations, which are typical for most real processors. This paper introduces an improved data structure leading to Binary Decision Diagram (BDD) based Polynomial Formal Verification (PFV) with support for both single-cycle and multi-cycle operations. We use the MicroRV32 processor as a case study. Our method leads to significant improvement in runtime over the previous method. The entire process of verification can be carried out in polynomial space and time complexities for multi-cycle operations.Keywords
This publication has 13 references indexed in Scilit:
- Polynomial word-level verification of arithmetic circuits2021
- PolyAdd: Polynomial Formal Verification of Adder Circuits2021
- Microcode Verification – Another Piece of the Microprocessor Verification Puzzle2014
- Formal Verification of Backward Compatibility of Microcode2005
- Formal Verification of Pentium ® 4 Components with Symbolic Simulation and Inductive Invariants2005
- Proof engineering in the large: formal verification of Pentium 4 floating-point dividerInternational Journal on Software Tools for Technology Transfer, 2003
- Formal verification of an ARM processor1999
- Automatic verification of pipelined microprocessor control1994
- Efficient implementation of a BDD package1990
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986