Interconnect delay driven placement and routing of an...

Details Interconnect delay driven placement and routing of an... Interconnect delay driven placement and routing of an...

1999-04-08

2001-12-04

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C716S030000

Reexamination Certificate

active

06327693

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to the optimization of placement and routing for an IC design.
2. Background Information
Over the years, because of the ever increasing complexity of IC designs, IC designers have become more and more reliant on electronic design automation (EDA) tools to assist them in designing ICs. These assistance span the entire design process, from synthesis, placement, routing, to layout verification.
In the art of placement and routing, i.e. placement of components and routing of connections connecting the various components, various techniques are known. For examples, in U.S. Pat. No. 5,818,729, issued to Wang et al, a method and system for placing cells using “quadratic placement” and a “spanning tree” model was disclosed; in U.S. Pat. No. 5,072,402, issued to Ashtaputre et al., a method for routing interconnections using a “channel” approach is disclosed; and in U.S. Pat. No. 5,550,748, issued to Xiong, a method for “delayed” routing, to satisfy timing constraints, using a “region search” approach is disclosed.
In recent years, various techniques for “jointly” performing placement and routing have also become known. For examples, in U.S. Pat. No. 5,798,936, issued to Cheng, a placement method including look ahead for routing congestion was disclosed; in U.S. Pat. No. 5,838,583, issued to Varadarajan et al., a “joint” method for optimizing placement and routing was disclosed; and in U.S. Pat. No. 5,847,965, issued to Cheng, a “joint” area based method for placing and routing an IC was disclosed.
While each of these prior art techniques has its own advantages, they all share at least one common disadvantage in that they do not adequately address the placement and routing need of sub-micron ICs. Increasingly, interconnect delay has become the primary obstacle preventing sub-micron ICs from realizing the full benefit of these ICs' further increase in compactness for their operating speed. Thus, a placement and routing technique that more adequately addresses the need of sub-micron IC designs is desired.
SUMMARY OF THE INVENTION
An EDA tool is provided with a placement and routing (P&R) module that optimizes placement and routing of an IC design in an interconnect delay driven manner. The P&R module systematically determines if it can improve (i.e. reduce) interconnect delays of the critical interconnect routing paths, by determining if it can improve the interconnect delay of each path's constituting segments connecting two pins through a component. For each such segment, the P&R modules determines if the interconnect delay of the segment can be improved by using a different interconnect routing path interconnecting the two pins through the component replaced to a different location, and alternatively through a logically equivalent component placed at a different location.
In one embodiment, the interconnect delay determination for each segment is made by determining the interconnect delays between the source pin and a number of candidate locations, and the interconnect delays between the candidate locations and the destination pin. In one embodiment, in each case, the interconnect delay determination includes determining resistance and capacitance of the candidate source/destination portion of the segment.
In one embodiment, the interconnect delays for the candidate source/destination portions of a segment are determined employing a performance driven routing technique. In each case, the resistance determination includes determining the longitudinal length of the candidate source/destination portion of the segment, and the capacitance determination includes determining the congestion conditions of various interconnect planes and an average inter-wire distance for the interconnect plane where the candidate source/destination portion is disposed. The determined average inter-wire distance is used to look up capacitance contributions of various interconnect plane pairs from a pre-determined capacitance table. The looked up capacitance contributions in turn are used to determined the capacitance in a weighted manner.


REFERENCES:
patent: 5072402 (1991-12-01), Ashtaputre et al.
patent: 5550748 (1996-08-01), Xiong
patent: 5610833 (1997-03-01), Chang et al.
patent: 5666290 (1997-09-01), Li et al.
patent: 5761076 (1998-06-01), Miki
patent: 5764954 (1998-06-01), Fuller et al.
patent: 5798936 (1998-08-01), Cheng
patent: 5818729 (1998-10-01), Wang et al.
patent: 5838583 (1998-11-01), Varadarajan et al.
patent: 5847965 (1998-12-01), Cheng
patent: 6002857 (1999-12-01), Ramachandran
patent: 6009248 (1999-12-01), Sato et al.
patent: 0814420A1 (1997-12-01), None
Gunther, B.K.; “The circuit object organisation library”; Computer Architecture Conference, 2000; 1999; pp. 26-33.*
Mathur, A.; Liu, C.L.; “Timing-driven placement for regular architectures”; IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; vol. 16 Iss. 6; Jun. 1997.*
Sung-Woo Hur et al., “Timing Driven Maze Routing”, Department of Electrical Engineering and Computer Science (MC 154), University of Illinois at Chicago, Apr., 1999 ISPD, pp. 1-15.
Fang-Jou Liu et al., “Design and Implementation of a Global Router Based on a New Layout-Driven Timing Model with Three Poles”, 1997 IEEE International Symposium on Circuits and Systems, Jun. 9-12, 1997, Hong Kong, pp. 1548-1551.
John Lillis, et al., “New Performance Driven Routing Techniques With Explicit Area/DelayTradeoff and Simultaneous Wire Sizing”, 33rd Design Automation Conference, Jun., 1996, pp. 395-400.

Affiliated with

Also associated with

Rating

Interconnect delay driven placement and routing of an... 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 delay driven placement and routing of an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interconnect delay driven placement and routing of an... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2593538