Model for simulating tree structured VLSI interconnect

Details Model for simulating tree structured VLSI interconnect Model for simulating tree structured VLSI interconnect

2000-03-08

2002-10-01

Smith, Matthew (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06460165

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention is directed to a method of simulating an RLC tree and more particularly to a method of evaluating time domain signals within an RLC tree with arbitrary accuracy in response to any input signal.
In circuit design, fast, accurate computer simulation of the behavior of the circuit is important. That is especially true with VLSI, in which hundreds of thousands of circuit elements can be placed on a single chip, and with ULSI, in which millions of circuit elements can be placed on a single chip.
It has become well accepted that interconnect delay dominates gate delay in current deep submicrometer VLSI circuits. With the continuous scaling of technology and increased die area, that situation is becoming worse. In order to design complex circuits properly, accurate characterization of the interconnect behavior and signal transients is required. An interconnect in a VLSI circuit is commonly tree structured. A single line is a special case of a tree that has only one output (or sink). Thus, the process of characterizing signal waveforms in tree structured interconnect is of primary importance.
One of the more popular delay models used within industry for RC trees is the Elmore delay model. Recently, an equivalent to the Elmore delay model has been introduced for RLC trees. Those models are used for fast approximate delay estimation. However, highly accurate estimation of signal transients within a VLSI circuit is required for performance-critical modules and nets and to accurately anticipate possible hazards during switching. Also, the increasing performance requirements forces the reduction of the safety margins used in a worst case design, requiring a more accurate delay characterization.
AWE (Asymptotic Waveform Evaluation) based algorithms have gained popularity as providing a more accurate delay model than the Elmore delay model. AWE uses moment matching to find a set of low frequency dominant poles that approximate the transient response at the nodes of an RLC tree. However, AWE suffers two major problems. The first problem is that the AWE method can lead to an approximation with unstable poles even for low order approximations. The second problem is that AWE becomes numerically unstable for higher order approximations, which limits the order of the approximations determined using AWE to fewer than eight poles, of which some poles may be unstable and have to be discarded. The limited number of poles is inappropriate to evaluate the transient response at the nodes of an underdamped RLC tree, which requires a much higher number of poles to accurately capture the transient response at all the nodes.
To overcome this limitation, a set of model order reduction algorithms have been developed to determine higher order approximations appropriate for RLC circuits based on the state space representation of an RLC network. However, these model order reduction techniques have significantly higher computational complexity than AWE. These techniques have super linear complexity with the order of the RLC tree, which is equal to the total number of capacitors and inductors in the tree. This high complexity is because these model order reduction techniques have to solve n linear equations in n variables several times. This complexity is much higher than the complexity of AWE, which is linearly proportional to n for an RLC tree. Note that n can be in the order of thousands for a typical large industrial net.
SUMMARY OF THE INVENTION
In light of the above, it will be apparent that a need exists in the art for a circuit analysis method and system which can accurately capture the transient responses at all nodes in a computationally efficient manner.
It is therefore a primary object of the invention to provide a method and system for evaluating the transient response at all of the nodes of a general RLC tree using high order approximations.
It is another object of the invention to provide such a method and system which can do so in a computationally efficient manner.
It is yet another object of the invention to provide such a method and system having a high degree of stability in terms of both numerical stability and pole stability.
To achieve the above and other objects, the present invention is directed to a method and system for evaluating the transient response at the nodes of a general RLC tree, the method and system being capable of determining high order approximations appropriate for underdamped RLC trees in a computationally efficient way (complexity linear with n). The present invention also has improved stability properties for low order approximations as compared to AWE, which can be a useful feature with RC trees which do not require high order approximations.
The method and system operate as follows. The RLC tree is divided into left and right sub-trees joined by the node closest to the input. Each of the left and right sub-trees is divided into left and right sub-trees joined by a node. The sub-trees are divided recursively into still smaller sub-trees until the RLC tree is completely decomposed into left and right sub-trees joined by nodes. At each node of the RLC tree, the numerator and denominator of the transfer function at that node are determined in accordance with the left and right sub-trees joined by the node. The denominator of the transfer function of the node closest to the input is taken to be the denominator of all of the transfer functions of the RLC tree. For each node, the numerators of the transfer functions of the left and right sub-trees joined at the node are corrected in accordance with the denominators of the transfer functions of the left and right sub-trees joined at that node.
The present invention evaluates the time domain signals within RLC trees with arbitrary accuracy in response to any input signal. It does so by finding a low frequency reduced order transfer function by direct truncation of the exact transfer function at different nodes of an RLC tree. The method is numerically accurate for any order of approximation, which allows finding approximations with large numbers of poles appropriate for approximating RLC trees with underdamped responses. The method is computationally efficient with a complexity linearly proportional to the number of branches in an RLC tree. The method determines a common set of poles to characterize the responses at all the nodes of an RLC tree, which enhances the computational efficiency of the proposed method. The stability is guaranteed for low order approximations with fewer than 5 poles. Such low order approximations are useful for evaluating monotone responses exhibited by RC circuits.


REFERENCES:
patent: 6009248 (1999-12-01), Sato et al.
patent: 6088523 (2000-07-01), Nabors et al.
patent: 6229861 (2001-05-01), Young
patent: 6298046 (2001-10-01), Thiele
patent: 6314546 (2001-11-01), Muddu
Ismail, Y. et al., Signal Waveform Characterization In Rlc Trees, Iscas 99, vol. 6, pp. 190-193.
Ismail, Y. et al., Inductance Effects in RCL Trees, Proceedings Ninth Great Lakes Symposium on VLSI, Mar. 1999, Ypsilanti, MI, USA, pp.56-59.

Affiliated with

Also associated with

Rating

Model for simulating tree structured VLSI interconnect does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Model for simulating tree structured VLSI interconnect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Model for simulating tree structured VLSI interconnect will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2998803