Novel modeling and optimization techniques for nano-scale VLSI designs

Today's integrated circuit design involves dealing with complex VLSI systems and increasingly large number of design constraints. Modern technology demands techniques for efficiently designing high-performance low-power integrated circuits, while requirements for shorter time-to-market restrict the design time. Hence, the design of circuits with millions of components relies on efficient design automation techniques and algorithms. This dissertation introduces several algorithms and modeling techniques for applying mathematical optimization to nano-scale VLSI designs. A novel design flow is proposed using a new mathematical model Numerically Convex Form, which advocates a fundamentally new paradigm for optimizing discrete data using geometric programming techniques. Convex fit, an algorithm for modeling discrete data in this form using the semidefinite programming framework is developed. Compared to the current closed-form modeling, significant reduction in modeling error is demonstrated using this new model. The dissertation proposes two smoothing algorithms; ConvexSmooth: a simultaneous convex fitting and smoothing algorithm and SmartSmooth: a linear time convexity preserving smoothing algorithm. The new model along with the smoothing algorithms are applied to the gate sizing optimization problem for combinational circuits. To demonstrate the applicability of numerically convex forms, a novel algorithm is developed for sizing synchronous sequential circuits, which form the core of modern IC designs. This algorithm combines gate sizing and clock skew optimization algorithm to add an additional degree of freedom to the optimization and can also handle feedback loops. Finally, a robust multi-corner gate sizing algorithm is proposed to concurrently account for the design constraints in multiple process corners and/or modes, while still achieving timing optimization in polynomial time for fast design-for-manufacturing closure.