TY - JOUR
T1 - Satisfiability-based automatic test program generation and design for testability for microprocessors
AU - Lingappan, Loganathan
AU - Jha, Niraj K.
N1 - Funding Information:
Manuscript received July 10, 2006; revised February 18, 2007. This work was supported by Semiconductor Research Corporation under Contract 2002-TJ-1039. L. Lingappan is with the NVIDIA Corporation, Santa Clara, CA 95050 USA. N. K. Jha is with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: [email protected]). Digital Object Identifier 10.1109/TVLSI.2007.896908
PY - 2007/5
Y1 - 2007/5
N2 - In this paper, we present a satisfiability (SAT)-based framework for automatically generating test programs that target gate-level stuck-at faults in microprocessors. The microarchitectural description of a processor is first translated into a unified register-transfer level (RTL) circuit description, called assignment decision diagram (ADD), for test analysis. Test generation involves extraction of justification/propagation paths in the unified circuit representation from an embedded module's input-output (I/O) ports to primary I/O ports, abstraction of RTL modules in the justification/propagation paths, and translation of these paths into Boolean clauses in conjunctive normal form (CNF). Additional clauses are added that capture precomputed test vectors/responses at the embedded module's I/O ports. An SAT solver is then invoked to find valid paths that justify the precomputed vectors to primary input ports and propagate the good/faulty responses to primary output ports. Since the ADD is derived directly from a microarchitectural description, the generated test sequences correspond to a test program. If a given SAT instance is not satisfiable, then Boolean implications (also known as the unsatisfiable segment) that are responsible for unsatisfiability are efficiently and accurately identified. We show that adding design for testability (DFT) elements is equivalent to modifying these clauses such that the unsatisfiable segment becomes satisfiable. Test generation at the RTL also imposes a large number of initial conditions that need to be satisfied for successful detection of targeted stuck-at faults. We demonstrate that application of the Boolean constraint propagation (BCP) engine in SAT solvers propagates these conditions leading to significant pruning of the sequential search space which in turn leads to a reduction in test generation time. Experimental results demonstrate an 11.1X speedup in test generation time for test generation at the RTL over a state-of-the-art gate-level sequential generator called MIX, at comparable fault coverages. An unsatisifiability-based DFT approach at the RTL improves this fault coverage to near 100% and incurs very low area overhead (3.1%). Unlike previous approaches that either generate a test program consisting of random instruction sequences or assume the existence of test program templates, the proposed approach constructs test programs in a deterministic fashion from the microarchitectural description of a processor.
AB - In this paper, we present a satisfiability (SAT)-based framework for automatically generating test programs that target gate-level stuck-at faults in microprocessors. The microarchitectural description of a processor is first translated into a unified register-transfer level (RTL) circuit description, called assignment decision diagram (ADD), for test analysis. Test generation involves extraction of justification/propagation paths in the unified circuit representation from an embedded module's input-output (I/O) ports to primary I/O ports, abstraction of RTL modules in the justification/propagation paths, and translation of these paths into Boolean clauses in conjunctive normal form (CNF). Additional clauses are added that capture precomputed test vectors/responses at the embedded module's I/O ports. An SAT solver is then invoked to find valid paths that justify the precomputed vectors to primary input ports and propagate the good/faulty responses to primary output ports. Since the ADD is derived directly from a microarchitectural description, the generated test sequences correspond to a test program. If a given SAT instance is not satisfiable, then Boolean implications (also known as the unsatisfiable segment) that are responsible for unsatisfiability are efficiently and accurately identified. We show that adding design for testability (DFT) elements is equivalent to modifying these clauses such that the unsatisfiable segment becomes satisfiable. Test generation at the RTL also imposes a large number of initial conditions that need to be satisfied for successful detection of targeted stuck-at faults. We demonstrate that application of the Boolean constraint propagation (BCP) engine in SAT solvers propagates these conditions leading to significant pruning of the sequential search space which in turn leads to a reduction in test generation time. Experimental results demonstrate an 11.1X speedup in test generation time for test generation at the RTL over a state-of-the-art gate-level sequential generator called MIX, at comparable fault coverages. An unsatisifiability-based DFT approach at the RTL improves this fault coverage to near 100% and incurs very low area overhead (3.1%). Unlike previous approaches that either generate a test program consisting of random instruction sequences or assume the existence of test program templates, the proposed approach constructs test programs in a deterministic fashion from the microarchitectural description of a processor.
KW - Design for testability
KW - Microprocessor
KW - Satisfiability
KW - Test generation
KW - Test program
UR - http://www.scopus.com/inward/record.url?scp=34249786276&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34249786276&partnerID=8YFLogxK
U2 - 10.1109/TVLSI.2007.896908
DO - 10.1109/TVLSI.2007.896908
M3 - Article
AN - SCOPUS:34249786276
SN - 1063-8210
VL - 15
SP - 518
EP - 530
JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
IS - 5
ER -