Interconnect optimization in deep sub-micron design under the transmission line model

As the VLSI technology has been scaled down to 0.18μm in recent years and is expected to be scaled down to 0.05μ m in the near future, interconnect delay becomes an important factor in achieving high performance. In deep sub-micron design, interconnect delay is shown to be 10 to a few hundred times bigger than the intrinsic gate delay for a global interconnect, and thus dominates the circuit delay. To reduce interconnect delay, wire-sizing and buffer insertion/sizing are two effective techniques. One of the approaches to wire-sizing is continuous wire-sizing. In continuous wire-sizing, the shape of a wire is described by a continuous function, and the objective is to find a shape function which minimizes delay or minimizes area subject to a delay bound.; In the first part of this dissertation, we present some continuous wire-sizing results under the Elmore delay model. Comparing with previous work, our algorithm can not only deal with uni-directional wires but also bi-directional wires, where both solutions are in closed form. We also develop an efficient algorithm to determine the optimal wire shape for wires with one or two neighboring wires. These results are useful in optimization under the transmission line model, since they can give very good initial solutions.; However, since it is well known that the Elmore delay model is not an accurate delay model, those optimal results determined under the Elmore delay model may be inferior. In the second part of this dissertation, we present some wire-sizing results under the transmission line model. For a special case where fringing capacitance and inductance are not considered, we solve the transmission line equations analytically and derive a closed form solution on the transient response for an exponential wire shape f( x) = ae−bx. We then determine a and b such that either delay is minimized or area is minimized subject to a target delay bound. For a general case where fringing capacitance and inductance are considered, we solve the transmission line equations by using the Picard-Carson method. We then develop a three pole based delay model. Analytical expressions for estimating delay at any threshold voltage and overshoot/undershoot voltage are further derived. The optimal wire shape is determined to minimize delay or area subject to undershoot voltage constraint. To calculate delays for interconnects with buffers inserted, we combine the wire delay model under the transmission line model with a buffer macromodel (k-factor equations) to provide a fast and accurate delay estimation method.; In the third part of this dissertation, we present a graph based algorithm for optimal buffer insertion under accurate delay models. The algorithm determines the 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 is a shortest path problem. Our 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.