Automated Design Debugging With Maximum Satisfiability
- 18 October 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 29 (11) , 1804-1817
Abstract
As contemporary very large scale integration designs grow in complexity, design debugging has rapidly established itself as one of the largest bottlenecks in the design cycle today. Automated debug solutions such as those based on Boolean satisfiability (SAT) enable engineers to reduce the debug effort by localizing possible error sources in the design. Unfortunately, adaptation of these techniques to industrial designs is still limited by the performance and capacity of the underlying engines. This paper presents a novel formulation of the debugging problem using MaxSAT to improve the performance and applicability of automated debuggers. Our technique not only identifies errors in the design but also indicates when the bug is excited in the error trace. MaxSAT allows for a simpler formulation of the debugging problem, reducing the problem size by 80% compared to a conventional SAT-based technique. Empirical results demonstrate the effectiveness of the proposed formulation as run-time improvements of 4.5 × are observed on average. This paper introduces two performance improvements to further reduce the time required to find all error sources within the design by an order of magnitude.Keywords
This publication has 22 references indexed in Scilit:
- Scaling VLSI design debugging with interpolation2009
- Optimal trace compaction with property preservation2009
- Spatial and temporal design debug using partial MaxSAT2009
- Evaluation of Cardinality Constraints on SMT-Based Debugging2009
- RTL Error Diagnosis Using a Word-Level SAT-Solver2008
- Using unsatisfiable cores to debug multiple design errors2008
- Improved Design Debugging Using Maximum Satisfiability2007
- Abstraction and Refinement Techniques in Automated Design Debugging2007
- Post-verification debugging of hierarchical designs2005
- Simulation-based bug trace minimization with BMC-based refinement2005