Description

Copyright 2001, Agrawal

Transcripts

Address 9 Combinational Automatic Test-Pattern Generation (ATPG) Basics Algorithms and representations Structural versus practical test Definitions Search spaces Completeness Algebras Types of Algorithms VLSI Test: Lecture 9

Origins of Stuck-Faults Eldred (1959) – First utilization of auxiliary testing for the Honeywell Datamatic 1000 PC Galey, Norby, Roth (1961) – First distribution of stuck-at-0 and stuck-at-1 deficiencies Seshu & Freeman (1962) – Use of stuck-shortcomings for parallel flaw recreation Poage (1963) – Theoretical examination of stuck-at issues VLSI Test: Lecture 9

Functional versus Basic ATPG VLSI Test: Lecture 9

Carry Circuit VLSI Test: Lecture 9

Functional versus Basic (Continued) Functional ATPG – create complete arrangement of tests for circuit input-yield blends 129 data sources, 65 yields: 2 129 = 680,564,733,841,876,926,926,749, 214,863,536,422,912 examples Using 1 GHz ATE, would take 2.15 x 10 22 years Structural test: No excess snake equipment, 64 bit cuts Each with 27 deficiencies (utilizing issue identicalness) At most 64 x 27 = 1728 flaws (tests) Takes 0.000001728 s on 1 GHz ATE Designer gives little arrangement of practical tests – enlarge with basic tests to help scope to 98 + % VLSI Test: Lecture 9

Definition of Automatic Test-Pattern Generator Operations on computerized equipment: Inject shortcoming into circuit displayed in PC Use different approaches to initiate and engender issue impact through equipment to circuit yield Output flips from anticipated that would broken sign Electron-bar ( E-pillar ) test watches inside signs – "picture" of hubs charged to 0 and 1 in various hues Too costly Scan plan – add test equipment to every flip-failure to make them a monster shift register in test mode Can move state in, sweep state out Widely utilized – makes consecutive test combinational Costs: 5 to 20% chip region, circuit delay, additional pin, longer test succession VLSI Test: Lecture 9

Circuit and Binary Decision Tree VLSI Test: Lecture 9

Binary Decision Diagram BDD – Follow way from source to sink hub – result of literals along way gives Boolean worth at sink Rightmost way: A B C = 1 Problem: Size changes extraordinarily with variable request VLSI Test: Lecture 9

Algorithm Completeness Definition: Algorithm is c omplete on the off chance that it at last can seek whole parallel choice tree, as required, to produce a test Untestable issue – no test for it even after whole tree sought Combinational circuits just – untestable issues are repetitive, demonstrating the nearness of pointless equipment VLSI Test: Lecture 9

Algebras: Roth\'s 5-Valued and Muth\'s 9-Valued Symbol D 0 1 X G0 G1 F0 F1 Failing Machine 0 1 0 1 X 0 1 Good Machine 1 0 1 X 0 1 X Meaning 1/0/1 0/0 1/1 X/X 0/X 1/X/0 X/1 Roth\'s Algebra Muth\'s Additions VLSI Test: Lecture 9

Roth\'s and Muth\'s Higher-Order Algebras Represent two machines, which are mimicked all the while by a PC program: Good circuit machine (1 st esteem) Bad circuit machine (2 nd esteem) Better to speak to both in the polynomial math: Need just 1 go of ATPG to understand both Good machine values that block terrible machine values get to be evident sooner & the other way around Needed for complete ATPG: Combinational: Multi-way refinement, Roth Algebra Sequential: Muth Algebra - great and awful machines may have distinctive starting qualities because of issue VLSI Test: Lecture 9

Exhaustive Algorithm For n - input circuit, create each of the 2 n input designs Infeasible, unless circuit is parceled into cones of rationale, with 15 inputs Perform comprehensive ATPG for every cone Misses blames that require particular actuation designs for numerous cones to be tried VLSI Test: Lecture 9

Random-Pattern Generation Flow graph for technique Use to get tests for 60-80% of issues, then change to D-calculation or other ATPG for rest VLSI Test: Lecture 9

Boolean Difference Symbolic Method (Sellers et al .) g = G ( X 1 , X 2 , … , X n ) for the issue site f j = F j ( g , X 1 , X 2 , … , X n ) 1 j m X i = 0 or 1 for 1 i n VLSI Test: Lecture 9

Boolean Difference (Sellers, Hsiao, Bearnson) Shannon\'s Expansion Theorem: F ( X 1 , X 2 , … , X n ) = X 2 F ( X 1 , 1, … , X n ) + X 2 F ( X 1 , 0, … , X n ) Boolean Difference (halfway subordinate): F j g Fault Detection Requirements: G ( X 1 , X 2 , … , X n ) = 1 F j g = F j (1, X 1 , X 2 , … , X n ) F j (0, X 1 , … , X n ) = F j (1, X 1 , X 2 , … , X n ) F j (0, X 1 , … , X n ) = 1 VLSI Test: Lecture 9

Path Sensitization Method Circuit Example Fault Sensitization Fault Propagation Line Justification VLSI Test: Lecture 9

Path Sensitization Method Circuit Example Try way f – h – k – L hindered at j , since there is no real way to legitimize the 1 on i 1 D 1 D 0 1 VLSI Test: Lecture 9

Path Sensitization Method Circuit Example Try concurrent ways f – h – k – L and g – i – j – k – L obstructed at k since D-outskirts (chain of D or D ) vanishes 1 D 1 D 1 VLSI Test: Lecture 9

Path Sensitization Method Circuit Example Final attempt: way g – i – j – k – L – test found! 0 D 1 D 1 VLSI Test: Lecture 9

Boolean Satisfiability 2SAT: x i x j + x j x k + x l x m … = 0 x p x y + x r x s + x t x u … = 0 3SAT: x i x j x k + x j x k x l + x l x m x n … = 0 x p x y + x r x s x t + x t x u x v … = 0 . . . . . . VLSI Test: Lecture 9

Satisfiability Example for AND Gate S a k b k c k = 0 (non-repetition) or P ( a k + b k + c k ) = 1 (satisfiability) AND entryway signal connections: Cube: If a = 0, then z = 0 a z If b = 0, then z = 0 b z If z = 1, then a = 1 AND b = 1 z abdominal muscle If a = 1 AND b = 1, then z = 1 a b z Sum to get: a z + b z + a b z = 0 (third relationship is excess with 1 st two) VLSI Test: Lecture 9

Pseudo-Boolean and Boolean False Functions Pseudo-Boolean capacity : use customary + - whole number math administrators Complementation of x spoke to by 1 – x F pseudo—Bool = 2 z + a b – a z – b z – a b z = 0 Energy capacity representation : let any variable be in the extent (0, 1) in pseudo-Boolean capacity Boolean false expression : f AND ( a , b , z ) = z ( stomach muscle ) = a z + b z + a b z VLSI Test: Lecture 9

AND Gate Implication Graph Really effective Each variable has 2 hubs, one for every exacting If … then condition spoke to by edge from if strict to then exacting Transform into transitive conclusion diagram When hub genuine, every reachable state are genuine ANDing administrator utilized for 3SAT relations VLSI Test: Lecture 9

Computational Complexity Ibarra and Sahni examination – NP-Complete (no polynomial expression observed for register time, dared to be exponential) Worst case: no_pi inputs, 2 no_pi input blends no_ff flip-flops, 4 no_ff beginning flip-flop states ( great machine 0 or 1 terrible machine 0 or 1 ) work to forward or invert reenact n rationale doors a n Complexity: O ( n x 2 no_pi x 4 no_ff ) VLSI Test: Lecture 9

History of Algorithm Speedups Algorithm D-ALG PODEM FAN TOPS SOCRATES Waicukauski et al. EST TRAN Recursive learning Tafertshofer et al. Est. speedup over D-ALG (standardized to D-ALG time) 1 7 23 292 1574 ATPG System 2189 ATPG System 8765 ATPG System 3005 ATPG System 485 25057 Year 1966 1981 1983 1987 1988 1990 1991 1993 1995 1997 VLSI Test: Lecture 9

Analog Fault Modeling Impractical for Logic ATPG Huge # of various conceivable simple flaws in advanced circuit Exponential multifaceted nature of ATPG calculation – a 20 flip-flop circuit can take days of processing Cannot bear to go to a lower-level model Most test-example generators for computerized circuits can\'t show at the transistor switch level (see course reading for 5 case of switch-level ATPG) VLSI Test: Lecture 9