As the continuous trend of Very Large Scale Integration (VLSI) circuits technology scaling and frequency increases, delay optimization techniques for interconnect are increasingly important for achieving timing closure of high performance designs. For the gigahertz microprocessor and multi-million gate ASIC designs it is crucial to have fast algorithms in the design automation tools for many classical problems in the field to shorten time to market of the VLSI chip. This research presents algorithmic techniques and constructive models for two such problems: (1) Fast buffer insertion for delay optimization, (2) Wire sizing for delay optimization and variation minimization on non-tree networks. For the buffer insertion problem, this dissertation proposes several innovative speedup techniques for different problem formulations and the realistic requirement. For the basic buffer insertion problem, an O(n log2 n) optimal algorithm that runs much faster than the previous classical van Ginneken’s O(n2) algorithm is proposed, where n is the number of buffer positions. For modern design libraries that contain hundreds of buffers, this research also proposes an optimal algorithm in O(bn2) time for b buffer types, a significant improvement over the previous O(b2n2) algorithm by Lillis, Cheng and Lin. For nets with small numbers of sinks and large numbers of buffer positions, a simple O(mn) optimal algorithm is proposed, where m is the number of sinks. For the buffer insertion with minimum cost problem, the problem is first proved to be NP-complete. Then several optimal and approximation techniques are proposed to further speed up the buffer insertion algorithm with resource control for big industrial designs. For the wire sizing problem, we propose a systematic method to size the wires of general non-tree RC networks. The new method can be used for delay optimization and variation reduction.

With the advances in process technology, comes the domination of interconnect in the overall propagation delay in modern VLSI designs. Hence, interconnect synthesis techniques, such as buffer insertion, wire sizing and layer assignment play critical roles in the successful timing closure for EDA tools. In this thesis, while our aim is to satisfy timing constraints, accounting for the overhead caused by these optimization techniques is of another primary concern. We utilized a Lagrangian relaxation method to minimize the usage of buffers and metal resources to meet the timing constraints. Compared with the previous work that extended traditional Van Ginneken’s algorithm, which allows for bumping up the wire from thin to thick given significant delay improvement, our approach achieved around 25% reduction in buffer + wire capacitance under the same timing budget.

Switching device power losses place critical limits on the design and performance of high-frequency integrated DC-DC converters. Especially, the layout of metal interconnects in lateral power MOSFETs has a profound effect on their on-resistances and conduction power losses. This thesis presents an analytical interconnect modeling and layout optimization technique for large-area power MOSFETs. The layout optimization of 24V LDMOS transistors in the area of 1 mm2 has achieved an improvement of 55 % in its on-resistance. The simulation result has been verified by experimental measurements on a test chip fabricated in TSMC 0.25 µm HV CMOS technology. In addition, this thesis presents an optimized output stage design methodology for the implementation of a 4 MHz, 12V to 1V integrated DC-DC converter. A segmented output stage scheme is employed to increase the converter efficiency at light load conditions. The peak efficiency of 84% was achieved at load current of 2 A.

Switching device power losses place critical limits on the design and performance of high-frequency integrated DC-DC converters. Especially, the layout of metal interconnects in lateral power MOSFETs has a profound effect on their on-resistances and conduction power losses. This thesis presents an analytical interconnect modeling and layout optimization technique for large-area power MOSFETs. The layout optimization of 24V LDMOS transistors in the area of 1 mm2 has achieved an improvement of 55 % in its on-resistance. The simulation result has been verified by experimental measurements on a test chip fabricated in TSMC 0.25 µm HV CMOS technology. In addition, this thesis presents an optimized output stage design methodology for the implementation of a 4 MHz, 12V to 1V integrated DC-DC converter. A segmented output stage scheme is employed to increase the converter efficiency at light load conditions. The peak efficiency of 84% was achieved at load current of 2 A.