Hierarchical Formal Verification of Hardware
- 12 February 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 44 (9) , 3629-3642
Abstract
Scaling hardware formal verification (FV) has been an ongoing challenge due to the state space explosion problem. In this article, we introduce a bottom-up verification methodology that leverages design hierarchy by using sound abstractions at each level in the hierarchy to decompose the overall FV problem into a set of smaller, more manageable FV tasks.We use the recently proposed instruction-level abstraction (ILA) as a complete specification at each level of the design hierarchy. We then utilize ILA-based verification methods to check correctness of modules composed at that level. The ILA specification includes an interface specification for each module and interface checks for verifying correct intermodule communication. This approach enables compositional verification with the following guarantee: if each hardware component refines its ILA specification and passes the interface checks, then the register-transfer level composition refines the ILA composition. We then show how this compositional verification methodology facilitates a bottom-up hierarchical verification approach, where the specification at one level serves as the implementation at the next higher level. We demonstrate the increased scalability of our methodology through several case studies, including complex modules in two deep learning accelerators (FlexASR and NVDLA), where verification fails to complete on the flat designs.Keywords
Funding Information
- Applications Driving Architectures (ADA) Research Center, a JUMP Center co-sponsored by SRC JUMP and DARPA (3004811115 (PRIME # 2018-JU-2775))
- NSF through XPS: FULL: Hardware Software Abstractions: Addressing Specification and Verification Gaps in Accelerator-Oriented Parallelism (1628926)
- SHFm (2107138)
- DARPA POSH Program Project: Upscale: Scaling Up Formal Tools for POSH Open Source Hardware (FA8650-18-2-7854)
This publication has 34 references indexed in Scilit:
- ILAng: A Modeling and Verification Platform for SoCs Using Instruction-Level Abstractions2019
- Compositional Reasoning2018
- SVA: The Power of Assertions in SystemVerilog2015
- HOL Light: An Overview2009
- Reducibility in analysis of coordination2006
- Interface Theories for Component-Based Design2001
- Microarchitecture Verification by Compositional Model Checking2001
- A compositional rule for hardware design refinement1997
- Automatic verification of pipelined microprocessor control1994
- In Transition From Global to Modular Temporal Reasoning about Programs1985