Title :
SmartSmooth: A linear time convexity preserving smoothing algorithm for numerically convex data with application to VLSI design
Author :
Roy, Sanghamitra ; Chen, Charlie Chung-Ping
Author_Institution :
Dept. of Electr. & Comput. Eng., Wisconsin Univ., Madison, WI
Abstract :
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 30times reduction in fitting square error over a posynomial fitting algorithm.
Keywords :
VLSI; circuit optimisation; convex programming; integrated circuit design; polynomials; ConvexFit; SmartSmooth; VLSI design; convex optimization; convex tables; fitting square error; global optimal point; linear time algorithm; linear time convexity; numerically convex data; posynomial fitting algorithm; smoothing algorithm; Algorithm design and analysis; Convergence; Design optimization; Fitting; Libraries; Numerical models; Shape; Smoothing methods; Table lookup; Very large scale integration;
Conference_Titel :
Design Automation Conference, 2007. ASP-DAC '07. Asia and South Pacific
Conference_Location :
Yokohama
Print_ISBN :
1-4244-0629-3
Electronic_ISBN :
1-4244-0630-7
DOI :
10.1109/ASPDAC.2007.358045