Lecture 11altAdvances in Combinational ATPG Algorithms: Lecture 11alt Advances in Combinational ATPG Algorithms Branch and Bound Search FAN – Multiple Backtrace, head lines (1983) TOPS – Dominators (1987) SOCRATES – Learning (1988) EST – Search space learning (1991) ATPG Performance improvements Summary


ATPG: A Boolean Satisfiability Problem: ATPG: A Boolean Satisfiability Problem CUT CUT with fault f(a,b,c) = 1 Test Vector (a,b,c)


SAT is NP-Complete: SAT is NP-Complete a c c b b 1 1 1 0 0 0 0 0 c c 0 1 f a b c f Binary Decision Diagram (BDD)


Search for a Solution: Search for a Solution Problem: Given a value of a Boolean function of binary variables, find values of the variables. Solution: Starting at the root, enumerative traversal of the binary decision diagram (BDD) until a solution is found. BDD is a search tree – search consists of Branch: Set an untried value for a variable Backtrack to previous branching point if there is no untried value Stop if solution found, or backtracked to root without untried values Or, bound search tree for future traversals if solution is impossible and backtrack to previous branching point (some variable orderings may lead to early bounding) Or, continue


Example: f = 1: Example: f = 1 a c c b b 1 1 1 0 0 0 0 0 c c 0 1 f a b c f Binary Decision Diagram (BDD) bound


FAN: Fujiwara and Shimono(1983): FAN: Fujiwara and Shimono (1983) New concepts: Unique sensitization Stop Backtrace at head lines Multiple Backtrace


PODEM Makes Unwise Signal Assignments: PODEM Makes Unwise Signal Assignments Blocks fault propagation due to assignment J = 0


Unique Sensitization of FAN with No Search: Unique Sensitization of FAN with No Search FAN immediately sets necessary signals to propagate fault Path over which fault is uniquely sensitized


Headlines: Headlines Headlines H and J separate circuit into 3 parts, for which test generation can be done independently


Contrasting Decision Trees: Contrasting Decision Trees PODEM decision tree FAN decision tree


Multiple Backtrace: Multiple Backtrace FAN – breadth-first passes – 1 time PODEM – depth-first passes – 6 times


AND Gate Vote Propagation: AND Gate Vote Propagation AND Gate Easiest-to-control Input: # 0’s = OUTPUT # 0’s # 1’s = OUTPUT # 1’s All other inputs: # 0’s = 0 # 1’s = OUTPUT # 1’s [5, 3] [5, 3] [0, 3] [0, 3] [0, 3] 0 0 0 0 0 1 1 1


Multiple Backtrace Fanout Stem Voting: Multiple Backtrace Fanout Stem Voting Fanout Stem -- # 0’s = Σ Branch # 0’s, # 1’s = Σ Branch # 1’s [5, 1] [1, 1] [3, 2] [4, 1] [5, 1] [18, 6]


PODEM Fails to Determine Unique Signals: PODEM Fails to Determine Unique Signals Backtracing operation fails to set all 3 inputs of gate L to 1 Causes unnecessary search sa1


FAN -- Early Determination of Unique Signals: FAN -- Early Determination of Unique Signals Determine all unique signals implied by current decisions immediately Avoids unnecessary search sa1


TOPS: DominatorsKirkland and Mercer (1987): TOPS: Dominators Kirkland and Mercer (1987) Dominator of g – all paths from g to PO must pass through the dominator Absolute -- k dominates B Relative – dominates only paths to a given PO If dominator of fault becomes 0 or 1, backtrack


SOCRATES: Learning (1988): SOCRATES: Learning (1988) Static and dynamic learning: a = 1 f = 1 means that we learn f = 0 a = 0 by applying the Boolean contrapositive theorem Set each signal first to 0, and then to 1 Discover implications Learning criterion: remember f = vf only if: f = vf requires all inputs of f to be non-controlling A forward implication contributed to f = vf


Improved Unique Sensitization Procedure: Improved Unique Sensitization Procedure When a is only D-frontier signal, find dominators of a and set their inputs unreachable from a to 1 Find dominators of single D-frontier signal a and make common input signals non-controlling


Constructive Dilemma: Constructive Dilemma [(a = 0) (i = 0)] [(a = 1) (i = 0)] (i = 0) If both assignments 0 and 1 to a make i = 0, then i = 0 is implied independently of a


EST: Search Space Learning (Giraldi and Bushnell): EST: Search Space Learning (Giraldi and Bushnell) E-frontier – partial circuit functional decomposition Equivalent to a node in a BDD Cut-set between circuit part with known labels and part with X signal labels EST learns E-frontiers during ATPG and stores them in a hash table Dynamic programming – when new decomposition generated from implications of a variable assignment, looks it up in the hash table Avoids repeating a search already conducted Terminates search when decomposition matches: Earlier one that lead to a test (retrieves stored test) Earlier one that lead to a backtrack Accelerated SOCRATES nearly 5.6 times


Fault B sa1: Fault B sa1


Fault h sa1: Fault h sa1


Summary: Summary Algorithm D-ALG PODEM FAN TOPS SOCRATES Waicukauski et al. EST TRAN Recursive learning Tafertshofer et al. Est. speedup over D-ALG (normalized 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 Performance improvement through 40 years of research.