Method for reducing RC parasitics in interconnect networks...

Details Method for reducing RC parasitics in interconnect networks... Method for reducing RC parasitics in interconnect networks...

2002-09-06

2004-07-13

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06763504

ABSTRACT:

FIELD OF THE INVENTION
This invention is related to the field of design automation, and more particularly, to a method for reducing the size of RC parasitics of interconnect networks in an integrated circuit (IC) in order to reduce circuit analysis time.
BACKGROUND OF THE INVENTION
During final timing verification of integrated circuits (ICs), it is crucial to rigorously account for all the RC parasitics in the interconnect networks that link the various transistors in the IC, a known cause of significant delays in the interconnects. Emerging newer and more complex technologies continue to shrink feature sizes, leading to increasing the dominance of the interconnect delays. At present, a circuit extraction tool is used to generate these RC parasitics from a description of the layout of the interconnect. Unfortunately, this creates extremely large RC networks with a wide range of dynamic time constants that can choke downstream detailed circuit analysis tools in the following manner: (1) the size of RC networks is very large, resulting in a significant increase in run-time due to the large size of the circuit matrices; and (2) the wide range of dynamic time constants causes the analysis tools to take extremely small numerical time-steps, resulting in a further increase in the run-time.
Thus, a rigorous accounting of metal R and C is highly advantageous, particularly in deep sub-micron technologies, because of the large delays attributable to these interconnects. It is also desirable to reduce (or crunch down) the large RC networks generated by circuit extraction tools by reducing the size and narrowing the range of dynamic time constants. It should be noted that the run-time advantage of crunching resistor networks in a more compact form applies at each time step of each simulation performed by the detailed circuit analysis tool. This is highly significant because each of these simulations are typically run multiple times during circuit optimization, and the same compressed RC network continues to be reused for all the iterations.
An integrated circuit can be represented by a collection of transistors with the terminals interconnected by nets. After completing the layout, each net is electrically modeled as an RC network of nodes and elements. The elements of the network are resistors (Rs) and capacitors (Cs). Nodes connecting transistor terminals are referred to boundary nodes, while the remaining ones are referred to as internal nodes of the RC network.
Prior art techniques select only internal nodes for elimination based on its nodal time constant defined by:
τ
=
C
γ
(
1
)
where C is the grounded capacitance of the node and &ggr; is the total conductance (i.e., the inverse of the resistance) connected to the node. For example, for node X shown in
FIG. 1
, the grounded capacitance and the total conductance are given by:
C=C
X
  (2)
&ggr;=
G
1
+G
2
+G
3
+G
4
  (3)
Prior art techniques eliminate an internal node when its nodal time constant &tgr; is smaller than a predetermined threshold &tgr;
max
. When a node is selected for elimination, the grounded capacitance of the node and all the resistors connected to the node are distributed to neighboring nodes using the following formula:
C
i
=
C
X
⁢
G
i
γ
(
4
)
G
ij
=
G
i
⁢
G
j
γ
(
5
)
where i and j represent the index of a pair of neighboring nodes of the node X being eliminated, C
i
is the additional capacitance to be added to the existing grounded capacitance at node i, and G
ij
is a (possibly new) conductance introduced between nodes i and j.
FIG. 2
is an illustration of the node elimination process for node X in the example given in FIG.
1
.
The total capacitance of the RC network remains the same after the elimination of an internal node:
∑
i
⁢
C
i
=
C
X
γ
∑
i
⁢
G
i
=
C
X
(
6
)
Moreover, it can be shown that the Elmore delays at all boundary nodes are preserved by the elimination process. (Elmore's delay is the first time-moment of the impulse response at a sink. The response at a sink due to an arbitrary input waveform is simply the convolution of the impulse response with the input waveform). This is highly regarded property of the RC reduction process.
Whenever a node is eliminated, the node count is reduced by 1, although the number of resistors may actually increase. For instance, in the example shown in
FIG. 2
, there are four resistors prior to elimination, but six thereafter. Increasing the total number of resistors is not desirable since the circuit matrices become denser. In general, for a node with k neighbors that already has m resistors among its neighbors, the fill-in count, or the total number of new resistors created after its elimination, is given by:
ξ
=
k
⁡
(
k
-
1
)
2
-
m
-
k
(
7
)
Internal node elimination is generally restricted to only those nodes that have a fill-in count of 0 or less to preserve the sparsity of the reduced RC network, since the total number of resistors cannot increase.
The problem with conventional techniques is that they apply only to the elimination of internal nodes, and not to boundary nodes of the RC networks. An example of the latter is shown in
FIG. 3
, where node X is connected to the gate terminal of a transistor external to the RC network. Even if node X had a small (<&tgr;
max
) time constant, prior art methods would not eliminate it because by eliminating node X, the gate terminal of the transistor shown in
FIG. 3
would have to be split up and distributed among the neighboring nodes (
1
,
2
,
3
, and
4
), resulting in a circuit that is not equivalent to the original one.
In transistor-level static timing analysis, circuits which contain large RC networks with many boundary nodes and a wide range (over seven orders of magnitude) of time constants are routinely encountered. Since algorithms in the prior art only eliminate internal nodes, their quality is limited since there usually remains a large number of boundary nodes with very small time constants (several orders of magnitude less than the Elmore delay).
OBJECT OF THE INVENTION
It is, therefore, an object of the invention to reduce large parasitic RC networks in the interconnect of an integrated circuit design, preferably after having applied internal node elimination techniques (or any other RC reduction technique).
It is another object to speed up the analysis of the resulting RC network without a significant loss of accuracy.
It is another object to provide the user with a smooth size-versus-accuracy tradeoff such that as the accuracy requirement is lowered, the size of the RC network approaches the lower limit of each interconnect having no resistors. The speed of the circuit analysis tools is the fastest at this extreme limit.
SUMMARY OF THE INVENTION
In a first aspect of the invention, there is provided a method for allowing further reduction of parasitic RC networks after applying conventional internal node elimination techniques.
The present inventive method further reduces (beyond only eliminating internal nodes) RC networks by shorting certain resistors connected to the boundary nodes, and adjusting the value of neighboring resistors to compensate for the errors introduced by the shorting. This additional reduction of the RC networks greatly improves the performance of downstream analysis tools, such as circuit simulators, without a significant loss of accuracy.
A resistor is selected as a candidate for shorting if the accumulated delay error at either end is less than a predetermined threshold. This threshold is a fraction (e.g., {fraction (1/10)}) of the time-constant threshold chosen for the internal node elimination conventional technique in order to limit the growth of the accumulated delay error. After shorting the resistor, the accumulated delay error at the merged node is updated and values of downstream resistors are changed to preserve the delay at downstream nodes. An important aspect of the invention is the simplicity of the formula used to change the downstream resist

Affiliated with

Also associated with

Rating

Method for reducing RC parasitics in interconnect networks... 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 for reducing RC parasitics in interconnect networks..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for reducing RC parasitics in interconnect networks... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3255445