Algorithms for interconnect planning and optimization in deep-submicron VLSI design

In this dissertation, we focus on the problems related to interconnect optimization and planning in deep-submicron (DSM) VLSI design.; We first address the problem of chip-level timing optimization by buffer insertion on global wires. We propose an approach which considers all global nets simultaneously to take advantage of slacks on noncritical nets. We formulate the problem as a constrained optimization problem, where buffer area is the objective function to be minimized and timing specifications are the constraints. We transform this problem into a series of subproblems using Lagrangian relaxation wherein the constraints are dropped out and added as penalties to the objective function. We show that each subproblem can be solved optimally, i.e., we can find optimal buffer solutions that minimize the objective in the subproblem. Experiments show our approach not only gives considerable timing optimization but also uses much less buffer area.; We then turn to the problem of clock tree generation for high-performance VLSI systems in presence of process variations. Traditionally, clock tree generation has been performed in several stages: topology generation, routing, and buffer insertion and wire sizing. However, a sequential approach cannot guarantee zero-skew. We propose an algorithm to consider clock tree routing, buffer insertion, and wire sizing at the same time. We integrate clock tree construction and buffer insertion/wire sizing in one algorithm to consider all the design variables simultaneously. We show the clock trees generated by this algorithm are zero-skew by construction and have small delay, while using the total wirelength comparable to existing approaches.; Finally, we address the problem of integrating floorplanning and power supply planning, in order to reduce hot spots in DSM integrated circuits. Our goal is to find a floorplan such that the power requirement of all the circuit blocks are met while the floorplan area and total wirelength are small. We prove that the optimal assignment of power bumps to circuit blocks can be solved using network flow algorithms, which are then used to evaluate the goodness of a floorplan in power distribution in a floorplanning algorithm. Furthermore, we propose a post-processing algorithm to further reduce the IR drop on power lines by restricted cell permutation. We experimentally show using our approach the penalty in the floorplan area and wirelength is small, while the power requirement of the circuit blocks are met.