Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Timing
Reexamination Certificate
1999-11-22
2003-11-25
Jones, Hugh (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Timing
C703S002000, C703S005000, C703S014000
Reexamination Certificate
active
06654713
ABSTRACT:
BACKGROUND OF THE INVENTION
During the design of silicon integrated circuits (ICs), a method is needed to verify that the circuit design will work at the required clocking speed before the IC is manufactured. This is necessary because the time delay in verifying that a design is too slow for its intended application by waiting for actual ICs to be fabricated results in a product that may be many months late coming into the market. Arriving late into the electronic market place frequently results in lower prices for an electronic component, and in lower market share, both typically causing reduced earnings.
One known method of verifying the functionality at operating speed of an IC design is to use what is known as a min max static timing verifier. Examples of commercial timing verifiers include Path Mill by Synopsis, Inc., Pearl by Cadence, Inc., and Veritime by Cadence Inc. Typical timing verifiers work by calculating the minimum possible time delay and the maximum possible time delay for a logic signal traversing a circuit path comprised of transistors or logic gate, and labeling any path that does not meet the required timing limits or constraints.
Within any of the known timing verifiers there are many different techniques for calculating the logic signal propagation delay along a circuit path of interest. Typically the circuit path is broken down into smaller and more easily calculated sections, for example, individual logic gates such as NAND gates, NOR gates, inverters, and channel connected regions (CCR). The logic delay for the circuit path is then simply the sum of all of the delays for the individual parts. The delays used by the timing verification tools for the NAND, NOR, inverters and CCRs are typically computed from characterization for delay models. These models characterize the delay and voltage transitions for each output of each given gate or CCR in a circuit path. If the total computed path delay results in a design violation along the circuit path of interest, then the designer will employ more accurate delay estimation methods to verify the path performance before potentially redesigning the circuit path. Commonly designers will use a circuit simulation tool, such as SPICE, Timing Mill by Synopsis, Inc., Starsim by Avant!, Inc., and ASX by IBM, Inc., as the accurate delay estimator tool for the circuit logic element, such as a NAND gate, CCR, or for the entire circuit path. In certain instances the timing verifier may be able to directly invoke the circuit simulator tool.
The circuit simulation tool produces a behavior model for the circuit that is represented as a waveform. These waveforms must be stored in a memory device for later use. Since memory resources are expensive, it is beneficial to provide a method for compressing the waveform data. Since minimum delay and maximum delay estimations are required by timing verifiers, known as min/max sides, then two waveforms may have to be stored, one for the minimum delay or fast estimations (known as early signals) and one for the maximum delay or slow estimations (known as late signals).
The waveforms just discussed are an example of typical two variable curves, in this particular case voltage versus elapsed time. To reduce the amount of data that needs to be stored, the voltage versus time curve maybe expressed as a series of voltage values at a series of evenly spaced time intervals. The more time intervals recorded (i.e., the shorter the time interval), the more accurately the stored compressed data approaches the original.
Limiting errors to one side of a curve is required when simulating integrated circuit performance to determine if a design will have speed related problems. In such a simulation it is necessary to calculate both the minimum and maximum possible time delays for a logic chain of circuit elements. Data compression of the transistor or logic gate voltage versus time relationship is necessary to reduce the very large amount of data that is produced by the simulation. Data compression may introduce errors into the data in either direction, i.e., either to the fast operating side or to the late side. Since it is necessary to have all possible error confined to the slow (i.e., late) side of the curve when calculating the maximum delay, or to the fast (i.e., early) side of the curve when calculating the minimum delay for the logic chain, the compressed data must be shifted in the desired direction by the maximum possible data error in order to ensure that all of the compressed data points are either early, or late. This shifting increases the total error between the compressed data and the original waveform by more than is acceptable in current calculation tools.
SUMMARY OF THE INVENTION
Therefore, it would solve a problem in the art to provide a method or a tool for ensuring that all of the data compression error in a timing verifier tool is confined to a selected side of the curve, since with such a method there would be no need to shift the compressed data by an amount equal to the maximum error toward the desired region, and no consequent increase in error introduced by the compression.
A method of data compression for open curves in two variables is presented which can guarantee that any compression error is exclusively on one selected side of the curve. In the example of a circuit model waveform, the variables are voltage and time, or current and time, etc., and the area to the right of the curve (i.e., increasing time) is the slow (or late) side. The method requires inputs to define a beginning point, an ending point, an accuracy limit, and the side to which the error is to be confined.
The curve is divided into rising and falling segments, and into curve sections, each of which is either convex shaped or concave shaped toward, for example, the late side. On convex sections of the curve, the compression method draws a tangent to the curve at the beginning point and calculates the difference between the tangent line and the curve until the difference reaches a predetermined accuracy value. A new tangent line is drawn to the curve at the point where the deviation from the original tangent reaches the limit, and the intersection point of the two tangents is stored in memory. This process is repeated until the end point of the convex segment is reached, where another tangent is drawn to conclude the convex section approximation and data compression, and to begin the concave curve section approximation and data compression. The convex portion of the curve has been thus been approximated by a piecewise linear set of lines connecting the intersection points of the tangent lines drawn on the selected side of the curve, and none of the points on the piecewise set of lines is ever on the opposite side of the original curve.
The concave section approximation continues the tangent line drawn at the inflection point between the convex and concave sections of the curve, until the deviation in value exceeds the accuracy value. A new tangent line is constructed at the point on the curve where the deviation exceeded the set accuracy and the intersection point of the two tangent lines is found. The angle between the two tangent lines is calculated and bisected, and a perpendicular line to the bisecting line is constructed. The intersection point between the perpendicular line and the original curve is stored in memory. Thus the concave section of the curve has been approximated by a piecewise linear set of lines connecting the points of the original curve that are nearest to the intersection of the tangent lines. Since the points are all on the original curve and the segment is concave, then every point on the piecewise linear set of lines is on the opposite side of the original curve from the tangent lines, and all points are on the selected side of the curve.
The curve or waveform maybe divided into rising and falling segments by using the predefined beginning and ending points, and all locations on the curve having a first derivative equal to zero, i.e., being horizontal. A falling segment may
Grundmann William J.
Nassif Nevine
Rethman Nicholas L.
Ferris Fred
Hewlett--Packard Development Company, L.P.
Jones Hugh
LandOfFree
Method to compress a piecewise linear waveform so... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method to compress a piecewise linear waveform so..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method to compress a piecewise linear waveform so... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3119699