Algorithms for non-Hanan-based optimization for VLSI interconnect under a higher-order AWE model
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
To improve the performance of critical nets where both timing and wire resources are stringent, we integrate buffer insertion and driver sizing separately with non-Hanan optimization and propose two algorithms: simultaneous buffer insertion and non-Hanan optimization (BINO) and full-plane AWE routing with driver sizing (FAR-DS). For BINO, we consider the realistic situation 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 objective, we suggest a greedy algorithm that considers two operations independently: 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 weighted sum of wire and driver cost while ensuring that the timing constraints are satisfied. Based on the curvature property, we search for the optimal solution in the continuous 2-D space. In both BINO and FAR-DS, a fourth-order AWE delay model is employed to assure the quality of optimization. Experiments 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. 2000 IEEE.
