Selection of partial scan flip-flops to break feedback cycles

• US 5,502,646 A
• Filed: 12/02/1993
• Issued: 03/26/1996
• Est. Priority Date: 12/02/1993
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC USA (NEC Corporation)
• Inventors: Balakrishnan, Arunkumar, Chakradhar, Srimat T.
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/161,140
• Time in Patent Office: 845 Days
• Field of Search: 364/488, 364/489, 371/22.1, 371/22.3, 371/22.5, 371/22.6
• US Class Current: 714/726
• CPC Class Codes: G01R 31/31707 Test strategies methods for generation of test sequences G01R31/318371
• CPC Class Codes: G01R 31/318586 with partial scan or non-scannable parts

Abstract

In partial scan testing of a circuit the optimal quantity of scan flip-flops required to eliminate all feedback, except self-loops, in a circuit is determined. For determining a minimal feedback vertex set (MFVS) for the S-graph of a circuit to be tested, MFVS-preserving transformations, partitioned search strategy and integer linear program (ILP)-based lower bounding techniques are combined to obtain an exact algorithm for computing the MFVS. The result is used in the fabrication of the circuit with minimal overhead in terms of area and performance degradation as a result of providing the capability to perform partial scan testing of the fabricated circuit.

Claims

1. A method of determining an optimal quantity of scan flip-flops required to eliminate feedback loops in a sequential logic circuit, comprising the steps of:

a) deriving an S-graph of the sequential logic circuit;

b) applying minimum feedback vertex set (MFVS) preserving transformations to the S-graph to reduce the S-graph to non-empty, compressed SCCs (strongly connected components);

c) performing a partitioned branch and bound method to solve the compressed SCCs of the graph;

d) applying integer linear programming (ILP) to obtain an optimal solution or lower bound for the MFVS of the S-graph, and

e) if a lower bound is obtained in step (d), repeat steps (c) and (d) or

f) if any optimal solution is obtained is step (d), incorporating the quantity of scan flip-flops obtained as the optimal solution into the sequential logic circuit for enabling partial scan testing of the sequential logic circuit.

2. A method as set forth in claim 1, wherein said applying MFVS preserving transformations comprises applying procedure transform_-- graph.

3. A method as set forth in claim 2, wherein said performing a partitioned branch and bound method comprises applying procedure SOLVE_-- SCC.

4. A sequential logic circuit including the quantity of flip-flops for performing partial scan testing as determined in accordance with the method of claim 3.

5. A method as set forth in claim 3 wherein said applying integer linear programming comprises:

minimizing Σ

x_i, subject to w_i -w_j +nx_i ≧

1 (v_i →

v_j) A, where 0≦

w_i ≦

n-1 and x_i are Boolean and where w_i are real value weights assigned to vertices v_i of the graph and for any arc v_i →

v_j, w_i >

w_j.

6. A sequential logic circuit including the quantity of flip-flops for performing partial scan testing as determined in accordance with the method of claim 5.

7. A method as set forth in claim 5, whereby for any cycle C in a graph Σ

_v.sbsb.i.sub. .spsb.C x_i ≧

1.

8. A sequential logic circuit including the quantity of flip-flops for performing partial scan testing as determined in accordance with the method of claim 7.

9. A method as set forth in claim 1, wherein said performing a partitioned branch and bound method comprises applying procedure SOLVE_-- SCC.

10. A sequential logic circuit including the quantity of flip-flops for performing partial scan testing as determined in accordance with the method of claim 1.

11. A method as set forth in claim 1 wherein said applying integer linear programming comprises:

minimizing Σ

x_i, subject to w_i -w_j +nx_i ≧

1 (v_i →

v_j) A, where 0≦

w_i ≦

n-1 and x_i are Boolean and where w_i are real value weights assigned to vertices v_i of the graph and for any arc v_i →

v_j, w_i >

w_j.

12. A method as set forth in claim 11, whereby for any cycle C in a graph Σ

_v.sbsb.i.sub. .spsb.C x_i ≧

1.

13. A method as set forth in claim 1, where said performing a partitioned branch and bound method is performed recursively.

14. A sequential logic circuit including the quantity of flip-flops for performing partial scan testing as determined in accordance with the method of claim 13.