Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-17
2002-06-04
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06401234
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a method and system for data processing in general, and in particular to a method and system for routing interconnects within an integrated circuit design. Still more particularly, the present invention relates to a method and system for re-routing interconnects within an integrated circuit design having blockages and buffer bays.
2. Description of the Prior Art
As integrated circuits become increasingly smaller, the resistance per unit length of interconnect continues to increase, but the capacitance per unit length of interconnect remains almost constant while logic delay continues to decrease. If this trend continues, interconnect delay will become more dominant than logic delay in the near future.
Generally speaking, the characteristic interconnect delay of an interconnect is directly proportional to the square of the length of the interconnect. One approach to reducing interconnect delay is to insert buffers along the interconnect because buffer insertion effectively divides the interconnect into smaller segments, which makes the interconnect delay almost linear with respect to the length of the interconnect. Hence, buffer insertion has become a necessary step in modern integrated circuit designs.
A Steiner tree algorithm is commonly used to perform interconnect routing, and a buffer insertion algorithm is then used to insert buffers into the previously routed interconnect network. When inserting buffers into a previously routed interconnect network (especially a hierarchical one), a buffer typically cannot be placed on top of a pre-existing circuit macro known as a blockage. Thus, if the interconnect network was routed mostly over one or more blockages, then no buffer insertion algorithm that follows the conventional Steiner tree routing topology will be able to find a solution. Referring now to the drawings and in particular to
FIG. 1
a
, there is illustrated an example of a two-pin net
10
whose Steiner tree route runs over a blockage
11
, on top of which buffers cannot be placed. However, if two-pin net
10
is re-routed as shown in
FIG. 1
b
, then buffers, such as b
1
and b
2
, can be judiciously inserted on two-pin net
10
, as depicted in
FIG. 1
c
, albeit for an additional wire length cost.
In some design methodologies, instead of trying to restrict buffer insertions to certain locations between large blockages, it may be more suitable to pre-assign certain locations specifically for buffer placements. These pre-assigned locations specifically reserved for buffer placements are known as buffer bays.
FIG. 2
a
shows an example of two-pin net
10
that does not pass through any buffer bays, such as a buffer bay
12
, and is totally blocked from buffer insertions. By re-routing two-pin net
10
through buffer bay
12
, as shown in
FIG. 2
b
, buffers such as b
3
and b
4
can be suitably inserted into two-pin net
10
, as shown in
FIG. 2
c.
The present disclosure provides an improved method and system for intelligently re-routing interconnects within an integrated circuit design that contains blockages and/or buffer bays.
SUMMARY OF THE INVENTION
In accordance with a preferred embodiment of the present invention, a net within an integrated circuit design is initially decomposed into multiple two-paths. The net includes interconnects previously routed by utilizing a Steiner tree routing algorithm. Next, a cost associated with each of the two-paths is calculated. A two-path having a high cost is subsequently selected and re-routed with a lower cost two-path.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 6289495 (2001-09-01), Raspopovic
patent: 6155725 (2001-12-01), Scepanovic
Alpert Charles Jay
Gandham Rama Gopal
Hu Jiang
Neves Jose Luis
Quay Stephen Thomas
Bracewell & Patterson L.L.P.
Do Thuan
Salys Casimer K.
Smith Matthew
LandOfFree
Method and system for re-routing interconnects within 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 Method and system for re-routing interconnects within an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for re-routing interconnects within an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2944174