Automatic Delay Adjustment for Static Timing Analysis

This invention is in the field of logic timing analysis, and particularly concerns the problem in logic circuit timing analysis of adjusting a path delay to account for the effect of phase differences between clock signals which drive data signals on the path.

In static timing analysis, the logic design of a circuit is analyzed to identify timing problems in the design. The logic design is analyzed by propagating cumulative path delays from the inputs of the circuit to its outputs in a single pass. A timing problem arises at a point in the circuit which joins two circuit paths when the signal along one of the paths arrives at the point with an improper timing relationship to the signal along the second path.

Static timing analysis, therefore, concerns a point-by-point analysis of a logic circuit in which all possible paths to the current point are analyzed to detect timing problems. This is contrasted with dynamic timing analysis in which logic circuit operation is simulated. One example of static timing analysis is found in U.S. Pat. No. 4,263,651, which is commonly assigned with this application.

Static timing analysis proceeds by propagating maximum delays from the inputs to the outputs of a design in a single pass through the design. Assuming that the design includes clocked elements such as latches, the single-pass analysis means that such elements would be clocked only once during the analysis. If data is generated at the output pin of the clocked element (the "source" element) later than it is expected to be clocked into the input pin of the next downstream clocked element (the "sink" element), the data will appear to be too late from the standpoint of the sink latch. This anomaly is resolved by making a timing adjustment to the delay value which is propagated out of the output pin of the source latch. The timing adjustment is made by subtracting a clock cycle from the delay value so that the data will appear to have been clocked out of the output pin during the clock cycle preceding that during which it is clocked into the downstream input pin.

An example of the timing adjustment problem is illustrated in FIG. 1. FIG. 1 illustrates how delay adjustments are made according to prior art static timing analysis methods. FIG. 1 illustrates a logic circuit design consisting of a plurality of circuit elements, called "blocks". Each block represents a particular kind of logic element and includes one or more input ports on its left-hand side and one or more output ports on its right-hand side. In FIG. 1, two distinct kinds of circuit elements are illustrated. Blocks (BLKS) 1, 2, 3, and 5 are clocked circuit elements called latches. Each latch consists of two elements, one including a data input pin D0, a clock input pin C0, and an output pin 10. The second element has a data input internally connected to the first element and uses the B0 input pin for clocking into the second element. Each latch is fed a clock signal consisting of two clock waveforms. Data presented to the D0 input enters the first element while the clock input to the C0 input pin has a positive level. The data is latched or retained in the first element at the rising edge of the clock input to the C0 pin. The data in the second element is thus available as the output at the next rising edge of the clock waveform at the B0 input pin.

Block 4 is representative of non-clocked combinatorial logic elements such as gates, inverters, and the like. In FIG. 1, block 4 represents an AND gate with two input pins A0 and A1 and a single output pin 10.

In the logic design of FIG. 1, any block whose output is provided to an input of another block in the design is termed a "source" block. Any input pin in the logic design of FIG. 1 which does not receive a signal from a source block in the logic design is termed a "primary" input, while the output of any block in the logic design which is not connected to the input of another block in the same logic design is termed a "primary" output.

The logic design of FIG. 1 employs multiple-phase system clocking in which the operations of clocked elements are controlled by a plurality of clock signals. These clock signals are illustrated in FIG. 2, and are interlaced in that all the clock signals have the same frequency, but separate respective phases. FIG. 2 illustrates four clocks T0, T1, T2, and T3. One system clock cycle of the logic design of FIG. 1 comprises an interlaced sequence of four staggered clock pulses, one from each of the respective clock signals T0-T3. The cycle length is 100 timing units; each clock signal has a pulse width of 20 timing units from rising to falling edge; and the falling edge of each clock signal is separated from the rising edge of the next clock signal by five timing units.

Returning to the description of timing adjustment according to prior art static timing analysis in FIG. 1, a goal of the procedure is to determine, for example, whether any timing problems exist between a data signal input to the input pin D0 of block 3 and the T1 clock input to the C0 input of the block. The analysis regards the arrival time of a signal produced from the output pin of block 4 with respect to the occurrence of the rising edge of the T1 clock. If the arrival time of the data signal precedes the rising edge of the T1 clock, the signal will be latched; otherwise, the rising edge of the T1 will latch an incorrect signal into the block. The output pin of block 4 produces the signal in response to signals produced by block 1 and block 2. Each of these signals has respective delay characteristics, and either can affect the output of block 4. Therefore, the timing analysis with respect to block 3 must take into consideration the fact that the output of block 4 can change at different times, depending upon the outputs of blocks 1 and 2.

As should be evident from the foregoing discussion, static timing analysis operates by tracing back the paths through the logic design from a point where the analysis is being conducted. Thus, if analysis is being conducted at the input of block 3, static timing analysis traces back the paths which feed input pin D0. The paths are rearwardly traced to those primary inputs which ultimately drive the pin of interest. In FIG. 1, T0 and T2 are the primary inputs which affect the signal input to pin D0 in block 3.

In prior art static timing analysis, once the primary inputs are identified, the paths beginning with those primary inputs are traced forward to the point of interest in the logic design while delay values are accumulated along the paths. In this regard, the number in parentheses in FIG. 1 represent the delay values that would be calculated by a static timing analysis program of the prior art. Consider, for example, the path from block 1 to block 3. The data is clocked out of block 1 by the clock T0 at time zero, with a delay through block 1 of five timing units. This delay value is denoted as (5) on the signal path connecting output pin 30 of block 1 to input pin A0 of block 4. Assuming a delay of two timing units through block 4, the total delay from block 1 to the data input pin of block 3 is 7 timing units.

Consider now the accumulated delay from block 2 to block 3. Output pin 30 of block 2 is clocked by the rising edge of clock T2, which is delayed by 50 timing units with respect to the beginning of a system clock cycle. Assuming delays of 5 timing units through block 2 and 2 timing units through block 4, a signal originating at block 2 will arrive at input pin D0 of block 3 with a delay of 62 timing units. Thus, data clocked out of block 2 by the clock T2 at time 50 will arrive at the input pin D0 of block 3 at time 62. Apparently, data is clocked out of block 2 later than it is expected to be clocked into block 3 by the rising edge of T1. Manifestly, the designer intends that data from the previous cycle of blocks is to be clocked into block 3. This intent is implemented by specifying an adjust value of -100 for the path from block 2 to block 3, which retards the delay value by one system clock cycle. The delay value will be denoted as (-43 ). In static timing analysis as presently practiced, this adjust value cannot simply placed at the input pin of block 3, because this would cause the path from block 1 to block 3 to be incorrectly adjusted. Therefore, it is necessary to follow the paths back from block 3 to the point at which they diverge to correctly place the adjust value. The correct placement of the adjust value is at A1 input to block 4 as illustrated in FIG. 1.

In a logic design with multi-phase clocks, many clocked elements, and many signal paths determining where an adjust value should be placed for static timing analysis is a difficult task. The adjust value must be placed so that the paths requiring an adjustment are adjusted, without affecting the paths not requiring adjustment. In fact, it may be the case in a logic configuration that an adjustment cannot be properly made because of conflicting adjust values. For example, consider block 5 in FIG. 1 where an adjust value is required at the A1 input to block 4 for the path from block 2 to block 3 as in the first example. However, the path from block 2 to block 5 does not require an adjust value because the data is clocked out of block 2 before being clocked into block 5. The requirement to adjust the delay value for the path from block 2 to block 3 does not apply to the path from block 2 to block 5. In this case, it is not possible to correctly analyze both paths in a single timing analysis run using previous static timing analysis tools.

The examples discussed with reference to FIG. 1 illustrate that generation of timing adjustments according to previous static timing analysis tools can be a complex, and potentially insoluble, problem. To set up timing adjustments required by previous static timing analysis tools, the designer must identify those paths requiring an adjustment, determine where along the path the adjust value can be placed so that other paths will be not incorrectly adjusted, and resolve any conflicting adjust values. This becomes more difficult as the amount of logic being analyzed increases. In addition to requiring a significant amount of effort, the prior art generation of timing adjustments is inconsistent and error prone and an incorrect set of timing adjust values can potentially hide an actual timing problem.

The invention is based upon the critical observation by the inventor that the prior art timing adjustment problem can be resolved by associating, with each delay value, information regarding the clock affecting the value. Now, when converging paths bring together multiple delay values, those multiple delay values can be propagated forwardly, one for each different clock, and the clock information can be used to automatically adjust the delay values, as needed.

The invention is practiced in a system for analyzing the operation of a multi-phase-clocked logic network under static conditions. The invention improves the analysis of signal delay through the logic network and includes a circuit simulation providing a logical counterpart of the logic network which represents a multi-phase clock, elements of the logic network and connections between those elements. The elements include clocked elements which responds to a particular phase of the multi-phase clock by accepting an input data signal.

The invention also includes a data object representing a data signal propagating through the logic network. The data object includes a first data field representing a phase of the multi-phase clock during which the represented data signal is generated and a second data field representing a delay time.

The system includes a propagation component for applying the data object to the clocked data element representation to simulate input of the data signal to the clocked element.

In the invention, a delay component cooperates with the propagating element by comparing the phase represented by the first data field with the representation of the particular phase to alter the second field to a value representing the cumulative delay of the data signal through the clocked element.

An objective of this invention is to provide for automatic adjustments of delay values propagated through a logic network design by a static timing analysis tool.

This and other important objectives are achieved by this invention, as will be appreciated by reading the following detailed description of the embodiment with reference to the below-described drawings.

FIG. 1 is a representation of a logic network illustrating timing analysis by prior art static timing analysis method.

FIG. 2 is a set of clock waveforms illustrating a multi-phase clock which synchronizes operations of clocked elements of the logic network illustrated in FIG. 1.

FIG. 3 illustrates how the invention is applied to the logic network of FIG. 1 to automatically identify where a delay value must be adjusted and to automatically adjust the delay value.

FIGS. 4-8 illustrate particular tables which are used in the practice of the invention.

FIG. 9 is a block diagram illustrating the structural relationship of functional elements of the invention.

The invention overcomes the timing adjustment problem of the prior art static timing analysis by automatically handling delay calculation and timing adjustments. This is done by (1) associating clock information with the delay values which are propagated through the logic design, (2) propagating multiple delay values downstream in the logic design from a point where different delay values converge, and (3) using the clock information associated with a delay to automatically adjust it as needed. An example of how the timing adjustment problem is handled by the invention is illustrated in FIG. 3.

In FIG. 3, a clock tag is associated with each of the delay values. The clock tag provides information about how a signal represented by the delay value was generated by a clocked circuit element. In FIG. 3, a clock tag is simply the name of the clock signal which operates the clocked element generating the signal with which the clock tag is associated. For example, clock tags of the form T0 indicate that the delay value represents clock signal T0. Clock tags of the form T0 R indicate that the delay value represents a data signal which is triggered by the rising edge of the specified clock. In the example, the output of block 1 has a clock tag of T0 R, because the latch signal provided at output pin 30 is triggered by the rising edge of the T0 clock signal. Similarly, the output of block 2 has a clock tag T2 R, because the output signal is triggered by the rising edge of the T2 clock signal.

Multiple delay values are also propagated along a path, one for each different block tag. As FIG. 3 illustrates, the combinatorial clock represented by block 4 has several inputs, each with a different clock tag. In the invention, the output of such a block will have clock tag/delay value pairs propagated downstream, one pair for each clock tag. As FIG. 3 illustrates, the pairs are propagated from the output pin 10 of block 4, one pair for the T0 R clock tag and the other for the T2 R clock tag.

The clock tags and multiple delay values are used by the invention to calculate delays through circuit blocks and to automatically perform timing adjustment, as needed. The adjustment is done by comparing all clock phase tags provided to the data input of the latch with the clock phase tag of the triggering clock input. If one of the tags indicates that the associated data signal was triggered before the rising edge of the clock signal which triggers the latch, no adjust is required. If the clock tag indicates that the associated data signal was triggered after the clock signal triggering the latch, then the data delay value is automatically adjusted. The adjustments are determined independently for each of the clock tags.

In the example of FIG. 3, the delay for T0 R in block 3 does not require an adjustment because the signal represented by the clock tag/delay pair was triggered by the rising edge of T0, which occurs before the rising edge of the clock signal T1. However, the delay for T2 R in block 3 requires an adjustment because the represented data signal was triggered by the rising edge of T2, which occurs after the rising edge of the triggering clock signal T1. For block 5, the delays for both T0 R and T2 R do not require adjustment because the associated signals were triggered before the rising edge of the clock signal T3. FIG. 3 clearly indicates that the problem of conflicting adjustment values is eliminated by the invention because adjustment is done at the input of a latch to the representation of the data signal and is done independently of any other representation of the same data signal at another logic circuit element.

The invention is embodied in the data structures illustrated in FIGS. 4-8 and the pseudo-code description contained in Tables I-VI. An overall structural relationship between the data structures and the table procedures is illustrated in FIG. 9.

In FIGS. 4-8, five data tables are illustrated. FIGS. 4-7 contain the essential description of the logic circuit being analyzed. The table of FIG. 8 contains timing analysis data illustrated and discussed with reference to FIG. 3 and Tables I-VI.

In FIG. 4, a structure table 30 contains a description of the logic design being analyzed. The logic design (refer to FIG. 3) consists of blocks with output pins and input pins. Output pins are designated by a two-digit numeric name and input pins are designated by a two-character alpha-numeric name. The output pins of blocks are connected to the input pins of other blocks to form a directed graph. The structure table describes this graph by listing the connections between a source block output pin and the sink block input pin to which it is connected. For example, the output pins 30 of both blocks 1 and 2 respectively are connected to input pins A0 and A1 of block 4. Output 10 of block 4 sources input pin D0 of block 3 and block 5. Input pins of blocks which are not connected to any other block are considered primary input pins to the design. Therefore, input pins D0 of block 1 and 2 are primary input pins. Output pins of blocks which are not connected to any other block are considered primary outputs of the design. Therefore, output pins 30 of blocks 3 and 5 are primary outputs.

FIG. 5 illustrates a block description table 32 in which each block in the design is listed, together with a description of the block type. The block type identifies the logic function performed by the circuit block and is used to find the description of the block type in a block rule table, discussed below. The block description table 32 of FIG. 5 describes blocks 1, 2, 3, and 5 as latches, and block 4 as a combinatorial circuit of the AND gate type.

In FIG. 6, a block rule table 35 describes how the input pins of a block are connected to the output pins of a block for each block type. For each input pin-to-output pin connection, the block rule table lists a path type with a connection, and a block delay for the connection. The path type field of the table 35 describes how a signal propagates from the input to the output pin of a block. The path type field can be THROUGH or TRIGGERED. A THROUGH path type represents a combinatorial circuit type such as an AND block where the rising or falling signal on the input pin propagates through to the output pin to create a rising or falling signal on the output pin. A TRIGGERED path type represents an edge-triggered circuit type such as a latch block where the leading edge of the input signal creates both a rising and falling signal on the output pin and the falling edge of the input signal does not propagate to the output pin. The block delay (BLK.sub.-- DELAY) field of the table is formed from a pair of numbers of the form (tplh, tphl) representing the amount of delay to be added to the rising and falling path delays of the input signal to calculate the path delay values at the output pin. The number tplh is the time required to propagate a low-to-high signal transition through the block, while the number tphl is the time required to propagate a high-to-low signal transition. The example block rule table in FIG. 6 shows the block rules for both latch and AND block types. For example, in a latch block type, the delay through the block for a low-to-high signal transition from the input pin B0 where a clock phase signal is connected to the output pin 30 is five timing units, while the delay for a high-to-low transition is six timing units.

A clock description table 36 is illustrated in FIG. 7, the table defining the clock signals used in the logic design and the relationship between the clocks. Each clock signal used in the design is defined in the clock description table. Each clock signal is defined by its rise time, fall time, and cycle length in timing units. As inspection of the table 36 in FIG. 7 will confirm, the four clock signal of FIG. 2 are completely described in the table.

FIG. 8 illustrates a path delay table 38 containing multi-field data elements representing the cumulative path delays for each input or output pin of every block included in the logic design.

In the path delay table 38 of FIG. 8 the cumulative path delay is included in a multi-field data object with fields identifying the block and pin, and Clock.sub.-- tag and Path.sub.-- delay fields. The path delay table is initialized at the beginning of static timing analysis by entry of path delays for all primary inputs of the design. This is indicated in the upper portion of the table 38 which is labeled "primary inputs". As path delays for other pins in the design are determined according to the invention, these values are entered into the lower portion of the table which is labeled "analysis values". The clock tag field of any entry in the path delay table 38 identifies the clocking information which is associated with the path delay value of the entry. In this regard, clocking information denotes information as to the name of a clock for clock signals and information as to the name of the clock which triggered the data for data signals. The clock tag field can have one of three values: ASYNC, name, or name R.

The ASYNC clock tag indicates that the path delay represents an asynchronous signal. An asynchronous signal is a signal without any clock information associated with it. An asynchronous signal cannot be adjusted by the procedures of this invention.

The "name" tag indicates that the path delay is associated with the clock signal "name", where "name" is a clock signal defined in the clock description table 36. Clock signals are assumed to repeat every cycle and may be adjusted according to this invention by the clock cycle length (which, in the example of FIG. 2, is 100 timing units).

The clock tag "name R" indicates that the path delay represents a data signal which was triggered by the leading (rising) edge of the clock "name", where "name" is a clock signal defined in the clock description table 36. Data signals on the data path represented by the pair "name R"/path.sub.-- delay are assumed to repeat on every cycle of the triggering clock and may be adjusted according to the invention by the clock cycle length.

The Path.sub.-- delay field of the table 38 includes a pair of numbers of the form (tph, tpl) representing a cumulative delay along a logic circuit path terminating at the pin identified in the Pin field of the table entry. The value tph is the cumulative delay to propagate a logical high signal to block/pin identified in the first two fields of the table entry; tpl is the cumulative delay to propagate a logical low signal to this block/pin. When used herein, the term "cumulative delay" denotes the sum of the block delays along a path from a primary input to the designated pin in the logic design. If there are several paths from a primary input to this pin, or if there are paths from several primary inputs to this pin, then the cumulative delay is the worst (largest) delay for all paths which lead to this pin.

Each pin of a block in the logic design may have multiple entries in the path delay table 38. A given block/pin combination will have an entry in the path delay table for each clock tag which is associated with the block/pin entry. For example, in the analysis value portion of the table 38, two entires are found for the block/pin pair BLK3/D0 (that is, block 3, input pin D0), each to denote a respective clock.sub.-- tag/path.sub.-- delay path which leads to the pin.

FIG. 9 is a block diagram illustrating the primary functional components and data structure which are embraced by the invention, together with the primary structural relationships between those blocks. The invention includes the tables 30, 32, 35, 36, and 38, described above, and function blocks 40, 42, 43, 44, 45, and 47. A set of flags 48 is maintained by the invention.

The invention receives input from a conventional logic circuit description 50 which can be provided by a great number of known and available systems. In the invention, the logic circuit prescription is used to create structure, block, and block rule tables.

In the invention, a propagation procedure 40 receives the description of the next pin for which delay and, if necessary, adjustment are to be determined. The data object passed has block and pin fields which, together, identify the next point in the described logic circuit for which delay and adjustment are to be calculated. The propagation procedure includes a recursive algorithm used to propagate cumulative path delays from the primary inputs to each input and output pin in the described logic circuit. Execution of the propagation procedure makes entries in the path delay table by entering into it the cumulative path delays for all input pins of the described logic circuit. The completed path delay table for the example of FIG. 3 is illustrated in FIG. 8. The propagation procedure works by selecting each block/pin combination in the logic design, determining the cumulative path delay for the combination, and creating entries in the path delay table 38 for the cumulative path delay values to all of the non-primary logic circuit input pins. During execution, the propagation procedure 40 accesses the structure table 30 using the block/pin pair as an index.

The propagation procedure 40 maintains a flag for each block/pin in the logic design to track the status of the block/pin identified by the flag. One such flag is indicated by reference numeral 48. When the block/pin is selected by the propagation procedure, the status of the associated flag is set to IN-PROGRESS. When the cumulative path delay for a block/pin has been calculated, the status of the block/pin is changed to DONE. During execution of the propagation procedure, if a block/pin is selected whose status is IN-PROGRESS, then a loop in the directed graph has been detected. A loop in the directed graph indicates an error condition which is handled by returning an error value as the cumulative path delay for the block/pin where the loop was detected. Following entry of an error value, the propagation procedure continues execution.

The propagation procedure 40 calls a block delay procedure 42 to calculate the delay through a block, determine the cumulative path delay from input to output pin of the block, and create entries in the path delay table for all table entries containing an output pin in the Pin field. During execution, the block delay procedure 42 obtains access to the block description table 32 using the current value of "block" as an index. The data pair block.sub.-- type/pin indexes the block rule table 35 for the block delay procedure 42. During execution, the block delay procedure 42, or one of its components steps 43, 44, and 45 may access the path delay table 38, using block/pin as the index.

The steps 43, 44, and 45 are routines called by the block delay procedure 42. The THROUGH step 43 determines clock tags and path delay values for a THROUGH path type in a non-triggered circuit element. The THROUGH/clock step 44 determines clock tags and delay values for a through connection from an input pin to the clocked output pin of a clocked circuit element. The TRIGGERED step 45 determines clock tags and delay values for a TRIGGERED connection from a clock input pin to the output pin of a clocked circuit element.

The timing adjustment procedure 47 is called by the THROUGH/clock step 44 to determine whether a timing adjustment is needed to adjust the data signal on the input pin of a latch into the proper relationship with the clock signal on the input pin which triggers the input data pin. Relatedly, the "proper relationship" of the data signal and clock signal requires that the data signal be initiated in the cycle immediately prior to that in which the clock signal occurs. The timing adjustment procedure 47 receives two inputs from the THROUGH/clock step 44, data.sub.-- tag, which is a clock tag of the data input delay value and clocking.sub.-- tag, which is the clock tag of the clock signal which triggers the data input pin. The timing adjustment algorithm returns a single value "adj" which is the adjustment amount.

Refer now to tables I-VI for an understanding of the operation of the invention. Assume first that the path delay table 38 has been initialized by entry of the primary input values as illustrated in FIG. 8. Assume that the block/pin pair passed to the propagation procedure 40 is BLK1/30. The propagation procedure 40 will set the flag for this block/pin to IN-PROGRESS and will begin execution according to table I.

In table I, the block/pin pair is BLK1/30, for which no cumulative path delay has yet been determined. Pin 30 is an output pin, so the procedure goes to step 2 of table I. At step 2, the propagation procedure calls the block delay procedure of table II to determine the cumulative path for output pin 30 of block 1.

In table II, the block/pin pair still has the value BLK1/30. In step 1 of table II, the block description table 32 is indexed by BLK1 to determine that block 1 is a LATCH. This value is used in step 2 of table II to find all input pins connected to output pin 30 of block 1. As the block rule table 35 indicates, input pin B0 is the sole pin connected to the output pin 30. In step 3, the input pin B0 is returned to the propagation procedure of table I for determination of the cumulative path delay for the block/input.sub.-- pin pair.

Returning to table I, in step 1, the cumulative path delay for BLK1/B0 has been determined by entry of data in the primary input section of the table during initialization. In this regard, the input pin B0 has a clock.sub.-- tag/path.sub.-- delay value of T0/(0,20). At this point, table I returns to step 3 of the block delay procedure.

In step 4 of table II, after return from table I, BLK1/30 indicates that the input pin-to-output pin path type between pin B0 and pin 30 is TRIGGERED. In this case, the output pin 30 is a clocked output pin. The block delay procedure now moves to step 5 of table II.

In step 5, the set of clock tags and delay values for output pin 30 of block 1 are determined for each input pin connected to output pin 30. In the case of block 1, the only input pin connected to the output pin 30 is input pin B0 whose path.sub.-- type is triggered. Thus, in step 5, the TRIGGERED step (denoted by reference numeral 45 in FIG. 9) is called.

Reference to table V will provide an understanding of the TRIGGERED step in the example under consideration. In the TRIGGERED step, the block/pin pair is still BLK1/30, the input pin is B0 of the path type TRIGGERED, with the number pair (tplh, tphl) equal to (5,6) as shown in the block rule table 35. In step 1 of table V, the cumulative path delays for the input pin B0 of block 1 are given as (0,20). In step 2, clock tag and delay values are created for the output pin 30 from the input pin cumulative path delays. In step 2.a., block.sub.-- tag and (tph, tpl) have the values T0 (0,20) as illustrated in the primary input section of the path delay table 38. In step 2.b., a new clock tag for the output pin 30 is determined from the input pin clock tag T0. In this case, the second condition of step 2.b. obtains, that is, the clock.sub.-- tag is T0; therefore, the new.sub.-- tag is T0 R. Last the path.sub.-- delay set is created by adding the value for tph to tplh and tphl, respectively. In this case, the path delay value is (0+5,0+6) or (5,6). Thus, the clock.sub.-- tag/path.sub.-- delay for output pin 30 of block 1 is T0 R/(5,6). The procedure of table V now returns to step 5.c. of table II.

When return is made to table II, the block delay procedure in step 6 establishes the cumulative path delay for BLK1/30 to the worst delay value for each unique clock tag which is returned. Since only a single input pin affects the signal provided by output pin 30, only one new clock tag is returned in step 5. In this case, in step 6.a., clock.sub.-- tag is T0 R, while tph.sub.-- max and tpl.sub.-- max are the largest (only) rising and falling delays returned by way of step 5. In step 6.b., an entry into the analysis portion of the path delay table 38 is created. Recall that the block and pin field values are BLK1 and 30, respectively. The clock.sub.-- tag and path.sub.-- delay values, are, respectively, T0 R and (5,6). Inspection of the entry for BLK1/30 in FIG. 8 will confirm the values developed for this example. It should be evident that the procedural sequence just described for the pair BLK1/30, when performed for the input pair BLK2/30 will give the clock.sub.-- tag and path.sub.-- delay values shown in FIG. 8 for that pair.

Consider now use of the invention to determine the delay at input pin A0 of block 4. The block/pin pair BLK4/A0 is passed to the propagation procedure, the related flag is set to IN-PROGRESS, and the procedure of table I is invoked. Since pin A0 is an input pin for which no cumulative path delay has been determined, the procedure drops to step 3. In step 3.a., BLK4/A0 indexes the structure table to find the source block and output pin connected to input pin A0. As the table 30 of FIG. 4 illustrates, this pair is BLK1/30. In step 3.b., the procedure determines the cumulative path delay for BLK1/30 as described in the preceding example, and the path.sub.-- delay pair (5,6) is returned. In step 3.c., there is only one source.sub.-- BLK/output.sub.-- pin pair feeding input pin A0 of block 4. Therefore, when steps 3.c.1 and 2 are executed, the clock.sub.-- tag/path.sub.-- delay pair will be T0 R/(5,6). This pair is entered in the path delay table 38 of FIG. 8.

When the block/pin pair BLK4/10 is passed to the propagation procedure, the procedure of table I branches to the block delay procedure at step 2. In table II, step 2 returns two input pins which are connected to the output pin 10; these pins are A0 and A1. For each of these input pins, table II branches back to the propagation algorithm in step 3 to determine delays for those pins. The previous example demonstrated how the cumulative delay for BLK4/A0 is determined; following the described procedure for BLK4/A1 will result in return of the clock.sub.-- tag/path.sub.-- delay pair shown in path delay table for BLK4/A1. The procedure now moves to step 4 of table II, with the two cumulative path delay values for input pins A0 and A1.

Step 4 of table II tells the procedure that the path type is not TRIGGERED; therefore, output pin 10 of block 4 is a non-clocked output pin.

In Step 5, the THROUGH step is selected and executed once for each input pin to block 4.

The THROUGH step of table III finds the cumulative path delays for the input pins A0 and A1 from the path delay table 38. For each of the path.sub.-- delay values returned for the input pins a0 and A1, the block.sub.-- delay value obtained from the block rule table 35 for the input pin-to-output pin path is added to the path.sub.-- delay to create a new delay value. Thus, for each input pin, a respective clock.sub.-- tag/path.sub.-- delay pair is created for the output pin 10.

Last, the THROUGH step returns to step 6 of table II to set the cumulative path delay for each clock tag returned from the THROUGH step. In this example, there will be two clock tags returned, T0 R for the A0 input and T2 R for the A1 input. Steps 6.a and b take the input clock tags, determine tph.sub.-- max and tpl.sub.-- max for each clock tag and make entries into the path delay table for BLK4/10 for the respective clock.sub.-- tag/path.sub.-- delay pairs. These entries are shown in FIG. 8 at indexes BLK4/10/T0 R and BLK/10/T2 R.

When the block/pin pair BLK3/D0 is passed to the propagation procedure, the procedure goes to step 3 of table I from where it is determined that pin 10 of block 4 is the only output pin connected to the input pin. The procedure explained above for this output pin is followed, with the result at the clock.sub.-- tag/path.sub.-- delay pairs for BLK4/10 in the path delay table are returned. These values are assigned to the two BLK3/D0 entries in the path delay table in steps 3.c.1 and 2 of table I.

As discussed above with reference to FIG. 3, output pin 10 of block 3 is clocked by clock signal T1, which requires an adjustment to signal transitions in the output of block 4 which result from transitions in the output pin 30 of block 2. This example illustrates how the static timing analysis procedure of this invention detects the need for, and makes, the adjustment while also determining the cumulative path delay for output pin 10 of block 3. When the block/pin pair BLK3/10 is passed to the propagation procedure, a branch is taken at procedure step 2 to the block delay procedure of table II. In table II, steps 1, 2, and 3 result in determination of the cumulative path delays for the input pins D0 and C0. As the previous example illustrated, two cumulative delay values will be calculated for input D0. The cumulative delay value for C0 is obtained from the primary input section of the path delay table.

Next, in step 4, since input pin C0 is connected to output pin 10 by a TRIGGERED path, the output pin is considered to be a clocked output pin.

The procedure of table II loops at step 5, once for each input pin. Assume the first loop is taken for input pin D0; this will result in invocation of the THROUGH/clocked step of table IV.

In the THROUGH/clocked step, the block/pin pair is BLK3/10, the input.sub.-- pin is D0, and, from the block rule table, (tplh,tphl) is (2,3).

In step 1 of the THROUGH/clocked step, it is determined that input pin C0 is connected by a TRIGGERED path type to output pin 10. The data pair block/clock.sub.-- pin has the value BLK3/C0 for which the cumulative path delay from the primary input portion of the path delay table is (25,45). In step 1.c, the set of clock tags which can trigger output pin 10 includes only T1.

Step 2 of table IV returns two cumulative path delays: T0 R/(7,7) and T2 R/(58,58).

In step 3a of table IV, the cumulative path delays of step 2 are formalized into clock.sub.-- tag/path.sub.-- delay pairs, while step 3.b returns a value of T1 for the "clocking" parameter. At step 3.c, the value of the clocking parameter, T1, is paired with each cumulative path delay input to pin D0. For each pair, a loop is taken through steps 3.c.1-3.

For the pair (T0,T1), the timing adjustment procedure of table VI is called. The timing adjustment procedure determines whether an adjustment must be made to the cumulative path delay for the data input of a latch because of an apparent timing ambiguity between it and the clock signal which triggers the output pin connected to the data input pin.

For the first pair, the parameter data.sub.-- tag is given the value T0 in step 1 of the procedure, which results in the "data.sub.-- cycle" parameter being set to a value of 100 (the cycle length of the clock signal T0) and the parameter "start" to a value of zero (the rise time of the T0 clock signal). In step 2 of the procedure, the parameter "clocking.sub.-- tag" has a value of T1 which indexes the clock description table to find the rise time and cycle length of the T1 clock signal. The parameter "clocking.sub.-- cycle" is set to a value of 100 (the cycle length of the T1 clock) while the parameter "expected" is set to a value of 25 (the rise time of the T1 clock signal). In procedure step 3, the greatest common divisor of the current values of the data.sub.-- cycle and clocking cycle parameters is 100; the parameter "adj.sub.-- cycle" is assigned this value. In step 4, the following equation is solved for the parameter "n":

Substituting the values for the parameters into equation (1) results in:

and inspection of these values results in assignment of a value of zero to the parameter n. Step 5 of table VI returns to the THROUGH/clocked step procedure at step 3.c.1. Now in procedure step 3.c.2, the new.sub.-- tag parameter for the output pin clock tag is T1 R the delay value for the output pin is calculated as (7+2+0,7+3+0), or (9,10). Therefore, the data pair T1 R/(9,10) is returned.

The procedure now loops back to step 3.c for the pair T2,T1. The first step in the loop calls the timing adjustment procedure of table VI.

When the pair T2,T1 is taken into the adjustment procedure of table VI, data.sub.-- tag=T2, data.sub.-- cycle=100, and start=50. Next, in step 2 of the procedure, clocking.sub.-- tag=T1 indexes the clock description table, with the result that clocking cycle=100, while expected=25. In step 3, adj.sub.-- cycle 100. In step 4, substitution of the values determined above into equation 1 results in:

for which n=-1. Thus, in step 5, the parameter "adj" is given the value -100. This value is returned to the THROUGH clocked procedure at step 3.c.1.

Next, a new.sub.-- tag/path.sub.-- delay value is determined as T1 R/(-40,-39). At this point, the returned value of -100 for the parameter adj has been used to temporarily adjust the input pin path delay for the T2 R clock tag to a value of -42 as shown in FIG. 3. Relatedly, the clock.sub.-- tag/path.sub.-- delay pair T2 R/(58,58) for entry at BLK3/D0 in the path delay table (FIG. 8) can be adjusted in the data provided to the user by adding the adjustment amount returned from the timing adjustment procedure to the path.sub.-- delay values in the table.

Returning to the determination of the clock.sub.-- tag/path.sub.-- delay pair for the output pin 10 of block 3, the two clock tag/path delay pairs are returned to the block delay procedure from the THROUGH/clocked step to step 5.b of table II.

The TRIGGERED step is invoked from block delay procedure step 5.c for the input pin CO, which returns a clock.tag/path.delay pair T1 R/(30,31). The procedure of table II then proceeds to step 6.

In step 6 of table II, the worst delay value is determined by comparing the path.sub.-- delay values calculated for T0, T2, and T1. Of these values, the T1 pair is the worst (maximum). Thus, in step 6.a, the clock.sub.-- tag/path.sub.-- delay pair calculated by the TRIGGERED step is assigned to output pin 10 and the entry is made to the path delay table.

When the procedures explained above are applied to block 5, the path delay table entries of FIG. 8 will be calculated and placed in the table.

It should be evident that the foregoing description and exemplary explanation of the invention are not intended to limit its practice to circuits which consist only of latches and AND gates. The invention is applicable generally to circuits with clocked storage elements and non-clocked combinatorial elements. Further, inspection of the block delay procedure, the linked steps, and the timing adjustment procedure will show that path delay values can be calculated for clocked circuit elements having output pins controlled by any number of input data and clock pins.

One significant advantage of the invention is its ability to maintain, for any block/pin in the logic design, more than one delay value, each for a unique clock tag. See BLK4/10 in FIG. 3 and in the analysis values of the Path Delay Table of FIG. 8. Prior static timing analysis tools could have maintained only a single delay value for any block/pin, and that without a clock tag. The invention permits adjustment for each delay value for any block/pin independent from other delay values occurring at the same block/pin.

Let block/pin be the block and pin that has been selected.

1. If the cumulative path delay for block/pin has already been determined, then no action is needed.

2. If pin is an output pin, then use the block delay procedure to determine the cumulative path delay for the output pin.

3. If pin is an input pin, then:

a. Use block/pin as indices into the structure table to find the source block "source.sub.-- blk" and output pin "output.sub.-- pin" which is connected to the input pin.

b. Use the block delay algorithm to find the cumulative path delay for source.sub.-- blk/output.sub.-- pin.

c. Set the cumulative path delay for block/pin to the cumulative path delay for source.sub.-- blk/output.sub.-- pin by doing the following for each source.sub.-- blk/output.sub.-- pin entry in the path delay table:

1. Let clock.sub.-- tag be the clock tag and let (tph, tpl) be the path delay for the course.sub.-- blk/output.sub.-- pin entry in the path delay table;

2. Create an entry in the path delay table for block/pin with a clock tag of clock.sub.-- tag and a path delay of (tph,tpl).

Let block/pin be a block and output pin.

1. Use "block" as the index into the block description table to find the block type "block.sub.-- type" of the block.

2. Use block.sub.-- type and "pin" as indices into the block rule table to find all input pins which are connected to the output pin.

3. For each input pin "input.sub.-- pin" which is connected to the output pin, use the propagation algorithm to determine the cumulative path delay for block/input.sub.-- pin.

4. Use block.sub.-- type and pin as indices into the block rule table to determine if there exists an input pin which is connected to the output pin by a path type of TRIGGERED. If there is, then the output pin is a clocked output pin; otherwise, the output pin is a non-clocked output pin.

5. Determine the set of clock tags and delay values for the output pin. For each input pin which is connected to the output pin, let input.sub.-- pin be the input pin and let path.sub.-- type be the path type.

a. If path.sub.-- type is THROUGH and the output pin is non-clocked, then use the THROUGH step.

b. If path.sub.-- type is THROUGH and the output pin is clocked, then use the THROUGH/clocked step.

c. If path.sub.-- type is TRIGGERED, then use the TRIGGERED step.

6. Set the cumulative path delay for block/pin to the worst delay value for each unique clock tag by doing the following for each unique clock tag;

a. Let clock.sub.-- tag be the clock tag and let tph.sub.-- max and tpl.sub.-- max be the worst (largest) rising and falling delays for the delay values with the clock tag clock.sub.-- tag;

b. Create an entry in the path delay table for block/pin with a clock tag of clock.sub.-- tag and a path delay of (tph.sub.-- max,tpl.sub.-- max).

Let block/pin be the block and output pin which is being processed. Let input.sub.-- pin be an input pin connected to the output pin by a path type of THROUGH and let (tplh, tphl) be the block delay value from the block rule table.

1. Use block/input.sub.-- pin as indices into the path delay table to find all cumulative path delays for the input pin.

2. Create clock tag and delay values for the output pin from the input pin cumulative path delays.

a. For each cumulative path delay of the input pin, let clock.sub.-- tag be the clock tag and let (tph,tpl) be the path delay value.

b. Create a delay value of (tph+tplh,tpl+tphl) with the clock tag clock.sub.-- tag for the output pin.

Let block/pin be the block and output pin which is being processed. Let input.sub.-- pin be an input pin connected to the output pin by a path type of THROUGH and let (tphl, tphl) be the block delay value from the block rule table.

1. Determine the set of clock tags which can clock the output pin by doing the following;

a. Use block.sub.-- type and pin as indices into the block rule table to find all input pins which are connected to the output pin and have a path type of TRIGGERED;

b. For each input pin clock.sub.-- pin which is connected to the output pin by a path type of TRIGGERED, use block/clock.sub.-- pin as indices into the path delay table to find all the clock tags for the cumulative path delays of block/clock.sub.-- pin;

c. The set of clock tags which can trigger the output pin is the set of all clock tags for all input pins which are connected to the output pin by a path type of TRIGGERED.

2. Use block/input.sub.-- pin as indices into the path delay table to find all cumulative path delays for the input pin.

3. Create clock tag and delay values for the output pin from the input pin cumulative path delay values.

a. For each cumulative path delay of the input pin, let "clock.sub.-- tag" be the clock tag and let (tph,tpl) be the path delay value

b. For each clock tag which can clock the output pin, let "clocking" be the tag which clocks the output pin.

c. For each pairing of cumulative path delay from the input pin and clocking tag of the output pin do

1. Use the timing adjustment algorithm to calculate the adjust value "adj" needed to adjust the clock tag of the input pin delay value to the clocking tag.

2. Determine the new clock tag "new.sub.-- tag" from the clocking clock tag.

If clocking is ASYNC then new.sub.-- tag is ASYNC.

If clocking is name then new.sub.-- tag is name R.

If clocking is name R then new.sub.-- tag is name R.

3. Create a delay value of (tph+tplh+adj,tpl+tphl+adj) with the clock tag "new.sub.-- tag" for the output pin.

Let block/pin be the block and output pin which is being processed. Let input.sub.-- pin be an input pin connected to the output pin by a path type of TRIGGERED and let (tplh,tphl) be the block delay value from the block rule table.

1. Use block/input.sub.-- pin as indices into the path delay table to find all cumulative path delays for the input pin.

2. Create clock tag and delay values for the output pin from the input pin cumulative path delays.

a. For each cumulative path delay of the input pin, let "clock.sub.-- tag" be the clock tag and let (tph,tpl) be the path delay value.

b. Determine the new clock tag "new.sub.-- tag" from the input pin clock tag clock.sub.-- tag.

If clock.sub.-- tag is ASYNC then new.sub.-- tag is ASYNC.

If clock-tag is name then new tag is name R.

If clock-tag is name R then new.sub.-- tag is name R.

c. Create a delay value of (tph+tplh,tph+tphl) with the clock tag new.sub.-- tag for the output pin.

If data.sub.-- tag or clocking tag is ASYNC then no adjusting is done and the adjustment amount adj is zero.

Otherwise

1. Use data.sub.-- tag as an index into the clock description table to find the rise time and cycle length of the clock which initiated the data signal. The data signal is assumed to be initiated at the rise of the clock and is assumed to repeat with every cycle of the clock. Let "data.sub.-- cycle" be the cycle length of the data clock and let "start" be the rise time of the data clock.

2. Use clocking.sub.-- tag as an index into the clock description table to find the rise time and cycle length of the clock which clocks the data into the latch. The data signal is expected to arrive at the latch before the rising edge of the clock and the rising edge of the clock is assumed to repeat with every cycle. Let "clocking.sub.-- cycle" be the cycle length of the clock and let "expected" be the rise time of the clock.

3. Determine the greatest common divisor of data.sub.-- cycle and clocking.sub.-- cycle. This will be the cycle length by which adjustments can be made. Let this value be "adj.sub.-- cycle".

4. Find an integer value "n" such that:

expected-adj.sub.-- cycle<=start+(n*adj.sub.-- cycle) and

start+(n*adj.sub.-- cycle)<expected

5. The adjustment amount adj is n*adj.sub.--cycle.

While I have described several preferred embodiments of my invention, it should be understood that modifications and adaptations thereof will occur to persons skilled in the art. Therefore, the protection afforded my invention should only be limited in accordance with the scope of the following claims.