Scribd Logo
Upload

Welcome to Scribd!

  • 65 views

    FAN

    Uploaded by

    Sinchana Gupta
    The document describes the FAN ATPG algorithm which aims to reduce test generation time by stopping backtracking at headline lines, immediately assigning uniquely determined signals, uniquely sensitizing faults, and using multiple backtracking. The key strategies of FAN include stopping backtracking at headlines, performing forward and backward implications to assign signals, uniquely sensitizing faults without search, and concurrently backtracking along multiple paths for more efficient testing.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    FAN

    Uploaded by

    Sinchana Gupta
    65 views33 pages
    The document describes the FAN ATPG algorithm which aims to reduce test generation time by stopping backtracking at headline lines, immediately assigning uniquely determined signals, uniquely sensitizing faults, and using multiple backtracking. The key strategies of FAN include stopping backtracking at headlines, performing forward and backward implications to assign signals, uniquely sensitizing faults without search, and concurrently backtracking along multiple paths for more efficient testing.

    Original Title

    FAN.ppt

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes the FAN ATPG algorithm which aims to reduce test generation time by stopping backtracking at headline lines, immediately assigning uniquely determined signals, uniquely sensitizing faults, and using multiple backtracking. The key strategies of FAN include stopping backtracking at headlines, performing forward and backward implications to assign signals, uniquely sensitizing faults without search, and concurrently backtracking along multiple paths for more efficient testing.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    65 views33 pages

    FAN

    Uploaded by

    Sinchana Gupta
    The document describes the FAN ATPG algorithm which aims to reduce test generation time by stopping backtracking at headline lines, immediately assigning uniquely determined signals, uniquely sensitizing faults, and using multiple backtracking. The key strategies of FAN include stopping backtracking at headlines, performing forward and backward implications to assign signals, uniquely sensitizing faults without search, and concurrently backtracking along multiple paths for more efficient testing.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 33

    FAN : FAN Oriented

    ATPG Algorithm
    Objective
    TG time reduction
    Reduced number of backtracks
    Find out the non-existence of solution as soon as
    possible
    Branch and bound

    1/8/2020 1
    1/8/2020 2
    FAN -- Fujiwara and
    Shimono
    (1983)
    New concepts:
     Stop Backtrace at head lines
     Immediate assignment of uniquely-
    determined signals using Forward and
    Backward Implications
     Unique sensitization
     Multiple Backtrace

    1/8/2020 3
    FAN Algorithm
    Strategies:
    Strategy 1:
    Stop the backtrace at a headline, and postpone the line
    justification for the headline to later

    1/8/2020 4
    1/8/2020 5
    Headlines

     When a line L is reachable from a fanout point, L is said to be


    bound
     A signal line that is not bound is said to be free
     When a line is adjacent to some bound line, it is said to be headline

     Headlines H and J separate circuit into 3 parts, for which test


    generation can be done independently

    1/8/2020 6
    1/8/2020 7
    1/8/2020 8
    Contrasting Decision Trees

    1/8/2020 9
    1/8/2020 10
    FAN Algorithm

     Strategies:
    Strategy 2: Immediate Implication
    In step of the algorithm determine as many signal values as
    possible
    Forward and Backward Implications

    Strategy 3: Unique Sensitization


    Assign faulty signal D or D’ that is uniquely determined or
    implied by the fault in question

    1/8/2020 12
    1/8/2020 13
    PODEM Fails to Determine Unique Signals

     Backtracing operation fails to


    set all 3 inputs of gate L to 1
     Causes unnecessary search
    1/8/2020 14
    FAN - Early Determination of Unique Signals

     Determine all unique signals


    implied by current decisions
    immediately
     Avoids unnecessary search
    1/8/2020 15
    FAN Algorithm
    Strategy 4:
     When the D-frontier consists of a single gate, apply
    unique sensitization

    1/8/2020 16
    1/8/2020 17
    PODEM Makes Unwise
    Signal Assignments

     Blocks fault propagation due to


    assignment J = 0

    1/8/2020 18
    Unique Sensitization of
    FAN with No Search

    Path over which fault is uniquely sensitized

     FAN immediately sets necessary signals to


    propagate fault

    1/8/2020 19
    1/8/2020 20
    1/8/2020 21
    FAN Algorithm
     Strategy 5:
     Multiple backtracing (concurrent backtracing of more than
    one path) is more efficient than backtracing along a single
    path

     FAN defines an objective during a multiple-backtrace as a triple:


     (s, n0(s), n1(s))
     where s is the objective line, n0(s) is the # of times 0 is
    required at s and n1(s) is the # of times 1 is required at s.

    1/8/2020 22
    1/8/2020 23
    Multiple Backtrace
    FAN – breadth-first
    passes –
    1 time

    PODEM –
    depth-first
    passes – 6 times
    1/8/2020 24
    Rules for Mutiple
    Backtracing
     Decisions are made at Fanout Stems
     In case of conflict, signals are assigned randomly at the
    stem and forward implication is carried out
     Else, signal with maximum votes is assigned to the stem
     In case of gates, if only one input is to be set, easiest to
    control input is voted
     Else all the inputs are voted

    1/8/2020 25
    1/8/2020 26
    AND Gate Vote Propagation
    [5, 3]
    [0, 3]
    [5, 3]
    [0, 3]
    [0, 3]

     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
    1/8/2020 27
    Multiple Backtrace
    Fanout Stem Voting
    [5, 1]
    [1, 1]
    [18, 6] [3, 2]

    [4, 1]
    [5, 1]

     Fanout Stem --
     # 0’s = S Branch # 0’s,
     # 1’s = S Branch # 1’s
    1/8/2020 28
    1/8/2020 29
    1/8/2020 30
     Note that this indicates that it is possible to satisfy the initial
    objectives without requiring the off-path inputs y and z to be set.

    1/8/2020 31
     Note that in this case, it is necessary to define the side inputs to
    establish the initial objectives.
     Add y as an objective to satisfy in the breadth-first search.
    1/8/2020 32
    Fault: r sa1

    1/8/2020 33
    Fault : h sa1

    1/8/2020 34

    You might also like