System and method for incremental statistical timing analysis of digital circuits

Abstract

The present invention is a system and method for efficiently and incrementally updating the statistical timing of a digital circuit after a change has been made in the circuit. One or more changes in the circuit is/are followed by timing queries that are answered efficiently, constituting a mode of timing that is most useful in the inner loop of an automatic computer-aided design (CAD) synthesis or optimization tool. In the statistical re-timing, the delay of each gate or wire is assumed to consist of a nominal portion, a correlated random portion that is parameterized by each of the sources of variation and an independent random portion. Correlations are taken into account. Both early mode and late mode timing are included; both combinational and sequential circuits are handled; static CMOS as well as dynamic logic families are accommodated.

1 . A system for incremental statistical timing analysis of an electrical circuit comprising:
 a. a results input for receiving one or more results of a first statistical timing analysis;   b. a change input for receiving one or more changes to the electrical circuit;   c. a query input for receiving one or more statistical timing queries that request updated statistical timing information about the electrical circuit; and   d. an incremental statistical timing process that provides the one or more answers to the respective queries as an output of the system, the answer being the requested statistical timing information for the electrical circuit with the changes.   
   
   
       2 . A system, as in  claim 1 , where the query is one or more of: a statistical arrival time at a node, a statistical required arrival time at a node, a statistical slack at a node, a statistical slew at a node, an arrival tightness probability of an edge, a required arrival tightness probability of an edge, a criticality probability of an edge, a criticality probability of a node, and a probability of a timing test being met. 
   
   
       3 . A system, as in  claim 2 , where the query requests one or more of the following: a mean, a variance, an independent random part, a sensitivity to a source of variation, a confidence level, and an entire probability distribution of a statistical timing quantity. 
   
   
       4 . A system, as in  claim 1 , where the query requests a criticality of one or more paths through the electrical circuit. 
   
   
       5 . A system, as in  claim 1 , where the query requests a listing of one or more paths through the electrical circuit with the highest probability of being critical. 
   
   
       6 . A system, as in  claim 1 , where the query requests a listing of a required number of paths through the electrical circuit in order of criticality probability. 
   
   
       7 . A system, as in  claim 1 , where the query requests a listing of one or more critical paths through the electrical circuit in order of criticality probability until the sum of the criticality probabilities exceeds a required probability threshold. 
   
   
       8 . A system, as in  claim 2 , where the query requests one or more of: a late mode statistical timing quantity, an early mode statistical timing quantity, a rising statistical timing quantity, and a falling statistical timing quantity. 
   
   
       9 . A system, as in  claim 1 , where the change is one or more of: a removal of a wire, an addition of a wire, a buffering of a wire, a removal of a gate, an addition of a gate, a removal of a latch, an addition of a latch, a removal of a clock phase, an addition of a clock phase, and a change in the operating conditions under which timing is performed. 
   
   
       10 . A system, as in  claim 9 , in which a change to the electrical circuit is the undoing of the previous change to the electrical circuit. 
   
   
       11 . A system, as in  claim 1 , where the electrical circuit is one of a combinational circuit and a sequential circuit. 
   
   
       12 . A system, as in  claim 1 , where the electrical circuit contains one or more of: a master-slave latch, a transparent latch, a dynamic circuit, and a flip-flop. 
   
   
       13 . A system, as in  claim 1 , where the electrical circuit has multiple clock phases. 
   
   
       14 . A system, as in  claim 1 , where a delay of each of one or more components of the electrical circuit is modeled as the sum of one or more of a constant part, a correlated random part, and an independent random part. 
   
   
       15 . A system, as in  claim 14 , where the correlated random part of the delay of each component is a function of one or more common sources of variation. 
   
   
       16 . A system, as in  claim 1 , where a first statistical timing analysis propagates timing values as a weighted sum of probability distributions of one or more of the sources of variation.