Node Mergers in the Presence of Don't Cares
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 414-419
Abstract
SAT sweeping is the process of merging two or more functionally equivalent nodes in a circuit by selecting one of them to represent all the other equivalent nodes. This provides significant advantages in synthesis by reducing circuit size and provides additional flexibility in technology mapping, which could be crucial in post-synthesis optimizations. Furthermore, it is also critical in verification because it can reduce the complexity of the netlist to be analyzed in equivalence checking. Most algorithms available so far for this goal do not exploit observability don't cares (ODCs) for node merging since nodes equivalent up to ODCs do not form an equivalence relation. Although a few recently proposed solutions can exploit ODCs by overcoming this limitation, they constrain their analysis to just a few levels of surrounding logic to avoid prohibitive runtime. We develop an ODC-based node merging algorithm that performs efficient global ODC analysis (considering the entire netlist) through simulation and SAT. Our contributions which enable global ODC-based optimizations are: (1) a fast ODC-aware simulator and (2) an incremental verification strategy that limits computational complexity. In addition, our technique operates on arbitrarily mapped netlists, allowing for powerful post-synthesis optimizations. We show that global ODC analysis discovers on average 25% more (and up to 60%) node-merging opportunities than current state-of-the-art solutions based on local ODC analysis.Keywords
This publication has 9 references indexed in Scilit:
- Using simulation and satisfiability to compute flexibilities in Boolean networksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- SAT sweeping with local observability don't-caresProceedings of the 39th conference on Design automation - DAC '02, 2006
- SAT-Based Complete Don't-Care Computation for Network Optimization2005
- A robust algorithm for approximate compatible observability don't care (CODC) computation2004
- Verification of large synthesized designs2002
- 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
- Using SAT for combinational equivalence checking2002
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999