Method and apparatus for efficient incremental statistical timing analysis and optimization

1. A method for determining an incremental extrema for a set of n random variables, given a change to at least one of the n random variables from a first value to a second value, the method comprising:

obtaining the n random variables;

obtaining a first extrema for the n random variables, the first extrema comprising an extrema computed prior to the change to the at least one of the n random variables;

removing the at least one of the n random variables to form an (n−1) subset;

computing a second extrema for the (n−1) subset in accordance with the first extrema and the first value of the at least one of the n random variables; and

outputting a third extrema computed as an extrema of the second extrema and the second value of the at least one of the n random variables as the incremental extrema for the set of n random variables,

wherein at least one of the removing or the computing is performed using a processor.

2. The method of claim 1 , wherein a plurality of the n random variables is changed, each of the plurality of the n variables being changed from a respective first value to a respective second value, and wherein the method further comprises:

performing one or more iterations of said obtaining the n random variables, obtaining a first extrema, said removing, said computing, and said outputting, wherein during each of said one or more iterations one of the plurality of n random variables is removed during the removing.

3. The method of claim 1 , wherein the incremental extrema is a minimum value of the set of n random variables.

4. The method of claim 1 , wherein the incremental extrema is a maximum value of the set of n random variables.

5. The method of claim 1 , wherein the n random variables comprise timing data for an integrated circuit chip.

6. The method of claim 5 , wherein the change to the at least one of the n random variables is the result of an incremental change made to the integrated circuit chip.

7. The method of claim 6 , wherein the incremental change comprises one of: buffer insertion, pin swapping, layer assignment, or cell sizing.

8. The method of claim 5 , wherein the method is implemented in accordance with an incremental timing operation.

9. The method of claim 5 , wherein the method is implemented in accordance with a yield computation operation.

10. The method of claim 5 , wherein the method is implemented in accordance with a yield prediction operation.

11. The method of claim 5 , wherein the method is implemented in accordance with a chip slack computation operation.

12. A computer readable storage device containing an executable program for determining an incremental extrema for a set of n random variables, given a change to at least one of the n random variables from a first value to a second value, where the program performs the steps of:

obtaining the n random variables;

obtaining a first extrema for the n random variables, the first extrema comprising an extrema computed prior to the change to the at least one of the n random variables;

removing the at least one of the n random variables to form an (n−1) subset;

computing a second extrema for the (n−1) subset in accordance with the first extrema and the first value of the at least one of the n random variables; and

outputting a third extrema computed as an extrema of the second extrema and the second value of the at least one of the n random variables as the incremental extrema for the set of n random variables.

13. The computer readable storage device of claim 12 , wherein a plurality of the n random variables is changed, each of the plurality of the n variables being changed from a respective first value to a respective second value, and wherein the method further comprises:

performing one or more iterations of said obtaining the n random variables, obtaining a first extrema, said removing, said computing, and said outputting, wherein during each of said one or more iterations one of the plurality of n random variables is removed during the removing.

14. The computer readable storage device of claim 12 , wherein the incremental extrema is a minimum value of the set of n random variables.

15. The computer readable storage device of claim 12 , wherein the incremental extrema is a maximum value of the set of n random variables.

16. The computer readable storage device of claim 12 , wherein the n random variables comprise timing data for an integrated circuit chip.

17. The computer readable storage device of claim 16 , wherein the change to the at least one of the n random variables is the result of an incremental change made to the integrated circuit chip.

18. The computer readable storage device of claim 17 , wherein the incremental change comprises one of: buffer insertion, pin swapping, layer assignment, or cell sizing.

19. The computer readable storage device of claim 16 , wherein the method is implemented in accordance with an incremental timing operation.

20. The computer readable storage device of claim 16 , wherein the method is implemented in accordance with a yield computation operation.

21. The computer readable storage device of claim 16 , wherein the method is implemented in accordance with a yield prediction operation.

22. The computer readable storage device of claim 16 , wherein the method is implemented in accordance with a chip slack computation operation.

23. A method for computing an incremental yield of a circuit, the method comprising:

changing a delay across an edge in the circuit;

computing a first value equal to a statistical maximum of path delays for paths not going through the edge;

computing a second value equal to a statistical maximum of path delays for paths going through the edge;

outputting a statistical maximum of the first value and the second value as the maximum of all paths delays in the circuit; and

predicting the incremental yield of the circuit in accordance with the maximum of all paths delays in the circuit

wherein at least one of: the changing, the computing the first value, the computing the second value, or the predicting is performed using a processor.

24. A method for determining an extrema for an (n−1) subset of a set of n random variables, given an extrema for the set of n random variables, the method comprising:

obtaining the n random variables;

obtaining the extrema for the n random variables;

removing one of the n random variables to form the (n−1) subset; and

computing the extrema for the (n−1) subset in accordance with the extrema of the set of n random variables and a value of the one of the n random variables that is removed,

wherein at least one of the removing or the computing is performed using a processor.