Handbook of Algorithms for Physical Design Automation part 24 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. | 212 Handbook of Algorithms for Physical Design Automation For the exchange and insert rotate and randomize operations the first l terms of the given CS will not be changed during perturbation where l min i j - 1 l i - 1 . Therefore for each perturbation we only need to consider the modules after the 1th term and perform incremental update on the existing packing solution . The coordinate of module bt in Si i l 1 . m can be obtained by inserting a node nt into two neighboring nodes nj and nk in L if Dt j k . However if the designated nodes do not exist in L we randomly insert the node nt into two arbitrary neighboring nodes nq and nr in L and thus Di q r . Note that we can guarantee a feasible solution after each perturbation by applying this process. Figure illustrates the procedure to perturb the CS using the exchange operation. If two modules f and h in S6 and S8 are exchanged we have the new CS shown in Figure . Figure shows the placement and L for the CS before perturbation. Modules a b c d and e are in the first five terms of the CS and will not be changed for this perturbationbecause l min 6 8 -1 5 here. The coordinates of the modules in the last three terms of CS can be obtained by their corresponding bends. We insert nodes between two designated neighboring nodes according to their bends . Figure shows the resulting placement and L after we insert the node nh between the nodes ne and nc in the L of Figure . Then for module g we cannot place it at the designated bend c t because there do not exist two adjacent nodes nc and nt in the L of Figure . Therefore we randomly insert ng into two arbitrary neighboring nodes in L. There are three candidate bends for placing module g s e e h and h t see the L and the placement . If we insert ng between ne and nh the new bend of module g becomes e h the resulting placement and L is given in Figure . Similarly we intend to insert nf between nodes nf and nc for the module f in the L of
