1、Lecture 8 Automatic Test Pattern Generation第八讲 自动测试生成Contents内容目录1.Testability Measures / 可测试性测度2.Combinational Circuit ATPG / 组合电路ATPG3.Sequential Circuit ATPG / 时序电路ATPG4.Summary / 小结1 Testability Measures可测试性测度lNeed approximate measure of:Controllability - Difficulty of setting internal circuit l
2、ines to 0 or 1 by setting primary circuit inputsObservability - Difficulty of observing internal circuit lines by observing primary outputs1.1 Purpose目的lUses:Analysis of difficulty of testing internal circuit parts redesign or add special test hardwareGuidance for algorithms computing test patterns
3、avoid using hard-to-control linesEstimation of fault coverageEstimation of test vector length1.2 Origins起源lControl theorylRutman 1972 - First definition of controllabilitylGoldstein 1979 - SCOAPFirst definition of observabilityFirst elegant formulationFirst efficient algorithm to compute controllabi
4、lity and observabilitylParker & McCluskey 1975Definition of Probabilistic ControllabilitylBrglez 1984 - COP1st probabilistic measureslSeth, Pan & Agrawal 1985 PREDICT1st exact probabilistic measures1.3 Testability Analysis可测试性分析lInvolves Circuit Topological analysis, but no test vectors and no searc
5、h algorithm.Static analysislLinear computational complexity, Otherwise, is pointless might as well use automatic test-pattern generation and calculate:Exact fault coverageExact test vectors1.4 SCOAP measuresSCOAP测度lSCOAP Sandia Controllability and Observability Analysis ProgramlCombinational measure
6、s:CC0 Difficulty of setting circuit line to logic 0CC1 Difficulty of setting circuit line to logic 1CO Difficulty of observing a circuit linelSequential measures analogous:SC0SC1SO1.4.1 Range of SCOAP MeasuresSCOAP测度范围lControllabilities 1 (easiest) to infinity (hardest)lObservabilities 0 (easiest) t
7、o infinity (hardest)lCombinational measures:Roughly proportional to # circuit lines that must be set to control or observe given linelSequential measures:Roughly proportional to # times a flip-flop must be clocked to control or observe given lineTo observe a gate input:Observe output and make other
8、input values non-controlling1.4.3 Observability Rules (Cont.)可观察性规则To observe a fanout stem:Observe it through branch with best observability1.4.4 D Flip-Flop RulesD触发器规则Assume a synchronous RESET line.CC1 (Q) = CC1 (D) + CC1 (C) + CC0 (C) + CC0 (RESET)SC1 (Q) = SC1 (D) + SC1 (C) + SC0 (C) + SC0 (RE
9、SET) + 1CC0 (Q) = min CC1 (RESET) + CC1 (C) + CC0 (C), CC0 (D) + CC1 (C) + CC0 (C)SC0 (Q) is analogousCO (D) = CO (Q) + CC1 (C) + CC0 (C) + CC0 (RESET)SO (D) is analogous1.4.4 D Flip-Flop Rules (Cont.)D触发器规则（续）CO (RESET) = CO (Q) + CC1 (Q) + CC1 (RESET) + CC1 (C) + CC0 (C)SO (RESET) is analogousThre
10、e ways to observe the clock line:Set Q to 1 and clock in a 0 from DSet the flip-flop and then reset itReset the flip-flop and clock in a 1 from DCO (C) = min CO (Q) + CC1 (Q) + CC0 (D) + CC1 (C) + CC0 (C), CO (Q) + CC1 (Q) + CC1 (RESET) + CC1 (C) + CC0 (C), CO (Q) + CC0 (Q) + CC0 (RESET) + CC1 (D) +
11、 CC1 (C) + CC0 (C)SO (C) is analogous1.4.5 Levelization Algorithm 6.1分级算法lLabel each gate with max # of logic levels from primary inputs or with max # of logic levels from primary outputlAssign level # 0 to all primary inputs (PIs)lFor each PI fanout:Label that line with the PI level number, &Queue
12、logic gate driven by that fanoutlWhile queue is not empty:Dequeue next logic gateIf all gate inputs have level #s, label the gate with the maximum of them + 1;Else, requeue the gate1.4.6 Testability Algorithm 6.2可测试性算法1.For all PIs, CC0 = CC1 = 1 and SC0 = SC1 = 02.For all other nodes, CC0 = CC1 = S
13、C0 = SC1 = 3.Go from PIs to POS, using CC and SC equations to get controllabilities - Iterate on loops until SC stabilizes - convergence guaranteed4.For all POs, set CO = SO = 05.For all other nodes, CO = SO = 6.Work from POs to PIs, Use CO, SO, and controllabilities to get observabilities7.Fanout s
14、tem (CO, SO) = min branch (CO, SO)8.If a CC or SC (CO or SO) is , that node is uncontrollable (unobservable)8 88 88 82 Combinational Circuit ATPG 组合电路ATPGlElectron-beam (E-beam) test observes internal signals “picture” of nodes charged to 0 and 1 in different colorsToo expensivelThe ATPG problem:Giv
15、en a logical fault model, and a circuit, determine a small set of test vectors that detect all faults in the circuit.2.1 Functional vs. Structural ATPG功能和结构测试2.1.1 Compare比较lFunctional ATPG generate complete set of tests for circuit input-output combinations 129 inputs, 65 outputs: 2129 = 680,564,73
16、3,841,876,926,926,749, 214,863, 536, 422, 912 patterns Using 1 GHz ATE, would take 2.15 x 1022 yearslStructural 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 ATElDesigner gives small s
17、et of functional tests augment with structural tests to boost coverage to 98+ %2.2 Algorithm Completeness算法完备性lDefinition: Algorithm is complete if it ultimately can search entire binary decision tree, as needed, to generate a testlUntestable fault no test for it even after entire tree searchedlComb
18、inational circuits only untestable faults are redundant, showing the presence of unnecessary hardware2.3 Algebras: 5-Valued and 9-Valued算法代数：5值和9值逻辑代数SymbolDD01XG0G1F0F1Meaning1/00/10/01/1X/X0/X1/XX/0X/1FailingMachine0101XXX01GoodMachine 1001X01XXRothsRothsAlgebraAlgebraMuthsMuthsAdditionsAdditions2
19、.3.1 Higher-Order Algebras高阶代数lRepresent two machines, which are simulated simultaneously by a computer program:Good circuit machine (1st value)Bad circuit machine (2nd value)lBetter to represent both in the algebra:Need only 1 pass of ATPG to solve bothGood machine values that preclude bad machine
20、values become obvious sooner & vice versalNeeded for complete ATPG:Combinational: Multi-path sensitization, Roth AlgebraSequential: Muth Algebra - good and bad machines may have different initial values due to fault2.4 Types of Algorithms 算法类型lExhaustive / 穷举算法lRandom-Pattern Generation / 随机码生成lBool
21、ean Difference Symbolic Method / 布尔差分符号方法lPath Sensitization Method / 路径敏化方法lBoolean Satisfiability / 布尔可满足性2.4.1 Exhaustive 穷举算法lFor n-input circuit, generate all 2n input patternslInfeasible, unless circuit is partitioned into cones of logic, with 15 inputsPerform exhaustive ATPG for each coneMiss
22、es faults that require specific activation patterns for multiple cones to be tested 2.4.2 Random-Pattern Generation随机码生成lFlow chart for methodlUse to get tests for 60-80% of faults, then switch to D-algorithm or other ATPG for rest2.4.3 Boolean Difference Symbolic Method布尔差分符号方法g = G (X1, X2, , Xn)
23、for the fault sitefj = Fj (g, X1, X2, , Xn) 1 j mXi = 0 or 1 for 1 i n lShannons Expansion Theorem: F (X1, X2, , Xn) = X2 F (X1, 1, , Xn) + X2 F (X1, 0, , Xn)lBoolean Difference (partial derivative): Fj glFault Detection Requirements: G (X1, X2, , Xn) = 1 Fj g2.4.3.1 Boolean Difference (Sellers, Hsi
24、ao, Bearnson)= Fj (1, X1, X2, , Xn) Fj (0, X1, , Xn)= Fj (1, X1, X2, , Xn) Fj (0, X1, , Xn) = 1 2.4.4 Path Sensitization Method路径敏化方法a.Fault Sensitization / 故障敏化b.Fault Propagation / 故障传播c.Line Justification / 线验证2.4.4.1 Circuit Example电路实例lTry path f h k L blocked at j, since there is no way to jus
25、tify the 1 on i1 10 0D DD D1 11 11 1D DD DD D2.4.4.1 Circuit Example (Cont.)电路实例（续）Try simultaneous paths f h k L and g i j k L blocked at k because D-frontier (chain of D or D) disappears1 1D DD DD DD DD D1 11 11 12.4.4.1 Circuit Example (Cont.)电路实例（续）lFinal try: path g i j k L test found!0 0D DD D
26、D D1 1D DD D1 10 01 12.4.5 Boolean Satisfiability布尔可满足性l2SAT: xi xj + xj xk + xl xm = 0 xp xy + xr xs + xt xu = 0l3SAT: xi xj xk + xj xk xl + xl xm xn = 0 xp xy + xr xs xt + xt xu xv = 0. . . . . . .2.4.5.1 Satisfiability Example for AND GatelS ak bk ck = 0 (non-tautology) or P(ak + bk + ck) = 1 (sa
27、tisfiability)lAND gate signal relationships: Cube:If a = 0, then z = 0 a zIf b = 0, then z = 0 b zIf z = 1, then a = 1 AND b = 1 z abIf a = 1 AND b = 1, then z = 1 a b zlSum to get: a z + b z + a b z = 0 (third relationship is redundant with 1st two)2.4.5.2 Pseudo-Boolean and Boolean False Functions
28、lPseudo-Boolean function: use ordinary + - integer arithmetic operatorsComplementation of x represented by 1 xFpseudoBool = 2 z + a b a z b z a b z = 0lEnergy function representation: let any variable be in the range (0, 1) in pseudo-Boolean functionlBoolean false expression: fAND (a, b, z) = z (ab)
29、 = a z + b z + a b z 2.4.5.3 AND Gate Implication Graph隐含图lReally efficientlEach variable has 2 nodes, one for each literallIf then clause represented by edge from if literal to then literallTransform into transitive closure graph When node true, all reachable states are truelANDing operator used fo
30、r 3SAT relations 2.5 Computational Complexity计算复杂性lIbarra and Sahni analysis NP-Complete (no polynomial expression found for compute time, presumed to be exponential)lWorst case: no_pi inputs, 2 no_pi input combinations no_ff flip-flops, 4 no_ff initial flip-flop states (good machine 0 or 1 bad mach
31、ine 0 or 1) work to forward or reverse simulate n logic gates a nlComplexity: O (n x 2 no_pi x 4 no_ff) 2.6 History of Algorithm Speedups算法历史AlgorithmD-ALGPODEMFANTOPSSOCRATESWaicukauski et al.ESTTRANRecursive learningTafertshofer et al.Est. speedup over D-ALG(normalized to D-ALG time)17232921574 AT
32、PG System2189 ATPG System8765 ATPG System3005 ATPG System48525057Year1966198119831987198819901991199319951997 2.7 Fault Coverage and Efficiency故障覆盖率和效率Fault coverage = Fault efficiency # of detected faultsTotal # faults# of detected faultsTotal # faults - # undetectable faults=2.8 Test Generation Sy
33、stems测试生成系统CircuitDescriptionTestPatternsUndetectedFaultsRedundantFaultsAbortedFaultsBacktrackDistributionFaultListCompacterSOCRATESWith faultsimulator2.9 Test Compaction测试压缩lFault simulate test patterns in reverse order of generationATPG patterns go firstRandomly-generated patterns go last (because
34、 they may have less coverage)When coverage reaches 100%, drop remaining patterns (which are the useless random ones)Significantly shortens test sequence economic cost reduction2.9.1 Static and Dynamic Compaction静态和动态压缩lStatic compactionATPG should leave unassigned inputs as XTwo patterns compatible
35、if no conflicting values for any PICombine two tests ta and tb into one test tab = ta tb using D-intersection Detects union of faults detected by ta & tblDynamic compactionProcess every partially-done ATPG vector immediatelyAssign 0 or 1 to PIs to test additional faults 2.9.2 Compaction Example压缩实例l
36、t1 = 0 1 X t2 = 0 X 1 t3 = 0 X 0 t4 = X 0 1lCombine t1 and t3, then t2 and t4 lObtain:t13 = 0 1 0 t24 = 0 0 1lTest Length shortened from 4 to 23 Sequential Circuits ATPG时序电路ATPGlA sequential circuit has memory in addition to combinational logic.lTest for a fault in a sequential circuit is a sequence
37、 of vectors, whichInitializes the circuit to a known stateActivates the fault, andPropagates the fault effect to a primary outputlMethods of sequential circuit ATPGTime-frame expansion methodsSimulation-based methods3.1 Time-Frames ExpansionlIf the test sequence for a single stuck-at fault contains
38、n vectors,Replicate combinational logic block n timesPlace fault in each blockGenerate a test for the multiple stuck-at fault using combinational ATPG with 9-valued logicComb.blockFaultTime-frame0Time-frame-1Time-frame-n+1Unknownor givenInit. stateVector 0Vector -1Vector -n+1PO 0PO -1PO -n+1Statevar
39、iablesNextstate3.1.1 Example for Logic Systems实例FF2 FF1A B s-a-13.1.1.1 Five-Valued Logic (Roth)0,1, D, D, X A BX X X 0s-a-1DA BX X X 0s-a-1DFF1FF1FF2FF2DDTime-frame -1Time-frame 03.1.1.2 Nine-Valued Logic (Muth)0,1, 1/0, 0/1, 1/X, 0/X, X/0, X/1, XA BX X X 0s-a-10/1A B0/X 0/X 0/1 Xs-a-1X/1 FF1FF1FF2
40、FF20/1X/1Time-frame -1Time-frame 03.1.2 Implementation of ATPGATPG实现lSelect a PO for fault detection based on drivability analysis.lPlace a logic value, 1/0 or 0/1, depending on fault type and number of inversions.lJustify the output value from PIs, considering all necessary paths and adding backwar
41、d time-frames.lIf justification is impossible, then use drivability to select another PO and repeat justification.lIf the procedure fails for all reachable POs, then the fault is untestable.lIf 1/0 or 0/1 cannot be justified at any PO, but 1/X or 0/X can be justified, the the fault is potentially de
42、tectable.3.1.3 Complexity of ATPG计算复杂性lSynchronous circuit - All flip-flops controlled by clocks; PI and PO synchronized with clock: Cycle-free circuit No feedback among flip-flops: Test generation for a fault needs no more than dseq + 1 time-frames, where dseq is the sequential depth. Cyclic circui
43、t Contains feedback among flip-flops: May need 9Nff time-frames, where Nff is the number of flip-flops.lAsynchronous circuit Higher complexity!Time-Frame0Time-Framemax-1Time-Framemax-2Time-Frame-2Time-Frame-1S0S1S2S3Smaxmax = Number of distinct vectors with 9-valued elements = 9Nff3.1.3.1 Cycle-Free
44、 Circuits无环电路lCharacterized by absence of cycles among flip-flops and a sequential depth, dseq.ldseq is the maximum number of flip-flops on any path between PI and PO.lBoth good and faulty circuits are initializable.lTest sequence length for a fault is bounded by dseq + 1.3.1.3.2 Cycle-Free Example无
45、环电路实例F1F2F3Level = 12F1F2F3Level = 1233dseq = 3s - graphCircuitAll faults are testable. See Example 8.6.3.1.3.3 Cyclic circuit循环电路 lCyclic structure Sequential depth is undefined.lCircuit is not initializable. No tests can be generated for any stuck-at fault.lAfter expanding the circuit to 9Nff = 81
46、, or fewer, time-frames ATPG program calls any given target fault untestable.lCircuit can only be functionally tested by multiple observations.lFunctional tests, when simulated, give no fault coverage.3.1.3.4 Cyclic Circuit Example循环电路实例F1F2CNTZModulo-3 counters - graphF1F23.1.3.5 Benchmark Circuits
47、CircuitPIPOFFGatesStructureSeq. depthTotal faultsDetected faultsPotentially detected faultsUntestable faultsAbandoned faultsFault coverage (%)Fault efficiency (%)Max. sequence lengthTotal test vectorsGentest CPU s (Sparc 2)s1196 14 14 18 529Cycle-free 412421239 0 3 0 99.8 100.0 3 313 10s1238 14 14 1
48、8 508Cycle-free 413551283 0 72 0 94.7 100.0 3 308 15s1488 8 19 6 653Cyclic-14861384 2 26 76 93.1 94.8 24 52519941s1494 8 19 6 647Cyclic-15061379 2 30 97 91.6 93.4 28 559191833.1.3.6 Asynchronous Circuit异步电路lAn asynchronous circuit contains unclocked memory often realized by combinational feedback.lA
49、lmost impossible to build, let alone test, a large asynchronous circuit.lClock generators, signal synchronizers, flip-flops are typical asynchronous circuits.lMany large synchronous systems contain small portions of localized asynchronous circuitry.lSequential circuit ATPG should be able to generate
50、 tests for circuits with limited asynchronous parts, even if it does not detect faults in those parts.3.1.3.7 Asynchronous Model异步电路模型ClockedFlip-flopsFeedbackdelaysSynchronous PIsSynchronous POsSystemClock, CKFast modelClock, FMCKCKCKFeedback-freeCombinationalLogicCCombinationalFeedback Paths:Feedb
