Method and apparatus for generating test patterns for use in at-speed testing

• US 8,176,462 B2
• Filed: 05/11/2009
• Issued: 05/08/2012
• Est. Priority Date: 05/11/2009
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Visweswariah, Chandramouli, Xiong, Jinjun, Zolotov, Vladimir
• Primary Examiner(s): Dinh, Paul
• Assistant Examiner(s): NGUYEN, NHA T
• Application Number:
  US12/464,025
• Publication Number:
  US 20100287432A1
• Time in Patent Office: 1,093 Days
• Field of Search: 716/106, 716/108, 716/113, 716/136
• US Class Current: 716/136
• CPC Class Codes: G01R 31/318328 for delay tests
• CPC Class Codes: G01R 31/318342 by preliminary fault modelling, e.g. analysis, simulation

Abstract

In one embodiment, the invention is a method and apparatus generating test patterns for use in at-speed testing. One embodiment of a method for use by a general purpose computing device that is configured to generate a set of test patterns with which to test an integrated circuit chip includes receiving, by an input device of the general purpose computing device, statistical timing information relating to the integrated circuit chip and a logic circuit of the integrated circuit chip and generating, by a processor of the general purpose computing device, the set of test patterns in accordance with the statistical timing information while simultaneously selecting a set of paths on which to test the set of test patterns.

Claims

1. A method for use by a general purpose computing device that is configured to generate a set of test patterns with which to test an integrated circuit chip, the method comprising:

generating, by a processor of the general purpose computing device, the set of test patterns; and

selecting, by the processor of the general purpose computing device, a set of paths on which to test the set of test patterns, wherein the selecting comprises;

sensitizing one or more potential paths for inclusion in the set of paths, wherein the sensitization is performed as the one or more potential paths are traversed, and wherein the sensitizing comprises, for each given path in the one or more potential paths, traversing the given path through a combined graph in order to assess an impact of the given path on the set of test patterns, wherein the combined graph merges a logical representation of the integrated circuit chip with a timing graph for the integrated circuit chip, and wherein the traversing comprises;

determining that a current node of the given path is a branch point for the given path, such that two or more sub-paths propagate from the current node;

propagating values of a required transition at the current node backward along a selected one of the two or more sub-paths that appears most promising;

performing said determining and propagating at a previous branch point in the given path, when none of the two or more sub-paths propagating from the current node appear promising, wherein the performing said determining and propagating at a previous branch point removes sensitization information previously set for sensitizing a part of the given path between the current node and the previous branch point;

setting, at each node of the given path, the required transition, wherein the setting comprises computing a pair comprising;

a signal that produces the required transition along at least one of the one or more potential paths and a unique identifier of the current node; and

justifying the values of the required transition by propagating the values forward and backward along circuits of the integrated circuit chip.

2. The method of claim 1, wherein the sensitization information that is removed is determined using the unique identifier.

3. The method of claim 2, wherein pairs in the sensitization information that have a unique identifier matching a unique identifier of the current node.

4. The method of claim 1, wherein the traversing further comprises:

determining that a current node of the given path is an endpoint for the given path; and

adding the given path to the set of paths.

5. The method of claim 4, further comprising:

filtering the given path in accordance with one or more criteria prior to adding the given path to the set of paths.

6. The method of claim 5, wherein the filtering comprises:

removing the given path from the set of paths when addition of the given path to the set of paths does not improve coverage of the integrated circuit chip.

7. The method of claim 1, wherein the generating comprises:

obtaining a logical representation of the integrated circuit chip;

obtaining a timing graph for the integrated circuit chip; and

merging the logical representation with the timing graph to form a combined graph.

8. The method of claim 7, wherein the merging comprises:

annotating one or more nodes of the logical representation with corresponding statistical arrival times and required arrival times; and

annotating one or more edges of the logical representation with corresponding statistical delays.

9. The method of claim 1, wherein the unique identifier comprises a distance between a current node of the given path and an output of the given path.

10. A computer readable storage medium containing an executable program for generating a set of test patterns with which to test an integrated circuit chip, where the program performs steps of:

generating the set of test patterns; and

selecting a set of paths on which to test the set of test patterns, wherein the selecting comprises;

sensitizing one or more potential paths for inclusion in the set of paths, wherein the sensitization is performed as the one or more potential paths are traversed, and wherein the sensitizing comprises, for each given path in the one or more potential paths, traversing the given path through a combined graph in order to assess an impact of the given path on the set of test patterns, wherein the combined graph merges a logical representation of the integrated circuit chip with a timing graph for the integrated circuit chip, and wherein the traversing comprises;

determining that a current node of the given path is a branch point for the given path, such that two or more sub-paths propagate from the current node;

propagating values of a required transition at the current node backward along a selected one of the two or more sub-paths that appears most promising;

performing said determining and propagating at a previous branch point in the given path, when none of the two or more sub-paths propagating from the current node appear promising, wherein the performing said determining and propagating at a previous branch point removes sensitization information previously set for sensitizing a part of the given path between the current node and the previous branch point;

setting, at each node of the given path, the required transition, wherein the setting comprises computing a pair comprising;

a signal that produces the required transition along at least one of the one or more potential paths and a unique identifier of the current node; and

justifying the values of the required transition by propagating the values forward and backward along circuits of the integrated circuit chip.

11. The computer readable storage medium of claim 10, wherein the generating comprises:

obtaining a logical representation of the integrated circuit chip;

obtaining a timing graph for the integrated circuit chip; and

merging the logical representation with the timing graph to form a combined graph.

12. The computer readable storage medium of claim 11, wherein the traversing further comprises:

determining that a current node of the given path is an endpoint for the given path; and

adding the given path to the set of paths.

13. The computer readable storage medium of claim 12, further comprising:

filtering the given path in accordance with one or more criteria prior to adding the given path to the set of paths.

14. The computer readable storage medium of claim 10, wherein the unique identifier comprises a distance between a current node of the given path and an output of the given path.

15. Apparatus for generating a set of test patterns with which to test an integrated circuit chip, the apparatus comprising:

means for generating the set of test patterns; and

means for selecting a set of paths on which to test the set of test patterns, wherein the means for selecting comprises;

means for sensitizing one or more potential paths for inclusion in the set of paths, wherein the sensitization is performed as the one or more potential paths are traversed, and wherein the sensitizing comprises, for each given path in the one or more potential paths, traversing the given path through a combined graph in order to assess an impact of the given path on the set of test patterns, wherein the combined graph merges a logical representation of the integrated circuit chip with a timing graph for the integrated circuit chip, and wherein the traversing comprises;

determining that a current node of the given path is a branch point for the given path, such that two or more sub-paths propagate from the current node;

propagating values of a required transition at the current node backward along a selected one of the two or more sub-paths that appears most promising;

performing said determining and propagating at a previous branch point in the given path, when none of the two or more sub-paths propagating from the current node appear promising, wherein the performing said determining and propagating at a previous branch point removes sensitization information previously set for sensitizing a part of the given path between the current node and the previous branch point;

setting, at each node of the given path, the required transition, wherein the setting comprises computing a pair comprising;

a signal that produces the required transition along at least one of the one or more potential paths and a unique identifier of the current node; and

justifying the values of the required transition by propagating the values forward and backward along circuits of the integrated circuit chip.