tailieunhanh - Handbook of algorithms for physical design automation part 62

Handbook of Algorithms for Physical Design Automation part 62 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. | 592 Handbook of Algorithms for Physical Design Automation convexifying the look-up table data with minimum perturbation can be formulated as a convex semidefinite optimization Roy 2005 problem and hence optimality can be reached in polynomial time. Thus given a numerical function g x for the original delay let f x g x 3 x . 3 x is the perturbation of g x and f x is the transformed function. Any function x is convex if and only if the Hessian matrix V2 x 0 for all x e DOM0. V2 x 0 means the Hessian of x is positive semidefinite . all the eigenvalues of the Hessian are greater than or equal to zero. Thus the fitting problem is to minimize 3 x to make the Hessian off x positive semidefinite. The problem is defined as follows minimize 2 1 x subject to V2 g x 3 x 0 x e DOMg Sequential Quadratic Programming Algorithm The convex optimization problem of concurrent gate and wire sizing can also be solved using the sequential quadratic programming SQP method Menezes 1997 Chu 1999b . SQP reduces a nonlinear optimization to a sequence of quadratic programming QP subproblems. A general convex quadratic program can be represented as minimize 1XT QX XT C subject to ATX bi i e I where Q is a symmetric positive semidefinite matrix I is the set of inequalities Now if we want to minimize a function F X subject to the constraints ht X 0 i 1. m then we can express the Lagrangian of F x as L X X F X kfa X i 1 where X is the Lagrange multiplier associated with the ith constraint. Now if G X VF x be the gradient of the objective function the original optimization problem can be solved by solving a sequence of QP subproblems as shown below minimize 2 X X0 TB X0 X X0 X X0 G X0 subject to X X0 TV hi X h X 0 i 1. m where X0 is the solution of the previous QP iteration B X0 is the approximation of the Hessian of the Lagrangian Variational Calculus-Based Nonuniform Sizing Algorithm All the wire-sizing techniques presented so far are uniform wire-sizing techniques. Now we .