SAT sweeping with local observability don't-cares

Qi Zhu*, Nathan Kitchen, Andreas Kuehlmann, Alberto Sangiovanni-Vincentelli

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

58 Scopus citations

Abstract

SAT sweeping is a method for simplifying an shape 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 Booleanreasoning 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 effort.

Original languageEnglish (US)
Title of host publication2006 43rd ACM/IEEE Design Automation Conference, DAC'06
Pages229-234
Number of pages6
DOIs
StatePublished - Dec 1 2006

Keywords

  • And/inverter graphs
  • Observability
  • SAT sweeping

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'SAT sweeping with local observability don't-cares'. Together they form a unique fingerprint.

  • Cite this

    Zhu, Q., Kitchen, N., Kuehlmann, A., & Sangiovanni-Vincentelli, A. (2006). SAT sweeping with local observability don't-cares. In 2006 43rd ACM/IEEE Design Automation Conference, DAC'06 (pp. 229-234) https://doi.org/10.1145/1146909.1146970