Interconnect routing using logic levels

Details Interconnect routing using logic levels Interconnect routing using logic levels

2002-08-06

2004-07-20

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06766504

ABSTRACT:

FIELD OF THE INVENTION
The invention relates generally to interconnect routing, and more particularly to routing interconnects for a network, as may be found in an integrated circuit.
BACKGROUND OF THE INVENTION
Integrated circuits comprise many interconnects for connecting blocks of circuitry. Accordingly, computerized routing tools for routing interconnects for connecting blocks of circuitry have been developed to handle this data intensive task.
Associated with each interconnect is a time delay. This interconnect delay may be characterized from a driver to a load. Stated another way, there is a delay between the time when a signal leaves an output of one circuitry block and arrives as an input to another circuitry block. This delay may be associated with one or more types of delays, such as signal propagation delays and clock-to-output delays, among other known types of delays. Accordingly, target delays are respectively associated with connections. A slack on a connection is the difference between actual delay and target delay. A negative slack indicates that a target delay is not being met, and a positive: slack indicates that a target delay is being met. A path, formed by one or more connections has a path delay determined by the delay of its constituent connections. A path may have an associated delay target, in which case a “path slack” is the difference between a path's target and actual delay.
A routing tool in a delay routing mode is configured to at least attempt to obtain a minimum interconnect delay using time delay as a primary criteria for evaluating possible routing paths from one block of circuitry, a “driver,” to another block of circuitry, a “load.” A routing tool in a resource (minimum resource) routing mode is configured to at least attempt to obtain a minimum number of resources using number of resources as a primary criteria for evaluating possible routing paths from a driver to a load. These different routing modes conventionally generate different results. Impact of these different routing modes may affect performance, for example operating frequency of an integrated circuit, and cost, such as die size.
Conventionally, in timing driven routing, slack allocation and analysis is done to determine delay targets for interconnects, and then these delay targets are used to at least attempt to produce routes for interconnects meeting such targets. In connection slack allocation, slack for a path is distributed or otherwise divided, not necessarily, equally among connections forming such a path. Thus, targets are provided for each connection in a path based on a portion of path slack. There are some limitations to this approach.
First, accurately predicting achievable interconnect delays is difficult. Conventionally, a heuristic based on fan out or current delay criteria is used. Moreover, this prediction is made even more difficult in integrated circuits that have different fan out characteristics based on programmed configuration, such as programmable logic devices (PLDs). Examples of such PLDs include, but are not limited to, Complex Programmable Logic Devices (CPLDs) and Field Programmable Gate Arrays (FPGAs).
Secondly, allocation of path slack among connections forming a path does not take into account, for example, whether a connection on such a path can exceed such a target, and whether it would be beneficial for such a target to be exceeded. A routing tool or “router” operating in a mode to meet delay targets does not attempt to surpass such targets. In other words, beating, and not just meeting predicted targets can alleviate requirements from other connections with negative slack. In such instances exceeding interconnect delay targets, i.e., using less delay than targeted, can allow other interconnects not to meet their respective interconnect delay targets and still achieve overall circuit performance.
One modification to time-driven routing as described above is to perform slack allocation, for example with a timing engine, and then route critical interconnects in delay mode. However, this modification runs the timing engine quite often to capture the benefit of delay mode routing of the critical interconnects, and thus there is a cost of doing a timing analysis for each of such runs. If impact of exceeding requirements by routing in delay mode is not captured by rerunning the timing engine, then excessive work may be done on what appears to be a critical connection but is no longer critical, as routing of some other connection(s) upstream or downstream in its path has alleviated criticality of such a connection.
Conventionally, a critical interconnect is one in which path slack is a negative value. Thus, if a routed path delay does not meet a target path delay for a path, then a negative value for path slack results.
Accordingly, it would be both desirable and useful to provide method and apparatus for routing fewer interconnects though in a delay mode in order to meet the desired circuit performance. Moreover, it would be both desirable and useful to provide method and apparatus for routing interconnects with reduced runtime expense for timing updates.
SUMMARY OF THE INVENTION
An aspect of the present invention is a method for identifying routing for interconnects for an integrated circuit. Logic level value for the interconnects are identified. The interconnects are routed responsive to a first criteria. Timing information associated with the interconnects routed is updated. A set of at least one connection from the interconnects responsive to the updated timing information is assembled, where the at least one connection has a respective negative slack. A logic level of the logic levels responsive to at least a portion of the set is identified, and at least one connection for the identified logic level is rerouted responsive to a second criteria. Timing information is updated. This process of assembling sets and selecting logic levels to route responsive to the second criteria may be continued, until there are no more connections with negative slack, or all the connections with negative slack have been routed responsive to the second criteria.
An aspect of the present invention is a method for routing connections for a network. Logic levels for the network are identified. Connections of the network responsive to the logic levels are identified. Path slacks for the paths are obtained, and minimum path slacks are ascribed to each of the connections responsive to the path slacks.
An aspect of the present invention is a method for routing connections for a network. A threshold number, such as a maximum or a minimum, of the connections needed to traverse from each source object to each connection is identified, and logic levels are indexed in response to the threshold number of the connections identified.
An aspect of the present invention is a method for routing interconnects for a network. The network is characterized into logic levels having a property of independence, such as in relating to timing update, of connections within each of the logic levels, and the connections within a logic level are changed in state, such as by routing.


REFERENCES:
patent: 5557531 (1996-09-01), Rostoker et al.
patent: 5937190 (1999-08-01), Gregory et al.
patent: 6067650 (2000-05-01), Beausang et al.
patent: 6263478 (2001-07-01), Hahn et al.
patent: 6367060 (2002-04-01), Cheng et al.
patent: 6591407 (2003-07-01), Kaufman et al.
Jiang, Y.-M. et al., “Dynamic timing analysis considering power supply noise effects”, Quality Electronic Design, 2000. ISQED 2000. Proceedings. IEEE 2000 First International Symposium on Mar. 20-22, 2000 pp.: 137-143.*
Frankle, Jon, “Iterative and Adaptive Slack Allocation for Performance-Driven Layout and FPGA Routing” Paper 34.1, pp. 536-542, 29.sup.th ACM/IEEE Design Automation Conference Proceedings 1992, Jun. 8-12, 1992, Anaheim, California.*
Jing-Jia Liou et al., “False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation”, Design Automation Conference, 2002. Proceedings. 3

Affiliated with

Also associated with

Rating

Interconnect routing using logic levels does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Interconnect routing using logic levels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interconnect routing using logic levels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3196696