Handbook of Algorithms for Physical Design Automation part 15 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. | 122 Handbook of Algorithms for Physical Design Automation X a 2D placement FIGURE Placements of priml using a two eigenvectors and b three eigenvectors. 0- Y . X b 3D placement Partitioning Solutions from Multiple Eigenvectors It is also possible to use multiple eigenvectors to determine arrangements of vertices that minimize the number of cuts. Hall Hal70 suggests that the location of the vertices in r-dimensional space can be used to identify blocks see for a description of his method . Two- and three-dimensional placements of priml are shown in . The three branches in the two-dimensional plot indicate three blocks should be formed. On the other hand it is not as obvious how to cluster vertices in the three-dimensional plot. Instead of minimizing the squared distance between two vertices as in Equations and Frankle and Karp FK86 transform the distance minimization problem to one of finding the point emanating from the projection of x onto all eigenvectors that is furthest from the origin. The vector induced by this point will give a good ordering with respect to the wirelength. Chan et al. CSZ94 use the cosine of the angle between two rows of the 71 x k eigenvector matrix V to determine how close the vertices are to each other. If the cosine between two vectors is close to 1 then the corresponding vertices must belong to the same block. Their k-way partitioning heuristic constructs k prototype vectors with distinct directions to represent blocks and places into the corresponding block the vertices that have corresponding vectors within n radians of the prototype vector. This approach was the starting point for a method devised by Alpert et al. The idea behind multiple eigenvector linear orderings MELO AY95 AKY99 is after removing the first column which corresponds to the zero eigenvalue from V call this matrix V the partition that satisfies the usual mincut objective
