1ECE 269Krish Chakrabarty1ECE 269VLSI System TestingKrish ChakrabartyLecture 9:Test Generation: Part 1ECE 269Krish Chakrabarty2Introduction• Classification of test generation methods• Fault table analysis• Boolean difference method• Propagation, implication and justification procedures• D-algorithm • 9-V algorithm (multiple path sensitization)2ECE 269Krish Chakrabarty3General Approaches• Systematic (algorithmic)– Fault table analysis– Boolean difference method– Fault-oriented methods (D-algorithm, PODEM)– Fault-independent methods (critical path tracing)• Exhaustive/pseudoexhaustive• Random/pseudorandomECE 269Krish Chakrabarty4Fault Table Analysis• Determine fault table via simulation and solve covering problem• Covering problems are NP-complete• Computationally infeasible2-input OR gateab00 x x x01 x x10 x x11 xa/0 a/1 b/0 b/1 z/0 z/1FaultazbTest3ECE 269Krish Chakrabarty5Fault-Oriented ATPGProcedureGenerate_Tests()beginrepeatbeginSelect uncovered fault fGenerate test for fEvaluate current fault coverageenduntilfault coverage > limit, or time runs outendECE 269Krish Chakrabarty6Boolean DifferenceThe Boolean difference of F(x1, x2 , x3,…, xn) with respect to xiis givenby∂F∂xi= F(x1, x2 ,…,1, x3,…, xn) ⊕F(x1, x2 ,…,0, x3,…, xn) A test pattern for xi/0 is an input combination that makes ∂F∂xi= 1 A test pattern for xi/1 is an input combination that makes ∂F∂xi= 1 Cofactor w.r.t. xiCofactor w.r.t. xixixiBoolean difference provides input combination for sensitized path4ECE 269Krish Chakrabarty7Boolean DifferencebacdefghijkTo find a test for a/0 or a/1, determine the Boolean difference of output z with respect to a:z∂z∂a= ?How to handle internal faults, e.g. j/0?ECE 269Krish Chakrabarty8Key Terminology•Backtrace: move a goal value backwards in a circuit to a primary input•Backtrack: return to a previous decision point in an algorithm and make an alternative decision•D-frontier: Set of gates closest to primary output with D or D on some input•Implication: Determine unique signal values that are forced by signal values already assigned•Justification: Determine values to unspecified inputs of gates whose outputs are specified (backward)•Propagation(D-drive): Determine path values needed to propagate an error signal to a primary output (forward)5ECE 269Krish Chakrabarty9Testing Fanout-Free Circuits• No (reconvergent) fanout– Propagation path from any line is unique– Each line justification problem is independent of all othersTest generation for line l/vin a fanout-free circuitbeginset all values to X (unknown)Justify(l,v)if v= 0 then Propagate(l,D)elsePropagate(l,D)endECE 269Krish Chakrabarty10Testing Fanout-Free Circuitserrerr11lError propagation:Propagate(l,err)/* erris D or D */beginset lto errif lis PO then returnk= the fanout gate of lc= controlling value of ki = inversion of kfor every input jof kother than lJustify(j,c)Propagate(k,err⊕i)end6ECE 269Krish Chakrabarty11Testing Fanout-Free Circuits11lLine JustificationJustify(l,val)beginset lto valif lis PI then return/* l is a gate (output) */c= controlling value of li = inversion of linval = val⊕iif(inval= c)then for everyinput jof lJustify(j,inval)elsebeginSelect one input (j) of lJustify(j,inval)end101lXX0ECE 269Krish Chakrabarty12Functional vs Structural Testing• Functional ATPG – generate complete set of tests for circuit input-output combinations– 129 inputs, 65 outputs:–2129patterns– Using 1 GHz ATE, would take 2.15 x 1022 years• Structural test:– No redundant adder hardware, 64 bit slices– Each with 27 faults (using fault equivalence)– At most 64 x 27 = 1728 faults (tests)– Takes 0.000001728 s on 1 GHz ATE• Designer gives small set of functional tests – augment with structural tests to boost coverage to 98+%7ECE 269Krish Chakrabarty13Algorithm Completeness• Definition: Algorithm is completeif it ultimately can search entire binary decision tree, as needed, to generate a test•Untestable fault– no test for it even after entire tree searched• Combinational circuits only – untestable faults are redundant, showing the presence of unnecessary hardwareECE 269Krish Chakrabarty14D-AlgorithmbacdezbABCEFGHB/1Decision Implication CommentB = D E = D, A = 0, a = 0 Activate faultb = 1 C = D Propagate via CF = 0 z = D End of D-driveH = 0 e = 0 Justify Fc = 0 (1) Justify ATest: abce = 01008ECE 269Krish Chakrabarty15D-AlgorithmbacdezbABCEFGHB/1Decision Implication CommentB = D E = D, A = 0, a = 0 Activate faultH = 1 F = D Propagate via FC = 0 z = D End of D-driveb = 0 e = 0 Justify Cc = 0 or e = 0 Justify ATest: abce = 0000ECE 269Krish Chakrabarty16D-AlgorithmbacdezDecision Implication ActionE = D, c = 0 i = D, f =1, h = 0 Activate fault, propagate via ij = k = 0 z = D End of D-drived = 1, b = 1 g = 0, e = 0 Justify j = 0, k = 0c = 0, d = 0 i = j = D propagate through i andjSingle path sensitizationdoes not always work!Fault e/0fghijkContradiction(Backtrack)9ECE 269Krish Chakrabarty17Comments on the D-Algorithm• Based on propagation (primary procedure), justification and implication• In complete form, guarantees test generation but may require multiple path sensitization (computationally expensive)• Practical restrictions:– Single path sensitization only– Limits placed on backtracking time (aborted faults)ECE 269Krish Chakrabarty189-V Algorithm• Nine logic values, specified as good/bad pairs: 1/1, 0/0, 1/0, 0/1, u/u, 1/u, 0/u, u/0, u/1• Example of logic operations: D.X = 1/0.u/u = u/0, i.e. provides more information than the X outcome for 5-valued algebra• Reduces backtracking– When there are k possible paths for error propagation, D-algorithm may try all 2k-1 combinations of paths– 9-V enumerates only k ways of propagation10ECE 269Krish Chakrabarty19Path Sensitization1Fault Sensitization2Fault Propagation3Line JustificationECE 269Krish Chakrabarty20Path Sensitization!Try path f –h –k –L blocked atj, since there is no way to justify the 1 oni11110000DDDDDDDD111111111111DDDDDDDDDDDD11ECE 269Krish Chakrabarty21Path Sensitization!Try simultaneous paths f –h –k –Landg –i –j –k –Lblocked at kbecause D-frontier(chain of Dor D) disappears1111DDDDDDDDDDDDDDDDDDDD111111111111ECE 269Krish Chakrabarty22Path Sensitization!Final try: pathg –i –j –k –L– test