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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 142 Handbook of Algorithms for Physical Design Automation a 5 b 9 e 1 i h 12 4 11 6 1 12 3 (b) 6 1 2 4 3 d 11 7 11 (c) 7 5 9 e h 1 i 4 8 11 8 8 c 9 5 2 4 (a) 12 10 7 g 12 5 f 10 3 a 9 6 2 8 d Finals Page 142 29-9-2008 #5 g 6 2 3f 7 b 10 c 10 (d) FIGURE 8.2 (a) Rectangular graph N, (b) its geometric dual without the vertex for the exterior face, (c) its inner dual, and (d) its rectangular dual. (Figure a, b, and c from Sur-Kolay, S. and Bhattacharya, B.B., Lecture Notes in Computer Science, 338, 88, 1988.) duals for a given R, the strength of the dualization method lies in the fact that a solution, if one exists, can nevertheless be found in linear time [14]. A graph embedding is a particular drawing of a graph on a surface (which may often be a twodimensional plane) such that its edges may intersect only at their endpoints. A graph is planar if there exists an embedding of it on a plane, whereas a plane graph is an embedding of a planar graph on a plane [5]. By definition, a rectangular floorplan is embedded on a plane, which therefore implies that its rectangular graph is a plane graph. As all intersections of cuts of F form T-junctions, all the internal faces of R, the rectangular graph of F, are triangles bounded by three edges. Hence, a rectangular graph is a plane triangulated graph [12,13]. Given an n-vertex plane triangulated graph G, its rectangular dual Rd , [12,13] consists of n nonoverlapping rectangles, where a rectangle in Rd corresponds to a distinct vertex i ∈ G, and rectangles i and j in Rd share at least a portion of a side if and only if there is an edge (i, j) in G. The rectangular dual of G, if it exists, corresponds to a valid rectangular floorplan where the rectangles represent the modules of the floorplan. Because all faces of G are triangles, no more than three rectangular faces in the rectangular dual of G meet at a vertex and thus the floorplan has only T-junctions and no cross junctions. A rectilinear embedding of a plane graph is an embedding in which all the edges of the graph are either horizontal or vertical. Thus, a cycle in the plane graph is embedded as a rectilinear polygon. Next, let G be a given plane triangulated graph and Gd be its geometric dual [5] whose vertices correspond to the faces of G and there is an edge between two vertices in Gd if and only if the corresponding faces in G share an edge. An inner dual D [16,33] of G is a rectilinear embedding of Gd , excluding the vertex corresponding to the exterior face of G, such that each internal face of D is bounded by four or more edges and embedded as a rectangle. All the internal vertices of D have degree 3. Thus, we can obtain the rectangular dual of G (Figure 8.2) by placing the inner dual of G within an enveloping rectangle, because the exterior face of G is not reflected in D, and then projecting each degree 2 (respectively, degree 1) vertex of D onto the side (respectively, two sides) of the enveloping rectangle nearest to it. A vertex in D has degree 1 if two of the edges of the corresponding triangular face in G lie on its exterior face and only the third edge is shared with another internal triangular face of G. But the key question is whether a rectangular dual exists and if so, how it can be constructed efficiently. 8.3.1 DUALIZABILITY A plane triangulated graph that is a rectangular graph has a rectangular dual, by definition. Every plane triangulated graph however does not have a rectangular dual. A triangle (or cycle of length 3) in a plane triangulated graph G, which is not the boundary of an internal face, is called a complex triangle [13,18]. In the graph shown in Figure 8.3a, the triangles ABD, BDC, and CDA are internal Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 143 29-9-2008 #6 143 Floorplanning: Early Research A A D B B (a) D C C (b) FIGURE 8.3 (a) Plane triangulated graph with a complex triangle and (b) conflict in constructing its rectangular dual. faces, but triangle ABC is not and is therefore a complex triangle. So in the rectangular dual, if rectangles A, B, and C have to share edges pairwise, then there is no room for rectangle D to share edges with all the three rectangles A, B, and C and yet not overlap with any of these three rectangles (Figure 8.3b). One of the necessary conditions for G to have a rectangular dual is that G has no complex triangles. Formally, a graph G is said to be a properly triangulated plane (PTP) graph, if it is a connected plane graph and satisfies the following properties [12]: P1 : Every face (except the exterior) is a triangle (i.e., bounded by three edges). P2 : All internal vertices have degree ≥4. P3 : All cycles that are not faces and the exterior face have length ≥4. Further, every planar graph that satisfies P1 and P3 also satisfies P2 [17]. The necessary and sufficient conditions under which a PTP graph G has a rectangular dual were established in Refs. [12,13]. A few definitions are needed for the statement of these conditions. A chord of a cycle in G is an edge between two nonconsecutive vertices on the cycle (so it is not part of the cycle). A chord (u, v) of the outermost cycle S of G is said to be critical if one of the two paths between u and v on the cycle has no end vertices of any other chord of S. Such a path is called a corner implying path. For instance, the edge (a, e) in Figure 8.1c is a chord, and a critical one as well where the path {a, h, e} is corner implying. The implication of this is that in the rectangular dual of R, the rectangle corresponding to vertex h has to be in a corner of the bounding rectangle of the dual. A graph G is said to be biconnected if between any two vertices u and v in G there exist two paths in G with no common vertices except u and v. Biconnected components of a graph are commonly called blocks, and a vertex shared by two blocks is an articulation point. So, the block neighborhood graph (BNG) of a graph G is a graph in which there is a distinct vertex for each block of G and there is an edge between two vertices if and only if the two corresponding blocks share a vertex. A corner implying path in a block of G is said to be critical if it contains no articulation points of G. Corner implying path criteria [12]: A PTP graph G has a rectangular dual if and only if one of the following is true: 1. G is biconnected and has no more than four corner implying paths. 2. G has k, k > 1, biconnected components; the BNG of G is a path itself; the biconnected components that correspond to the ends of this path have at most two critical corner implying paths; and no other biconnected component contains a critical corner implying path. Intuitively, a biconnected rectangular graph should have no more than four vertices having degree 2 and these, if at all present, should appear on the outermost cycle because a rectangular dual can have at most four rectangles at the four corners of its bounding rectangle. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 144 Finals Page 144 29-9-2008 #7 Handbook of Algorithms for Physical Design Automation It can be shown that biconnectivity and the properties P1 and P3 of a rectangular graph imply that its embedding is unique. Kozminski and Kinnen gave an O(n2 ) time algorithm for constructing such a dual. Bipartite matching criteria: Another elegant characterization of rectangularity based on the perfect matching problem in bipartite graphs was established in Ref. [13]. Each T-junction may be uniquely associated with the module whose side (wholly or partially) forms the crosspiece (defined later in Section 8.3.2.1) of the T-junction. As the T-junctions in the rectangular dual correspond to the triangular faces in the PTP graph, each triangular face in the PTP graph is assigned to one of its three vertices (indicated by arrows in Figure 8.4) for construction of a floorplan. Although there may be more than one such assignment for a given R (Figure 8.4a and b), an arbitrary assignment may not guarantee a feasible rectangular dual. Further, to take into account the T-junctions along the boundary of the rectangular dual, the graph R is extended by adding four special vertices t, r, b, and l to represent the four sides of the boundary and all vertices on the outermost cycle of R are connected appropriately to these four sides to retain the PTP property. Each corner vertex has two extra edges and each of the remaining vertices on the outermost cycle has one extra edge. A bipartite graph B = (X ∪ Y , E) is derived thus from the PTP graph R, where (1) each vertex in X corresponds to a triangular face of R, (2) Y is a set of vertices associated with each vertex υ of R such that if degree of υ is d(υ), then there are exactly d(υ) − 4 instances of υ, and (3) there is an edge between a vertex x ∈ X and a vertex y ∈ Y if the PTP face corresponding to x is adjacent to the PTP vertex represented by y. In the PTP of Figure 8.4, the outermost cycle has six vertices of which vertices h, b, c, and d are chosen as corners. and therefore each of these has two extra edges in the extended graph and vertices a and e have only one extra edge each. The dualizability criteria [13] are as follows: 1. PTP graph admits a rectangular dual if and only if each triangular face can be assigned to one of its adjacent vertices such that each vertex y with degree d(υ) has d(υ) − 4 triangular faces assigned to it. 2. PTP graph admits a rectangular dual if and only if there is a perfect matching in the bipartite graph associated with it. a h t8 t1 f t6 e t5 g b t2 a b c1 c2 d e1 t1 t2 t3 t4 t5 a b c1 c2 d e1 t1 t2 t3 t5 f t3 t7 c t4 d (a) e2 t6 t7 t8 a h t8 (b) t1 f t6 e t5 d g b t2 t7 t4 e2 f t3 c t4 t6 t7 t8 FIGURE 8.4 (a) Rectangular graph R with a feasible assignment of triangular faces to vertices, and the maximum matching in its bipartite graph B that corresponds to the floorplan in Figure 8.1a; (b) another feasible assignment for R and the maximum matching in B that corresponds to the floorplan in Figure 8.1b. Matched edges are indicated by thick lines. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 145 29-9-2008 #8 145 Floorplanning: Early Research Steps of rectangular dualization Input: A block-level circuit connectivity graph C. Output: A floorplan F. 1. Planarization of C by edge deletion or dummy node addition 2. Triangulation of the planar graph 3. Elimination of complex triangles from the plane triangulated graph to obtain a PTP graph 4. Construct and report a rectangular dual of the PTP graph At this juncture, the steps of floorplanning by rectangular dualization [19] of a circuit are summarized above as an analysis of its time complexity is in order. The first step of planarization of the logical network of the circuit by deleting a minimum number of edges or a set of edges with minimum total weight is known to be NP-complete [20]. The second step of triangulating a planar graph can be done in linear time. But, there is neither a polynomial time optimum algorithm nor a NP-completeness proof [18] for the third step of eliminating all complex triangles from the plane triangulated graph. Efficient polynomial time algorithms for constructing a rectangular dual for a given PTP graph have been proposed in Refs. [12,13,17]. This has been improved by Bhasker and Sahni to a linear time algorithm [14] to check existence of a rectangular dual for a given planar triangulated graph and construct it, if it exists. An outline of this algorithm appears below in Algorithm I and the major steps are demonstrated in Figure 8.5. The limitation of rectangular dualization stems from its requirement of a PTP graph, but this can be overcome as discussed in Section 8.4.4. The algorithmic efficacy of rectangular dualization often leads to employing this method to generate a good topology on which other iterative floorplanning methods can be applied to obtain very good solutions quickly. Algorithm 1 Linear time algorithm to find a rectangular dual [14] Algorithm RD_Floorplan begin 1. For each biconnected component of given PTP graph Embed it on a plane such that P1 and P3 are satisfied and all its articulation points are on the outermost cycle; If no embedding exists, then report ‘NOT DUALIZABLE’ and halt; 2. Find the critical corner implying paths and assign four corners NW, NE, SE, SW to vertices on the outermost cycle; 3. Add to the graph a special vertex Head-node and new directed edges from it to all the vertices on the outermost cycle between NW and NE; 4. Starting from NW , traverse downward from Head-node; 5. For each directed path from Head-node starting with the leftmost one for each vertex in the directed path order place a new rectangle below its predecessor such that the adjacency with rectangles for vertices on the path immediately to its left is maintained. end. 8.3.2 SLICIBILITY OF RECTANGULAR DUALS Several investigators have advocated that in top-down hierarchical circuit design, slicing structures have advantages over general nonslicing ones. Slicible floorplans can be represented by elegant data structures such as series-parallel polar graphs [6,8], slicing trees [7], and normalized Polish postfix Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 146 Finals Page 146 29-9-2008 #9 Handbook of Algorithms for Physical Design Automation Head-node a h b NW a h f e c d (a) SW b NE g g d b f e f e g a h d c SE (b) c (c) FIGURE 8.5 (a) Rectangular graph R, (b) its path directed graph with a special head-node and the four corners marked, and (c) rectangular dual construction by traversing each directed path from the special head-node in left to right order as indicated by dashed lines. expressions [21]. These types of floorplans are computationally easier to deal with because they allow a natural partition of the design into partially independent subproblems, hence the divide-and-conquer strategy succeeds. The problem of optimal orientations of modules is solvable in polynomial time for a slicible floorplan, but remains NP-complete in the strong sense for general floorplans [22]. Slicing facilitates not only floorplanning but also wiring. Optimal wiring of a single net in a slicing structure, minimizing the overall area instead of wirelength, can be done in O(n log n) time [23]. This problem is far more complicated in the general nonslicible case. In fact, the next chapter of this handbook dwells exclusively on slicing floorplans. Notwithstanding the fact that slicible floorplan topologies have enjoyed preference owing to their divide-and-conquer algorithms, nonslicible floorplans are better as far as optimal sizing is concerned, and hence their intriguing properties are addressed later in this chapter. The distinguishing criterion between slicibility and nonslicibility of a floorplan succinctly epitomized in Ref. [24] is presented next. The issue of representing nonslicible floorplans is addressed in Section 8.4. The salient question whether a slicible floorplan exists for a given neighborhood graph for modules of a circuit is also taken up thereafter. 8.3.2.1 Four-Cycle Criterion for Slicibility of a Floorplan A graph-theoretic characterization of slicible floorplans [24] is based on the concept of a channel graph, where a channel in a floorplan is a cutline. From the convention of T-junctions, no two channels overlap. If two perpendicular channels a and b intersect at a point p, then p is an endpoint of either a or b, but not both; the one of which p is an endpoint is called the base of the T-junction and the other is called the crosspiece. The two parts of the crosspiece channel on either side of the junction are called arms. The same cut may be the base of one T-junction and crosspiece of another T-junction. A channel graph of a floorplan is a directed graph C = (V , A) where there is a distinct vertex in V for each channel and there is an arc (a, b) from a to b in A if and only if there is a T-junction of which channel a is the base and channel b the crosspiece. Figure 8.6b and d shows the respective channel graphs of the slicible and nonslicible floorplan in Figure 8.6a and c. The following two crucial theorems about channel graphs of floorplans were proved in Ref. [24]: 1. Four-cycle theorem: A channel graph has a directed cycle if and only if it has a cycle of length 4. 2. Slicing theorem: A channel graph of a floorplan is acyclic if and only if the floorplan is a slicible floorplan. Essentially, by detecting directed four-cycles in the channel graph of a given floorplan, its nonslicibility can be decided and this is achievable in linear time. There are two possible arrangements Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 147 29-9-2008 #10 147 Floorplanning: Early Research h 7 1 a f 4 e 2 (a) 3 5 g b 6 1 7 a 4 3 1 c h 7 e 5 2 2 (b) 6 (c) b f 5 4 d 3 d g 7 1 6 c 3 4 5 2 6 (d) FIGURE 8.6 (a) Slicible floorplan Fs and (b) its channel graph; (c) nonslicible floorplan Fn and (d) its channel graph containing a directed four-cycle. of channels in a floorplan that produce directed four-cycles in the channel graph. This property can also be employed in a polynomial time heuristic for converting a nonslicible floorplan to a slicible one with minimal alterations [25]. A few more properties of channel graphs have been observed [26,27]. A channel graph C is (1) connected, (2) planar but not necessarily embeddable on a planar grid, (3) bipartite, (4) outdegree of any vertex in C ≤ 2, (5) at least four vertices in C have outdegree 1, (6) every internal face of C is bounded by exactly four arcs, (7) the number of arcs shared by two adjacent directed four-cycles is less than or equal to 1, and (8) C has no bridges [5]. The channel graph of a given floorplan is unique, but there may be more than one floorplan with the different neighborhood relations corresponding to a given channel graph. The existence of a floorplan corresponding to a planar, bipartite digraph with maximum outdegree of 2 and at least four vertices having outdegree 1 was raised in Ref. [27], and the affirmative answer was proven in Ref. [28]. The next section addresses certain important features of nonslicible floorplans. 8.4 NONSLICIBILE FLOORPLAN TOPOLOGIES 8.4.1 MAXIMAL RECTANGULAR HIERARCHY The several efficient representation schemes that follow naturally from the recursive definition of slicible floorplans are not directly applicable to nonslicible floorplans. Nevertheless, a general nonslicible floorplan has a unique representation based on the concept of maximal rectangular hierarchy (MRH) [25] and above all, this representation is supportive of divide-and-conquer algorithms. Similar representations have been proposed independently in Refs. [29–32], although they mostly assume that at each level there can be a branching of at most five as is the case for the basic nonslicible pattern. A close relation between the strongly connected components of the channel graph of a nonslicible floorplan and its MRH was established [26], which leads to a simple depth-first search based O(n) algorithm for extraction of MRH where the floorplan has n modules. A maximal rectangle in a floorplan can be defined as one which is not contained in any rectangle other than the envelope of the floorplan, or does not partially overlap with any other rectangle. A nonslicible floorplan can be decomposed uniquely into a nonempty set of mutually exclusive (nonoverlapping) and collectively exhaustive maximal rectangles. This is demonstrated in Figure 8.7. If the floorplan is slicible and has a single through cut at the top level of the slicing tree, then the two rectangles on either side of the through cut are the only maximal rectangles. In the case of multiple through cuts in the same direction at the top level, the boundary is the only maximal rectangle; all indivisible blocks within it are its children in the MRH. The usual slicing tree may be utilized for processing within this maximal rectangle. Maximal rectangles can be defined recursively to produce a hierarchy of maximal rectangles, called the maximal rectangular hierarchy. A maximal rectangle may contain a slicible or a nonslicible pattern of rectangles. At the top level, we have just the bounding rectangle of the floorplan. Each Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 148 Finals Page 148 29-9-2008 #11 Handbook of Algorithms for Physical Design Automation 2 17 5 1 6 16 3 10 7 4 9 19 20 15 27 25 14 18 11 21 8 22 12 26 23 24 28 13 (a) 21 11 12 13 14 15 16 17 1 2 3 4 5 6 7 8 9 10 (b) 18 28 22 19 20 23 24 25 26 27 FIGURE 8.7 (a) Maximal rectangular hierarchy of a floorplan topology and (b) the corresponding hierarchy tree. Each level of the hierarchy is marked by a different line thickness. (From Sur-Kolay, S., Studies on nonslicible floorplans in VLSI layout design, Doctoral dissertation, Jadavpur University, 1991.) level of the MRH has a rectangular boundary and a set of mutually exclusive and collectively exhaustive maximal rectangles. This hierarchy can be represented by a tree. Because the set of maximal rectangles at each level is unique, the MRH of a nonslicible floorplan is also unique. 8.4.2 INHERENT NONSLICIBILITY The fact that a rectangular graph can have more than one nonisomorphic dual brings us to the fundamental question about the existence of rectangular graphs that have no slicible duals. This is equivalent to characterizing slicibility of rectangular graphs. A rectangular graph is inherently nonslicible if there exists no slicible rectangular dual of it, consequently no slicible floorplan. It turns out that [33] there exists an inherently nonslicible graph N, having nine vertices. N is a minimum (in the number of vertices and edges) inherently nonslicible rectangular graph. The inherently nonslicible graph, N, is a maximal rectangular graph (MRG) (i.e., no edge can be added without violating rectangularity) of 9 vertices and 20(=3∗ 9 − 7) edges. An MRG of n vertices is not unique. For all n ≥ 4, there exists an MRG with (3n − 7) edges that has a slicible dual. It follows that any rectangular graph with 8 or fewer vertices has a slicible rectangular dual. Moreover, the minimum rectangular graph that is inherently nonslicible is unique. There exists a family of inherently nonslicible floorplans, named INS [25]. Besides the first member N, (Figure 8.2a), few more are shown in Figure 8.8a through d, and in fact, there are an infinite number of members in INS. The peculiarity of inherent nonslicibility can be demonstrated by examining a few pairs of similar floorplans. Consider the one in Figure 8.8a. The cut β acts like a lock and blocks slicibility. But addition of another vertical cut to divide the block below it produces a slicible floorplan so this new cut acts like a handle aiding slicibility. With this insight, pseudomaximality at any level of the MRH is defined so that if any maximal rectangle has more than four T-junctions around it externally, then the next level of the MRH within it cannot be ignored. The intuition behind this is that the inner level may provide a handle and produce an equivalent slicing. This idea is applicable for deciding membership in INS. Although nonslicibility of given floorplan can be easily decided as mentioned earlier in Section 8.3.2.1, the necessary and sufficient conditions Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 149 29-9-2008 #12 149 Floorplanning: Early Research b (a) (c) (b) (d) FIGURE 8.8 Members of family INS: (a) second smallest having two 5-wheels, (b) third smallest having three 5-wheels, (c) fourth smallest having four 5-wheels, and (d) template for a general member. (Figure a, c, and d from Sur-Kolay, S. and Bhattacharya, B.B., in Proc. Inter. Symp. Circuits and Systems, Singapore, 1991, pp. 2850–2853.) for INS are still an open problem. But few sufficient conditions for slicibility of rectangular graphs that have been proven [26,28] are listed next. Slicibility and vertex degree pattern: In a floorplan F, an indivisible rectangular module has k ≥ 4 T-junctions (including corners) on it, which is called a facial k-cycle. First, F is pseudomaximally reduced to F , then extracting the dual of F gives a reduced rectangular graph R . If R satisfies any of these conditions that can be checked quickly, then we can guarantee the existence of a slicible equivalent of F , hence F. A reduced rectangular graph is slicible if (1) all its internal vertices have degree 5 or more, or (2) none of its internal vertices have degree 5. Hence, all facial cycles in F have length 4 or more than 5, but not 5. In the members of INS discovered, there is always a vertex of degree 4 with at least two adjacent vertices having degree 5. Slicibility and three-chromaticity: A rectangular graph is slicible if it is (1) three-chromatic or (2) outerplanar [5]. Checking whether a given rectangular graph is three-chromatic as well as determining a valid vertex coloring with three colors can be done in linear time. Tighter criterion of slicibility: A fairly recent result on slicibility [34] states that a rectangular graph R with n vertices, n > 4, is slicible if it satisfies either of the following conditions: 1. Its outermost face is a four-cycle and not all four exterior vertices are required to be corners. 2. All the complex four-cycles in R are maximal (i.e., not contained in any other four-cycle). 8.4.3 CANONICAL EMBEDDING OF RECTANGULAR DUALS Nonuniqueness of the rectangular dual of a neighborhood graph has associated with it the notion of equivalence of two rectangular duals with isomorphic neighborhood graphs being isomorphic. Equivalent floorplans are not isomorphic in terms of definition of the channels. Nonisomorphic floorplans correspond to different rectangular dissections, so the associated cutlines are different. Any floorplan with n modules has n − 1 channels and (2n − 2) T-junctions. Hence, the number of Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 150 Finals Page 150 29-9-2008 #13 Handbook of Algorithms for Physical Design Automation 16 2 3 17 19 18 5 20 11 6 1 21 4 10 9 22 26 12 7 15 8 28 23 27 25 14 24 13 (a) 14 1 2 3 4 5 6 7 8 9 10 11 12 17 28 13 16 15 21 18 19 20 22 (b) 23 24 25 26 27 FIGURE 8.9 (a) Canonical embedding of the floorplan in Figure 8.7a and (b) its MRH tree. Each level is marked with different line thickness. (From Sur-Kolay, S., Studies on nonslicible floorplans in VLSI layout design, Doctoral dissertation, Jadavpur University, 1991.) nodes and arcs in the two channel graphs are equal, but the difference lies in the set of arcs. This leads to the concept of a canonical rectangular dual or a canonical embedding for a class of equivalent floorplans. A canonical embedding of a rectangular dual is a rectilinear embedding, which (1) is a valid equivalent floorplan and (2) the corresponding channel graph has the minimum number of directed four-cycles. A maximal rectangle at any level of the MRH is said to be strongly maximal (smr) if it has exactly four T-junctions around it externally. It has been shown that any level of the strong MRH (i.e., MRH with smr’s) can have at most one smr in the canonical form [35] of the rectangular dual (Figure 8.9). The properties of nonslicible rectangular duals in this section are useful in producing desired floorplan topologies, and are also relevant to the subsequent routing phase. 8.4.4 DUALIZATION WITH RECTILINEAR MODULES If a given adjacency graph is not dualizable, then one approach discussed earlier is to convert it to a PTP graph by planarizing and eliminating all forbidden complex triangles [18]. But this very often ends up in large wasted space because of the introduction of several dummy modules. An alternative approach is to introduce L-shaped modules [36], or even two-concave rectilinear modules with shapes like Z, T, W, or U [37] (Figure 8.10). The necessary and sufficient conditions under which a plane triangulated graph admits a dual with such rectilinear modules appear in Ref. [37] and their construction algorithm for a dual with n modules requires O(n) time. The origin of L-shaped modules is in the complex triangles in the adjacency graph. A floorplan, or the dual of the graph, is now seen as a dissection of a bounding rectangle into L-shaped regions where a rectangle is a special type of L-shaped region. A plane triangulated graph with a complex triangle (Figure 8.3a) is no longer forbidden because one of the three vertices of the complex triangle, say C, Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 151 29-9-2008 #14 151 Floorplanning: Early Research Z T W U FIGURE 8.10 Four possible two-concave rectilinear shapes of module and each can be decomposed into two L-shaped modules as indicated by the dashed line. (From Yeap, G. and Sarrafzadeh, M., SIAM J. Comput., 22, 500, 1993.) can be realized as an L-shaped module having a concave corner to satisfy all adjacency conditions. As a matter of fact, for each complex triangle, at least one of its three vertices must have an L-shaped module in the dual, i.e., the floorplan topology. An assignment of a complex triangle to a vertex needs to be made to accommodate a concave corner in the corresponding module. A conflict is said to occur if a vertex is simultaneously assigned to two complex triangles where one is not contained in the other. An adjacency graph is said to be fully assigned if all its complex triangles can be assigned without any conflicts. The set of vertices assigned is termed as the assignment set. The characterization of graphs that admit L-shaped duals is given by the following criteria. A plane triangulated adjacency graph G has an L-shaped dual De if and only if it satisfies the following two properties [37]: 1. G has at least five vertices and the exterior face of G is a cycle of length greater than 4. 2. G can be fully assigned and the corresponding assignment set A does not include the four vertices on the exterior face. An algorithm to find a geometric dual containing both rectangular and L-shaped duals has been designed based on finding an assignment set using maximum matching [36]. This has also been generalized to the case where the input graph is not biconnected. The time complexity to test whether a given G admits an L-shaped dual is O(n3/2 ) and to construct one, if it exists, is O(n2 ), where n is the number of modules. Incidentally, given such a topology, a simulated annealing-based algorithm for floorplan sizing with L-shaped modules was designed and implemented by Wong and Liu [38]. Further generalization to two-concave rectilinear modules with eight sides, six convex corners, and two concave corners has also been proposed in Ref. [37]. The necessity for these arises from the fact that conflicts may arise during assignment of vertices to complex triangles. A perfect assignment of a plane triangulated graph G is a set of assignments of all its complex triangles where (1) every complex triangle is assigned to a vertex, (2) no vertex has more than two assignments, and (3) the four vertices t, l, b, and r on the exterior face are unassigned. The necessary condition for the existence of a dual, i.e., floorplan topology with two-concave rectilinear modules for a given G is finding a perfect assignment. Such an assignment and thus a floorplan can be constructed in time linear in the number of modules. The key result is that every biconnected planar triangulated graph admits a floorplan with twoconcave rectilinear modules. Hence, these modules are the ultimate, i.e., necessary and sufficient for floorplanning by graph dualization. 8.5 HIERARCHICAL FLOORPLANNING As finding an optimal solution to the floorplanning problem is computationally expensive, hierarchical approach for handling larger instances is a natural choice. The fundamental idea is to divide and conquer with a very small branching factor at each level. Although the number of possible floorplans for a given problem is exponential, enumeration of all possible floorplans for only three

Handbook of algorithms for physical design automation part 17

Nội dung