Hybrid algorithm for test point selection for scan-based BIST

• US 6,256,759 B1
• Filed: 06/15/1998
• Issued: 07/03/2001
• Est. Priority Date: 06/15/1998
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: Agere Systems Incorporated (Broadcom, Inc.)
• Inventors: Lin, Chih-Jen, Tsai, Huan-Chih, Cheng, Kwang-Ting, Bhawmik, Sudipta
• Primary Examiner(s): HUA, LY
• Application Number:
  US09/097,488
• Time in Patent Office: 1,114 Days
• Field of Search: 714/726, 714/727, 714/724, 714/733
• US Class Current: 714/726
• CPC Class Codes: G01R 31/318591 Tools
• CPC Class Codes: G06F 30/333 Design for testability [DFT], e.g. scan chain or built-in self-test [BIST]

Abstract

A test point selection method for scan-based built-in self-test (BIST). The method calculates a hybrid cost reduction (HCR) value as an estimated value of the corresponding actual cost reduction for all nodes in a circuit under test. A test point is then selected having a largest HCR. This iterative process continues until the fault coverage of the circuit under test reaches a desired value or the number of test points selected is equal to a maximum number of test points. In an alternative embodiment, the cost reduction factor is calculated for all nodes in the circuit under test, the HCR is calculated for only a selected set of candidates, and the candidate having the largest HCR is selected as the test point. The test point selection method achieves higher fault coverage results and reduces computational processing relative to conventional selection methods.

Claims

1. A method for selecting test points for a full-scan based built-in self-test circuit under test having a plurality of primary inputs and a plurality of primary outputs, said method comprising the steps of:

(a) calculating a controllability for every node in the circuit under test;

(b) calculating an observability for every node in the circuit under test;

(c) calculating a controllability gradient for every node in the circuit under test;

(d) calculating an observability gradient for every node in the circuit under test;

(e) evaluating a hybrid cost reduction for an observation point, wherein step (e) comprises;

(f) scheduling an observation point candidate in an observability event list;

(g) calculating an observability ratio for each node in a fanin cone starting from the observation point candidate toward the primary inputs, the observability ratio being defined as

2. The method in accordance with claim 1, before step (a) further comprising selecting from one of a timing driven mode and an area driven mode, wherein if a timing driven mode is selected computing slacks for all nodes in the circuit under test.

3. The method in accordance with claim 2, wherein step (e) comprises determining for each node in the circuit under test whether one of the timing driven mode is selected and a slack due to insertion of an observation point is less than a slack of the node, wherein if one of the area driven mode is selected and a slack due to insertion of an observation point is greater than or equal to a slack of the node, performing step (k).

4. The method in accordance with claim 3, wherein step (k) comprises determining for each node in the circuit under test whether one of the timing driven mode is selected and a slack due to insertion of a control point is less than a slack of the node, wherein if one of the area driven mode is selected and a slack due to insertion of a control point is greater than or equal to a slack of the node performing step (p).

5. A method for selecting test points for a partial-scan based built-in self-test circuit under test including a near acyclic circuit, a plurality of primary inputs, and a plurality of primary outputs, said method comprising the steps of:

(a) calculating a controllability for every node in the circuit under test;

(b) calculating an observability for every node in the circuit under test;

(c) calculating a controllability gradient for every node in the circuit under test;

(d) calculating an observability gradient for every node in the circuit under test;

(e) evaluating a hybrid cost reduction for an observation point, wherein step (e) comprises;

(f) scheduling an observation point candidate in an observability event list;

(g) calculating an observability ratio for each node in a fanin cone starting from the observation point candidate toward the primary inputs, the observability ratio being defined as

6. The method in accordance with claim 5, before step (a) further comprising selecting from one of a timing driven mode and an area driven mode, wherein if a timing driven mode is selected computing slacks for all nodes in the circuit under test.

7. The method in accordance with claim 6, wherein step (e) comprises determining for each node in the circuit under test whether one of the timing driven mode is selected and a slack due to insertion of an observation point is less than a slack of the node, wherein if one of the area driven mode is selected and a slack due to insertion of an observation point is greater than or equal to a slack of the node, performing step (k).

8. The method in accordance with claim 7, wherein step (k) comprises determining for each 10node in the circuit under test whether one of the timing driven mode is selected and a slack due to insertion of a control point is less than a slack of the node, wherein if one of the area driven mode is selected and a slack due to insertion of a control point is greater than or equal to a slack of the node performing step (p).

9. The method in accordance with claim 5, before step (a) further comprising the steps of:

(r) decomposing the near acyclic circuit into blocks comprising a set of logic gates and non-self-loop flip-flops feeding one of the plural primary outputs and a self-loop flip-flop having a feedback port; and

(s) levelizing the decomposed near acyclic circuit into a plurality of Macro-Levels of a vertex in a derived circuit graph of one of a self-loop flip-flop, a primary input, and a primary output in a derived circuit graph in the near acyclic circuit defined as

ML=0 if the vertex is a primary input

ML=1+max(ML(k)) for all vertices k'"'"'s that directly feed the vertex.

10. The method in accordance with claim 9, wherein step (a) comprises computing controllabilities of each block from the primary inputs to the primary outputs.

11. The method in accordance with claim 10, wherein step (a) further comprises the steps of:

(t) assigning a symbolic variable to the feedback port of each self-loop flip-flop;

(u) expressing controllabilities of internal signals in the fanout cone of the feedback port as a polynomial function of the symbolic variable;

(v) simplifying a highest exponent of the polynomial function;

(w) deriving the value of the symbolic variable; and

(x) calculating controllabilites of the internal signals in a fanout cone of each block based on the derived value of the symbolic variable.

12. The method in accordance with claim 11, wherein step (b) comprises computing observabilities for each block from the primary outputs to the primary inputs.

13. The method in accordance with claim 12, wherein step (b) comprises the steps of:

(y) assigning a symbolic variable to the feedback port of each self-loop flip-flop;

(z) expressing the observabilities of internal signals in the fanout cone of the feedback port as a polynomial function of the symbolic variable;

(aa) simplifying a highest exponent of the polynomial function;

(bb) deriving the value of the symbolic variable;

(cc) calculating observabilities of the internal signals in a fanout cone of each block based on the derived value of the symbolic variable.

14. The method in accordance with claim 13, wherein step (c) comprises calculating the observability gradient one block at a time from a lowest macro-level block toward a highest marco-level block.

15. The method in accordance with claim 14, wherein step (c) comprises the step of:

(dd) computing observation gradient values for input nodes of the self-loop flip-flop, except for the feedback port, based on the controllability and observability values;

(ee) assigning a symbolic variable to the feedback port of each self-loop flip-flop;

(ff) computing observation gradient values for all nodes as a linear function of the symbolic variable; and

(gg) deriving the value of the symbolic variable.

16. The method in accordance with claim 15, wherein step (d) comprises calculating the controllability gradient one block at a time from a highest macro-level block toward a lowest marco-level block.

17. The method in accordance with claim 16, wherein step (d) comprises the step of:

(hh) computing observation gradient values for input nodes of the self-loop flip-flop, except for the feedback port, based on the controllability and observability values;

(ii) assigning a symbolic variable to the feedback port of each self-loop flip-flop;

(jj) computing observation gradient values for all nodes as a linear function of the symbolic variable; and

(kk) deriving the value of the symbolic variable.

18. The method in accordance with claim 17, wherein step (k) further comprises identifying private nodes of each self-loop flip-flop block.

19. The method in accordance with claim 18, wherein step (l) comprises calculating the controllability ratio for each private node in the self-loop flip-flop block.