Handbook of Algorithms for Physical Design Automation part 38 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. | 352 Handbook of Algorithms for Physical Design Automation Given that forces tend to zero at infinity a closed form solution for f x y exists and is given by i 7 r x y - r x y f x y k d x y - dxdy -7-7 r x y - r x y 2 where r x y is the vector representation of position x y . Clearly there is an analogy to electrostas-tics where cell area is interpreted as electric charge f x y is electric potential and f x y represents an electric force field. In practice the force computation is accomplished using a set of discrete bins superimposed over the placement region. The Poisson equation is solved using discretization and finite differences to determine the values of f x y at the centers of bins in the grid. Finally forces are computed approximately using the difference of f x y between adjacent bins. An alternative approach for force computation was proposed in Ref. 16 where the force computation was based on an analogy with the n-body problem. In this method the continuous integral in Equation is replaced with a bin structure based on a Barnes-Hut quad-tree 17 and the forces are computed using a particle-mesh-particle approach. The magnitudes or strength of the constant forces at each iteration must be determined in relationship to the spring forces representing the quadratic wirelength. The spreading of cells should not be too fast otherwise the quality of the placement will be compromised. Conversely the forces should not be weighted too small otherwise their impact will be negligible and many placement iterations will be required for convergence. Hence proper force weighting is a significant implementation decision. In Kraftwerk it is advocated that the maximum strength of all constant forces should be equivalent normalized to the force of a net with wirelength K W H where W and H are the width and height of the placement region respectively. The constant K is a user parameter that can be used to trade-off speed of convergence and the quality of results. .
