Numerically Convex Forms and Their Application in Gate Sizing

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.