problem has become one of the dominant factors in determining system reliability. This problem is caused by high current density flowing in the metal interconnect. Therefore, current evaluation is a crucial concern in IC design. SPICE level circuit simulators are excellent for doing current calculation, however, their running time are too expensive to be used repeatedly in design synthesis loops. In this paper, we propose an efficient approach for the interconnect current calculation. This method is based on moment matching but does not need high order moments. It only needs traversing the RC tree once to get the mean current value of every segment, traversing the tree once more is enough for the RMS current calculation, and two more traversals is sufficient for the peak current calculation. We apply our method to a larger number of interconnects getting close-to-SPICE accuracy at significantly faster runtimes. In particular, applying the method to 17,387 wire segments in the clock tree of a commercial IC, we obtained that the average deviation error of mean current is 0.0569%, average RMS current error is 0.703 % and average peak current error is 6.552%. It took 28 hours for HSPICE to get current value of all the wire segments and it only took our method 156 seconds. I.

Delay evaluation is always a crucial concern in the VLSI design and it becomes increasingly more critical in the nowadays deep-submicron technology. To obtain an accurate delay value, the gate modeling is a key issue. As the VLSI feature size scaling down and meanwhile operating frequency increasing, the modeling work becomes more difficult than ever for high-performance digital ICs. Nevertheless, most conventional techniques of gate modeling are based on the switch-resistor model;(i.e., a voltage source concatenating a driving resistance), which can only capture the gate characteristic in its switching region. Hence, these modeling techniques have to decouple the gate with its interconnects and compute a piecewise linear function for the driving source in the iterative computation of effective capacitance [1, 3, 4]. Since the driving source of the model is dependent on gate load, when the design modification affects the load, the gate has to be modeled again almost from the beginning for a new timing analysis. The efficiency will be deteriorated in synthesis loops due to this. In this paper, we present an explicit gate delay model, which is not sensitive to gate load and can be pre-computed before timing analysis and synthesis. Thus, the repetition of modeling work is totally unnecessary even when the gate load keeps on changing in the performance optimization procedure. The efficiency is certainly improved in the synthesis/optimization loops. The advantage is attributed to using a second-order circuit as the model base. This two-pole approach also certifies the model to yield an accurate result to match the non-linear output of gate.

The authors address the problem of simultaneous routing and buffer insertion. Recently the authors considered simultaneous maze routing and buffer insertion under the Elmore delay model. Their algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that the Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, constraints cannot be imposed on the transition times of the output signal waveform at the sink or at the buffers on the route. The authors extend the algorithm in so that accurate delay models (e.g., transmission line model, delay lookup table from SPICE, etc.) can be used. They show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, they guarantee that all transition time constraints are satisfied. Their algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that their algorithm performs well.

In this paper we address the problem of simultaneous routing and buffer insertion. Simultaneous maze routing and buffer insertion under the Elmore delay model have been reported in the literature previously. Such algorithms can take into account both routing obstacles and restrictions on buffer locations. It is well known that Elmore delay is only a first-order approximation of signal delay and hence could be very inaccurate. Moreover, we cannot impose constraints on the transition times of the output signal waveform at the sink or at the buffers on the route. In this paper we extend previously reported algorithm so that accurate delay models (e.g., transmission line model, delay look-up table from SPICE, etc.) can be used We show that the problem of finding a minimum-delay buffered routing path can be formulated as a shortest path problem in a specially constructed weighted graph. By including only the vertices with qualifying transition times in the graph, we guarantee that all transition time constraints are satisfied. Our algorithm can be easily extended to handle buffer sizing and wire sizing. It can be applied iteratively to improve any given routing tree solution. Experimental results show that our algorithm performs well.

As the VLSI technology scaling down, the electromigration problem becomes one of the major concerns in high-performance IC design for both power network and signal interconnects. For a uniform width metal interconnect, the current flows through the driving point is much larger than that flows through the fan-out point since much of current bypasses to the ground through the parasitic capacitance. This causes the lifetime of driving point to be quite shorter than that of fan-out point due to electromigration. In order to avoid breakdown at the driving point, wire sizing is an effective solution. Thus we present a wire shape, of which the current density as well as the lifetime is uniform along the wire. SPICE simulation results show the uniformity of current density of this wire shape. Under the same current density bound, we demonstrate that chip area and power consumption are significantly reduced for this wire shape compared to the uniform width wire. The wire shape functions we derived are continuous. However, it is not necessary to ultra-accurately reproduce the continuous shape on the silicon, since we can round the continuous shape to the nearest available litho width and this will not degrade the uniformity of current density.

In this paper, we present a fast and accurate delay estimation method for buffered interconnects. The interconnect wire is modeled by the transmission line model which is more accurate and efficient than lumped circuit model. For the interconnect wire, we specify the wire shape to be of the form f(x) = ae-bx. Note that if we let b = 0, our work is reduced to uniform wire case. By using first three poles in the transfer function, we derive analytical expressions for calculating delay at any threshold voltage under a finite ramp input. The expressions involved in calculating coefficients in the transfer function are also analytical. We use k-factor equations to estimate delays for buffers. Since the k-factor equations require a loading capacitance for delay computation, we use the effective capacitance technique introduced in [17] to calculate the effective capacitance for each interconnect wire which is connected to a buffer. Therefore, our delay calculation for buffered interconnects is analytical and thus very efficient. Our experiments show that signal waveforms estimated by our method are very close to SPICE's results.

Buffer insertion is an efficient technique in interconnect optimization. This paper presents a graph based algorithm for optimal buffer insertion under accurate delay models. In our algorithm, a signal is accurately represented by a finite ramp which is characterized by two parameters, shift time and transition time. Any accurate delay model, such as delay models based on the transmission line model and SPICE simulations, can be incorporated into our algorithm. The algorithm determines the optimal number of buffers and their locations on a wire such that some optimization objective is satisfied. Two typical examples of such optimization objectives are minimizing the 50% threshold delay and minimizing the transition time. Both can be easily determined in our algorithm. We show that the buffer insertion problem can be reduced to a shortest path problem. The algorithm can be easily extended for simultaneous buffer insertion and wire-sizing, and complexity is still polynomial. The algorithm can also be extended to deal with problems such as buffer insertion subject to transition time constraints at any position along the wire.

In this paper, we consider continuous wire-sizing optimization for delay minimization and ringing control. The optimization is based on a fast and accurate delay estimation method under a finite ramp input, where an analytical expression is also derived to estimate overshoot/undershoot voltage. In this paper we specify the wire shape to be of the form f(x)=ae/sup -bx/, since previous studies under the Elmore delay model suggest that exponential wire shape is effective for delay minimization. The relevant transmission line equations are solved by using the Picard-Carson method. The transient response in the time domain is derived as a function of a and b. The coefficients a and b are then determined such that either the actual delay (50% delay) is minimized, or the wiring area is minimized subject to a delay bound. At the same time, the overshoot/undershoot voltage is bounded to prevent false switching. Our method for delay estimation is very efficient. In all the experiments we performed, it is far more accurate than the Elmore delay model and the estimated delay values are very close to SPICE's results. We also find that in determining the optimal shape which minimizes delay, the Elmore delay model performs as good as our method in terms of the minimum actual delay it achieves, i.e. the Elmore delay model has high fidelity. However, in determining the optimal shape which minimizes area subject to a delay bound the Elmore delay model performs much worse than our method. We also find that the constraint for overshoot/undershoot control does affect optimization results for both delay and area minimization objectives.

In this paper, by using calculus of variations, we determine the optimal shape for a wire under the Elmore delay model. Coupling capacitance has been taken into consideration explicitly by treating it as another source of grounded capacitance. Given two wires in parallel, one has uniform width and the other has non-uniform width whose shape is described by a function f(x). Let T/sub D/ be the delay through the non-uniform wire. We determine f(x) such that T/sub D/ is minimized. We also extend our study to the case where a non-uniform wire has two neighboring wires. Our study shows that the optimal shape function satisfies an integral equation. Numerical methods are employed to solve the corresponding differential equation and carry out the integration. We provide an efficient algorithm to find the optimal solution. Experiments show that it only takes several iterations to get the optimal results by using our algorithm. Our experiments also show that the wire delay T/sub D/ is a convex function of the wire width at the driver end.

In this paper, we determine the optimal shape function for a bidirectional wire under the Elmore delay model. Given a bidirectional wire of length L, let f(x) be the width of the wire at position x, 0/spl les/x/spl les/L. Let T/sub DR/ be the right-to-left delay. Let T/sub DL/ be the left-to-right delay. Let T/sub BD/=/spl alpha/T/sub D/R+/spl beta/T/sub DL/ be the total weighted delay where /spl alpha//spl ges/0 and /spl beta//spl ges/0 are given weights such that /spl alpha/+/spl beta/=1. We determine f(x) so that T/sub BD/ is minimized. Our study shows that, /spl alpha/=/spl beta/, the optimal shape function is f(x)=c, for some constant c; if /spl alpha//spl ne//spl beta/, the optimal shape function can be expressed in terms of the Lambert's W function as f(x)=-c/sub f//2c/sub 0/((1/W(-ae/sup -bx/))+1), where c/sub f/ is the unit length fringing capacitance, c/sub 0/ is the unit area capacitance, a and b are constants in terms of the given circuit parameters. If /spl alpha/=0 or /spl beta/=0, our result gives the optimal shape function for a unidirectional wire.

Because of the inaccuracy of the Elmore delay model and its inability to handle inductance, it is necessary to use a more accurate delay model in wire-sizing optimization. This paper presents continuous wire-sizing optimization by using a three pole based delay model. Our work is focused on exponential wire shape f(x)=ae/sup -bx/, i.e, we determine a and b such that either delay or area is minimized. Fringing capacitance and inductance, which have been neglected in previous work on wire sizing, are taken into consideration in the delay model. Expressions involved in calculating all three poles are derived with the help of the Picard-Carson method. Since these expressions are all analytical, the delay calculation is very efficient. In our experiments, the delay model is found to be far more accurate than the Elmore delay model. We also observe that in determining the optimal shape that minimizes delay, the Elmore delay model performs as well as our delay model. However, in determining the optimal shape that minimizes area subject to a delay bound, the Elmore delay model performs much worse than our delay model.

Article Shaping a VLSI wire to minimize delay using transmission line model Share on Authors: Youxin Gao Department of Computer Sciences, University of Texas at Austin, Austin, Texas Department of Computer Sciences, University of Texas at Austin, Austin, TexasView Profile , D. F. Wong Department of Computer Sciences, University of Texas at Austin, Austin, Texas Department of Computer Sciences, University of Texas at Austin, Austin, TexasView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 611–616https://doi.org/10.1145/288548.289096Published:01 November 1998 22citation222DownloadsMetricsTotal Citations22Total Downloads222Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We determine the optimal shape function for a bi-directional wire under the Elmore delay model. Given a bi-directional wire of length L, let f(x) be the width of the wire at position x, 0/spl les/x/spl les/L. Let T/sub DR/ be the right-to-left delay. Let T/sub DL/ be the left-to-right delay. Let T/sub BD/=/spl alpha/T/sub DR/+/spl beta/T/sub DL/ be the total weighted delay where /spl alpha//spl ges/0 and /spl beta//spl ges/0 are given weights such that /spl alpha/+/spl beta/=1. We determine f(x) so that T/sub BD/ is minimized. Our study shows that, if /spl alpha/=/spl beta/, the optimal shape function is f(x)=c, for some constant c; if /spl alpha//spl ne//spl beta/, the optimal shape function can be expressed in terms of the Lambert's W function as f(x)=-(c/sub f/)/(2c/sub 0/)(1/(W(-ae/sup -bx/)+1)), where c/sub f/ is the unit length fringing capacitance, c/sub 0/ is the unit area capacitance, a and b are constants in terms of the given circuit parameters. If /spl alpha/=0 or /spl beta/=0, our result gives the optimal shape function for a uni-directional wire.