IC timing analysis with known false paths

Details IC timing analysis with known false paths IC timing analysis with known false paths

2001-05-31

2002-10-08

Hoang, Huan (Department: 2818)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06463572

ABSTRACT:

FIELD OF THE INVENTION
This invention is directed to the design of integrated circuits, and particularly to performing timing analysis for use during integrated circuit design phases.
BACKGROUND OF THE INVENTION
Timing analysis of an integrated circuit (IC) is performed during the design phase of the IC. More particularly, the circuit designer calculates the times of signal arrival and departure to identify a time delay along a given path in the circuit. The timing analysis is used by the designer to optimize the circuit, resulting in changes to the IC design and the netlist. This procedure is repeated numerous times during IC design causing changes in the netlist.
Timing analysis is performed using a timing graph, which is an oriented graph representing the signal flow. The nodes of the graph are all of the pins in the netlist. To perform timing analysis, the timing graph is traversed twice. In the first pass, graph is traversed from the start points and the worst signal arrival time is calculated at each pin. Similarly, in the second pass, graph is traversed backwards and the departure time (sometimes called the “required” time) is calculated. The departure time represents the required duration for propagation of a signal through the cell. For each pin, the sum of arrival and departure times represents the delay of the worst path going through the pin.
In almost every design, there are paths that the user wants to be disregarded from the timing analysis. These are called “false paths” and are conveyed to the timing analysis engines by the designer or user through “timing constraints”. Identifying and removing false paths from consideration is a difficult problem for the circuit designer. Belkhale et al., in “Timing Analysis with Known False Sub Graphs”,
Proceedings of the IEEE/ACM International Conference on Computer-Aided Design
(
ICCAD
'95), pp 736-740 (1995) suggest identifying portions of the timing graph (subgraphs) that correspond to the false paths. However, the Belkhale et al. technique requires complex computation of multiple arrival and multiple departure times at each node, with different arrival and departure times at a node distinguished based on a set attribute. The set attribute value gives the set of false subgraphs the signal has come through. The complexity of the Belkhale et al. approach expands as the process is repeated for changes in the netlist.
SUMMARY OF THE INVENTION
In accordance with the present invention, a timing graph contains one or more known false paths containing nodes of at least two sets selected from FROM, THROUGH and TO nodes. The false paths are processed to include both FROM and TO nodes. The processed false paths are transformed into equivalent sets of two logical false paths. True path intervals are constructed as logical subgraphs that do not describe any equivalent false path.
In some embodiments, the processing of the false paths include combining false paths having two identical sets of FROM, THROUGH and TO nodes, and normalizing the false paths to have both FROM and TO sets. More particularly, the timing graph is traversed backward from the THROUGH nodes for all false paths having only THROUGH and TO sets to insert FROM sets, and is traversed forward from the THROUGH nodes for all false paths having only FROM and THROUGH sets to insert TO sets.
In other embodiments the false paths are transformed into equivalent sets have either (i) disjoint FROM nodes, or (ii) identical sets of FROM nodes and disjoint TO nodes. More particularly, the false paths are transformed to have sets of either identical or disjoint FROM nodes. The false paths are sorted into groups having common FROM sets, and the false paths having identical FROM sets are transformed to have sets of either identical or disjoint TO nodes.
In preferred embodiments, the process is carried out by a computer under the control of a computer readable program embedded as code on a computer readable medium, such as a hard disk drive. The computer operates under control of the computer readable program code to carry out the process and define the timing of the timing graph.


REFERENCES:
patent: 5648909 (1997-07-01), Biro et al.
patent: 5659486 (1997-08-01), Tamiya
patent: 6321186 (2001-11-01), Yuan et al.
patent: 6412096 (2002-06-01), Ventrone

Affiliated with

Also associated with

Rating

IC timing analysis with known false paths does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with IC timing analysis with known false paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and IC timing analysis with known false paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2993189