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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 212 Finals Page 212 29-9-2008 #11 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 lth term and perform incremental update on the existing packing (solution). The coordinate of module bi in Si , i = l + 1, . . . , m, can be obtained by inserting a node ni into two neighboring nodes nj and nk in L if Di = [j, k]. However, if the designated nodes do not exist in L, we randomly insert the node ni 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 11.8 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 11.8a. Figure 11.8b 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 perturbation because 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 11.8c shows the resulting placement and L after we insert the node nh between the nodes ne and nc in the L of Figure 11.8b. 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 11.8c. 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 11.8d. Similarly, we intend to insert nf between nodes nf and nc for the module f in the L of Figure 11.8d. However, L n s ne n c n t CS = 〈..., (f, [e, c]) (g, [c, t ]) (h, [f, c])〉 e f Exchange f and h CS⬘ = 〈..., (h, [e, c]) (g, [c, t ]) (f, [f, c])〉 a (a) L h d c b g (b) ns ne nh nt e a (c) L ns ng nh nt d b c a (d) ns nf nt g e h L h d b g f e c a h d c b (e) CS⬘ = 〈..., (h, [e, c]) (g, [e, h]) (f, [g, h])〉 (f) FIGURE 11.8 Example of exchanging two modules bf and bh in S6 and S8 for the CS. (a) CS after the modules in S6 and S8 have been exchanged. (b) L for those modules a, b, c, d, and e whose coordinates remain the same. (c)–(e) Resulting placement and L after the modules h, g, and f have been packed, respectively. (f) Resulting CS after the operation. (From Lin, J.-M., Chang, Y.-W., and Lin, S.-P., IEEE Trans. VLSI Syst., 11, 679, 2003. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 213 29-9-2008 #12 213 Packing Floorplan Representations there do not exist two neighboring nodes nf and nc in the L of Figure 11.8d, we thus randomly insert it between the nodes ng and nh . See Figure 11.8e for the resulting placement and L. Finally, we have the resulting CS shown in Figure 11.8f. 11.5 SEQUENCE PAIR Sequence pair (SP) is proposed by Murata et al. [6]. An SP is an ordered pair of module name sequences to model general floorplans. 11.5.1 FROM A PLACEMENT TO AN SP Figure 11.9 gives an example placement P on a chip. The following procedure encodes P to an SP. For each module bi , we draw two lines, up-right locus and down-left locus. The up-right locus of module bi is initially located at the upper-right corner of bi and starts to move upward. It turns its direction alternately right and up until it reaches the upper-right corner without crossing: (1) boundaries of other modules, (2) previously drawn lines, and (3) the boundary of the chip. The down-left locus of bi can be drawn in the similar method. The union of these two loci and the connecting diagonal line of bi is called the positive locus of bi . They are referred to by the corresponding module names. An example of resulting positive loci is shown in Figure 11.10a. With the construction of positive loci, we have that no two positive loci cross each other. Thus, these positive loci can be linearly ordered, as well as the corresponding modules. Here we order the positive loci from left. Let + be the module name sequence in this order. In Figure 11.10a, + = ecadfb is obtained. Negative loci are drawn similarly as the positive loci. The difference is that a negative locus is the union of the left-up locus and right-down locus. Let − be the module name sequence in the order of the negative loci from left. An example of negative loci is shown in Figure 11.10b. Observing it from left, − = fcbead is obtained. Finally, the SP (+ , − ) is obtained. 11.5.2 FROM AN SP TO A PLACEMENT Given an SP (+ , − ), the geometric relation of modules can be derived from an SP as follows. Module bi is left (right) to module bj if bi appears before (after) bj in both + and − . Module bi is below (above) module bj if bi appears after (before) bj in + and bi appears before (after) bj in − . W e d a H c f b FIGURE 11.9 Placement P on a chip. (From Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y., IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 15, 1518, 1996. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 214 Finals Page 214 29-9-2008 #13 Handbook of Algorithms for Physical Design Automation e e d a d a c c f f b (a) b (b) FIGURE 11.10 (a) Positive loci and (b) negative loci. (From Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y., IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 15, 1518, 1996. With permission.) To obtain the placement from an SP, we construct an m × m grid. Label the horizontal grid lines and vertical grid lines with module names along + and − from top and from left, respectively. A cross point of the horizontal grid line of label i and the vertical grid line of label j is referred to by (i, j). Then, rotate the resulting grid by 45◦ counterclockwise to get an oblique grid. (Figure 11.11) Put each module bi with its center being on (i, i). Expand the separation of grid lines enough to eliminate overlapping of modules. The resulting packing trivially satisfies the constraint implied by the given SP. An example is shown in Figure 11.11. Given an SP (+ , − ), the optimal packing under the constraint can be obtained in O(m2 ) time, where m is the number of modules, by applying the well-known longest path algorithm for nodeweighted directed acyclic graphs. The process is given below. We first construct the horizontalconstraint graph, a directed and node-weighted graph GH (V , E) (where V is the set of nodes, and E is the set of edges), based on the “left of” constraint of (+ , − ). e d a c b f FIGURE 11.11 Packing on an oblique grid for (+ , − ) = (ecadfb, fcbead). (From Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y., IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 15, 1518, 1996. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 215 29-9-2008 #14 215 Packing Floorplan Representations 1. V : source s, sink t, and m nodes labeled with module names 2. E: (s, i) and (i, t) for each module bi , and (i, j) if and only if bi appears before (after) bj in both + and − (the “left of” constraint) 3. Node-weight: zero for s and t, width of module bi for the remaining nodes Similarly, the vertical-constraint graph GV (V , E) is constructed using the “below” constraint and the height of each module. There should be no directed cycle in both graphs. We set the x-coordinate of bi to be the longest path length from s to i in GH . The y-coordinate of bi is set independently using GV . If two modules bi and bj are in horizontal relation, then there is an edge between i and j in GH , and thus they do not overlap horizontally in the resulting placement. Similarly, if bi and bj are in vertical relation, they do not overlap vertically. Because any pair of modules are either in horizontal or vertical relation, no two modules overlap each other in the resulting placement. The width (height) of the chip is determined by the longest path length between the source and the sink in GH (GV ). The longest path length calculation on each graph can be done in O(m2 ) time, proportional to the number of edges in the graph. For the GH and GV shown in Figure 11.12, we have (+ , − ) = (ecadfb, fcbead). The resulting placement after the longest path length calculation is shown in Figure 11.13. On the basis of the longest common subsequence (LCS), two faster packing algorithms with respective time complexities O(lg n) and O(lg lg n) to transform a SP to its placement are proposed by Tang, Tian, and Wong [14] and Tang and Wong [15]. Given an SP (+ , − ), let +R denotes the reverse of + , and define lcs(X, Y ) as the length of the LCS of X and Y . That is, if Z = z1 , z2 , . . . , zn n is the LCS of two weighted sequences X and Y , lcs(X, Y ) = i=1 w(zi ), and w(zi ) is the weight of zi . If an SP (+ , − ) = (X1 bX2 , Y1 bY2 ), then lcs(X1 , Y1 ) is the x coordinate of the block b, where w(i) is the width of the block i, and lcs(+ , − ) is the width of the placement. For the y coordinate, if an SP (+ , − ) = (X1 bX2 , Y1 bY2 ), then (+R , − ) = (X2R bX1R , Y1 bY2 ) and lcs(X2R , Y1 ) is the y coordinate of the block b, where w(i) is the height of the block i, and lcs(+ , − ) is the width of the placement. Thus, given an SP, we can compute the LCS to determine the x and y coordinates of all blocks and the width/height of the placement. The packing times are O(lg n) and O(lg lg n) when the balanced search tree and host tree are used to compute the LCS [14], respectively. e a e d a d c c b f b f (a) (b) FIGURE 11.12 (a) Constraint graph GH and (b) constraint graph GV (transitive edges are not shown in both graphs for simplicity). (From Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y., IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 15, 1518, 1996. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 216 Finals Page 216 29-9-2008 #15 Handbook of Algorithms for Physical Design Automation d a e c b f FIGURE 11.13 Best packing with the minimum area induced by (+ , − ) = (ecadfb, fcbead). (From Murata, H., Fujiyoshi, K., Nakatake, S., and Kajitani, Y., IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 15, 1518, 1996. With permission.) 11.5.3 SP PERTURBATIONS There are three types of pair-interchanges: (1) two module names in + , (2) two module names both in + and − , and (3) the width and the height of a module, where the last one is for orientation optimization. 11.6 BOUNDED-SLICELINE GRID A BSG structure [7] contains rooms, horizontal unit segments, and vertical unit segments. Figure 11.14 shows an example of a BSG of dimension p × q, BSGp×q . When using a BSG structure to represent a placement, p × q must be larger or equal to the number of modules. A rectangular space surrounded by an adjacent pair of vertical and horizontal units is called the room. Vertical unit y (p,q) (0,0) x FIGURE 11.14 BSG of dimension p × q, BSGp×q . (From Nakatake, S., Fujiyoshi, K., Murata, H., and Kajitani, Y., Proceedings of International Conference on Computer-Aided Design, 1996. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 217 29-9-2008 #16 217 Packing Floorplan Representations segments define the vertical relations, while horizontal unit segments define the horizontal ones. The placement of m modules is formulated as the room assignment of m modules by placing m modules into different rooms. The next section describes an algorithm to transform the BSG room assignment to the corresponding placement. 11.6.1 FROM A BSG ASSIGNMENT TO A PLACEMENT Given a set of modules M, where |M| = n. Assuming that p × q ≥ n, an assignment of M is a one-to-one mapping of modules into the rooms of BSGp×q . A room to which no module is assigned is called an empty room. We use the example shown in Figure 11.15 to explain the process of transforming the BSG to the corresponding placement. Given four modules (Figure 11.15a) and the assignment of four modules in the BSG (Figure 11.15b), we construct a horizontal unit adjacency graph Gh (Vh , Eh ) and a vertical unit adjacency graph Gv (Vv , Ev ) according to the BSG, and assign the weight of the edges in the unit adjacency graphs. If e ∈ Eh and e crosses a nonempty room, w(e) = height of the module assigned there. If e ∈ Ev and e crosses a nonempty room, w(e) = width of the module assigned there. Otherwise, if e crosses an empty room or is incident on the source or the sink, w(e) = 0. The corresponding horizontal unit adjacency graph Gh (Vh , Eh ) and the vertical unit adjacency graph Gv (Vv , Ev ) to the assignment are shown in Figure 11.15c and d, respectively. Let Gh (Vh , Eh ) be the horizontal unit adjacency graph. For each vertex u ∈ Vh , lh (u) denotes the length of the longest path from the source sh to u. Similarly in Gv , lv (u) denotes the longest path length from sv to u ∈ Vv . We use a longest-path algorithm to determine the positions of modules. The longest-path algorithm works in linear time of the number of edges when the input G is a directed acyclic graph. The total number of edges of the unit adjacency graphs is between 2(pq + p + q) and 2(pq + p + q) − 4. So, the time complexity to find the longest path is O(pq). a d b b d c a (8, 3) (6, 9) c (9, 8) (11, 4) (b) (a) tv 0 0 0 8 3 0 8 0 9 9 0 0 sh 0 0 6 0 0 0 (c) 0 0 th 4 0 0 0 11 sv 0 (d) FIGURE 11.15 (a) Input modules, (b) BSG assignment, (c) horizontal unit adjacency graph Gh (Vh , Eh ), and (d) vertical unit adjacency graph Gv (Vv , Ev ). (From Nakatake, S., Fujiyoshi, K., Murata, H., and Kajitani, Y., Proceedings of International Conference on Computer-Aided Design, 1996. With permission.) Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 218 Finals Page 218 29-9-2008 #17 Handbook of Algorithms for Physical Design Automation x 12 a 9 4 d b c y (0,0) 6 8 17 FIGURE 11.16 Corresponding placement of the example in Figure 11.15. (From Nakatake, S., Fujiyoshi, K., Murata, H., and Kajitani, Y., Proceedings of International Conference on Computer-Aided Design, 1996. With permission.) The following BSG-PACK procedure transforms a BSG with a given assignment to the corresponding placement [7]: Given an assignment of M to BSGp×q , let m be a module assigned to a room whose left (vertical) boundary unit is Vm and bottom (horizontal) boundary unit is Hm . Then, place m such that its left bottom is at (lv (uVm ), lh (uHm )) where uVm and uHm are the vertices corresponding to the units Vm and Hm in the vertical unit and horizontal unit adjacency graphs, respectively. The area of the packing is (lv (tv ) × lh (th )). Figure 11.16 gives the resulting placement for the assignment of Figure 11.15. 11.6.2 BSG PERTURBATIONS It is very simple to perturb one BSG assignment to get another BSG assignment. We can first choose two different rooms, and then interchange (swap) the contents of them to generate a new BSG assignment. 11.7 TRANSITIVE CLOSURE GRAPH The transitive closure of a directed acyclic graph G is defined as the graph G = (V , E ), where E = {(ni , nj ): there is a path from node ni to node nj in G}. The representation, proposed by Lin and Chang in Refs. [4,12], describes the geometric relations among modules based on two graphs, namely a horizontal TCG Ch and a vertical TCG Cv . In this section, we first introduce the procedure for constructing Ch and Cv from a placement. Then, we describe how to pack modules from TCG. 11.7.1 FROM A PLACEMENT TO A TCG For two nonoverlapped modules bi and bj , bi is said to be horizontally (vertically) related to bj , denoted by bi bj (bi ⊥ bj ), if bi is on the left (bottom) side of bj and their projections on the y(x) axis overlap. Note that two modules cannot have both horizontal and vertical relations unless they overlap. For two nonoverlapped modules bi and bj , bi is said to be diagonally related to bj if bi is on the left side of bj and their projections on the x and the y axes do not overlap. In a placement, every two modules must bear one of the three relations: horizontal relation, vertical relation, and diagonal relation. To simplify the operations on geometric relations, we treat a diagonal relation for modules bi and bj as a horizontal one, unless there exists a chain of vertical relations from bi (bj ), followed by Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 219 29-9-2008 #18 219 Packing Floorplan Representations 3 2 nd ne ne e 6 3 c a d nc nb na 6 nc 4 7 b (a) 4 nd Ch 4 na 6 Cv nb (b) FIGURE 11.17 (a) Placement in a chip and (b) the corresponding TCG. (From Lin, J.-M., and Chang, Y.-W., IEEE Trans. VLSI Syst., 13, 288, 2005. With permission.) the modules enclosed with the rectangle defined by the two closest corners of bi and bj , and finally to bj (bi ), for which we make bi ⊥ bj (bj ⊥ bi ). Figure 11.17a shows a placement with five modules ba , bb , bc , bd , and be whose widths and heights are (6, 4), (4, 6), (7, 4), (6, 3) and (3, 2), respectively. In Figure 11.17a, ba bb , ba ⊥ bc , and module be is diagonally related to module bb . There exists a chain of vertical relations formed by modules be , bc , and bb between the two modules be and bb (i.e., bb ⊥ bc and bc ⊥ be ). Therefore, we make bb ⊥ be . Also, module be is diagonally related to module bd . However, there does not exist a chain of vertical relations between modules be and bd , and thus we make be bd . TCG can be derived from a placement as follows. For each module bi in a placement, we introduce a node ni with the weight being the width (height) in Ch (Cv ). If bi bj , we construct a directed edge from node ni to node nj (denoted by (ni , nj )) in Ch . Similarly, we construct a directed edge (ni , nj ) in Cv if bi ⊥ bj . Given a placement with m modules, we need to perform the above process m(m − 1)/2 times to capture all the geometric relations among modules (i.e., Ch and Cv have m(m − 1)/2 edges in total). As shown in Figure 11.17b, for each module bi , i ∈ {a, b, c, d, e}, we introduce a node ni in Ch and also in Cv . For each node ni in Ch (Cv ), i ∈ {a, b, c, d, e}, we associate the node with a weight equal to the width (height) of the corresponding module bi . Because ba bb , we construct a directed edge (na , nb ) in Ch . Similarly, we construct a directed edge (na , nc ) in Cv because ba ⊥ bc . This process is repeated until all geometric relations among modules are defined. As shown in Figure 11.17b, each TCG has five nodes, and there are totally ten edges in Ch and Cv (four in Ch and six in Cv ). 11.7.2 FROM A TCG TO A PLACEMENT We now present the packing method for a TCG. Given a TCG, its corresponding placement can be obtained in O(m2 ) time by performing a well-known longest path algorithm on the TCG, where m is the number of modules. To facilitate the implementation of the longest path algorithm, we augment the given two closure graphs as follows. We introduce two special nodes with zero weights for each closure graph, the source ns and the sink nt , and construct an edge from ns to each node with in-degree equal to zero, and also from each node with out-degree equal to zero to nt . (Note that the TCG augmentation is performed only for packing. It will be clear later that such augmentation is not needed for other operations such as solution perturbation.) Let Lh (ni )(Lv (ni )) be the length of the longest path from ns to ni in the augmented Ch (Cv ). Lh (ni )(Lv (ni )) can be determined by performing the single source longest path algorithm on the augmented Ch (Cv ) in O(m2 ) time, where m is number of modules. The coordinate (xi , yi ) of a module bi is given by (Lh (ni ), Lv (ni )). Because the respective width and height of the placement for the given TCG are Lh (nt ) and Lv (nt ), the area of the placement is given by Lh (nt )Lv (nt ). Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 220 Finals Page 220 29-9-2008 #19 Handbook of Algorithms for Physical Design Automation 11.7.3 TCG PROPERTIES A feasible TCG has the following three properties: (1) Ch and Cv are acyclic (2) each pair of nodes must be connected by exactly one edge either in Ch or in Cv and (3) the transitive closure of Ch (Cv ) is equal to Ch (Cv ) itself. Property 1 ensures that a module bi cannot be both left and right to (below and above) another module bj in a placement. Property 2 guarantees that no two modules overlap because each pair of modules have exactly one of the horizontal or vertical relation. Property 3 is used to eliminate redundant solutions. It guarantees that if there exists a path from ni to nj in one closure graph, the edge (ni , nj ) must also appear in the same closure graph. For example, there exist two edges (ni , nj ) and (nj , nk ) in Ch , which means that bi bj and bj bk , and thus bi bk . If the edge (ni , nk ) appears in Cv instead of in Ch , bk is not only left to bi but also above bi . The resulting area of the corresponding placement must be larger than or equal to that when the edge (ni , nk ) appears in Ch . On the basis of the properties of TCG, there exists a unique placement corresponding to a TCG, and the size of the solution space for TCG is (m!)2 , where m is the number of modules [4]. 11.7.4 TCG PERTURBATIONS To ensure the correctness of the new TCG after perturbation, as described in the preceding section, the new TCG must satisfy the aforementioned three feasibility properties. To identify a feasible TCG for perturbation, we introduce the concept of transitive reduction edges of TCG. An edge (ni , nj ) is said to be a reduction edge if there does not exist another path from ni to nj , except the edge (ni , nj ) itself; otherwise, it is a closure edge. Because TCG is formed by directed acyclic TCGs, given an arbitrary node ni in one TCG, there exists at least one reduction edge (ni , nj ), where nj ∈ Fout (ni ). Here, we define the fan-in (fan-out) of a node ni , denoted by Fin (ni )(Fout (ni )), as the nodes nj ’s with edges (nj , ni )(ni , nj ). For nodes nk , nl ∈ Fout (ni ), the edge (ni , nk ) cannot be a reduction edge if nk ∈ Fout (nl ). Hence, we remove those nodes in Fout (ni ) that are fan-outs of others. The edges between ni and the remaining nodes in Fout (ni ) are reduction edges. For the Cv shown in Figure 11.17a, Fout (na ) = {nc , ne }. Because ne belongs to Fout (nc ), edge (na , ne ) is a closure edge while (na , nc ) is a reduction one. We apply the following four operations to perturb a TCG: • • • • Rotation: rotate a module Swap: swap two nodes in both of Ch and Cv Reverse: reverse a reduction edge in Ch or Cv Move: move a reduction edge from one TCG (Ch or Cv ) to the other Rotation and swap do not change the topology of a TCG while reverse and move do. To maintain the properties of the TCG after performing the reverse and move operations, we may need to update the resulting graphs. Rotation. To rotate a module bi , we only need to exchange the weights of the corresponding node ni in Ch and Cv . TCG is closed under the rotation operation, and such an operation takes O(1) time. Swap. To swap two nodes ni and nj , we only need to exchange two nodes in both Ch and Cv . TCG is closed under the swap operation, and such an operation takes O(1) time. Reverse. The reverse operation reverses the direction of a reduction edge (ni , nj ) in a TCG, which corresponds to changing the geometric relation of the two modules bi and bj . For two modules bi and bj , bi bj (bi ⊥ bj ) if there exists a reduction edge (ni , nj ) in Ch (Cv ); after reversing the edge (ni , nj ), we have the new geometric relation bj bi (bj ⊥ bi ). Therefore, the geometric relation among modules is transparent not only to the TCG representation but also to the reverse operation (i.e., the effect of such an operation on the change of the geometric relation is known before packing); this property can facilitate the convergence to a desired solution. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C011 Finals Page 221 29-9-2008 #20 Packing Floorplan Representations 221 To reverse a reduction edge (ni , nj ) in a TCG, we first delete the edge from the graph, and then add the edge (nj , ni ) to the graph. For each node nk ∈ Fin (nj ) ∪ {nj } and nl ∈ Fout (ni ) ∪ {ni } in the new graph, we shall check whether the edge (nk , nl ) exists in the new graph. If the graph contains the edge, we do nothing; otherwise, we need to add the edge to the graph and delete the corresponding edges (nk , nl ) (or (nl , nk )) in the other TCG, if any, to maintain the properties of the TCG. To maintain the properties of a TCG, we can only reverse a reduction edge. Further, for each edge introduced in a TCG, we remove its corresponding edge from the other graph. Therefore, there is always exactly one relation between each pair of modules. TCG is closed under the reverse operation, and such an operation takes O(m2 ) time, where m is the number of modules in the placement. Move. The move operation moves a reduction edge (ni , nj ) in a TCG to the other, which corresponds to switching the geometric relation of the two modules bi and bj between a horizontal relation and a vertical one. For two modules bi and bj , bi bj (bi ⊥ bj ) if there exists a reduction edge (ni , nj ) in Ch (Cv ); after moving the edge (ni , nj ) to Cv (Ch ), we have the new geometric relation bi ⊥ bj (bi bj ). Therefore, the geometric relation among modules is also transparent to the move operation. To move a reduction edge (ni , nj ) from a TCG G to the other G in a TCG, we first delete the edge from G and add it to G . Similar to the reverse operation, for each node nk ∈ Fin (ni ) ∪ {ni } and nl ∈ Fout (nj ) ∪ {nj }, we shall check whether the edge (nk , nl ) exists in G . If G contains the edge, we do nothing; otherwise, we need to add the edge to G and delete the corresponding edge (nk , nl ) (or (nl , nk )) in G, if any, to maintain the properties of the TCG. To maintain the properties of a TCG, we can only move a reduction edge. If we move a closure edge (ni , nk ) associated with the two reduction edges (ni , nj ) and (nj , nk ) in one TCG to the other, then there exist a path from ni to nk in the two graphs, implying that bi bk and bi ⊥ bk , which gives a redundant solution. Further, for each edge introduced in a TCG, we remove its corresponding edge from the other graph. Therefore, there is always exactly one relation between each pair of modules. TCG is closed under the move operation, and such an operation takes O(m2 ) time, where m is the number of modules in the placement. 11.8 TCG-S TCG-S representation, also proposed by Lin and Chang in Refs. [5,13], combines TCG = (Ch , Cv ) and SP = (+ , − ), which uses a horizontal and a vertical TCGs as well as the packing sequence − to represent a placement. TCG-S tries to combine the advantages of SP and TCG and at the same time eliminate their disadvantages. With the property of SP, faster packing and perturbation schemes are possible. Inheriting some nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. With the characteristics of TCG and SP, TCG-S has the following four feasibility properties: 1. Ch and Cv are acyclic. 2. Each pair of nodes must be connected by exactly one edge either in Ch or in Cv . 3. Transitive closure of Ch (Cv ) is equal to Ch (Cv ) itself. 4. Packing sequence − is the topological order of both Ch and Cv . 11.8.1 FROM A PLACEMENT TO TCG-S For two nonoverlapped modules bi and bj , they could bear one of the horizontal, vertical, and diagonal relations as defined in Section 11.7. If bi is horizontally (vertically) related to bj , denoted by bi bj (bi ⊥ bj ), then bi is left to (below) bj and their projections on the y(x) axis overlap. The diagonal relation between two modules bi and bj is also defined in Section 11.7, and is treated as a horizontal one unless there exists a chain of vertical relations from bi (bj ), followed by the modules

Handbook of algorithms for physical design automation part 24

Nội dung