Method and apparatus for statistical path selection for at-speed testing

1. A method for selecting at least one path of an integrated circuit chip for at-speed testing, the method comprising:

computing a cumulative process coverage metric for a plurality of paths in the integrated circuit chip, wherein a process coverage metric for a given path in the plurality of paths is a value that directly defines a probability that the integrated circuit chip will have no timing violations if the given path passes at-speed testing; and

selecting, from among the plurality of paths, the at least one path that maximizes a value of the cumulative process coverage metric for the plurality of paths,

wherein at least one of the computing and the selecting is performed using a processor.

2. The method of claim 1 , wherein the process coverage metric for the given path is computed using results from statistical static timing of the integrated circuit chip.

3. The method of claim 1 , wherein the selecting is performed in accordance with a branch and bound algorithm that traverses each of the plurality of paths in a backward manner from an end point to a start point.

4. The method of claim 1 , wherein the computing comprises, for each of the plurality of paths;

calculating, at each node in a given sub-path, the process coverage metric for each path that passes through the node along the sub-path;

identifying a path passing through the node for which the process coverage metric is best;

continuing traversal of the sub-path along the identified path to a next node, if the process coverage metric for the identified path is better than a process coverage metric of a currently identified best path; and

investigating an alternate path, if the process coverage metric for the identified path is not better than a process coverage metric of the currently identified best path.

5. The method of claim 4 , further comprising:

iterating the calculating, identifying, continuing, and investigating until a start point is reached, at which point a complete path is obtained.

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

comparing the process coverage metric for the complete path to the process coverage metric of the currently identified best path; and

replacing the currently identified best path with the complete path, if the process coverage metric computed for the complete path is better than the process coverage metric computed for the currently identified best path.

7. The method of claim 4 , wherein traversal of the sub-path begins at a start point of a timing graph and proceeds forward toward an end point of the timing graph.

8. The method of claim 4 , wherein traversal of the sub-path begins at an end point of a timing graph and proceeds backward toward a start point of the timing graph.

9. The method of claim 4 , wherein traversal of the sub-path begins at an interior node of a timing graph and proceeds either forward toward an end point of the timing graph or backward toward a start point of the timing graph.

10. The method of claim 1 , wherein the computing comprises, for each of the plurality of paths:

calculating, at each node in a given sub-path, the process coverage metric for each path that passes through the node along the sub-path;

identifying a path passing through the node for which the process coverage metric is best; and

continuing traversal of the sub-path along the identified path to a next node, if the process coverage metric for the identified path is better than a process coverage metric of a worst path in a set of best paths.

11. The method of claim 10 , further comprising:

iterating the calculating, identifying, continuing, and investigating until a start point is reached, at which point a complete path is obtained.

12. The method of claim 11 , wherein the selecting comprises:

comparing the process coverage metric for the complete path to the process coverage metric of the worst path; and

replacing the worst path with the complete path, if the process coverage metric computed for the complete path is better than the process coverage metric computed for the worst path.

13. The method of claim 1 , wherein the computing comprises, for each of the plurality of paths;

calculating, at each node in a given sub-path, the process coverage metric for each path that passes through the node along the sub-path;

identifying a path passing through the node for which the process coverage metric is best; and

continuing traversal of the sub-path along the identified path to a next node, if replacement of a worst path in a set of best paths with the identified path will result in a better cumulative process coverage metric for the set of paths.

14. The method of claim 13 , further comprising:

iterating the calculating, identifying, continuing, and investigating until a start point is reached, at which point a complete path is obtained.

15. The method of claim 14 , wherein the selecting comprises:

comparing the process coverage metric for the complete path to the process coverage metric of the worst path; and

replacing the worst path with the complete path, if the replacement will result in a better cumulative process coverage metric for the set of paths.

16. The method of claim 1 , wherein the method is applied in the field of critical path reporting.

17. The method of claim 1 , wherein the method is applied in the field of a common path pessimism reduction.

18. The method of claim 1 , wherein the method is applied in the field of chip binning.

19. The method of claim 1 , wherein the method is applied in the field of yield optimization.

20. The method of claim 1 , wherein the at least one path is selected to detect late mode setup violations.

21. The method of claim 1 , wherein the at least one path is selected to detect early mode hold violations.

22. A computer readable storage device containing a program for selecting at least one path of an integrated circuit chip for at-speed testing, where the program is executable by a computer and performs steps of:

computing a cumulative process coverage metric for a plurality of paths in the integrated circuit chip, wherein a process coverage metric for a given path in the plurality of paths is a value that directly defines a probability that the integrated circuit chip will have no timing violations if the given path passes at-speed testing; and

selecting, from among the plurality of paths, the at least one path that maximizes a value of the cumulative process coverage metric for the plurality of paths.

23. The computer readable device of claim 22 , wherein the computing comprises, for each of the plurality of paths;

calculating, at each node in a given sub-path, the process coverage metric for each path that passes through the node along the sub-path;

identifying a path passing through the node for which the process coverage metric is best;

continuing traversal of the sub-path along the identified path to a next node, if the process coverage metric for the identified path is better than a process coverage metric of a currently identified best path; and

investigating an alternate path, if the process coverage metric for the identified path is not better than a process coverage metric of the currently identified best path.

24. Apparatus for computing a metric for selecting at least one path of an integrated circuit chip for at-speed testing, the apparatus comprising:

means for computing a cumulative process coverage metric for a plurality of paths in the integrated circuit chip, wherein a process coverage metric for a given path in the plurality of paths is a value that directly defines a probability that the integrated circuit chip will have no timing violations if the given path passes at-speed testing; and

means for selecting, from among the plurality of paths, the at least one path that maximizes a value of the cumulative process coverage metric for the plurality of paths.

25. The method of claim 1 , wherein the value of the cumulative process coverage metric increases as a number of paths in the plurality of paths increases.