Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design · 2006 · 130 citations · 30 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationCombinational Logic DescriptionComputational ComplexityDigital Logic DesignEquivalence CheckingLogic SynthesisVerificationBoolean SatisfiabilityBoolean Satisfiability ProblemCircuit Equivalence CheckingCombinational Equivalence CheckingCombinational Logic SynthesisDecision-making HeuristicsSatisfiabilityTopological Order
The paper explores several ways to improve the speed and capacity of combinational equivalence checking based on Boolean satisfiability (SAT). State-of-the-art methods use simulation and BDD/SAT sweeping on the input side (i.e. proving equivalence of some internal nodes in a topological order), interleaved with attempts to run SAT on the output (i.e. proving equivalence of the output to constant 0). This paper improves on this method by (a) using more intelligent simulation, (b) using CNF-based SAT with circuit-based decision heuristics, and (c) interleaving SAT with low-effort logic synthesis. Experimental results on public and industrial benchmarks demonstrate substantial reductions in runtime, compared to the current methods. In several cases, the new solver succeeded in solving previously unsolved problems.
30
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
SIS : A System for Sequential Circuit Synthesis
Ellen Sentovich · 1992 · 1.9K citations