Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-06-07
2003-07-15
Nguyen, Ha (Department: 2812)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06594806
ABSTRACT:
I. BACKGROUND OF THE INVENTION
1. Field of the Invention
The automation of interface timing verification is important for the design of reliable systems composed of several interconnected components. Due to manufacturing or environmental variation, the delay between two signal transitions of a component may not be a precise number, and is usually specified with a lower bound and an upper bound by the manufacturers. Exhaustive simulation, where all possible combinations of delay values are checked, is impractical for large systems. Therefore, efficient analytical verification algorithms are necessary to ensure that all timing requirements will be satisfied for all possible delay values.
2. Description of the Related Art
A convenient means for describing the timing interaction of signals and events is a timing diagram. A timing diagram is a set of signals, where each signal is composed of signal edges which represent events in time such as a transition from high to low, transition from high impedance to driven, etc. The time position of events in the timing diagram is determined by timing constraints between events. A constraint [c
ij
] (meaning a constraint between events i and j) in general has a lower bound component, lower c
ij
, and an upper bound component, upper c
ij
. There are many possible timing constraints between signal events with various semantic definitions, but only two types, the most common in practice, are considered here:
linear,
max
i
(
time
[
i
]
+
lower
[
c
ij
]
)
≤
time
[
j
]
≤
min
i
(
time
[
i
]
+
upper
[
c
ij
]
)
and
max
,
max
i
(
time
[
i
]
+
lower
[
c
ij
]
)
<=
time
[
j
]
<=
max
i
(
time
[
i
]
+
upper
[
c
ij
]
)
.
In a practical context, guarantees and requirements are linear constraints and delays are max constraints.
Note that only maximum separations need be calculated, because minimum separations can be calculated by:
min(time[
i
]−time[
j
])=−max(time[
j
]−time[
i
]).
A timing diagram is modeled by an event graph whose nodes represent events and whose weighted directed edges are timing constraints, either linear or max. Each edge is labeled with both the lower bound and upper bound component associated with the edge.
One of the shortcomings of currently available commercial tools is that they either do not deal with guarantees and requirements, or, if they do, the results are frequently incorrect or unreliable. Many commercial tools are based on a timing analysis engine that handles only max or min timing relationships. This limits the application of these tools for describing timing guarantees, signal tracking and clock jitter, all of which require linear constraints as well as max constraints. Also, the inability to use linear constraints prevents the possibility of error diagnosis capability in timing analysis.
A previous paper, “Efficient Algorithms for Interface Timing Verification,” T.-Y. Yen, A. Ishii, A. Casavant, and W. Wolf, Proceedings, European Conference on Design Automation, (EDAC), 1994, pp. 34-39, describes an algorithm for performing timing verification in designs having minimum and maximum event separations expressed using max and linear timing relationships. This algorithm is known as the “Max-Plus-Linear” (hereinafter, “MPL”) Algorithm, and is described in more detail below.
Since the present invention is primarily concerned with the MPL algorithm, previous work in the algorithm area will just be touched on. However, general work in the area can be found in “Solving Linear, Min and Max constraint Systems Using CLP based on Relational Interval Arithmetic,” P. Girodias, E. Cerny, and W. J. Older, Theoretical Computer Science, 1997, Vol. 173, No. 1, February, pp. 253-281; “Interface Timing Verification with Delay Correlation Using Constraint Logic Programming,” P. Girodias, E. Cerny, Proceedings of the European. Design and Test Conference, 1997. pp. 12-19; “High-Level Timing Analysis using Constraint Logic Programming and Interval Arithmetic,” P. Girodias and E. Cerny, Proceedings of the Canadian Conference on Electrical and Computer Engineering, Vol. 2, 1995, pp. 636-639; “Modeling and Execution of Timing Diagrams and Multi-Match Events,” K. Khordoc, E. Cerny, and M. Dufresne, TAU '92; “Algorithms for Interface Timing Verification,” K. L. McMillan and D. L. Dill, Proceedings of IEEE International Conference on Computer Design (ICCD), 1992, pp. 48-51; “Verification of Asynchronous Circuits Using Time Petri Net Unfolding,” A. Semenov and A. Yakovlev, Proceedings of ACM IEEE Design Automation Conference, 1996, pp. 59-62; “Specification and Analysis of Timing Constraints in Signal Transition Graphs,” P. Vanbekbergen, G. Goossens, and H. DeMan, Proceedings, European Conference on Design Automation, (EDAC), 1992, pp. 302-306.
Work specifically in the max plus linear realm can be found in “Interface Timing Verification With Application to Synthesis,” E. A. Walkup and G. Boriello, Proceedings, Design Automation Conference, (DAC), 1994, pp. 106-112; “Algorithms for Interface Timing Verification,” K. L. McMillan and D. L. Dill, Proceedings of IEEE International Conference on Computer Design (ICCD), 1992, pp. 48-51.
Work in the cyclic version of max plus linear is in “An Algorithm for Exact Bounds on the Time Separation of Events in Concurrent Systems,” T. Amon, H. Hulgaard, S. M. Bums, and G. Borriello, Proceedings, IEEE International Conference on Computer Design, (ICCD), 1993, pp. 166-173; “Efficient Timing Analysis of a Class of Petri Nets.” H. Hulgaard and S. M. Burns, CAV '95, LNCS 939; “Maximum Time Separation of Events in Cyclic Systems with Linear and Latest Timing Constraints,” F. Jin. H. Hulguard, E. Cerny, FMCAD '98.
The details of the MPL algorithm and outlines of proofs can be found in “Efficient Algorithms for Interface Timing Verification,” mentioned above. Here, a brief overview of the MPL algorithm will be given to provide background for the following discussion of the invention.
In
FIG. 1
, the initialization step uses a single source longest path algorithm (Bellman-Ford algorithm) described in Chapter 25 of
Introduction to Algorithms
, T. H. Cormen, C. E. Leiserson, and R. L. Rivest, McGraw Hill, 1990. In the Iterative Adjustment Step, on each iteration, a slack graph is constructed. The nodes in the slack graph are events, as in the event graph. The edges, however, represent the available slack between two events.
FIG. 2
defines bound satisfaction for upper and lower bounds. In the upper portion of
FIG. 2
, events A and B occur at event times t
a
and t
b
, respectively. If the difference between t
b
and t
a
is less than or equal to a particular upper bound, then that upper bound is satisfied. Similarly, in the lower portion of
FIG. 2
, the difference between t
b
and t
a
must be greater than or equal to a particular lower bound for that bound to be satisfied.
The slack calculation for a lower bound of a max or linear constraint is shown boxed on the left of FIG.
3
. All lower bounds, whether associated with linear constraints or max constraints are compulsory, meaning that they must always be satisfied.
The slack calculation for an upper bound of a max or linear constraint is shown boxed on the right of FIG.
3
. The upper bounds of linear constraints are compulsory, but the upper bounds of max constraints are max-optional. Max-optional bounds may or may not be satisfied on a constraint by constraint basis. Slacks of compulsory bounds and satisfied upper bounds of max constraints have positive slack and become edges in the slack graph. In a consistent solution, at least one of the max optional bounds entering an event must be satisfied.
The shortest slack &dgr;[i] is calculated as the minimum of the compulsory slack &dgr;
c
[i] and the max-optional slack &dgr;
m
[i] as shown in
FIG. 3. A
procedure based on Dijkstra's shortest path algorithm (Chapter 25 in
Introduct
NEC Corporation
Nguyen Ha
Whitmore Stacy A
LandOfFree
System and method for performing timing analysis, including... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing timing analysis, including..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing timing analysis, including... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038525