SmartSmooth: A linear time convexity preserving smoothing algorithm for numerically convex data with application to VLSI design

摘要

Convex optimization problems are very popular in the VLSI design society due to their guaranteed convergence to a global optimal point. While optimizing tabular data, significant fitting efforts are required to fit the data into convex form. Fitting the tables into analytically convex forms like posynomials, suffers from excessive fitting errors, as the fitting problem may be non-convex. In recent literature optimal numerically convex tables have been proposed. Since these tables are numerical, it is extremely important to make the table data smooth, and yet preserve its convexity. The smoothness ensures that the convex optimizer behaves predictably and converges quickly to the global optimal point. The existing smoothing techniques either cannot preserve convexity, or require very high execution time. In this paper, we propose a linear time algorithm to smoothen a given numerically convex data and at the same time preserve convexity. Our proposed algorithm SmartSmooth can smoothen the data in linear time without introducing any additional error on the numerically convex data. We present our SmartSmooth results on industrial cell libraries. SmartSmooth when applied on convex tables produced by ConvexFit shows a 30 reduction in fitting square error over a posynomial fitting algorithm.