Fundamental Algorithms for System Modeling, Analysis, and ...

1 Fundamental Algorithms for System Modeling, Analysis, and OptimizationEdward A. Lee, Jaijeet Roychowdhury, Sanjit A. SeshiaUC BerkeleyEECS 144/244 Fall 2010 Copyright 2010, E. A. Lee, J. Roychowdhury, S. A. Seshia, All rights reservedLec 15: Testing for Fault Detection/DiagnosisThanks to Cheng, S. Devadas, K. Keutzer for some slides2 Fault Detection and DiagnosisA fault is the adjudged or hypothesized cause of a System detection (is there a fault?) and diagnosis (where is the fault?) are key steps in System design and Circuits Faults: manufacturing defects or electrical effectsControl Systems ( chemical process plants) Faulty sensors or actuators, operator error, mechanical failuresCyber-Physical Systems ( , cars, spacecraft) Faulty sensors/actuators, mechanical failures, ..3 Fault Detection and Diagnosis..INPUTSOUTPUTSXVEO verall SystemPropagation (observability)VcActivation(controllabil ity)Component4 Observability and ControllabilityControllability A System with internal state xis called controllable if the state can be modified by changing the input to the System .

2 , for circuits: put a 0 or 1 at an arbitrary internal nodeObservability A System with internal state xis called observable if the state can be determined by observing the outputs of the System . , for circuits, observe the 0-1 value of an internal node from System Testing in ICsApply a sequence of input vectors to a circuitObserve the output response and compare the response with a precomputed or expected responseAny discrepancy is said to constitute an error, the cause of which is a physical defectFAB?absq01dclk6 Defects and Fault modelsManufacturing defects can manifest in a variety of ways: Bridging Contaminants Shorts Opens Transistors stuck -openThese need to be reduced to models: Single stuck -at-1, stuck -at-0 Multiple stuck -at-1, stuck -at-0 Delay fault models: Gate Path single- stuck -at fault model ubiquitous some use of delay fault modeling7 Defect Model: stuck -At FaultsAny input or internal wire in circuit can be stuck -at-1 or stuck -at-0 Single stuck -at-fault model: In the faulty circuit, a single line/wire is S-a-0 or S-a-1 Multiple stuck -at fault model: In the faulty circuit any subset of wires are S-a-0/S-a-1 (in any combination)abf1f2 ABCD8 Outline of TopicsBasics & TerminologySingle stuck -at faults and path sensitizationBoolean Satisfiability-based technique9 Formal Problem DefinitionGiven a combinational circuit on n variables x1, x2.

3 , xnwith m outputs f1, f2, .., fmLet g be an internal net that is stuck at 0 Then, we wish to find values of x1, x2, .., xnsuch thatg(x1, x2, .., xn) = 1and there exists some j in 1,2,..m, such thatfj(x1, x2, .., xn) takes different values depending on whether g is stuck at 0 or does the definition change for g stuck at 1 ?10 Problem: What about the Flip-Flops?Solution 1: Unroll the sequential ckt in time[Murray & Hayes, IEEE Computer, 1996]11 Solution 2: Add scan logicScan Flip-flopsCombinationalLogicadd additional state to flip-flops(15 - 20% area overhead)inputsoutputsScan-chainScan-cha in[See Murray & Hayes, IEEE Computer, 1996]12 Outline of TopicsBasics & TerminologySingle stuck -at faults and path sensitizationBoolean Satisfiability-based technique13 Single stuck -At FaultsA fault is assumed to occur only on a single = x1x2+ x2x3a s-a-1 Z = ?G s-a-1 Z = ?x1x2x3abGThis model is used because it has been found to bestatistically correlated with defect-free circuits14 Single stuck -At FaultsA fault is assumed to occur only on a single = x1x2+ x2x3a s-a-1 Z = x1 + x2x3G s-a-1 Z = x2x3x1x2x3abGThis model is used because it has been found to bestatistically correlated with defect-free circuits15 Activation and Path SensitizationIn order for an input vector X to detect a fault h s-a-D, D = 0,1 the input X must cause the signal h in the normal (fault-free) circuit to take the value activate the fault , detect hs-a-1 we first need to make h = 0.

4 How?16G3 Fault Activationh0/10/10/1hs-a-1, for hto be 0, need x2= x3= 0 ( x2x3 )G1G5fG4G2xx2x3x1x4 The condition is necessary but not sufficient. Error signal must be propagated to output(must affect the output value).17 The error signal must be propagated along some path from its origin to an outputHow to propagate the fault?G3 Fault Propagationh0/1hs-a-1, for hto be 0, need x2= x3= 0 ( x2x3 )G1G5fG4G2xx2x3x1x418 The error signal must be propagated along some path from its origin to an outputOnly one path G3, G5In order to propagate an error through AND gate G3, other input x1= 1. To propagate through G5, need G4= 0, x1+ x4G3 Fault Propagationh0/10/10/101hs-a-1, for hto be 0, need x2= x3= 0 ( x2x3 )G1G5fG4G2xx2x3x1x419 Formal Problem Definition, RevisitedGiven a combinational circuit on n variables x1, x2, .., xnwith m outputs f1, f2, .., fmLet g be an internal net that is stuck at 0 Then, we wish to find values of x1, x2.

5 , xnsuch thatg(x1, x2, .., xn) = 1and there exists some j in 1,2,..m, such thatfj(x1, x2, .., xn) takes different values depending on whether g is stuck at 0 or (Controllability)(Observability)20 Single Path Sensitization (SPS) :Specify inputs so as to generate the appropriate value (0 for s-a-1, 1 for s-a-0) at the site of the Propagate:Select a path from the site of the fault to an output and specify additional signal values to propagate the fault signal along this path to the output(error propagation). :Specify input values so as to produce the signal values specified in (2)(line justification).21 Sensitization Example h s-a-1 Activate?f1f2G6G5G4G3G1h s-a-1G2 DABCEx22 Sensitization Example h s-a-1 Activate: To generate h = 0, need A = B = C = 1 Propagate?f1f2G6G5G4G3G1hG2 DABCEx23 Sensitization Example h s-a-1To generate h = 0, need A = B = C = 1 Have a choice of propagating through G5or via G6. Propagating through G5requires G2= 1 A = D = 0 ContradictionPropagating through G6requires G4= 1 C = 1, E = valid test vector is ABCEf1f2G6G5G4G3G1hG2 DABCEx24 Line JustificationE s-a-1 E = 0C = D = 1 to propagate through propagate through G4, need G2 = G3= 1 How do we justify these values?

6 G31G4G21G1x0s-a-1 BHAFCDE25 Line Justification - 2 Attempt to line justify G2= G3= 1G3= 1 possible if A = F = 1 or B = H = 1If A = C = 1, then G2= 0. G3= 1 B = H = 1G2= 1 needs A = 0 or F = 0 Tests are A BCDE H, BCDE F HG31G4G21G1x0 BHAFCDEs-a-126 Not all faults result in failures!Existence of a fault does not change the functionality of a circuit redundant faultf = x1+ x1x2f = x1+ x2A test generation algorithm is deemed complete if it either finds a test for any fault or proves its redundancy, upon of SPS method ?d s-a-0 A = B = 1 Propagate along G3, G6 C = 1G2= G4= G5= 1 For G4= 1 either its top input = 0 or E = 0If G1= 0 fault is not activated (don t want to force G1= 0)If E = 0 (B must be 1) G5= 0 InconsistencyABxds-a-0fG2G6G3G4G5 CEG128 Completeness of SPS? - 2 Propagation along G4, G6also results in inconsistencies by symmetric argumentIs there no test?ABxds-a-0fG2G6G3G4G5 CEHow about C = E = 1?29 Multiple Path SensitizationError propagates down two paths G3, G6and G4, G6to output (G3, G4values are correlated)It s natural to work backwards (justifying) and forwards (propagating) from point of fault activation but this focuses on sensitizing a single pathAttempting to sensitize a single path will not find a test for this fault11111/010/10/11xds-a-0fG2G6G3G4G51/ 030 Note on the D-Algebra/ D-calculusNeed to be able to deal with an arbitrary error at the inputs to a gateD represents a signal which has value 1 in normal circuit, and value 0 in faulty 0/1D, D behave like Boolean variablesDDDD00D1 DDDDDD0D0031 Outline of TopicsBasics & TerminologySingle stuck -at faults and path sensitizationBoolean Satisfiability-based technique32 Another approach to ATPG (Larrabee, 1989)The ATPG problem (automatic test pattern generation)The CIRCUIT-SAT problemThe Boolean Satisfiability (SAT)

7 Problem SATCIRCUIT-SATATPG33 The ATPG problemDoes there exist a value assignment to the primary inputs which distinguishes the faulty and correct circuits ? A logic circuit A fault point A fault valueabcdefghis-a-100(1)(1)00(1)(1)11000 0001111111, asf Circuit C34 The CIRCUIT-SAT problemDoes there exist a value assignment to the primary inputs which causes the primary output to assume logic value 1 ?abcdefghi35 ATPG as a CIRCUIT-SAT problemabcdefghi1hfift = 1?ATPG C CircuitCan we find an input value in which the faulty circuit and the good circuit differ?36 The Boolean Satisfiability (SAT) problemGiven a formula, f :))()((cbacacba C1C2C3a=b=c=1(a,b,c)(C1,C2,C3) Comprised of a conjunction (AND) of clauses Defined over a set of variables, V Each clause is a disjunction (OR) of literals of the variables VExample :Example :Does there exist an assignment of Boolean values to the variables, V which sets at least one literal in each clause to 1 ?

8 37 CIRCUIT-SAT as a SAT problemA set of clauses representing the functionality of each gateA unit literal (i)clause asserting the output to be 1 abcdefghi))()((fcbfcfb ))()((hfahfha ))()((gedgegd )(i))()((ighigih 38 Solving the SAT problemNP-complete problem, yet efficient techniques exist to solve probems encountered in practiceWe will review some of these methods in the next lecture 39 Current Status on Manufacture TestPractical approach to test: use scan achieve 99%+ stuck -at coverageSingle stuck -at-fault testing for combinational logic is a ``solved problem Despite the fact that it is NP-complete After 20+ years of research Results applied to combinational-equivalence checking