Handbook of algorithms for physical design automation part 23.pdf (Sổ tay thuật toán)

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 202 Finals Page 202 24-9-2008 #19 Handbook of Algorithms for Physical Design Automation 2. S. Zhou, S. Dong, C. K. Cheng, and J. Gu. ECBL: An extended corner block list with solution space including optimum placement. International Symposium on Physical Design, Sonoma, California, 2001. 3. K. Sakanushi and Y. Kajitani. The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization. Proceedings of IEEE Asia Pacific Conference on Circuits and Systems, Tianjin, China, pp. 829–832, 2000. 4. K. Sakanushi, Y. Kajitani, and D. P. Mehta. The quarter-state-sequence floorplan representation. IEEE Transactions on Circuits and Systems I, 50(3): 376–386, 2003. 5. C. Zhuang, K. Sakanushi, L. Jin, and Y. Kajitani. An enhanced Q-sequence augmented with empty room insertion and parenthesis trees. Design, Automation and Test in Europe Conference and Exhibition, Paris, France, pp. 61–68, 2002. 6. B. Yao, H. Chen, and C. K. Cheng. Floorplan representations: Complexity and connections. ACM Transactions on Design Automation of Electronic Systems, 8(1): 55–80, 2003. (ISPD 2001). 7. G. Baxter. On fixed points of the composite of commuting functions. Proceedings of American Mathematics Society, 15: 851–855, 1964. 8. F. R. K. Chung, R. L. Graham, J. E. E. Hoggatt, and M. Kleiman. The number of Baxter permutations. Journal of Combinatorial Theory, Series A, 24(3): 382–394, 1978. 9. S. Dulucq and O. Guibert. Baxter permutations. Discrete Mathematics, 180: 143–156, 1998. 10. E. F. Y. Young, C. C. N. Chu, and Z. C. Shen. Twin binary sequences: A non-redundant representation for general non-slicing floorplan. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(4): 457–469, 2003. (ISPD 2002). 11. Y. Ma, S. Dong, X. Hong, Y. Cai, C. -K. Cheng, and J. Gu. VLSI floorplanning with boundary constraints based on corner block list. IEEE Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 509–514, 2001. 12. Y. Ma, X. Hong, S. Dong, Y. Cai, C. K. Cheng, and J. Gu. Floorplanning with abutment constraints and L-shaped/T-shaped blocks based on corner block list. Proceedings of the 38th ACM/IEEE Design Automation Conference, Las Vegas, NV, pp. 770–775, 2001. 13. Z. C. Shen and C. C. N. Chu. Bounds on the number of slicing, mosaic and general floorplans. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(10): 1354–1361, 2003. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 203 29-9-2008 #2 Floorplan 11 Packing Representations Tung-Chieh Chen and Yao-Wen Chang CONTENTS 11.1 Introduction.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.1.1 Problem Definition ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.2 O-Tree . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.2.1 Relationship between a Placement and an O-Tree . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.2.2 O-Tree Perturbations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.3 B∗ -Tree . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.3.1 From a Placement to a B∗ -Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.3.2 From a B∗ -Tree to a Placement.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.3.3 B∗ -Tree Perturbations .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.4 Corner Sequence . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.4.1 From a Placement to a CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.4.2 From a CS to a Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.4.3 CS Perturbations . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.5 Sequence Pair . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.5.1 From a Placement to an SP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.5.2 From an SP to a Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.5.3 SP Perturbations.. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.6 Bounded-Sliceline Grid .. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.6.1 From a BSG Assignment to a Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.6.2 BSG Perturbations . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.7 Transitive Closure Graph . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.7.1 From a Placement to a TCG .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.7.2 From a TCG to a Placement .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.7.3 TCG Properties.. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.7.4 TCG Perturbations . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.8 TCG-S . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.8.1 From a Placement to TCG-S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.8.2 From TCG-S to a Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.8.3 TCG-S Perturbations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.9 Adjacent Constraint Graph . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.9.1 ACG Properties . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.9.2 ACG Perturbations ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.10 Discussions . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.10.1 Comparisons between O-Trees and B∗ -Trees . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 11.10.2 Equivalence of SP and TCG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 204 204 205 205 206 207 207 207 208 208 209 209 211 213 213 213 216 216 217 218 218 218 219 220 220 221 221 223 223 224 225 226 227 227 228 203 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 204 Finals Page 204 29-9-2008 #3 Handbook of Algorithms for Physical Design Automation 11.11 3D Floorplan Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.11.1 T-Tree . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.11.2 Sequence Triplet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.11.3 3D-SubTCG .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.12 Application in Handling other Constraints in Floorplan Design . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.12.1 Boundary Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.12.2 Rectilinear Modules.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 11.13 Summary . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . 229 229 231 231 233 233 234 236 237 11.1 INTRODUCTION As technology advances, design complexity is increasing and the circuit size is getting larger. To cope with the increasing design complexity, hierarchical design and IP modules are widely used. This trend makes module floorplanning/placement much more critical to the quality of a VLSI design than ever. A fundamental problem to floorplanning/placement lies in the representation of geometric relationship among modules. The representation profoundly affects the operations of modules and the complexity of a floorplan/placement design process. It is thus desired to develop an efficient, flexible, and effective representation of geometric relationship for floorplan/placement designs. Many floorplan representations have been proposed in the literature. We can represent a floorplan as a rectangular dissection of the floorplan region, and classify the representations based on the floorplan structures that the representations can model. Preceding chapters have covered the slicing structure [1,2], which can be obtained by repetitively subdividing rectangles horizontally or vertically into smaller rectangles, and the mosaic structure [3] for which the floorplan region is dissected into rooms so that each room contains exactly one module. The mosaic structure is more general than the slicing structure in the sense that the former can model more floorplan structures. This chapter focuses on the representations for the packing structure, the most general floorplan representation that can model a floorplan with empty rooms. There is a special type of the packing structure, the compacted structure, for which modules are compacted to some corner of the floorplan region, say the bottom-left corner, and no module can further be shifted down or left. The compacted structure induces much smaller solution spaces than the general one. Unlike the general packing representation, which can fully model the topological relationship among modules [4–8], however, the compacted packing representations [9–11] can model only partial topological information, and thus the module dimensions are required to construct an exact floorplan. In this chapter, we shall detail the modeling, properties, and operations of the popular packing floorplan representations in the literature: compacted floorplan representations such as O-tree, B∗ -tree, and corner sequence (CS), and general packing ones such as sequence pair (SP) [6], boundedsliceline grid (BSG), transitive closure graph (TCG), transitive closure graph with a sequence (TCG-S), and adjacent constraint graph (ACG) [8]. 11.1.1 PROBLEM DEFINITION To make this chapter self-contained, we shall start with the definition of the floorplanning problem. Let B = {b1 , b2 , . . . , bm } be a set of m rectangular modules whose width, height, and area are denoted by wi , hi , and ai , 1 ≤ i ≤ m. Each module is free to rotate. Let (xi , yi ) denote the coordinate of the bottom-left corner of module bi , 1 ≤ i ≤ m, on a chip. A placement P is an assignment of (xi , yi ) for each bi , 1 ≤ i ≤ m, such that no two modules overlap. The goal of floorplanning/placement is to optimize a predefined cost metric such as a combination of the area (i.e., the minimum bounding rectangle of P) and wirelength (i.e., the summation of half bounding box of interconnections) induced by a placement. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 205 29-9-2008 #4 205 Packing Floorplan Representations In the following sections, we first introduce the compacted packing floorplanning representations, O-tree [10], B∗ -tree [9], and CS [11], and then the general ones, SP [6], BSG [7], TCG [4,12], TCG-S [5,13], and ACG [8]. 11.2 O-TREE An O-tree is used to model an admissible placement defined in Ref. [10]. A placement is said to be admissible if and only if all modules are compacted in both x- and y-directions; i.e., no module can shift left or down with other modules being fixed. Figure 11.1a gives an example of an admissible placement. 11.2.1 RELATIONSHIP BETWEEN A PLACEMENT AND AN O-TREE An O-tree is a rooted ordered tree structure with an arbitrary number of branches (children) for each node. There are two types of O-trees, horizontal O-trees and vertical O-trees. Given an admissible placement, a horizontal O-tree T can be constructed as follows. The root represents the left boundary of the placement. The children are adjacent to and on the right-hand side of their parent with zero separation distance in the x-direction. See Figure 11.1b for a horizontal O-tree of the admissible placement shown in Figure 11.1a. A vertical O-tree can similarly be defined by making the root represent the bottom boundary of the placement and an edge represent the vertical geometrical relationship between two modules. An O-tree is encoded by the two-tuple (S, π), where the 2(n − 1)-bit string S identifies the branching structure of the n-node tree, and the permutation π denotes the module sequence for the depth-first search (DFS) traversal of the tree. A “0” (“1”) represents a traversal which descends (ascends) an edge in the tree. An example is shown in Figure 11.1b for the two-tuple (S, π) = (001100011101, abcdef ) that encodes the placement/floorplan shown in Figure 11.1a. Because the root of a horizontal O-tree represents the left boundary of the placement/floorplan, we set its coordinate (xroot , yroot ) = (0, 0). Let node ni be the parent of node nj , we have xj = xi + wi . For each module bi , let L(i) be the set of modules bk ’s on the left of bi in π, and interval (xk , xk + wk ) overlaps interval (xi , xi + wi ) by a nonzero length. If L(i) is nonempty, we have maxk∈L(i) {yk + hk }, L(i) = ∅ yi = 0, otherwise We can find a placement by visiting the tree in the DFS order from an horizontal O-tree. To efficiently compute the y-coordinate from a horizontal O-tree, we can adopt the contour data structure [10] to facilitate the operations on modules. The contour structure is a doubly linked list for modules, describing the contour curve in the current compaction direction. A horizontal f c d Root 0 e na 0 1 1 1 0 b 0 nf 1 0 nb a nc 1 nd 0 1 ne (a) (b) FIGURE 11.1 (a) Admissible placement and (b) O-tree for the placement shown in (a). Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 206 Finals Page 206 29-9-2008 #5 Handbook of Algorithms for Physical Design Automation Horizontal contour Newly added module Original contour f c d New contour e b a FIGURE 11.2 To add a new module on top, we search the horizontal contour from left to right and update it with the top boundary of the new module. contour (Figure 11.2) can be used to reduce the running time for finding the y-coordinate of a newly inserted module. Without the contour, the running time for determining the y-coordinate of a newly inserted module would be linear to the number of modules. However, the y-coordinate of a module can be computed in amortized O(1) time by maintaining the contour structure [10], making the overall packing time for a floorplan to be linear to the number of modules. Figure 11.2 illustrates how to update the horizontal contour after inserting a new module. 11.2.2 O-TREE PERTURBATIONS An O-tree can be perturbed by the following steps: (1) select a module bi in the original O-tree (S, π), (2) delete a module bi from the O-tree (S, π), and (3) insert a module bi in the position with the best value of the cost function among all possible external positions in (S, π). Figure 11.3 gives the definition of the internal and external positions. Given an O-tree with n nodes, there are 2n − 1 possible inserting positions as external nodes. In Figure 11.3, there are 13 possible inserting positions in the 7-node tree. The operation of finding these positions on (S, π) is simply adding a string 01 to any position in bit string S and adding the label to its related position in π. Root na nc nb nd ne nf External node Internal node FIGURE 11.3 Internal and external insertion positions. To facilitate updating the encoding tuple, the O-tree allows a node to be inserted only at the external positions. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 207 29-9-2008 #6 207 Packing Floorplan Representations 11.3 B∗ -TREE B∗ -trees, proposed by Chang et al. [9], are based on ordered binary trees and the admissible placement. Inheriting from the nice properties of ordered binary trees, B∗ -trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only constant, constant, and linear times. There exists a unique correspondence between an admissible placement and its induced B∗ -tree. Given an admissible placement P, in other words, we can construct a unique B∗ -tree corresponding to P, and the packing corresponding to the B∗ -tree is the same as P. Therefore, an optimal placement (in terms of packing area)—an admissible placement—always corresponds to some B∗ -tree. The nice property of the unique correspondence between an admissible placement and its induced B∗ -tree prevents the search space from being enlarged with redundant solutions and guarantees that an optimal placement can be found by searching on B∗ -trees. 11.3.1 FROM A PLACEMENT TO A B∗ -TREE Given an admissible placement P, we can represent it by a unique (horizontal) B∗-tree T . Figure 11.4b gives an example of a B∗ -tree representing the placement of Figure 11.4a. A B∗ -tree is an ordered binary tree whose root corresponds to the module on the bottom-left corner. Similar to the DFS procedure, we construct the B∗ -tree T for an admissible placement P in a recursive fashion: Starting from the root, we first recursively construct the left subtree and then the right subtree. Let Ri denote the set of modules located on the right-hand side and adjacent to bi . The left child of the node ni corresponds to the lowest module in Ri that is unvisited. The right child of the node ni represents the lowest module located above and with its x-coordinate equal to that of bi . Following the aforementioned DFS procedure and definitions, we can guarantee the One-to-one correspondence between an admissible placement and its induced B∗ -tree. As shown in Figure 11.4, it makes the module a the root of T because a is on the bottom-left corner. Constructing the left subtree of na recursively, it makes nb the left child of na . Because the left child of nb does not exist, it then constructs the right subtree of nb . The construction is recursively performed in the DFS order. After completing the left subtree of na , the same procedure applies to the right subtree of na . The resulting B∗ -tree for the placement of Figure 11.4a is shown in Figure 11.4b. The construction takes only linear time. 11.3.2 FROM A B∗ -TREE TO A PLACEMENT Given a B∗ -tree T , we shall compute the x- and y-coordinates for each module associated with a node in the tree. The x- and y-coordinates of the module associated with the root (xroot , yroot ) = (0, 0) f c d na e nc nb a nd b nf ne (a) (b) FIGURE 11.4 (a) Admissible placement and (b) the (horizontal) B∗ -tree representing the placement. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 208 Finals Page 208 29-9-2008 #7 Handbook of Algorithms for Physical Design Automation because the root of T represents the bottom-left module. The B∗ -tree keeps the geometric relationship between two modules as follows. If node nj is the left child of node ni , module bj must be located on the right-hand side and adjacent to module bi in the admissible placement; i.e., xj = xi + wi . Besides, if node nj is the right child of ni , module bj must be located above, with the x-coordinate of bj equal to that of bi ; i.e., xj = xi . Therefore, given a B∗ -tree, the x-coordinates of all modules can be determined by traversing the tree once. Similar to the O-tree, the contour data structure is adopted to efficiently compute the y-coordinate from a B∗ -tree (Section 11.2.1). Overall, given a B∗ -tree, we can determine the corresponding packing (i.e., compute the x- and y-coordinates for all modules) in linear time. 11.3.3 B∗ -TREE PERTURBATIONS Given an initial B∗ -tree (a feasible solution), we perturb the B∗ -tree to another using the following three operations. • Op1: rotate a module • Op2: move a module to another place • Op3: swap two modules Op1 rotates a module, and the B∗ -tree structure is not changed. Op2 deletes and inserts a node. Op2 and Op3 need to apply the deletion and insertion operations for deleting and inserting a node from and to a B∗ -tree. We explain the two operations in the following. Deletion: There are three cases for the deletion operation. • Case 1: a leaf node • Case 2: a node with one child • Case 3: a node with two children In Case 1, we simply delete the target leaf node. In Case 2, we remove the target node and then place its only child at the position of the removed node. The tree update can be performed in O(1) time. In Case 3, we replace the target node nt by either its right child or its left child nc . Then we move a child of nc to the original position of nc . The process proceeds until the corresponding leaf node is handled. Such a deletion operation requires O(h) time, where h is the height of the B∗ -tree. Note that in Cases 2 and 3, the relative positions of the modules might be changed after the operation, and thus we might need to reconstruct a corresponding placement for further processing. Insertion: While adding a module, we can place it around some module. We define two types of positions as follows. • Internal position: a position between two nodes in a B∗ -tree • External position: a position pointed by a NULL pointer We can insert a new node into either an internal or an external position. 11.4 CORNER SEQUENCE Corner Sequence (CS) = (S1 , D1 )(S2 , D2 ) · · · (Sm , Dm ) uses a packing sequence S of the m modules as well as the corresponding bends D formed by the modules to describe a compacted placement [11]. Each two-tuple (Si , Di ), 1 ≤ i ≤ m, is referred to as a term of the CS. We first show how to derive a CS representation from a compacted placement. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 209 29-9-2008 #8 209 Packing Floorplan Representations 11.4.1 FROM A PLACEMENT TO A CS A module bi is said to cover another module bj if bi is higher than bj and their projections in the x axis overlap, or bi is right to bj and their projections in the y axis overlap (i.e., yj ≤ yi , xj > xi and xj < xi , or if xj ≤ xi , yj > yi and yj < yi ). Here, xi = xi + wi and yi = yi + hi . Given an admissible placement [10] (a left and bottom compacted placement), we first pick the dummy modules bs and bt , and make R = st for the two chosen modules. The module bi on the bottom-left corner of P is picked (i.e., S1 = bi and D1 = [s, t]) because it is the unique module at the bend of R, and the new R becomes sit. When there exists more than one module at bends, we pick the left-most module that does not cover other unvisited modules at the bends. Therefore, the module bj at the bend [s, i] is picked if bj exists and bj does not cover the other unvisited module bk at the bend [i, t]; otherwise, bk is picked. This process continues until no module is available. On the basis of above procedure, there exists at least one module at a bend of the current R before all modules are chosen because the placement is compacted. Therefore, there exists a unique CS corresponding to a compacted placement. Figure 11.6a through h show the process to build a CS from the placement P of Figure 11.5a. R initially consists of s and t. Module a at bottom-left corner is chosen first because it is the unique module at the bend of R(S1 = a and D1 = [s, t]). Figure 11.6a shows the resulting R (denoted by heavily shaded areas). Similarly, module b is chosen (S2 = b and D2 = [a, t]) and the new R is shown in Figure 11.6b. After module bd in Figure 11.6b is chosen, a and b are removed from R because the corner formed by a and b is already occupied (see Figure 11.6c for the new R). As shown in Figure 11.6d, there exist two modules bf and bc at bends. Although bf is left to bc , we pick bc first because bf covers bc . This process repeats until no module is available, and the resulting CS is shown in Figure 11.6i. 11.4.2 FROM A CS TO A PLACEMENT The dynamic sequence packing (DSP for short) scheme [11] is used to transform a CS into a placement. For DSP, a contour structure is maintained to place a new module. Let L be a doubly linked list that keeps modules in a contour. Given a CS, we can obtain the corresponding placement in O(m) time by inserting a node into L for each term in the CS, where m is the number of modules. L initially consists of ns and nt that denote dummy modules s and t, respectively. For each term (i, [j, k]) in a CS, we insert a node ni between nj and nk in L for module bi , and assign the x(y) coordinate of module bi as xj (yk ). This corresponds to placing module bi at the bend [j, k]. Then, those modules that are dominated by bi in the x(y) direction should be removed from R. This can be done by deleting the predecessor (successor) np ’s of ni in L if yp ’s (xp ’s) are smaller than yi (xi ). The [s, e] e f d a b [e, h] e h f h s c a d c b g g [s, t] t (a) (b) FIGURE 11.5 (a) Placement P in a chip. (b) Contour R of P. (From Lin, J.-M., Chang, Y.-W., and Lin, S.-P., IEEE Trans. VLSI Syst., 4, 679, 2003. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 210 Finals Page 210 29-9-2008 #9 Handbook of Algorithms for Physical Design Automation S1 = a, D1 = [s, t ] e f s h d a S2 = b, D2 = [a, t ] e c b f s d a g b S4 = e, D4 = [s, b ] fbf d a h b e f s d a g h S7 = g, D7 = [c, t ] a f b h f a g h d c b g t (f) S8 = h, D8 = [f, c ] e f s c b e s c (e) d S6 = f, D6 = [e, c ] t (d) s g (c) t e c b t S5 = c, D5 = [d, t ] c h d a g (b) e f t (a) s e s c t a g h d CS = < (a, [s, t ]) (b, [a, t ]) (d, [a, b ]) (e, [s, b ]) (c, [d, t ]) (f, [e, c ]) (g, [c, t ]) (h [f, c ]) c b g t t (g) h S3 = d, D3 = [a, b ] (h) (i) FIGURE 11.6 (a–h) Process to build a CS from a placement. (Note that the heavily shaded modules denote those in R and the lightly shaded ones denote the visited modules.) (i) Resulting CS. (From Lin, J.-M., Chang, Y.-W., and Lin, S.-P., IEEE Trans. VLSI Syst., 11, 679, 2003. With permission.) process repeats until no term in the CS is available. Let W (H) denote the width (height) of a chip. W = xu (H = yv ) if nu (nv ) is the node right before (behind) nt (ns ) in the final L. Figure 11.7 gives an example of the packing scheme for the CS shown in Figure 11.7a. L initially consists of ns and nt . We first insert a node na between ns and nt because S1 = a and D1 = [s, t]. The x(y) coordinate of ba is xs (yt ). Figure 11.7b shows the resulting placement and L. Similarly nb is inserted between na and nt in L of Figure 11.7b because S2 = b and D2 = [a, t] (see Figure 11.7c for the resulting placement and L). After we insert a node nd between the two nodes na and nb in L of Figure 11.7c for the third term (d, [a, b]) in the CS, the predecessor na (successor nb ) of nd is deleted because ya ≤ yd (xb ≤ xd ) (see Figure 11.7d). The process repeats for all terms in the CS, and the resulting placement and L are shown in Figure 11.7i. The width (height) of a chip is W = xh (H = ye ) because the node right before (behind) nt (ns ) is nh (ne ) in L. The DSP packing scheme packs modules correctly in O(m) time, where m is the number of modules. The solution space of CS is bounded by (m!)2 , where m is the number of modules. It should be noted that, in addition to the number of modules, the solution space of CS also depends on the dimensions of the modules. The above theorem considers the worst case for CS—all modules appear Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 211 29-9-2008 #10 211 Packing Floorplan Representations CS = < (a, [s, t ])(b, [a, t ])(d, [a, b ])(e, [s, d ]) (c, [d, t ])(f, [e, c ])(g, [c, t ])(h, [f, c ]) > (a) L ns na nt ns na nb nt L s L ns a d a a b b t t t (b) (c) L ns ne nd nt (d) L ns ne nc nt e ns ne nf L e e s s d b d c d a t t (f) L n s ne e d (g) ng nt L ns ne nh nt e fbf s a nf n c a g d h c g b t t (h) fbf s c b c b b t n c nt fbf s a (e) nt s s a nd (i) FIGURE 11.7 (b–i) DSP packing scheme for the CS shown in (a), where CS = (a, [s, t])(b, [a, t]) (d, [a, b])(e, [s, d])(c, [d, t])(f , [e, c])(g, [c, t])(h, [f , c]). (From Lin, J.-M., Chang, Y.-W., and Lin, S.-P., IEEE Trans. VLSI Syst., 11, 679, 2003. With permission.) in the contour all the time during packing. Obviously, it is quite often that only part of the modules are in the contour. Therefore, the practical solution space of CS is significantly smaller than (m!)2 . 11.4.3 CS PERTURBATIONS A CS can be perturbed by the following four perturbations to obtain a new CS: • • • • Exchange: exchange two modules in Si and Sj . Insert: insert the ith term between the jth and (j + 1)th terms. Rotate: rotate a module in Si . Randomize: randomize a new Di for the module in Si by choosing arbitrary neighboring nodes in L.

Handbook of algorithms for physical design automation part 23

Nội dung