tailieunhanh - Handbook of algorithms for physical design automation part 13

Handbook of Algorithms for Physical Design Automation part 13 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 102 Handbook of Algorithms for Physical Design Automation GEOMETRIC PROGRAMMING For circuit design applications we often encounter optimization problems with design variables corresponding to the geometry of the circuit. Such problems naturally take the form of a geometric program GP whose definition is described below. An example of a geometric program in the context of physical design is described in Chapter 29. Basic Definitions A monomial function is defined as f x cx x22 xann where c 0 aj e domain off x is x xt 0 For example f x 5x2 3x-0 7x2 5 is a monomial. The nonnegativity of variables xt follow from the fact that they correspond to geometric sizing parameters. Notice that a monomial function is nonconvex in general. For instance f x1 x2 x1x2 is a nonconvex monomial. A posynomial function is defined as the sum of monomial functions f x c . A k 1 where Ck 0 a k e -K and again the domain of f x is x xt 0 A n dv nmnl nnoirn fN-m 1 ci 1 10 mt r m v v _ v2 v 1 v0 5 I O v2 1 v3 An example of posynomial is given uy j A1 A2 A3 A1A2 A3 2A1 A2. A GP is an optimization problem in the form minimize f0 x subject to ft x 1 i 1 . m ht x 1 i 1 . p where f0 . fm are posynomial functions h1 . hp are monomial functions In this original form GP is not a convex problem in general because the constraint functions s are not convex and the equality functions hj s are not affine. However there exists a nonlinear transformation under which the GP problem Equation can be reformulated as an equivalent convex optimization problem. Convex Reformulation of a GP Consider the following nonlinear transformation yt log At At eyt Optimization Techniques for Circuit Design Applications 103 Under this transformation a monomail function f x cxa x x n can be written as log f ey1 . eyn 1 1 --- anyn fi which is affine in y where fi logc. Moreover iff x 2rk l cx xy x1 is posynomial then r log f ey1 . eyn log 22 exp 1ky1 --- a y fik k 1 which is convex in y where fik log ck.