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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 192 Finals Page 192 24-9-2008 #9 Handbook of Algorithms for Physical Design Automation Transformation from Q-sequence to floorplan 1. Initialize the floorplan with block n. 2. For i = n − 1 to 1 do /∗ Let I(i) be the Q-state of block i. ∗ / 3. If I(i) contains ‘R’s, 4. Add block i from the left of the chip pushing aside top mi blocks, where mi is the number of ‘R’s in I(i), that are adjacent to the left boundary of the chip. 5. If I(i) contains ‘B’s, 6. Add block i from the top of the chip pushing down leftmost mi blocks, where mi is the number of ‘B’s in I(i), that are adjacent to the top boundary of the chip. FIGURE 10.13 Transformation from Q-sequence to floorplan. 10.3.1 EXTENDED Q-SEQUENCE The Q-sequence representation is extended [5] to allow empty√room insertion to include the optimal packing in the solution space. It is proven that at most n − 4n − 1 empty rooms are needed to represent any packing and the size of the solution space will become 26n (2n)!/n! if empty rooms are included. A new move to perturb a floorplan by making use of a parenthesis tree pair is introduced to improve the packing performance. A linear-time decoding algorithm to realize a floorplan from a Q-sequence is given in Figure 10.13 and an example that illustrates the decoding steps is shown in Figure 10.14. 10.3.1.1 New Move Based on Parenthesis Constraint Tree The R parenthesis tree of a Q-sequence is obtained by representing the corresponding RQ-sequence in the form of a tree such that each node represents a pair of parentheses corresponding to a room. We label the “R” corresponding to the open parenthesis of room i by Ri for i = 1, . . . , n. An example is shown in Figure 10.15. The B parenthesis tree can be constructed similarly from the BQ-sequence and the “B”s are also labeled from 1 to n accordingly. Parenthesis trees have the following properties: 3 R 5 4 6 R B 6 5 4 (a) (b) 2 3 4 (d) B B R 1 R 6 5 4 (e) B 6 5 (c) 2 2 3 1 3 6 5 4 6 5 (f) FIGURE 10.14 Example of realizing a floorplan from its Q-sequence RRBB1RR2BB3BB4R5R6, showing (a) the floorplan after adding block 5, (b) the floorplan after adding block 4, (c) the floorplan after adding block 3, (d) the floorplan after adding block 2, (e) the floorplan after adding block 1, and (f) the final floorplan. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 Finals Page 193 24-9-2008 #10 193 Floorplan Representations p4 p3 p1 ( R4 p2 ( R1 B2 B1 p5 ) ( ( ) 1 R3 R2 2 ) B6 B3 ) ( B5 3 B4 4 R5 p6 ) ( ) 5 R6 6 FIGURE 10.15 Q-sequence and its R parenthesis system. Property 1 Given two rooms i and j corresponding to node i and node j, respectively, in the R parenthesis tree, if node i is an ancestor (the left sibling) of node j, room i is below (on the left of) room j in the packing. Property 2 Given two rooms i and j corresponding to node i and node j, respectively, in the B parenthesis tree, if node i is an ancestor (the left sibling) of node j, room i is on the right of (above) room j in the packing. Property 3 The rooms corresponding to the nodes whose parent is the root in the R (B) parenthesis tree are placed along the bottom (right) boundary of the packing. The R and B parenthesis trees of the floorplan in Figure 10.14f are shown in Figure 10.16. The Q-sequence can be perturbed by moving the positional symbols “R”s and “B”s back and forth as long as the corresponding RQ-sequence and BQ-sequence are still well formed. Parenthesis trees can help to constrain the movement such that the resulting Q-sequence will remain feasible. For example, when an Ri is moved to the left, some of node i’s siblings in the R parenthesis tree will become node i’s children, but we cannot move Ri to the left of Rj where node j is the parent of node i. Similarly, when Ri is moved to the right, some of node i’s children in the R parenthesis tree will become node i’s left siblings, but we cannot move Ri to the right of the label of room i. If moving a positional symbol “R” will result in a blank subsequence between two room labels i and j where j > i, one can place the positional symbol Bj between the labels i and j to restore a feasible Q-sequence. In the annealing process, four perturbation operations can be applied to change a Q-sequence: (1) rotate a module, (2) swap the modules in two rooms, (3) move an “R” randomly and feasibly in R parenthesis tree P4 P1 P5 P3 P6 B parenthesis tree P2 P1 P2 FIGURE 10.16 Parenthesis trees of the packing in Figure 10.14f. P6 P3 P5 P4 Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 194 Finals Page 194 24-9-2008 #11 Handbook of Algorithms for Physical Design Automation the Q-sequence, and (4) move a “B” randomly and feasibly in the Q-sequence. It can be shown that starting from any arbitrary initial floorplan, we can transform it to any other floorplan by applying at most O(n) perturbation operations. 10.4 TWIN BINARY TREES Yao et al. [6] proposed another representation for floorplans and derived the exact number of floorplan configurations. Let M(n) be the number of floorplans with n rooms. These floorplans can be analyzed in terms of the numbers of T-junctions on the top and right boundaries of the floorplan. Let Fn (i, j) denote the number of floorplans with n rooms, with i T-junctions on the top boundary and j T-junctions on the right boundary. M(n) where n ≥ 1 can be computed by the following equation: M(n) = Fn (i, j) i,j>0 When n = 1, Fn (0, 0) = 1, and when n > 1, Fn (0, 0) = 0, because there is at least one T-junction on either the top or the right boundary when the floorplan has two or more rooms. Also, Fn (i, j) = 0 when i + j ≥ n, because there are at most n − 1 T-junctions on the top and right boundaries for a floorplan with n rooms. A recurrence for Fn (i, j) can be obtained by deleting the top-right room in the floorplan as described in the section on CBL. Fn+1 (i + 1, j + 1) = ∞ [Fn (i + k, j) + Fn (i, j + k)], n≥1 k=1 It turns out that the base cases and the recurrence for Fn (i, j) are identical to those used for generating the Baxter number B(n) [7]. The Baxter number B(n) has been shown by Chung et al. [8] to have the form −1 −1 n n+1 n+1 n+1 n+1 n+1 (10.1) B(n) = k+1 k 1 2 k−1 k=1 Therefore, the number of floorplans with n rooms is given by Equation 10.1. By borrowing the concept of the Baxter permutation, an efficient representation for floorplans is developed. A bijection between Baxter permutations and twin binary trees (TBTs) was introduced in Ref. [9], where TBTs are defined as follows: Definition 2 The set of twin binary trees TBTn ⊂ Treen × Treen is the set TBTn = {(b1 , b2 )|b1 , b2 ∈ Treen ∩ (b1 ) = c (b2 )} where Treen is the set of all binary trees with n nodes, and (b) is the labeling of a binary tree b obtained as follows. Beginning with an empty sequence, perform an in-order traversal on the tree. Whenever encountering a node with no left (right) child, a bit “0” (“1”) is appended to the sequence. The first “0” and the last “1” are omitted. c is the complement of in which the bits “0” and “1” are interchanged. Except for the four corners of a floorplan, all block corners are formed by T-junctions. There are four possible orientations for the T-junctions: 0◦ , 90◦ , 180◦ , and 270◦ as shown in Figure 10.17. To construct the TBT representation of a mosaic floorplan, the following terminologies concerning mosaic floorplan are defined: Definition 3 If room A is not at the top-right corner of a floorplan, the T-junction at the top-right corner of A is either a 0◦ T-junction or a 270◦ T-junction. Let B be the room adjacent to A by the noncrossing segment of that T-junction, B is called the C + -neighbor of A. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 Finals Page 195 24-9-2008 #12 195 Floorplan Representations A B A B (a) 0⬚ T-junction (b) 90⬚ T-junction B B A (c) 180⬚ T-junction A (d) 270⬚ T-junction FIGURE 10.17 Four different types of T-junctions, with (a) 0◦ rotaion, (b) 90◦ rotation, (c) 180◦ rotation, and (d) 270◦ rotation. Definition 4 If room A is not at the bottom-left corner of a floorplan, the T-junction at the bottomleft corner of A is either a 90◦ T-junction or a 180◦ T-junction. Let B be the room adjacent to A by the noncrossing segment of that T-junction, B is called the C − -neighbor of A. Every room, except the top-right corner room, has exactly one C + -neighbor. Similarly, every room, except the bottom-left corner room, has exactly one C − -neighbor. If we represent each room by a node and connect each node to its C + -neighbor, we can construct a tree whose root is the top-right corner room of the floorplan. Similarly, if we connect each node to its C − -neighbor, we can construct a second tree whose root is the bottom-left corner block of the floorplan. The algorithm for obtaining the TBT representation of a floorplan is shown in Figure 10.18 and an example of the TBT representation of a floorplan is shown in Figure 10.19. The complexity of this algorithm is O(n) where n is the total number of rooms and the pair of trees so generated is a pair of TBTs. Moreover, there is a one-to-one mapping between TBTs (τ1 , τ2 ) and all floorplans. This property makes the TBT a nonredundant representation for floorplans. Theorem 1 The pair of trees (τ1 , τ2 ) generated by the algorithm in Figure 10.18 is a pair of twin binary trees. Theorem 2 Given a floorplan, there exists a unique twin binary tree representation for the floorplan. Similarly, a twin binary tree represents a unique floorplan. Transformation from floorplan F to TBT 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. E + = E − = ∅. Let V + = V − = {i| block i ∈ F}. For each block i: If i is not the top-right corner block of F, Get C + -neighbor j of i. Put E + = E + ∪ (j, i). If block j is on the right of i, set i be the left child of j, else set i be the right child of j. If i is not the bottom-left corner block of F, Get C − -neighbor j of i. Put E − = E − ∪ (j, i). If block j is on the left of i, set i be the right child of j, else set i be the left child of j. τ+ = (V + , E + ), τ− = (V − , E − ). Output (τ− , τ+ ). FIGURE 10.18 Transformation from floorplan to TBT. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 196 Finals Page 196 24-9-2008 #13 Handbook of Algorithms for Physical Design Automation τ− τ+ E A B A B F C B D E F C D G G D G A C F E FIGURE 10.19 TBT representation of a mosaic floorplan. 10.5 TWIN BINARY SEQUENCES Twin binary trees can represent floorplans uniquely, but it is not known how to use them effectively to generate different floorplans. The Twin binary sequence (TBS) is proposed in Ref. [10] to effectively encode TBT with four-tuples s = (π, α, β, β ) such that necessary and sufficient conditions for the feasibility of an encoding can be identified, and feasible encodings can be generated effectively according to these conditions. Each four-tuple s = (π, α, β, β ) represents a floorplan with n modules, where π is a permutation of the module names, α is a sequence of n−1 bits, and β and β are sequences of n bits. These four-tuples can be one-to-one mapped to pairs of binary trees t1 and t2 such that t1 and t2 are twin binary to each other and can uniquely describe a floorplan. In addition, empty rooms can be inserted to include the optimal solution in the solution space. Instead of including an excessive number of dummy blocks in the set of modules, which will increase the size of the solution space significantly, the TBS representation allows us to insert an exact number of irreducible empty rooms in a floorplan such that every packing can be obtained uniquely from one and only one floorplan. The size of the solution space is O(n!23n /n1.5 ), which is the size with no empty room insertions, but every packing can be generated uniquely and efficiently from one√floorplan in the solution space in linear time without any redundancy. A lower bound of Ω(n − 2 n) empty rooms are needed to obtain any packing. Together with the upper bound from Ref. [5], the number of empty rooms required is √ exactly (n − 2 n). The definition of TBS is based on an observation that an arbitrary pair of binary trees t1 and t2 is a TBT representation of a floorplan if and only if they are twin binary to each other and their inorder traversals are the same. However, the labeling and the inorder traversal are not sufficient to identify a unique pair of t1 and t2 . Given a permutation of n module names π and a labeling α of n − 1 bits, there can be more than one valid pairs of t1 and t2 such that their inorder traversals are π and (t1 ) = c (t2 ) = α. To specify a pair of trees uniquely, two additional bit sequences β and β can be used for t1 and t2 , respectively. In β(β ), the ith bit is equal to “1” if the ith module in the inorder traversal of t1 (t2 ) is the right child of its parent and is “0” otherwise. These bits are called directional bits. Notice that any n − 1 bit sequence α = α1 α2 · · · αn−1 and n bit sequence β = β1 β2 · · · βn will correspond to the labeling and the directional bit sequence of a binary tree t if and only if the sequence β1 α1 β2 α2 · · · αn−1 βn has one “0” more than “1,” and for any prefix of this sequence, the number of “0”s is not less than the number of “1”s. Now we can use a four-tuple (π, α, β, β ) to represent a floorplan where π is a permutation of n module names, α is an n − 1 bit sequence, and β and β are n bit sequences such that the pairs α and β, and α c and β satisfy the above conditions of representing the labeling and the directional bit sequence of a binary tree. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 Finals Page 197 24-9-2008 #14 197 Floorplan Representations Transformation from TBS (π, α, β, β ) to floorplan 1. Initialize the floorplan with block πn . 2. For i = n − 1 to 1: 3. If αi is zero, 4. Find the smallest k where i < k ≤ n and βk is equal to one. 5. Add block πi to the floorplan from the left, pushing aside the set S = {πj |i < j ≤ k and βj not deleted yet} of blocks. 6. Delete βi+1 , βi+2 · · · βk from β. 7. If αi is one, 8. Find the smallest k where i < k ≤ n and βk is equal to one. 9. Add block πi to the floorplan from the top, pushing down the set S = {πj |i < j ≤ k and βj not deleted yet} of blocks. 10. Delete βi+1 , βi+2 · · · βk from β . FIGURE 10.20 Transformation from TBS to floorplan. i=4 i=3 i=2 i=1 B B D C D A C (a) pABCD a010 b0011 b⬘0 0 0 1 (b) pABCD a010 b0011 b⬘0 0 0 1 (c) C D pABCD a010 b001 b⬘0 0 0 1 (d) D pABCD a010 b 0 01 b⬘0 0 FIGURE 10.21 Example of constructing a floorplan from its TBS. This four-tuple representation is called TBS and the mapping between TBS and floorplans is oneto-one. Therefore, there is no redundancy in the TBS representation, and the size of the solution space for n modules is equal to the Baxter number B(n) [6] and can be shown to be bounded by O(n!23n /n1.5 ). An algorithm to realize a floorplan from a given TBS representation (π, α, β, β ) in linear time by scanning the sequences only once is given in Figure 10.20 with an example shown in Figure 10.21. To include the optimal solution in the solution space, empty rooms can be inserted. In TBS, empty rooms can be inserted exactly into the representation such that every nonslicing structure can be generated from one and only one mosaic floorplan nonredundantly. In a packing, there are two kinds of empty rooms. One results because the room assigned to a module is too large. This type of empty room is called reducible and is not considered because the topological relationship is not affected. The other type is called irreducible and refers to rooms that cannot be removed by merging with the neighboring rooms. Examples of reducible and irreducible empty rooms are shown in Figure 10.22. The T-junctions at the four corners of an irreducible empty room must form a wheel shape and the neighboring rooms at those T-junctions must not be irreducible empty rooms themselves. To construct a packing from a floorplan, we only need to consider the insertion of those irreducible empty rooms (called “X” in the following). Irreducible empty rooms can only be of the two forms shown in Figure 10.23. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 198 Finals Page 198 24-9-2008 #15 Handbook of Algorithms for Physical Design Automation Irreducible empty room Reducible empty room FIGURE 10.22 Examples of reducible and irreducible empty rooms. D D B D C D X A B A B A t1 (a) X X X C B C t2 (b) C A t1 t2 FIGURE 10.23 Two types of irreducible empty rooms, with (a) an anticlockwise wheel and (b) a clockwise wheel. In the construction, a vertical sliceline with a T-junction on each side will be mapped to an anticlockwise “X,” while a horizontal sliceline with a T-junction on each side will be mapped to a clockwise “X.” This mapping and the corresponding changes needed to be made to the TBTs are shown in Figure 10.24. This mapping is unique, i.e., every packing can be obtained by this mapping from one and only one floorplan. The empty room insertion process is based on two observations. First, it is known that the adjacent rooms of an irreducible empty room must be occupied by some blocks, so the “X”s must be inserted between some module nodes as in Figure 10.25. Initially, as many “X”s as possible will be inserted into the two TBTs (Figure 10.25b) according to the two possible forms of insertions (Figure 10.24). The invalid ones will then be deleted. This deletion is based on the second observation that a pair of TBT can represent a floorplan if and only if their inorder traversals are equivalent. By tracing the inorder traversal of the two trees after inserting all the possible “X”s, we can match those “X”s easily because there must be an equal number of “X”s between any two consecutive module names. There B D A C B D A X X C B A t1 t2 (a) B D D A (b) C B D A D B D C C A t1 t2 D C B X C B t1 A A C t2 X t1 t2 FIGURE 10.24 Mapping between mosaic floorplan and nonslicing floorplan, showing (a) mapping to an anticlockwise wheel and (b) a mapping to a clockwise wheel. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 Finals Page 199 24-9-2008 #16 199 Floorplan Representations A A E B A C D C t1 (b) (a) X E A X D B C X X E A X D X B X Matched X X D C E X B t2 X X B E C E B X X D A D E D X X B A C t ⬘1 t 2⬘ Leading and trailing “X”s are deleted Unmatched X is deleted (c) A E A (d) D E D B C D t ⬙1 C X C X B E B A t 2⬙ FIGURE 10.25 Constructing a packing from a floorplan, showing (a) the original mosaic floorplan, (b) the twin binary trees before and after inserting irreducible empty rooms, (c) the inorder traversals of the twin binary trees, and (d) the final floorplan with its twin binary tree representation. may be choices in the mapping but each different choice will correspond to a different nonslicing floorplan. In this way, we can insert an exact number of irreducible empty rooms at the right places to produce different nonslicing structures. This empty room insertion step can be implemented directly on a TBS efficiently. It is shown that at most n − 1 irreducible empty rooms are needed√to construct any packing structure from a floorplan. On the other hand, a lower bound of n − 2 n + 1 irreducible empty rooms is proven with an example. Together with the upper bound from Ref. [5], the number of empty √ rooms required is (n − 2 n). 10.6 PLACEMENT CONSTRAINTS IN FLOORPLAN DESIGN The CBL representation has been extended to handle boundary constraints, abutment constraints, and rectilinear block packing. Boundary constraints are useful for satisfying I/O requirements and the abutment requirements between neighboring units in modern designs. The necessary and sufficient conditions for a module satisfying boundary constraints in a floorplan represented by a CBL have been derived [11]. By making use of these conditions, the required boundary constraints can be checked in linear time by scanning the CBL. The CBL can be fixed as much as possible in case some constraints are violated. A penalty function is derived to measure the degree of violation of the constraints. The conditions are based on the observation that in the process of transforming a CBL to a floorplan, if a module is required to be placed on the left (bottom) boundary of the floorplan, the module should be placed on top (the right hand side) of all the previously placed modules when it is being processed. On the other hand, if a module is required to be placed along the right (top) boundary, no modules processed afterward should be placed on its right (above it). These conditions can be checked very efficiently for a given CBL = (S, L, T ) by computing two lists of numbers, Ritn and Titn for i = 1, . . . , n, associated with the n insertion steps in the transformation process from CBL to floorplan as follows: Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 200 Finals Page 200 24-9-2008 #17 Handbook of Algorithms for Physical Design Automation R1tn = T1tn = 0 Li−1 = 1 ⇒ Li−1 = 0 ⇒ tn − TNi−1 Ritn = Ri−1 tn tn T = T i−1 + 1 itn tn +1 Ri = Ri−1 tn tn Ti = Ti−1 − TNi−1 (10.2) where TNi is the number of “1”s before the ith “0” in the list T . The necessary and sufficient conditions for a module Mi to satisfy boundary constraint are stated in the following theorem: Theorem 3 A module Mi in list S is along the left (bottom) boundary of the final chip if and only if Titn = 0(Ritn = 0). A module Mi in list S is along the top (right) boundary of the final chip if and only if Tktn > Titn (Rktn > Ritn ) for all k = i + 1, . . . , n. The algorithm for boundary constraint checking given a CBL is shown in Figure 10.26. In this boundary checking algorithm, the CBL is scanned twice, one from left to right and once from right to left, so the complexity of this algorithm is O(n). In case some constraints are violated, the corresponding CBL can be fixed as much as possible by swapping the modules that violate Scan a CBL (S, L, T) to find all the modules lying along the boundaries and compute the penalty cost penalty = 0, Ptn = T1tn = 0 and BT = BB = BL = BR = ∅. For i = 2 to n do: Find Ritn and Titn according to equation (2). If Titn = 0, BL = BL ∪ {Mi }. If Ritn = 0, BB = BB ∪ {Mi }. If Mi is constrained to the left boundary, penalty = penalty + Titn . If Mi is constrained to the bottom boundary, penalty = penalty + Ritn . Find kt where Mkt is the last module whose T tn equals 0. Find kr where Mkr is the last module whose Rtn equals 0. min_rtn = min_ttn = ∞. For i = n to min{kt, kr} do: If Mi is constrained to the top boundary, penalty = penalty + max{0, Titn − min_ttn + 1}. If Mi is constrained to the right boundary, penalty = penalty + max{0, Ritn − min_rtn + 1}. If Ritn < min_rtn, BR = BR ∪ {Mi }. min_rtn = Ritn . If Titn < min_ttn, BT = BT ∪ {Mi }. min_ttn = Titn . penalty = penalty+ number of modules before Mkt and Mkr in S and limited by the top or right boundary constraint. 25. Output penalty, BT , BB , BL and BR . 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. FIGURE 10.26 Boundary check. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C010 Finals Page 201 24-9-2008 #18 201 Floorplan Representations TABLE 10.1 Comparisons between Different Representations Representation CBL Q-sequence TBT TBS Solution Space Packing Time Flexibility O(n!23n−3 ) O(n!23n−1 ) (n!23n /n4 ) (n!23n /n4 ) O(n) O(n) O(n) O(n) Mosaic Mosaic Mosaic Mosaic the constraints with free modules in the sets BT , BL , BR , and BB . If there are still violations after this swapping step, the corresponding floorplan does not have enough positions along the boundary to satisfy all the requirements, and a penalty term will be included in the cost function of the annealing process to penalize the remaining violated constraints. This penalty term will drop to zero as the annealing process proceeds. A similar approach can be used to handle abutment constraints [12]. Abutment constraints are useful in practice as designers may want the logic blocks in a pipeline of a circuit to abut with one another to favor the transmission of data between them. By scanning the CBL of a candidate floorplan solution, the abutment information of all the blocks can be obtained efficiently in linear time. The CBL can be fixed as much as possible in case some constraints are violated. Based on this approach, L-shaped and T-shaped blocks can also be handled by partitioning a rectilinear block into a few abutting rectangular subblocks. Besides abutment constraints and rectilinear blocks, rotation and reflection of L-shaped and T-shaped blocks have also been considered [12]. 10.7 CONCLUDING REMARKS We have discussed four different types of representations for floorplans, including CBL, Q-sequence, TBT, and TBS. These representations are compared in Table 10.1. (A similar table compares packing representations in the next chapter.) They exhibit some interesting relationships with each other [6]. For example, given a floorplan F, the inorder traversal of the trees in its TBT representation is identical to the sequence S in the CBL representation (S, L, T ) of the floorplan obtained by rotating F by 90◦ . All of these representations are practically useful because there are efficient linear-time algorithms for floorplan realization and encoding. However, CBL and Q-sequence have redundancy in their representations and the sizes of their solution space are both upper bounded by O(n!23n ). TBT and TBS are nonredundant representations and the size of their solution space is (n!23n /n4 ) according to the analysis in Ref. [13] on the exact number of floorplans with n modules. All these representations can be extended to generate any general packing structure by including dummy empty blocks. According to the results from Refs. [5,10], the√exact number of dummy empty blocks needed to generate any general packing structure is (n − 2 n). However, if these extra dummy blocks are added, the size of the solution space will be increased significantly. For TBS, it is possible to identify the exact locations in the representation where dummy empty blocks should be inserted such that every packing structure can be generated from exactly one floorplan. By using this property, Zion et al. [13] obtained a tighter upper bound for the total number of general packings of O(n!25n /n4.5 ) by bounding the number of ways to insert dummy empty rooms into a TBS. REFERENCES 1. X. Hong, S. Dong, G. Huang, Y. Cai, C. K. Cheng, and J. Gu. Corner block list representation and its application to floorplan optimization. IEEE Transactions on Circuits and Systems II, 51(5): 228–233, 2004. (ICCAD 2000).

Handbook of algorithms for physical design automation part 22

Nội dung