VLSI interconnect layout optimization

As VLSI circuitry reaches deep submicron (DSM) device dimension, operates at giga-Hertz clock frequencies, and is packaged in highly integrated multichip modules, the performance of interconnect structures becomes a dominating factor in determining system performance and reliability. The interconnect design and optimization problem is one of the most challenging issues today in the design of high-performance and high-density circuits in the DSM VLSI technologies. This dissertation presents three interrelated topics on VLSI interconnect layout design and optimization: the simultaneous driver/buffer and wire sizing (SD/BWS) problem, the minimum-cost bounded-skew tree (BST) routing problem, and the required-arrival-time Steiner tree (RATS-tree) routing problem.; The SD/BWS problem concerns the optimization of the number of cascaded chain of drivers, the driver/buffer sizes, and the wire widths for a given routing tree with prescribed buffer locations such that either (i) the delay is minimized, or (ii) the combined objective of delay and power dissipation is minimized. We establish a general dominance property of the SD/BWS problem. This property leads to a polynomial-time algorithm that computes tight upper and lower bounds of an optimal solution, which enables us to efficiently compute the optimal SD/BWS solution.; The minimum-cost BST problem captures several engineering trade-offs in the design of routing topologies with controlled skew. Our BST algorithm constructs bounded-skew routing solutions via constructions of well-behaved merging regions. We present two approaches to construct the merging regions: (i) the boundary merging and embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the interior merging and embedding (IME) algorithm which considers merging points that are interior to, as well as on the boundary of the merging regions.; The RATS-tree formulation handles a large class of routing topologies, ranging from shortest-path Steiner routing, bounded-radius Steiner routing, to minimal Steiner routing. In our RATS-tree algorithm, we try to bridge the gap between the timing models used for circuit simulation and those used in interconnect optimization. Our new incremental moment computation method enables easy incorporation of moment computation and accurate delay modeling into interconnect optimization. We perform optimization of topology, wire-sizing, and termination simultaneously to optimize not just signal delay, but also signal integrity under a higher-order interconnect model.