loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2007 Asia and South Pacific Design Automation Conference
SmartSmooth: A linear time convexity preserving smoothing algorithm for numerically convex data with application to VLSI design
Yokohama
January 23-January 26
ISBN: 1-4244-0629-3
Sanghamitra Roy, ECE Department, University of Wisconsin-Madison. roy1.wisc.edu
Charlie Chung-Ping Chen, EE Department, National Taiwan University. cchen@cc.ee.ntu.edu.tw
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.
Citation:
Sanghamitra Roy, Charlie Chung-Ping Chen, "SmartSmooth: A linear time convexity preserving smoothing algorithm for numerically convex data with application to VLSI design," asp-dac, pp.559-564, 2007 Asia and South Pacific Design Automation Conference, 2007
Usage of this product signifies your acceptance of the Terms of Use.