Application of DAG-Aware MIG Rewriting Technique in Logic Synthesis and Verification
Date Issued
2016
Date
2016
Author(s)
Wang, Li-Wei
Abstract
A Majority-Inverter Graph (MIG) is a recently introduced logic representation form which manipulates logic by using only 3-input majority function (MAJ) and inversion function (INV). Its algebraic and Boolean properties enables efficient logic optimizations. In particular, MIG algorithms obtained significantly superior synthesis results as compared to the state-of-the-art approaches based on AND-inverter graphs and commercial tools. In this thesis, we integrate the DAG-aware rewriting technique, a fast greedy algorithm for circuit compression, into MIG and apply it not only in the logic synthesis but also verification. Experimental results on logic optimization show that heavily-optimized MIGs can be further reduced by 20.4% of network size while depth preserved. Experimental results on datapath verification also show the effectiveness of our algorithm. With our MIG rewriting applied, datapath analysis quality can be improved with the ratio 3.16. Runtime for equivalence checking can also be effectively reduced.
Subjects
Majority-Inverter Graph
Logic Synthesis
Datapath Verification
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R03943084-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):dd9fe2b8abbfbf62d9d8f1252fd5d6dd