Formal Verification of Structurally Complex Multipliers

✍ Scribed by Alireza Mahzoon, Daniel Große, Rolf Drechsler

• Publisher: Springer
• Year: 2023
• Tongue: English
• Leaves: 134
• Category: Library

✦ Synopsis

This book addresses the challenging tasks of verifying and debugging structurally complex multipliers. In the area of verification, the authors first investigate the challenges of Symbolic Computer Algebra (SCA)-based verification, when it comes to proving the correctness of multipliers. They then describe three techniques to improve and extend SCA: vanishing monomials removal, reverse engineering, and dynamic backward rewriting. This enables readers to verify a wide variety of multipliers, including highly complex and optimized industrial benchmarks. The authors also describe a complete debugging flow, including bug localization and fixing, to find the location of bugs in structurally complex multipliers and make corrections.

✦ Table of Contents

Preface
Acknowledgements
Contents
1 Introduction
1.1 Overview
1.2 Outline
2 Background
2.1 Circuit Modeling
2.1.1 Gate-Level Netlist
2.1.2 AND-Inverter Graph
2.2 Integer Multiplier
2.2.1 Structure
2.3 Formal Verification of Multipliers
2.3.1 Equivalence Checking Using BDDs
2.3.2 Equivalence Checking Using SAT
2.3.3 Binary Moment Diagram
2.4 Term Rewriting
2.5 Formal Verification Using SCA
2.5.1 Definitions
2.5.2 Theory of Gröbner Basis
2.5.3 SCA-Based Verification
2.5.4 State-of-the-art of SCA-Based Verification Methods
3 Challenges of SCA-Based Verification
3.1 Introduction
3.2 Verification of Structurally Simple Multipliers
3.2.1 Definition of Structurally Simple Multipliers
3.2.2 Experimental Results
3.2.3 Discussion
3.3 Verification of Structurally Complex Multipliers
3.3.1 Definition of Structurally Complex Multipliers
3.3.1.1 Sophisticated Multiplication Algorithms
3.3.1.2 Optimization
3.3.2 Experimental Results
3.3.3 Discussion
3.4 Overcoming the Challenges
3.5 Conclusion
4 Local Vanishing Monomials Removal
4.1 Introduction
4.2 Vanishing Monomials Example
4.3 Basic Theory of Vanishing Monomials
4.4 Vanishing Monomials and Multiplier Architecture
4.5 Removing Vanishing Monomials
4.5.1 Converging Node Cone Detection
4.5.2 Local Removal of Vanishing Monomials
4.6 Conclusion
5 Reverse Engineering
5.1 Introduction
5.2 Atomic Blocks
5.3 Advantages of Reverse Engineering in SCA
5.3.1 Detecting Converging Node Cones
5.3.2 Limiting Search Space for Vanishing Removal
5.3.3 Speeding up Global Backward Rewriting
5.4 Proposed Reverse Engineering Technique
5.4.1 Atomic Blocks Library
5.4.2 Atomic Blocks Identification
5.5 Conclusion
6 Dynamic Backward Rewriting
6.1 Introduction
6.2 Multiplier Optimization
6.2.1 Multiplier Structure After Optimization
6.2.2 Backward Rewriting for Optimized Multipliers
6.3 Proposed Dynamic Backward Rewriting Technique
6.3.1 Definitions
6.3.2 Algorithm
6.4 Conclusion
7 SCA-Based Verifier RevSCA-2.0
7.1 Introduction
7.2 Top-Level Overview
7.3 Implementation
7.3.1 Polynomial Data Structures
7.3.2 Reverse Engineering
7.4 Multiplier Generator
7.4.1 Overview and Data Structures
7.4.2 Generation of Multipliers
7.5 Experimental Results
7.5.1 General Details
7.5.2 Clean Multipliers
7.5.3 Dirty Optimized Multipliers
7.6 Conclusion
8 Debugging
8.1 Introduction
8.2 Fault Model
8.3 Limitations of SCA-Based Debugging
8.3.1 Vanishing Monomials in Remainder
8.3.2 Blow-up During the Verification of Buggy Circuits
8.4 Proposed Debugging Method
8.4.1 Overview
8.4.2 Verification
8.4.3 Localization
8.4.3.1 Extracting Initial Suspicious Gates
8.4.3.2 Generating Test-Vectors
8.4.3.3 Insertion of XORs
8.4.3.4 Refining Suspicious Gates
8.4.4 Fixing
8.5 Experimental Results
8.6 Conclusion
9 Conclusion and Outlook
9.1 Conclusion
9.2 Outlook
A SCA-Verification Website
References
Index