Numerically convex forms and their application in gate sizing
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
26
Journal Issue
9
Pages
1637-1647
Date Issued
2007
Author(s)
Abstract
Convex-optimization techniques are very popular in the very large-scale-integration design society due to their guaranteed convergence to a global optimal point. The table data need to be fitted into convex forms to be used in the convex optimization problems. Fitting the tables into polynomials, which are analytically convex under logarithmic transformation, may suffer from the excessive fitting errors as the fitting problem is nonconvex. In this paper, we propose to directly adjust the lookup-table values into a numerically convex lookup table without any explicit analytical form. We show that numerically "convexifying" the lookup-table data with minimum perturbation can be formulated as a convex semidefinite optimization problem, and hence, optimality can be reached in polynomial time. We also propose three algorithms to make the table data smooth to enable faster convergence of the convex optimizer. Results from extensive experiments on industrial cell libraries demonstrate 9.6 improvement in fitting error over a well-developed polynomial-fitting procedure. We illustrate the effectiveness of this model in a convex optimization problem by providing results for using our model in the optimal gate sizing of standard cells. We observe a 5.07% improvement in the delay of International Symposium on Circuits and Systems (ISCAS) benchmark circuits over the polynomial-fitting procedure.
SDGs
Type
journal article