System and method for efficient statistical timing analysis of cycle time independent tests

Abstract

A system performing selected timing comparisons in a digital electronic design includes propagating from signal sources to timing comparisons of one or multiple signal labels. The signal label includes signal source identifiers and signal path cycle adjust information. Timing comparisons are determined in which signal label values at each input of the timing comparison are required to compute the selected timing comparisons. The propagation back from the timing comparisons are needed signal labels, followed by the propagation and computing timing data from the signal source applied to the propagated signal labels corresponding to the required signal labels.

Claims

1. A system for statistical static timing analysis (SSTA) of a digital electronic design, the system comprising: one or more computer processors, one or more computer-readable storage media, and program instructions stored on the one or more computer-readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising: program instructions to propagate, using a computer, a signal label from a signal source to a cycle time dependent timing test, the signal label comprising at least one of: a signal source identifier, and a signal path cycle adjust information; program instructions to identify, at each input of the cycle time dependent timing test, which timing values of the signal label are needed to compute a downstream cycle time independent timing test; program instructions to propagate back from the cycle time dependent timing test to the signal source a flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test; program instructions to compute timing data only for the identified values of the signal label which are needed to compute the downstream cycle time independent timing test; program instructions to generate a final circuit design based on the computed timing data; and program instructions to cause the final circuit design to be fabricated.

2. The system of claim 1, wherein the signal path cycle adjust information includes a cumulative cycle adjust quantity.

3. The system of claim 2, wherein the cumulative cycle adjust quantity comprises at least one segment adjust quantity.

4. The system of claim 1, wherein the program instructions to propagate the signal label further comprises: program instructions to store on a node a union of the signal label propagated to the node from predecessor nodes.

5. The system of claim 1, wherein the downstream cycle time independent timing test further comprises cycle time independent timing tests performed during a product stress testing.

6. The system of claim 1, further comprising: program instructions to specify, by the signal source identifier, a synchronous domain to identify the signal source.

7. The system of claim 1, wherein the downstream cycle time independent timing test excludes comparisons between signal labels comprising different synchronous domain specifications.

8. The system of claim 1, wherein the cycle time dependent timing test comprises same mode tests, domino tests, tests involving multiple clock domains, user-specified tests, tests within abstracted library elements, asserted arrival time constraints, point to point delay constraints, skew tests, window tests, and any combination thereof.

9. The system of claim 1, wherein the program instructions to propagate back the flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test further comprises: program instructions to propagate, by at least one outgoing edge, a flag set to true for a given node.

10. The system of claim 1, wherein the program instructions to propagate back the flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test further comprises: program instructions to propagate, by at least one test, a flag set to true for a given node.

11. The system of claim 1, wherein the program instructions to propagate back the flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test further comprises: program instructions to set the flag as false when no outgoing edge propagates an arrival time (AT) needed value set as true for a given node.

12. The system of claim 1, wherein the timing data comprises statistical AT, slew and delay values.

13. The system of claim 1, further comprising: program instruction to compute a unique flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test for each signal label among the union of corresponding signal labels.

14. The system of claim 1, wherein the signal label and the flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test are incrementally re-propagated responsive to at least one design change.

15. The system of claim 14, wherein the at least one design change comprises at least one of a topological change to a timing graph, an introduction of at least one new timing test, and a modification of adjust values.

16. The system of claim 1, further comprising: program instructions to introduce new test points resulting in additional value needed propagations; and program instructions to change the timing graph topology causing changes in the signal label and the flag indicating the identified timing values of the signal label needed to compute the downstream cycle time independent timing test.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying drawings, which are incorporated in and which constitute part of the specification, illustrate the presently preferred embodiments of the invention which, together with the general description given above and the detailed description of the preferred embodiments given below serve to explain the principles of the invention.

(2) FIG. 1 shows a flowchart illustrating an embodiment of the present invention.

(3) FIG. 2 is an exemplary circuit used to illustrate an embodiment of the present invention.

(4) FIG. 3 depicts a forward-levelized timing graph applied to the aforementioned exemplary circuit.

(5) FIG. 4 shows a table listing nodes of the aforementioned timing graph, and illustrating the propagation from a signal source to a timing comparison having a signal label, the signal label including at least one signal source identifier, and signal path cycle adjust information.

(6) FIG. 5 shows a table listing the nodes of the aforementioned timing graph, illustrating the propagation back from the timing comparisons needed signal labels.

DETAILED DESCRIPTION

(7) The present invention and various features, aspects and advantages thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description.

Glossary of Terms

(8) In order to clarify the meaning of terms recited in the disclosure, a glossary of the terms as defined is added herein below:

(9) Adjust: Modification of a timing quantity typically specified by the application of a timing constraint.

(10) Segment adjust: A particular type of adjust applied to values propagating through a particular edge of the timing graph.

(11) Cumulative adjust: Sum total of adjusts along a path.

(12) Forward propagation: Propagation of values along the direction of directed edges in a timing graph.

(13) Backward propagation: Propagation of values in the direction opposite to directed edges in a timing graph (e.g., propagation from sink node to a source node).

(14) Signal source: A node within a timing graph containing a user-specified arrival time.

(15) Signal source identifier: Phase tag or other flag indicating the signal source of a given arrival time or slew value.

(16) Referring to FIG. 1, an embodiment of the disclosure is illustrated, wherein Step 101 begins with forward propagating from one or more signal sources to one or more timing tests a signal label consisting of at least one signal source identifier, and corresponding cumulative adjust information.

(17) In Step 102, wherein at one or more timing test, a determination is made of which signal labels are required to perform the timing test.

(18) In Step 103, the determination of the signal labels required to perform a timing test is followed by propagating back from at least one timing test value needed flags for signal labels.

(19) In Step 104, the propagation and computation of timing data occurs only for the propagated signal labels where a value is necessitated.

(20) Referring now to FIG. 2, a non-limiting simple exemplary circuit diagram is shown to illustrate an application of an embodiment. In the simple exemplary illustrative circuit, early and late mode arrival times are assumed to be asserted at the input “A” of box201. For the purpose of clarity, both the output L2 of box205 and the input D box 203 are left as open circuits. Box201 and box202 are buffers that propagate a clock signal to clock inputs of box203 and box205 intending to illustrate edge-sensitive storage elements (e.g., flip-flops). Similarly, box204 depicts a buffer propagating a data signal from the L2 output of box203 to D input of box205.

(21) A user-specified full clock period adjust at the Z output of box204 is shown (in general, such adjust values can be stored on a node, an edge, a path, or any combination thereof, in which an embodiment accommodates all of such forms). For the purpose of simplicity, a full clock period adjust is chosen in the illustrative example, although in an embodiment it can be applied in the presence of arbitrary timing adjusts. The value of individual adjusts need not to be exactly equal to the clock period, e.g., multiple adjusts can accumulate along a path that taken together, add to the greatest common divisor GCD of the launch and capture clock cycles.

(22) Referring to FIG. 3, a forward levelized timing graph representation of the above simple non-limiting illustrative circuit is shown. Such a timing graph is typically constructed ahead of the propagating timing information, although it can also occur in concert with the propagation of any timing flags or values. Multiple timing tests (i.e., setup and hold) are depicted between input box205/D and box205/C.

(23) Referring to FIG. 4, the resulting signal labels are obtained when applying the aforementioned Step 101 of FIG. 1 previously described, as applied to the timing graph of the exemplary circuit. In a simple non-limiting illustration it as assumed that the asserted arrival time at box201/A is cycle time independent. Therefore, a value of zero cycle adjust propagates forward from box201/A. In an embodiment, all general cases are asserted where arrival times can themselves be cycle time dependent and consequently, a non-zero cycle adjust value can immediately begin propagating forward from the asserted signal source(s). The value of a zero total adjust continues to propagate forward until a user-specified timing adjust of one clock cycle is encountered at box204/Z. It is worth noting that adjusts are recorded for both the early and the late mode transitions. For the purpose of simplicity, in the non-limiting example, the same user-specified adjust value is shown to be applied in both the early and late modes, where distinctions between the rise and fall transitions have been omitted. An embodiment of the disclosure can accommodate all the general cases where unique adjust values are propagated for early and late modes, and where unique adjusts are propagated for the rise and the fall transitions thereof. Furthermore, in the simple exemplary illustration, for the purpose of determining a signal source label, a single synchronous clock domain referenced as “C” is assumed. Nonetheless, an embodiment of the present invention accommodates all the generalizations of signal source labels, including propagation of multiple such labels, e.g., in order to store timing values unique to multiple synchronous clock domains per graph node, unique labels for the early versus the late mode and unique labels for rising and falling transitions thereof.

(24) For further illustration, in a non-limiting example shown in FIG. 4 it is assumed that the signal labels are forward propagated in a breadth-first forward propagated fashion. There are multiple ways of forward the propagating information in the levelized graph, and an embodiment accommodates all possible forward propagation methods, including demand-driven (i.e., propagation to a specific node of interest), and all combinations of depth and breadth-first traversal. During the propagation of signal labels, it is possible to encounter a graph node which has multiple incoming edges (e.g., FIG. 3 box203/L2). When multiple incoming edges are present, the union of signal labels is retained.

(25) FIG. 5 illustrates the application of Steps 102 and 103 of FIG. 1 previously described, to the timing graph of the exemplary circuit. In the present example, FIG. 1 Step 102 applies to nodes box205/D and box205/C that are involved in both setup and hold tests with respect to each other.

(26) Focusing first on the setup test case, the general slack equation for a setup test is:
SLACK=EARLY CLOCK AT−LATE DATA AT+CYCLE ADJUST.

(27) Applying to the aforementioned nodes,
SLACK=EARLY AT (205/C)−LATE AT (205/D)+CYCLE ADJUST (ONE CLOCK PERIOD)

(28) Referring back to FIG. 4, it has been determined that box205/D has a cumulative adjust of −1 clock period, whereas box205/C has zero cumulative adjust. Plugging adjusts in the aforementioned setup slack equation, it is evident that the setup test between box205/D and box205/C is a cycle time independent (since adjust −1 clock period for box205/D cancels out the CYCLE ADJUST+1 clock period in the setup slack equation above). Therefore, the LATE mode AT value for box205/D is required for a cycle time independent test (e.g., for the setup test against box205/C), and the same can be for the EARLY mode AT value for box205/C.

(29) Focusing next on a hold test case, the general slack equation for the hold test is
SLACK=EARLY DATA AT−LATE CLOCK.

(30) Applying to the aforementioned nodes,
SLACK=EARLY AT((205/D)−LATE AT (205/C).

(31) Referring back to FIG. 4, it is determined that box205/D has a cumulative adjust −1 cycle, whereas box205/C has zero cumulative adjust. Plugging adjusts to the hold slack equation above, it is evident that the hold test between box205/D and box205/C is cycle time dependent (i.e., the slack will vary as a function of clock cycle time due to the fact that the EARLY AT for box205/D has a cycle time dependent adjust). Therefore, the EARLY mode AT value for box205/D is not required for a cycle time independent test (i.e., the only test that the EARLY mode AT for box205/D is involved with is a hold test, and as described previously, the particular hold test is cycle time dependent). The same applies to the LATE mode AT value for box205/C.

(32) Still referring back to FIG. 1, Step 103 applies to all predecessor nodes of box205/D and 205/C by back-propagating “AT needed for a downstream cycle time independent test” values (abbreviated “AT needed” hereinafter), resulting in a remainder of the values shown in FIG. 5. Generally, for any node having at least one outgoing edge, test edge, the “AT needed” flag is set to true if at least one outgoing edge propagates an “AT needed” value of true, or at least one test contributes an “AT needed” value of true, in accordance with the embodiment related to FIG. 1, Step 102. Otherwise, if no outgoing edge propagates an “AT needed” value true, and neither does any test, the “AT needed” flag is set false, as is the case for box205/L2 in the aforementioned example. If multiple signal labels propagate in accordance with FIG. 1 Step 101, then each signal label is assigned its own “AT needed” flag, in accordance with FIG. 1 Step 103 and the aforementioned description.

(33) It should be noted that while the example above referred to specific instances of setup and hold tests, the present invention accommodates all timing tests, including same mode tests, domino tests, tests involving multiple clock domains, tests involving user specified constraints on the alignment of launch and capture edges, user-specified tests, domino tests, tests within abstracted library elements, asserted arrival time constraints, point to point delay constraints, skew tests, window tests, and any combination thereof. Furthermore, while the example above focused on indentifying cycle time independent tests for statistical timing analysis, the present invention also accommodates the identification of cycle time independent tests performed during product stress testing, as well as for identifying cycle time dependent tests. And furthermore, in cases involving multiple synchronous clock domains, the present invention also accommodates excluding tests between pairs of non-synchronous clocks, and marking corresponding AT values as “value needed” false where non-synchronous relationships disable a timing test.

(34) Additionally, with reference to the example above, timing data (including statistical AT, slew and delay values) are propagated and computed only for those signal identifiers for which an “AT needed” flag is set to true.

(35) Moreover, the aforementioned steps can be performed in an incremental fashion, i.e., causing signal labels and value needed flags to be updated in response to a design change, after an initial timing propagation has occurred. For example, if a new adjust is added, cumulative adjust values can be updated, which in turn may cause “value needed” flags to change based on new cumulative adjusts propagating to tests. Similarly, the introduction of new test points may result in additional “value needed” propagations. And similarly, changes in timing graph topology can cause changes in both signal labels and “value needed” flags. Such incremental propagation may occur through well-known means, such as the use of delta lists and queues, which can be further processed using well-known techniques of level-limiting to minimize recalculation efforts.

(36) Finally, the present invention can be realized in hardware, software, or a combination of hardware and software. The present invention can further be realized in a centralized fashion in one computer system or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods described herein—is suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein.

(37) Embodiments of the disclosure can be embedded in a computer program product, which includes all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out these methods.

(38) Computer program means or computer program in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation and/or reproduction in a different material form.

(39) While the present invention has been particularly described in conjunction of a simple illustrative embodiment, it is to be understood that one of ordinary skill in the art can extend and apply this invention in many obvious ways. In the embodiments described herein, for purposes of clarity, rising and falling timing quantities were not differentiated, but one of ordinary skill in the art could apply the present invention to a situation with different rising and falling delays, slews, ATs and RATs. Embodiments of the invention apply to any type of static timing analysis, including but are not limited to both deterministic (e.g., single corner) and statistical timing of gate-level circuits, transistor-level circuits, hierarchical circuits, circuits with combinational logic, circuits with sequential logic, timing in the presence of coupling noise, timing in the presence of multiple-input switching, timing in the presence of arbitrary timing tests such as setup, hold, end-of-cycle, pulse width, clock gating and loop-cut tests, and timing in the presence of multiple clock domains. It is also evident that many alternatives, modifications and variations will be apparent to those skilled in the art in light of the present description.

(40) It is therefore contemplated that the appended claims will embrace any such alternatives, modifications and variations as falling within the true scope and spirit of the present invention.