2000 · 30 citations · 12 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsDesign AutomationFault-tolerant ComputingDigital Logic DesignTiming AnalysisBoolean SatisfiabilityBoolean Satisfiability ProblemCircuit SatisfiabilityConstraintsDelay Fault TestingLogic VerificationSatisfiabilitySatisfiability Problem
The Boolean satisfiability problem (SAT) has various applications in electronic design automation (EDA) fields such as testing, timing analysis and logic verification. SAT has been typically applied to EDA as follows: 1) formulation of the given problem as a SAT instance 2) solution of the SAT instance. In this paper, we present a method to simultaneously solve several closely related SAT instances using incremental satisfiability (ISAT). In ISAT, the decision sequence made for a “prefix ” function is used to solve another set of functions which have a number of new constraints (extensions) added to the prefix function. Our experiments show that we can achieve significant gains in total runtime when we use this methodology as opposed to resetting the decision sequences and solving each instance from scratch. Application of ISAT to delay fault testing is
12
GRASP - A New Search Algorithm for Satisfiability
1996 · 860 citations
Using CSP look-back techniques to solve real-world SAT instances
Roberto J. Bayardo, Robert Schrag · 1997 · 598 citations
Delay testing for non-robust untestable circuits
Kwang‐Ting Cheng, H.-C. Chen · 2002 · 159 citations
Engineering, Computer Engineering, Electrical Engineering +8