Algorithms for non-Hanan-based optimization for VLSI interconnect under a higher-order AWE model

To improve the performance of critical nets where both timing and wire reso urces are stringent, we integrate buffer insertion and driver sizing separa tely with non-Hanan optimization and propose two algorithms: simultaneous b uffer insertion and non-Hanan optimization (BINO) and full plane AWE routin g with driver sizing (FAR-DS). For BINO, we consider the realistic situatio n that buffer locations are restricted to a limited set of available spaces after cell placement, The objective of BINO is to minimize a weighted sum of wire and buffer costs subject to timing constraints. To achieve this obj ective, we suggest a greedy algorithm that considers two operations indepen dently: iterative buffer insertion and iterative buffer deletion, Both are conducted simultaneously with non-Hanan optimization until the improvement is exhausted, For FAR-DS, we investigate the curvature property of the sink delay as a function of both connection location and driver stage ratio in a two-dimensional (2-D) space. The objective of FAR-DS is to minimize a wei ghted sum of wire and driver cost while ensuring that the timing constraint s are satisfied. Based on the curvature property, we search for the optimal solution in the continuous 2-D space, In both RING and FAR-DS, a fourth-or der AWE delay model is employed to assure the quality of optimization, Expe riments of BINO and FAR-DS on both integrated circuit and MCM technologies showed significant cost reductions compared with SERT and MVERT in addition to making the interconnect to satisfy timing constraints.