SAT sweeping with local observability don't-cares
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the 39th conference on Design automation - DAC '02
- No. 0738100X,p. 229-234
Abstract
SAT sweeping is a method for simplifying an AND/inverter graph (AIG) by systematically merging graph vertices from the inputs towards the outputs using a combination of structural hashing, simulation, and SAT queries. Due to its robustness and efficiency, SAT sweeping provides a solid algorithm for Boolean reasoning in functional verification and logic synthesis. In previous work, SAT sweeping merges two vertices only if they are functionally equivalent. In this paper we present a significant extension of the SAT-sweeping algorithm that exploits local observability don't-cares (ODCs) to increase the number of vertices merged. We use a novel technique to bound the use of ODCs and thus the computational effort to find them, while still finding a large fraction of them. Our reported results based on a set of industrial benchmark circuits demonstrate that ODC-based SAT sweeping results in significantly more graph simplification with great benefit for Boolean reasoning with a moderate increase in computational effortKeywords
This publication has 15 references indexed in Scilit:
- Early research experience with OpenAccess gear2005
- Dynamic transition relation simplification for bounded property checking2005
- Verification of large synthesized designs2002
- HANNIBAL: An efficient tool for logic verification based on recursive learning2002
- Robust Boolean reasoning for equivalence checking and functional property verificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002
- The use of observability and external don't cares for the simplification of multi-level networks2002
- Compatible observability don't cares revisited2002
- Using SAT for combinational equivalence checking2002
- Logic optimization and equivalence checking by implication analysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Multi-level logic simplification using don't cares and filters1989