Decision-Based Interpolation Generation Algorithm:A Novel Boolean Circuit Resynthesis Technique
Date Issued
2009
Date
2009
Author(s)
Hsu, Chih-Jen
Abstract
Boolean circuit manipulation is one of the most important techniques generally used in the design automation. To extend it for future design paradigms, we study two of the most important Boolean circuit rewriting techniques, redundancy addition and removal (RAR) and functional decomposition, and explore the possibility of unifying these two techniques on a unified Boolean circuit optimization platform. From problem formulation, theoretical analysis, to the comparison of pros and cons in the related algorithms, such unification exploration enlights us several interesting observations and conclusions in the technique of circuit rewriting. The first is a claim that constraint deduction in RAR is a mechanism equivalent to perform constraint solving and explore Craig interpolation. The second is a novel algorithm that embeds the Craig interpolant generation in SAT solving without constructing resolution graph and thus serves as a white-box technique to increase the controllability, flexibility, and capability in optimization. The third is an integrated algorithm, a framework for circuit resubstitution with the novel interplant constructing algorithm. The experimental results show that our algorithm has the advantages over the prior interpolant generation techniques in both memory usage and interpolation circuit size.
Subjects
Circuit rewriting
Redundancy addition and removal (RAR)
functional decomposition
Boolean Satisfiability (SAT)
Craig interpolation
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96943073-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):9e4f03ad0af0049ced75807ec2094cca