Handbook of Algorithms for Physical Design Automation part 21 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. | 182 Handbook of Algorithms for Physical Design Automation b w x y z h c Parent links X Y X Z 1 2 3 4 5 Indices 1 23456789 d FIGURE a 3D slicing floorplan with five modules. b Corresponding slicing tree. c Dimensions of a 3D block. d Static array. where n is the number of modules. Each of the first n 1 elements in the array represents an internal node and the first element always represents the root of the tree. The last n elements represent the leaves. Each element of the array is associated with a ten-tuple t p l r x y z w d h . The t is the tag information and its value is X Y or Z for each internal node and a module name for a leaf. p I and r denote the element indices in the array for the parent the left child and the right child of a node respectively. The x y z w d h are the dimensional information of a module or a subfloorplan and x y z is called the base point see Figure . Figure is the static array for the slicing tree shown in Figure where only the parent link of each element is drawn for simplicity. Given the static array of a slicing tree the position of each module and the dimensions of the corresponding floorplan can be calculated by a recursive procedure starting from the root. Two kinds of moves exchange and rotation are used during the annealing process for generating neighboring solutions. An exchange move randomlychooses two subtrees and swaps them as aresult the two corresponding elements in the static array will be updated accordingly. On the other hand a rotation move randomly selects a subtree and rotates the corresponding subfloorplan along x- y- or z-axis as a result the elements of the static array corresponding to the internal nodes contained in the subtree will be updated accordingly. It can be proved that the two neighborhood moves are complete in the sense that each slicing tree can be reached from another one via at most 10n 6 moves. This 3D floorplanner can be specialized to solve the 2D problem as well and .
