Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-02-23
2004-07-13
Thompson, A.M. (Department: 2815)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C438S129000, C702S085000, C703S019000
Reexamination Certificate
active
06763506
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computer-assisted methods and apparatus for generating or compiling electronic designs such as designs for digital integrated circuits. More specifically, the invention relates to improvements in using timing information while compiling electronic designs.
Electronic design automation (“EDA”) is becoming increasingly complicated and time consuming, due in part to the greatly increasing size and complexity of the electronic devices designed by EDA tools. Such devices include general purpose microprocessors as well as custom logic devices including Application Specific Integrated Circuits (“ASICs”). Examples of integrated circuits include non-programmable gate arrays, field programmable gate arrays (“FPGAs”), and complex programmable logic devices (“PLDs” or “CPLDs”). The design of even the simplest of these devices typically involves generation of a high level design, logic simulation, generation of a network, timing simulation, etc.
Meeting timing requirements is important to the correct operation of an integrated circuit. For example, for a plurality of D-type flip-flops (“DFFs”) to feed through some logic to another plurality of DFFs, it is generally required that the signals from the first set of DFFs must finish propagating through any intermediate logic and have settled to their final state on the D-input of each of the destination DFFs before the next rising edge of the clock. (In fact they must finish before the next clock edge by an amount known as the setup delay of the register T
su
.) If the delay through the resulting logic is greater than the time between rising clock edges, then the state that the destination DFFs will hold on the next clock edge will be undefined.
In order to implement a source electronic design, such as might be represented by a schematic or netlist among other possibilities, into a hardware device, such as a PLD or CPLD, several steps are used to generate an efficiently implemented design. BTwo of these steps are placement and routing. Placement and routing are responsible for assigning logic elements in a source electronic design to individual locations in the target device, such a s a programmable logic device. Most circuit optimization methods, such as those occurring during placement and routing, depend upon an identification of “critical connections” between circuit elements or blocks. A delay for a path will be the sum of delays on its constituent connections. Critical paths include those signal paths with excessive delays and that play an important role in limiting the performance of the electronic design implemented in the hardware device. There may be several critical paths in a circuit. The cycle time of the clock that controls the DFF's at the beginning and end of the path cannot be any less than this delay. A critical path may consist of one or more connections, and all those connections will be critical. Those connections lying on critical paths will be labeled critical connections and are described as having high criticality. Emphasis is made during optimization to optimize the timing of those connections having the greatest criticality. For example, during placement, the placement algorithm will attempt to keep those elements or blocks having a critical connection in a configuration where the connection would be made with as little delay as possible, i.e. by interconnecting the elements or blocks with fast wiring lines.
Prior approaches have computed the criticality of a connection based on its “slack”. The slack of a connection is the amount of delay that could be added to a connection without causing any timing constraint depending on that connection to be violated. Stated another way, for a given connection, slack is the deviation of the calculated arrival time made by timing analysis from the required arrival time specified by the designer. See “Use of Slack as a Measurement of Being On Time and the Procedure for Calculating Slack,” IBM Technical Disclosure Bulletin, November 1982, pp. 2826-2830. Negative slacks indicate that the calculated path timing exceeds the timing constraint. Criticality is an inverse function of slack. Connections with low, zero, or negative slack have a high criticality.
One method of timing analysis currently used in circuit optimization estimates the slack of each connection to determine which connections are critical and therefore need to be made or placed using fast wiring lines to avoid slowing down the circuit. For example, in implementing a design into a programmable logic device, a placement and routing tool would assign the source design logic elements to individual locations on the device. To minimize delay in a hierarchical architecture device, the connection between logic elements might use a local connection, i.e. occurring within the same logic array block (“LAB”), as the “fast wiring”. In other devices, the “fast” wiring might be determined by minimizing the length of the connection between the two logic elements. Current methods have difficulty in identifying the most critical of the connections. For example, current methods on some occasions, fail to differentiate between connections having identical slacks but lying on different paths having different relative margins for additional delay. This may occur, for example, when a connection is on a path having a relatively large timing constraint, e.g., 100 nanoseconds (“ns”). On some of such paths, there may be little margin for additional delay. Yet, the connection at issue may possess the same slack value (say 2 nanoseconds) as another connection that is on a different path that has a relatively small timing constraint, say 4 nanoseconds. While the slack based criticality of the two connections is identical, their true criticality is rather different. The first path has very little slack remaining relative to the length of the timing constraint on which it lies (98 nanoseconds of the 100 nanosecond delay budget for the path is used up). So it is more likely that the timing constraint on the first connection here will be violated than the timing constraint on the second connection.
Under current approaches, an initial timing analysis will often yield several connections having a negative slack. These negative slacks generally must be dealt with separately in a criticality computation and tend to lead to many connections with high criticality. Excessive numbers of connections with high criticality tend to make the optimization tools behave poorly because they are attempting to optimize too many connections at once and, as a result, optimize all connections poorly. Another problem to be addressed, them, is how to deal with negative slack connections so that the portion of negative slack connections with the highest criticality are optimized first. What is needed is an improved method for determining criticality.
SUMMARY OF THE INVENTION
The present invention provides a method of generating an electronic design. Optimizing the timing of a circuit relies on methods of identifying critical connections between circuit elements or blocks. Extra effort is made during optimization to ensure that connections with the highest criticality have their timing optimized. The invention provides a new method of computing the criticality of connections in electronic systems with multiple timing constraints. The criticality is computed as a function of slack ratio. Slack is the amount of delay that can be added to a connection without causing any timing constraint depending on that connection to be violated. The slack ratio of a path is the slack of that path divided by the magnitude of the timing constraint applicable to that path. Connections typically lie on multiple paths, each of which is potentially governed by a different timing constraint. The slack ratio of a connection is the minimum slack ratio of all the paths that pass through that connection. An electronic representation of the electronic design is received which includes various connections between various blocks specifying
Betz Vaughn Timothy
Galloway David Reid
Altera Corporation
Beyer Weaver & Thomas LLP
Chu Chris C.
Thompson A.M.
LandOfFree
Method of optimizing the design of electronic systems having... 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 of optimizing the design of electronic systems having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimizing the design of electronic systems having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3226820