Reducing time to measure constraint parameters of components in an integrated circuit

Reducing the time required to measure constraint parameters (setup time, hold time and pulse width) of components in integrated circuits. For example, the delay of propagation of a signal between an input node and an intermediate node of a component are measured. An approximate range of possible values is formulated, and a search (by applying signals assuming one of the values in the approximate range and examining the output signal(s)) is conducted within the range to determine the value of the constraint parameters.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to design methodologies used to implement integrated circuits, and more specifically to a method and apparatus for reducing time to measure constraint parameters of various components used in integrated circuits.

2. Related Art

Integrated circuits generally contain several components such as flip-flops and registers. It is often desirable to determine several characteristics of the components, for example, to determine a maximum clock speed at which an integrated circuit may be operated. Some of such characteristics of interest are constraint parameters. Constraint parameters generally refer to values specifying the minimum delay/duration between occurrence of two signals, with the reference signal being termed as a constraining signal and the other signal being referred to as a constrained signal.

For example, constraint parameters of interest with reference to sequential components (having memory, e.g. flip-flops) include setup time, hold time and minimum pulse width. As is well known, setup time generally refers to a minimal time duration a signal of interest (e.g., input signal as the constrained signal) is to reach a desired signal level ahead of a reference signal (constraining signal). Hold time refers to a minimum duration of time the signal of interest is to stay at the desired level after an edge of a clock signal, for example, to enable proper sampling. Pulse width refers to a minimum pulse duration the reference/constraining signal (e.g. clock signal) needs to stay at a desired signal level for a signal of interest to be sampled accurately by a sequential component.

A prior approach may consume a substantial amount of time to measure constraint parameters while designing integrated circuits. For example, in a common design cycle, a component is represented in the form of digital data, and input signals are applied to the component assuming a specific value for a constraint parameter. The output of the component is examined to determine if the component would operate accurately with the constraint parameter. Several iterations of applying input signals (with different values for the constraint parameter), may be performed to determine an accurate value for the constraint parameter. In general, the time to design an integrated circuit increases with an increase in the number of iterations.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

An aspect of the present invention reduces the time to measure constraint parameters of a component by first measuring delay between a pair of nodes forming a part of an entire path from an input to an output (of the component). The measured delay is used to determine an optimal range in which the actual value of a constraint parameter is present. The actual value of a constraint parameter may be determined by applying signals, each signal conforming to a value of the parameter within the optimal range, and observing the output (of the component) for correctness according to the logical utility (also known as function) of the component.

As the range of values is determined based on the measured delay, the approximate range can be estimated in a short range accurately. As a result, the number of signals to be applied for determining the correct value may also be small. Thus, the time to determine the constraint parameters may be reduced. The advantages of the described embodiments will be clearer from an understanding of a prior approach which may not use at least some features of the present invention. Accordingly, a prior approach is described first with reference to example components and corresponding example constraint parameters.

2. Prior Approach in an Example Component

FIG. 1is a block diagram illustrating the basic operation of D flip-flop100. D flip-flop100is used to illustrate some prior approaches. D flip-flop100is shown receiving D-input110and clk-input120, and generating Q-output140in response.

D flip-flop100transfers the signal received on D-input110to Q-output when clk-input120transitions from a logical low to high. Thus, the signal at Q-output on path140may be similar to the signal to D-input but appears after certain delay. The constraint parameters of D flip-flop100are illustrated below with reference to FIG.2.

FIG. 2is a timing diagram illustrating example constraint parameters with reference to operation of D flip-flop100.FIG. 2is shown containing three lines210,220and230representing the signal to D-input on path110, Q-output on path140and clk-input on path120respectively.

Setup time refers to a minimum time duration D-input110has to change ahead of a time point at which the signal to clk input120changes. Duration240represents a duration between CLK230going high and D-input110has changed, and the minimum permissible corresponding duration refers to as setup time. In addition, the signal on D-input110needs to be at a logic high to transfer to Q-output for certain time duration after an edge (at time point270) of clk-input120. The corresponding time duration is is shown with numeral280, and the corresponding minimum permissible duration is referred to as hold time. Similarly, clk-input120needs to be at a logic level for a minimum pulse duration to transfer D-input110to Q-output140. The corresponding pulse duration is termed as pulse width, and is shown as Tw290.

Assuming for illustration that D flip-flop100is provided in a cell library, the constraint parameters of D flip-flop100may be of interest to a designer implementing a product using D flip-flop100in the cell library. However, the parameters may not be available to the designer (in the cell library or elsewhere). Accordingly it may be desirable to quickly determine the parameters.

In one prior approach, a binary search algorithm may be used to measure setup time Tsu240. Broadly, the binary search algorithm may be performed in a large search range to measure the setup time for all process temperatures and voltages (PTV), and slew combinations. In a first iteration, a transition is caused on D-input110and a transition on clk-input120is caused after certain time period within the search range.

Q-output140is observed (e.g., using SPICE simulator, well known in the relevant arts) to determine whether the transition is propagated or not. If the transition is not propagated, the setup time used in the corresponding iteration is deemed to be inadequate. If the transition is propagated, the setup time used at least equals the minimum setup time with which flip-flop100can operate. Similar searches may be performed iteratively until the correct/accurate setup time is determined. Other constraint parameters Thold280and Tw290may also be similarly determined.

One problem with the above approach is that it may be necessary to use a large approximate range to measure the possible actual values for the constraint parameter. The large range to search generally leads to a correspondingly long time to determine the actual value. Accordingly, it is desirable to minimize the time to measure constraint parameters. The present invention enables such minimization in the measurement of constraint parameters as described below in detail.

FIG. 3is a flowchart illustrating the details of a method using which the time to measure constraint parameter may be reduced according to an aspect of the present invention. For illustration, the method is described with reference to FIG.1. However, the method can be implemented in several other embodiments as will be apparent to one skilled in the relevant arts based on the disclosure provided herein. The method begins in step301in which control passes to step310.

In step310, the delay between two nodes forming a portion of the path from the input to the output of a component (e.g., D flip-flop100) may be measured. In general, an input signal is applied at a first node and the time taken for the input signal to propagate to a second node is determined.

Various approaches may be employed in selecting the two nodes. In an embodiment described below, the input terminal is conveniently chosen as one of the two nodes since the input terminal provides a convenient point at which various signals can be applied and measurements taken. The second node is selected at an internal point at which the signals have stability and can be examined for attainment of desired logical states. For example, for a D flip-flop implemented as a master slave latch, the second node is selected as a connecting point of the master latch and slave latch.

In step330, an approximate value for the constraint parameter is determined based on the delay measured in step310. Example equations for determining various constraint parameters are described below in further detail. Some of the equations may entail measuring other delays as well.

In step350, an optimal range to search for the actual value of constraint parameter is formulated using the approximated value of constraint parameter. In general, a narrow range would lead to minimization of the number of searches. However, if the actual value is not within the range (due to error in computation, etc.), additional computations may need to be performed to search outside of the optimal range. As a result, the time to compute the constraint parameter may become higher. In an embodiment, if the approximated value of constraint parameter is ‘A’, then the optimal range is formulated as (0.8×A) to (1.2×A), where ‘×’ represents multiplication.

In step370, input signals are applied based on various values in the optimal range to determine the actual value of a constraint parameter. For example, a transition on clk-input120is caused at different time points (in different iteration within the optimal range) with reference to a transition on D-input110till the actual value of setup time is determined. In other words, the output signal(s) generated by the component are examined to determine whether the component would be operational (perform the corresponding function) with the corresponding value in the optimal. Similarly, the time points at which the transitions on input signals are applied may be changed to determine the actual values for hold time and pulse width. The method ends in step399.

However, in some situations, the constraint parameter may not lie in the optimal range formulated in step350. In such a situation, a dynamic range recovery algorithm is applied, in which the optimal range may be increased in both directions (i.e., lowering the lower limit and increasing the upper limit). The actual value of the constraint parameter may be determined as described in step370by searching in the new search range. The search range may be increased until the actual value for the dynamic range is determined.

From the above, it may be appreciated that the search range may be reduced by identifying the internal node and thus the time to measure constraint parameter may be reduced. However, the circuits in which the internal nodes cannot be identified, a small value for the optimal range may be formulated as dynamic range recovery algorithm may increase the search range if the constraint parameter doesn't lie in the optimal range. An example implementation of the method ofFIG. 3is described below.

4. Example Component

FIG. 4Ais a circuit diagram of a scan flip-flop400illustrating an example component in which the present invention can be implemented. In general, scan flip-flop400represents a D flip-flop with additional circuitry provided for testing as described below. Scan flip-flop400is shown containing multiplexer410, master latch440and slave latch470. Each component is described below.

Scan flip-flop400operates as a D flip-flop in functional mode and as a scan flip-flop in test mode (e.g., using ATPG technique). Scan flip-flop400receives input signals D, SD (scan data), CLK and SCAN and provides output Q and QZ. When SCAN input is asserted, the flip-flop operates in a test mode, and in functional (non-test) mode otherwise. The input signal D provides input in non-test mode and SD provides input in the test mode. The selected signal of D or SD is provided as output Q. Output QZ represents the complement of Q.

Multiplexer410selects either input data D or scan data SD, and provides the selected data to master latch440. The selection of the specific input is controlled by SCAN input. Scan data SD is selected when SCAN input is high (scan mode) and input data D is selected when SCAN input is at logic low.

Multiplexer410is shown containing four PMOS transistors411,412,415, and416, and four NMOS transistors413,414,417and418. Each of transistors412and413receives D input and each of transistors415and417receives SD input on their respective gate terminals. Each of transistors411and418receives SCAN input and each of transistors414and416receives complement of SCAN input (SCANZ) on their respective gate terminals.

In test mode, when SCAN input is at logic high (SCANZ is at logic low), transistors416and418are turned on, which causes SD input to be selected. In non-test mode, when SCAN input is at logic low (SCANZ is at logic high), transistors411and414are turned on, which causes to select D input.

Master latch440receives input signal from multiplexer410and provides the same signal on path421in a master latch enabled state. A master latch enabled state is present when CKB402is at logic low and CKZ403is at logic high. CKB402and CKZ403are complement to each other and are generated from CLK input signal. It may be appreciated that master latch enabled state is present during half cycle of flip-flop input clock CLK.

Master latch440is shown containing first pass gate (formed by PMOS transistor441and NMOS transistor442), second pass gate (formed by PMOS transistor444and NMOS transistor443), first inverter formed by NAND gate containing transistors445,446,447, and448, and second inverter formed by NAND gate containing transistors461,462,463, and464. First pass gate is closed when CKB402is at logic low and CKZ403is at logic high since the gate terminals of PMOS transistor441and NMOS transistor442are respectively coupled to CKB402and CKZ403. In the closed state, first pass gate passes the signal received from multiplexer410, and the passed signal is further propagated through first and second inverters to slave latch470. In the same duration, second pass gate is open.

First pass gate is open when CKB402is at logic high and CKZ403is at logic low. In the same duration, second pass gate is closed. The combination of first inverter, second inverter and second pass gate operate to hold the previous data which was transferred when CKB402was at logic low.

Slave latch470receives input signal on path421and provides the outputs Q and QZ in a slave latch enabled state. A slave latch enabled state is present when CKB402is at logic (logical) high and CKZ403is at logic low. It may be further appreciated that the slave latch enabled state is present during one half of flip-flop input clock CLK and the master latch enabled state is present in the other half.

Slave latch470is shown containing third pass gate (formed by transistors477and478), third inverter formed by transistors495and496, fourth inverter formed by transistors497and498, third NAND gate formed by transistors491,492,493and494, a fourth logic gate formed by transistors471,472,473,474,475, and476. Third pass gate is in a closed state when CKB402is at logic high and CKZ403is at logic low since the gate terminal of NMOS transistor477and PMOS transistor478are respectively coupled to CKB402and CKZ403. In the closed state, the input signal on path421is passed to generate output QZ and Q.

Each of transistors492and494receive PREZ signal and each of transistors471and476receives CLRZ signal on the respective base terminals. The PREZ and CLRZ signals cause scan flip-flop400to generate a value on output Q and QZ independent of the input signals D and SD.

Therefore, master latch440receives signal from multiplexer410and provides the same signal to slave latch470on path421when CKB402is at logic low. Slave latch470provides the received signal on path421as output Q when CKB402is at logic high. Thus, it may be appreciated that the signal on path421does not change when CKB402is at a logic high even if the input signal changes. The manner in which CKB402and CKZ403can be generated is described below with reference to FIG.4B.

FIG. 4Bis a circuit diagram illustrating the details of generating clock signals CKB402and CKZ403from CLK401. Transistors A and B form a CMOS inverter and transistors C and D form another CMOS inverter. Each of transistors A and B receive CLK401on their respective gate terminals and provide CLKZ on path403, which is an inverted CLK401. Similarly, each of transistors C and D receive CLKZ403on their respective gate terminals and provide CLKB on path402, which is a delayed CLK401. Therefore, CLKB402and CLKZ403are compliments to each other.

Continuing with reference toFIG. 4A, constraint parameters of scan flip-flop400may be measured by selecting a node on path421(which connects master latch440to slave latch470). As noted above, master latch440provides the input signal (D or SD) on path421during one half cycle of CLK401and slave latch transfers the same signal to output Q during next half cycle of CLK401. The signal on path421would be stable in between the transfer.

The delay of the input signals to reach path421may be measured to estimate the constraint parameters. Additional accuracy in estimation may be achieved by measuring additional delays as described below in further detail with reference to FIG.6.

5. Increasing Accuracy of Estimation

FIG. 6is a timing diagram illustrating the general timing relationship of various signals ofFIGS. 4A and 4B. The timing diagram is shown containing CLK (401), D, Q, INT and CLKZ (403) signals. The signals are described in further details.

Setup time (Tsu610), hold time (Th620) and pulse width are shown for understanding the parameters. The setup time is shown as a duration between the rise of the D signal and the following rise of the CLK signal. The hold time is shown being measured from the rise of the D signal. The pulse width is shown being measured from the rise of the CLK signal. The manner in which the three constraint parameters can be estimated accurately is described below.

In an embodiment, the setup time is estimated according to the following equation:
Estimation of Setup time=Time duration650−Time duration660Eq. (1)

wherein time duration650represents the amount of time taken for an input signal D to arrive (propagate and settle) at the internal node on path421. Time duration660represents an amount of time taken for a transition on CLK signal to arrive at CLKZ. As may be appreciated fromFIG. 6, the setup time may be approximated using Equation (1). Due to such estimation, the setup time may be accurately determined in a few iterations.

According to another aspect of the present invention, the hold time is also approximated using Equation (1). The underlying rationale may be appreciated by understanding that hold time (like setup time) depends on how fast CLK reaches CLKZ with respect to how fast D reaches INT. For illustration, assume that the D signal is removed after some time of CLK active transition. If D reaches INT faster than CLK reaches CLKZ, then wrong value will be latched. Thus, as in the case of setup time, Equation (1) may be used to approximate the hold time as well.

According to one more aspect of the present invention, the pulse width is estimated according to the following equation:
Estimation of pulse width=Time duration650+Time duration660Eq. (2),

wherein time durations650and660are described above with reference to Equation (1).

Equation (2) may be appreciated by understanding that the pulse width needs to be long enough to make sure that D transitions arrive INT before clock CLK removal (clock inactivation) reaches CLKZ, which ensures that D reaches output in one clock pulse. In an alternative embodiment, pulse width may be estimated (approximated) according to the following equation:
Estimation of pulse width=Higher one of the two values
(Time Duration650and 2*Time Duration660)  Eq. (3)

wherein * represents a multiplication operation. Instead, as time duration650is generally more than time duration660, Equation (2) may be employed as a more conservative estimate of the pulse width.

Thus, using the above equations, the constraint parameters may be estimated. An optimal range is then formulated and accurate values are determined, for example, as described with reference to FIG.4.

The determination of constraint parameters can be used in several environments. For example, in software based systems used to design integrated circuits, the constraint parameters can be determined to characterize various cells in a library. The results of characterization generally facilitate a determination of whether a specific cell can be used (in combination with other cells) in an integrated circuit. At least in such environments, the constraint parameters can be determined in a computer system. An example implementation of such a computer system is described below in further detail.

6. Computer System

FIG. 5is a block diagram of computer system500illustrating an example environment for implementing the present invention. Computer system500may contain one or more processors such as central processing unit (CPU)510, random access memory (RAM)520, secondary memory530, graphics controller560, display unit570, network interface580, and input interface590. All the components except display unit570may communicate with each other over communication path550, which may contain several buses as is well known in the relevant arts. The components ofFIG. 5are described below in further detail.

CPU510may execute instructions stored in RAM520to provide several features of the present invention. CPU510may contain multiple processing units, with each processing unit potentially being designed for a specific task. Alternatively, CPU510may contain only a single processing unit. RAM520may receive instructions from secondary memory530using communication path550. Data representing various cell libraries may be stored and retrieved from secondary memory530(and/or RAM520) during the execution of the instructions.

Graphics controller560generates display signals (e.g., in RGB format) to display unit570based on data/instructions received from CPU510. Display unit570contains a display screen to display the images defined by the display signals. Input interface590may correspond to a key-board and/or mouse, and generally enables a user to provide inputs. Network interface580enables some of the inputs (and outputs) to be provided on a network. In general, display unit570, input interface590and network interface580enable a user to design integrated circuits, and may be implemented in a known way.

Secondary memory530may contain hard drive535, flash memory536and removable storage drive537. Secondary storage530may store the software instructions and data (e.g., interconnections of modules), which enable computer system500to provide several features in accordance with the present invention. Some or all of the data and instructions may be provided on removable storage unit540, and the data and instructions may be read and provided by removable storage drive537to CPU510. Floppy drive, magnetic tape drive, CD-ROM drive, DVD Drive, Flash memory, removable memory chip (PCMCIA Card, EPROM) are examples of such removable storage drive537.

Removable storage unit540may be implemented using medium and storage format compatible with removable storage drive537such that removable storage drive537can read the data and instructions. Thus, removable storage unit540includes a computer readable storage medium having stored therein computer software and/or data. An embodiment of the present invention is implemented using software running (that is, executing) in computer system500.

In this document, the term “computer program product” is used to generally refer to removable storage unit540or hard disk installed in hard drive535. These computer program products are means for providing software to computer system500. As noted above, CPU510may retrieve the software instructions, and execute the instructions to provide various features of the present invention. The features of the present invention are described above in detail.

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.