Handbook of Algorithms for Physical Design Automation part 37 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. | 342 Handbook of Algorithms for Physical Design Automation to. For each region this introduces an equation as an additional constraint on the solution of the QP Equation . Kleinhans et al. 1991 show how this constrained quadratic program can be reduced elegantly to an unconstrained QP with the following transformation. For n movable cells and k additional constraints the constrained QP may be written in the form min x Ax. 2bT x . I S x t where the k x n-matrix I S consists of the k x k-identity matrix I and a k x n k -matrix S. With x O wherex1 e Rk andx2 e Rn k the linear constraints can be written as x1 t Sx2. Hence we only have to compute the entries of x2 by solving the following unconstrained problem on n k variables t Cr T ft t t Sx2 t Sx2 t Sx2 A x . x2 x2 x2 By ignoring all constant summands in the objective function we get the equivalent problem min x2T UTAUx2 2vTx2 where U j and v UT b A . The matrix UTAU is positive definite if A is positive definite but usually UTAU will not be sparse. Therefore for an efficient solution an explicit computation of UTAU must be avoided. Fortunately the conjugate gradient method see Section only requires to multiply UTAU with a vector which can be done by three single multiplications of a sparse matrix and a vector. Hence provided that the number of constraints is small compared to the number of cells the conjugate gradient method will efficiently solve the problem Equation . Prescribing the centers of gravity of the cell groups is an efficient way to spread the cells over the chip area. However we cannot be sure that all cells are placed inside their region which can be a problem for ensuing partitioning steps. Moreover the constraints may be too strong if we do not demand an even distribution of the cells. If we allow a higher area utilization in some regions it will often be reasonable to place cells in their region in such a way that their center of gravity is far away from the center of the .
