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

Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 152 Finals Page 152 29-9-2008 #15 Handbook of Algorithms for Physical Design Automation or four modules/rectangles at any level with their given connectivity and size specifications takes constant time. Another strong motivation for employing a hierarchical approach is that because floorplanning decisions affect the subsequent phases of placement or global routing, it is desirable to integrate these phases as much as possible. A hierarchical method makes this computationally feasible as designed and implemented by Dai et al. [16,39] and Lengauer et al. [40]. As part of the macrocell based layout system called BEAR, the hierarchical floorplanner by Dai et al. consists of three steps: Step 1—Bottom-up clustering: A hierarchical tree is constructed in a bottom-up fashion by clustering strongly connected modules greedily. Each cluster has a limited number of modules, typically upto four. For each cluster, the shapes of the blocks are also considered so that there is no mismatch within the cluster. Issues with size incompatibility at higher levels between two neighboring clusters with fewer connections may arise, but these can be resolved by limiting the sizes of the clusters at the higher levels so that the smaller sized clusters are dealt with earlier, thereby reducing the percentage of wasted area. Step 2—Top-down placement: The cluster tree is traversed from the root, which has its desired shape and terminals specified. These requirements are propagated to the children clusters and their respective shape and terminals are determined. The small number of possible floorplan templates (Figure 8.11) are enumerated and clusters are assigned to rectangles or rooms in a template to obtain a floorplan topology. In most cases, the winning topology is determined by computing the estimated routing space for each of the possible topologies. This is continued till the orientations of the leaf modules are decided. It may be pointed out that this method works well when the leaf level modules can be of flexible shape. A certain amount of look ahead to the grandchild level is also added during top-down shape determination. The system allows the user to monitor the trade-off among shape, area, and connections costs. Step 3—Floorplan optimization: This step improves the solution obtained above by iteratively selecting certain blocks and resizing them. The blocks selected usually lie on the longest paths through the placement based on the routing estimates. Such paths are either between the left and right sides of the chip or the top and bottom sides. The routing cost is computed by adding the edge weights (number of net connections) between pairs of clusters multiplied by the distance between their centers in the current placement. The global routing information is updated incrementally after each iteration. The stopping criterion is that the longest paths contain fixed size blocks only or flexible blocks that belong to the longest path in the perpendicular direction as well. Although this method is very efficient for small circuits, it needs to be executed in a two-pass mode iteratively, one for each direction, to achieve fast convergence for larger circuits. In the hierarchical approach taken by Lengauer et al. [40], the hierarchy or cut-tree is generated in a top-down manner by recursive mincut method initially and then the bottom levels of the tree are obtained by bottom-up clustering. Once again the degree of the cut-tree is restricted to 4. Floorplan FIGURE 8.11 Some templates used in hierarchical floorplanner BEAR with at most degree 4 branching at any node of the hierarchy. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Floorplanning: Early Research Finals Page 153 29-9-2008 #16 153 sizing is done by bottom-up traversal of the cut-tree to compute the floorplan alternatives based on the shape function for the children modules/rectangles. Finally, a particular floorplan alternative and its corresponding global routing are constructed simultaneously. For a floorplan topology, there exists a breadth-first top-down labeling of the nodes of the cut-tree with a particular pattern. The pattern selection performed at each node is guided by the external wiring costs computed for the previous cut-tree level without the need for penalty functions à la Dai et al. for assigning modules to rectangular regions smaller than the requirement. Moreover, the number of patterns is bounded by a small integer. The sizing algorithm employs shape function instead of the penalty-oriented method by Dai et al. Thus, this method implemented in the system FRODO reports better results over BEAR. 8.6 FLOORPLAN SIZING METHODS Given a floorplan topology, the second task is to obtain the aspect ratios of the modules so that the overall area, total netlength, and maximum netlength is optimal. Some of the major techniques are listed below and more details of two important ones appear in the subsequent sections. 1. Force-directed with slicing [41]: The PIONEER system is an iterative method. It provides two capabilities: extraction of initial layout from a user-specified data and interactive graphics for improving the initial layout. The improvement of initial layout proceeds in three steps. First, macrocenters are determined, then a slicing structure is generated, and finally the layout is expanded. 2. Relaxation method [42,43]: This iterative floorplanning method is different from improvement by interchange because relaxation implies an obvious next state. In Ref. [42], dimensional relaxation is used to improve a floorplan. It consists of modifying the shapes of cells as well as the topology of the horizontal and vertical line segments that define the floorplan. 3. Simulated annealing: Timber Wolf [44] is one of the first floorplanning systems based on simulated annealing technique. It produces not only the relative positions of the modules but also their aspect ratios and pin positions. The algorithms for optimal floorplan design, reported in Ref. [21,38], also use simulated annealing. The first algorithm can generate slicing structures with rectangular modules only, whereas the second one can produce nonslicing floorplans and even L-shaped modules. A new representation of floorplans using normalized Polish expressions facilitates selection during iterative improvement by pairwise interchange (see Chapter 9 for details). The major disadvantages of these systems are that they are computation intensive and may not be readily adapted to deal with various constraints on floorplan. 4. Genetic algorithm [45]: This stochastic iterative method requires appropriate encoding of a floorplan and its associated cost function along with the definition of effective crossover and mutation operators for iterative moves. Each move has an activation probability. It can handle large floorplans and the quality of the solutions are comparable with simulated annealing-based methods. 5. Analytic force-directed method with packing [46,47]: Iterative floorplanning by this method consists of two subtasks. First, an initial placement is obtained either by potential energy method, or by attractive and repulsive force method as in the CHAMP system. Then a semiautomatic block packing process is undertaken by relocating and reshaping modules as well as the chip boundary. Constraint-based analytic sizing methods have also been proposed [48–50]; further details are elaborated in the following section. 6. Branch-and-bound [29]: Layouts occupying minimum area can be obtained by this method using graph-theoretic representation of floorplan and suitably formulating a network flow optimization problem. Graph-theoretic representation can also yield optimal aspect ratios of modules in any floorplan by a branch-and-bound heuristic. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 154 Finals Page 154 29-9-2008 #17 Handbook of Algorithms for Physical Design Automation 8.7 ANALYTIC SIZING The floorplan sizing algorithms that adopt an analytical approach essentially model the problem as a set of constraints on the dimensions and connectivities of the rectangular modules such that a certain objective function is minimized. Among these, a method based on potential energy modeling of overlap and separation was proposed by Ying et al. [48]. The shape constraints are met by bounding penalty functions. An unconstrained minimization problem is then solved heuristically. As the time complexity is high, the authors mention incorporating hierarchical floorplanning by using the method recursively. The most effective and widely referred analytic floorplan sizing algorithm based on mixed integer programming formulation was proposed by Sutanthavibul et al. [49]. The essence of this is described next. The assumption is that the area of a rectangular module is known a priori, but its actual shape may be either fixed or flexible within certain limits for the aspect ratios (width to height ratio). The variables in the mixed integer programming are of two types, namely integer variables (xi , yi ) indicating the x- and y-coordinates of the lower left corner of module i, and certain 0–1 variables that primarily take care of different constraints. The width and height of module i is denoted by (wi , hi ). Constraints for nonoverlap of modules i and j: If both modules are rigid, we have the four linear inequalities (I.a). Typically, the bounds on the width W and height H of the chip may be specified. By employing two 0–1 integer variables xij and yij , we can ensure that at least one of the four inequalities (I.b) holds for any pair of modules i and j. Thus for any one of the four possible values of (xij , yij ), only one of the four inequalities is applicable, the other three being vacuously true. It is assumed that for all i, the values of (xi , yi ) are nonnegative and definitely less than the chip width or height as the case may be. Constraints for nonoverlap of two rigid modules i and j xi + wi ≤ xj , i left of j xi − wj ≥ xj , i right of j yi + hi ≤ yj , i below j yi − hj ≥ yj , i above j xi + wi xi − wj yi + h i yi − h j ≤ xj + W (xij + yij ) ≥ xj − W (1 − xij + yij ) ≤ yj + H(1 + xij − yij ) ≥ yj − H(2 − xij − yij ) (I.a) Variable-size chip (I.b) Fixed-size chip If rotation by 90◦ is to be permitted for the rigid modules, then an additional 0–1 integer variable zi is introduced and the constraints are modified to the following where M = max(W , H): xi + zi hi + (1 − zi )wi ≤ xj + M(xij + yij ) xi − zj hj + (1 − zj )wj ≥ xj − M(1 − xij + yij ) yi + zi wi + (1 − zi )hi ≤ yj + M(1 + xij − yij ) yi − zj wj + (1 − zj )hj ≥ yj − M(2 − xij − yij ) Next, modules with flexible shapes but fixed area si are considered in the inequalities (I.c and I.d) by converting the quadratic relation wi hi = si to a linear one, i.e., by expressing hi as a linear function of wi based on the first two terms of the Taylor series expansion about the point wi max as given below: hi = si si + (wi max − wi ) 2 or, hi = hi0 + wi λi wi max wi max Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 155 29-9-2008 #18 155 Floorplanning: Early Research where hi0 = si wi max , λi = si wi2max , and wi = wi max − wi Constraints for nonoverlap of a flexible module i xi + wi max − wi yi + hi0 + wi λi xi − wj yi − h i ≤ xj ≤ yj ≥ xj ≥ yj (I.c) With rigid module j xi + wi max − wi ≤ xj yi + hi0 + wi λi ≤ yj xj + wj max − wj ≤ xi yj + hj0 + wj λj ≤ yi (I.d) With flexible module j Constraints on interconnection length can also be thrown in with few continuous positive variables per net and the half-perimeter metric is used. The complexity of the entire mixed integer linear programming problem may be reduced by considering the constraints for critical nets only as this number is far smaller. Routability is modeled by linear constraints based on the rule that the total net length is 0.5 times the length of the routing tracks in the chip. This ensures that enough empty space around each module is reserved for routing. For each pair of modules, two continuous and one integer variable is introduced. The package LINDO is used to solve for the values of the variables and arrive at a floorplan solution. If the topology is given, then all the 0–1 integer variables acquire specific values and the problem of determining the shapes of the modules reduces to standard linear programming one and is hence polynomially solvable. The number of continuous variables and the linear constraints are respectively 2n and O(n) where the floorplan has n modules. The major drawback of this approach is the huge solution time for mixed integer linear programming. For example, a floorplan with 25 modules may need about 600 integer variables. The technique devised to overcome this is to consider very few, typically 10–12, modules at a time and then successively augment the floorplan in a locally optimal way by adding a new group of modules each time till all modules have been processed. The selection of the groups of modules can be performed either by clustering based on connectivity or linear ordering depending on the I/O connections. The key to reducing the complexity is to have fewer number of variables, thus the already positioned modules in a partial floorplan are replaced by fewer number of covering rectangles. The floorplanning algorithm by analytical method [49] is given in Algorithm 2. Algorithm 2 Floorplanning algorithm by mixed integer linear programming [49] Algorithm MILP_Floorplan begin Select a group S of k modules as seed; Formulate MILP for S; Solve to generate partial floorplan for S; while (k ≤ n)do/ ∗ n is total number of modules ∗/ Select a new group of e modules based on connections to already positioned modules; Find a set of d covering rectangles for the present partial floorplan where d ≤ k; Formulate MILP for d covering rectangles and e unpositioned modules; Solve to obtain new partial floorplan; k = k + e; endwhile; end. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 156 Finals Page 156 29-9-2008 #19 Handbook of Algorithms for Physical Design Automation 8.8 BRANCH-AND-BOUND STRATEGY FOR SIZING One of the early algorithms for optimal sizing of general floorplans with rigid modules was devised by Wimer et al. [29]. The input to this algorithm is a floorplan topology represented by a pair of dual polar graphs, also known as the x-graph or horizontal constraint graph, and the y-graph or vertical constraint graph. Each graph is planar, directed acyclic with a single source and a single sink corresponding to the left (top) and right (bottom) edges of the bounding rectangle of the floorplan. A vertex in the x-graph corresponds to a vertical side of a rectangular module in the floorplan. There is a directed arc from a vertex i to a vertex j if there is a rectangular module in the floorplan whose left and right edges correspond to i and j, respectively. In the y-graph, the vertices denote the horizontal edges of the modules and the directed arc goes from the top edge i lying above the bottom edge j of a module. Each module Mk in the floorplan topology has a set of one or more specified dimensions, so in the x-graph the directed edge from the left to the right vertical edge of Mk has an associated weight denoting the width wk of Mk . Similarly, in the y-graph the weight of a directed edge corresponds to the height of the module whose top and bottom edges form the endpoints of the edge. In the floorplan sizing problem, the goal is to determine the positions of all the modules for a given topology such that the total area of the bounding rectangle is minimized. For slicing topologies, the two graphs belong to the special class called series parallel. If each leaf has finitely many possible shapes, then Stockmeyer’s bottom-up sizing algorithm [22] becomes applicable. However, for the general case the problem is NP-hard so a branch and strategy is chosen. It proceeds as follows: First, a module is chosen based on some criterion for a particular level. In other words, if there are n modules, then there are n levels in the branch-and-bound tree and the degree of a node in the ith level is equal to the number of possible shapes of module Mi . A linear order of the modules is obtained so that along any directed path of x- or y-graph, the predecessors of a module appear in the linear order before the module. At the root, each edge of the x- and y-graphs is assigned the smallest possible value it may take among all given shapes for the first module in the linear order. While going from the ith level to the (i + 1)th, appropriate values are assigned to the edges corresponding to the module Mi+1 in the two graphs. At each node of the tree, the width and height of the partial floorplan is computed. When going down along a path in the tree from root to a leaf, the area is nondecreasing in the number of already positioned modules. Let Amin denote the minimum value of area achieved thus far. The forward processing is performed in level order from the root. If at a node in ith level, the area A is greater than the current Amin of the (i + 1)th level processed thus far from left, then this node is not expanded any further (Figure 8.12) and the process backtracks upward till it finds a suitable node for branching downward. The efficiency of the method is influenced by the following factors: (1) the value of Amin as early backtracks are desirable; (2) the area of a partial floorplan obtained is a lower bound on the area of the complete floorplan, hence if the lower bound is raised, early backtracks will occur; and (3) the order in which the possible dimensions of module Mi are examined at the ith level of the branch-and-bound tree. Intuitively, a module whose size is likely to have greater effect on the area of the complete floorplan, such as one with large size or one which lies on a critical (longest) path or many directed paths in the polar dual graphs, should be considered earlier. Along with a branching strategy that guarantees attainment of global minimum, a very effective bounding value for the area of the remaining modules is computed to guide the search. Additional efficiency of the method is attained by decomposing the floorplan topology into maximal slicible structures for which series-parallel algorithm is applied. Branch-and-bound strategy is used only for the maximal rectangles as discussed in Section 8.4.1. Another constraint-based floorplanning algorithm proposed by Vijayan et al. [50] also can handle flexible, fixed (rigid), and preplaced modules. The input is specified as two sets of constraints in the form of the two directed acyclic horizontal and vertical constraint graphs. A linear time algorithm for topological sorting of directed acyclic graphs is used to find the critical (longest) paths in the Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Finals Page 157 29-9-2008 #20 157 Floorplanning: Early Research B1 B2 B3 (b) (a) (c) 0 B1 B2 B3 4 4 4,1 30∗ 2,5 18 5,2 9,1 3,3 1,9 27 45 99 9,1 3,3 14 5,2 1,9 4 2,2 24 20 2,5 1,4 15 2,5 5,2 9,1 3,3 1,9 9,1 3,3 1,9 9,1 3,3 1,9 9,1 3,3 1,9 27 35 77 54 32 56 45 42 78 54 24 42 (d) FIGURE 8.12 (a) Example floorplan topology with three modules, (b) its x-graph, (c) its y-graph, and (d) its branch-and-bound tree where shape lists are B1 : (4,1),(2,2),(1,4), B2 : (5,2),(2,5), and B3 : (9,1),(3,3),(1,9). The width–height pair appears inside the node and the area of the subfloorplan at that level, outside it. A node marked “∗” has area greater than minimum bound at that stage and hence no further branching from it is required. (From Wimer, S., Koren, I., and Cederbaum, I., IEEE Trans. Computer-Aided Design, 8, 139, 1989.) two graphs. Redundant constraints are removed and flexible blocks on the more critical paths are reshaped. Certain criteria to characterize two different notions of redundancy among constraints are formulated and utilized to reduce the time complexity. This heuristic is iterated until a floorplan solution of desired dimensions is obtained. 8.9 KNOWLEDGE-BASED FLOORPLANNING APPROACHES Floorplanning is meaningful for very large designs tackled in a top-down fashion. There is generally a vast amount of design data and the optimization problems are computatinally hard. Often more than one objective has to be optimized. Thus, artificial intelligence techniques have been attempted by a few researchers, especially when details of modules are not known. FLOYD, one of the early rule-based expert systems for floorplanning, was designed and implemented by Dickinson [1]. The key idea in another system FLUTE [2] is to produce a rectangular topology by placing the modules on a rectangular grid graph using a set of rules that take shape and connectivity constraints into account. Then sizing or geometric realization is achieved by a heuristic method to solve a system of linear and quadratic inequalities. Like many artificial intelligence systems, this is implemented in LISP. Jabri and Skellern [4] adopt a combination of algorithmic and knowledge-based approach for a top-down floorplanning system called PIAF. Rectangular dualization method is used to generate topologies and then other constraints are introduced for knowledge-based estimation and prediction of dimensions and areas of modules. The final phase consists of a greedy algorithm for determining the exact shapes and locations of the modules. The system FLAIR developed by Brück et al. [3] employs a band of expert systems for estimating a broad range of design parameters relevant to Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 158 Finals Page 158 29-9-2008 #21 Handbook of Algorithms for Physical Design Automation transforming an architectural plan to a geometric one in two steps—first producing a rough or postulative plan and then a final one. In general, these systems are fairly complex to design, implement, and validate. Accurate definition of the rule base and its fine tuning are required for attaining optimality. These have greater potential in interactive design environments. 8.10 UNIFIED METHOD FOR TOPOLOGY GENERATION AND SIZING With exponentially many feasible topologies for a given neighborhood graph, design space exploration and optimality are limited if the sizing is performed on a particular feasible topology. Among the very few methods that integrate the two subtasks of floorplanning, two are notable. The first one is a dynamic programming based method [51] that can handle slicible floorplans only. A set of slicing trees is enumerated by top-down partitioning of the adjacency graph and represented by an enumeration tree model. Size optimization is carried out simultaneously by Stockmeyer’s method [22] for each topology enumerated. The role of dynamic programming is to reduce the time complexity to polynomial time by memoization of optimal solutions for subfloorplans. The second method [52] is a two-phase technique applicable to nonslicible floorplans including inherently nonslicible ones. Canonical embedding results of Section 8.4.3 are applied to establish that a binary tree representation for general floorplans exists where the internal nodes correspond to either straight cutlines or Z-cuts having two monotonic staircase bends. The possible topologies are derived by top-down partitioning and kept in an AND–OR graph. A bottom-up sizing phase finally reports the optimal floorplan. The slicibility criterion in Ref. [34] can provide additional improvement in the speed of the floorplanner with negligible sacrifice of solution quality. ACKNOWLEDGMENTS The author would like to thank all her floorplanning research collaborators, especially Professors Bhargab B. Bhattacharya of Indian Statistical Institute and Parthasarathi Dasgupta of Indian Institute of Management, Kolkata. Part of the Sections 8.3, 8.3.1, 8.4.2, and 8.7 has been published in Sur-Kolay, S. and Bhattacharya, B.B., Foundations of Software Technology and Theoretical Computer Science, LCNS 338, 88, 1988; Bhasker, S. and Sahni, S., Algorithmica, 3, 274, 1988; Sur-Kolay, S. and Bhattacharya, B.B., Proceedings of the ISCAS, pp. 2850–2853, 1991; Sutanthavibul, E., et al., IEEE Trans. Computer-Aided Design, 10, 761, 1991, respectively. With permission. REFERENCES 1. A. Dickinson. Floyd: A knowledge-based floorplan designer. In Proceedings of the IEEE International Conference on Computer Design (ICCD), San Jose, CA, October 1–4, pp. 176–179, 1986. 2. B. Ackland and H. Watanabe. Flute: An expert floorplanner for full-custom VLSI design. IEEE Design and Test of Computers, 4:32–41, 1987. 3. R. Brück, K.-H. Temme, and H. Wronn. FLAIR: A knowledge-based approach to integrated circuit floorplanning. In Proceedings of the International Workshop on Artifical Intelligence for Industrial Applications, Hitachi City, Japan, May 25–27, pp. 194–199, 1988. 4. M.A. Jabri and D.J. Skellern. PIAF: A knowledge-based/algorithmic top-down floorplanning system. In Proceedings of the 26th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 25–29, pp. 582–585, June 1989. 5. F. Harary. Graph Theory. Addison-Wesley Publishing Co., Reading, MA, 1969. 6. R.H.J.M. Otten. Automatic floorplan design. In Proceedings of the 19th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 14–16, pp. 261–267, June 1982. 7. R.H.J.M. Otten. Efficient floorplan optimization. In Proceedings of the IEEE International Conference on Computer Design (ICCD), Port Chester, NY, pp. 499–502, October 1983. 8. R.L. Brooks, C.A.B. Smith, A.H. Stone, and W.T. Tutte. The dissection of rectangles into squares. Duke Mathematical Journal, 7: 312–340, 1940. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 Floorplanning: Early Research Finals Page 159 29-9-2008 #22 159 9. U. Lauther. A min-cut placement algorithm for general cell assemblies based on a graph representation. In Proceedings of the 16th ACM/IEEE Design Automation Conference (DAC), San Diego, CA, June 25–27, pp. 1–10, June 1979. 10. D.P. LaPotin and S.W. Director. MASON: A global floorplanning approach for VLSI design. IEEE Transactions on Computer-Aided Design, CAD-5(4): 477–489, October 1986 (ICCAD 1985). 11. H. Modarres and A. Kelapure. An automatic floorplanner upto 100,000 gates. IEEE Transactions on Computer-Aided Design, VLSI Systems Design, pp. 38–44, December 1987. 12. K. Kozminski and E. Kinnen. Rectangular duals of planar graphs. Networks, 15: 145–157, 1985. 13. S.M. Leinwand and Y.T. Lai. Algorithms for floorplan design via rectangular dualization. IEEE Transactions on Computer-Aided Design, 7(12), December 1988. (DAC 1984). 14. J. Bhasker and S. Sahni. A linear time algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica, 3(2): 274–278, 1988 (DAC 1986). 15. B. Lokanathan and E. Kinnen. Performance optimized floorplanning by graph planarization. In Proceedings of the 26th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 25–29, pp. 116–121, June 1989. 16. W.M. Dai and E.S. Kuh. Simultaneous floor planning and global routing for hierarchical building-block layout. IEEE Transactions on Computer-Aided Design, 6: 828–837, September 1987 (DAC 1986). 17. J. Bhasker and S. Sahni. A linear time algorithm to check for the existence of rectangular dual of a planar triangulated graph. Networks, 17: 307–317, 1987. 18. K. Koike, S. Tsukiyama, and I. Shirakawa. An algorithm to eliminate all complex triangles in a maximal planar graph for usein VLSI floorplan. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), San Jose, CA, May 5–7, pp. 321–324, IEEE, 1986. 19. G. Sorkin, W.R. Heller, and K. Maling. The planar package planner for system designers. In Proceedings of the 19th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 14–16, pp. 253–260, June 1982. 20. M.J. Garey and D.J. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., San Francisco, CA, 1979. 21. D.F. Wong and C.L. Liu. A new algorithm fir floorplan design. In Proceedings of the 23rd ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 29–July 2, pp. 101–107, June 1986. 22. L.J. Stockmeyer. Optimal orientation of cells in slicing floorplan designs. Information and Control, 57: 187–192, 1983. 23. P. Sipala, W.K. Luk, and C.K. Wong. Minimum area wiring for slicing structures. IEEE Transactions on Computer-Aided Design, C-36(6): 745–760, June 1987. 24. K.J. Supowit and E.F. Slutz. Placement algorithms for custom VLSI. In Proceedings of the 20th ACM/IEEE Design Automation Conference (DAC), Miami Beach, FL, June 27–29, pp. 164–170, June 1983. 25. S. Sur-Kolay and B.B. Bhattacharya. On the family of inherently nonslicible floorplans in VLSI design. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), pp. 2850–2853, Singapore, June 1991. 26. S. Sur-Kolay and B.B. Bhattacharya. The cycle structure of channel graphs for nonslicible floorplans and a unified algorithm for feasible routing order. In Proceedings of the IEEE International Conference on Computer Design (ICCD), pp. 524–527, Boston, October 1991. 27. Y. Cai and D.F. Wong. A channel/switchbox definition algorithm for building-block layout. In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC), Orlando, FL, June 24–28, pp. 638–641, June 1990. 28. S. Sur-Kolay. Studies on Nonslicible Floorplans in VLSI Layout Design, Doctoral dissertation, Jadavpur University, Calcutta, 1991. 29. S. Wimer, I. Koren, and I. Cederbaum. Optimal aspect ratios of building blocks in VLSI. IEEE Transactions on Computer-Aided Design, 8(2): 139–145, February 1989. 30. D.F. Wong and P.S. Sakhamuri. Efficient floorplan area optimization. In Proceedings of the 26th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, June 25–29, pp. 586–589, June 1989. 31. C.-H. Chen and I.G. Tollis. Area optimization of spiral floorplans. Journal of Circuits, Systems and Computers, 3(4): 833–857, 1993 (ICCD 1991). 32. K. Chong and S.Sahni. Optimal realizations of floorplans. IEEE Transactions on Computer-Aided Design, 12(6): 793–804, June 1993. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C008 160 Finals Page 160 29-9-2008 #23 Handbook of Algorithms for Physical Design Automation 33. S. Sur-Kolay and B.B. Bhattacharya. Inherent nonslicibility of rectangular duals in VLSI floorplanning. Foundations of Software Technology and Theoretical Computer Science, LCNS 338: 88–107, 1988. 34. P.S. Dasgupta and S. Sur-Kolay. Slicibility conditions of rectangular graphs and their applications to floorplan optimization. ACM Transactions on Design Automation of Electronic Systems, 6(4): 447–470, October 2001. 35. S. Sur-Kolay and B.B. Bhattacharya. Canonical embedding of rectangular duals. In Proceedings of the 29th ACM/IEEE Design Automation Conference (DAC), Aneheim, CA, June 8–12, pp. 69–74, June 1992. 36. S. Sun and M. Sarrafzadeh. Floorplanning by graph dualization: L-shaped modules. Algorithmica, 10: 429–456, 1993. 37. G. Yeap and M. Sarrafzadeh. Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal of Computing, 22(3): 500–526, June 1993. 38. D.F. Wong and C.L. Liu. Floorplan design for rectangular and L-shaped modules. In Digest of ACM/IEEE International Conference on Computer Aided Design (ICCAD), Santa Clara, CA, November 9–12, pp. 520–523, 1987. 39. W. Dai, B. Eschermann, E.S. Kuh, and M. Pedram. Hierarchical placement and floorplanning in BEAR. IEEE Transactions on Computer-Aided Design, 8(12): 1335–1349, December 1989. 40. T. Lengauer and R. Muller. Robust and accurate hierachical floorplanning with integrated global wiring. IEEE Transactions on Computer-Aided Design, 12(6): 802–809, June 1993. 41. L.S. Woo, C.K. Wong, and D.T. Tang. Pioneer: A macro-based floorplanning design system. VLSI System Design, CAD-4: 32–43, August 1986. 42. E. Berkcan and E. Kinnen. Ic layout planning and placement by dimensional relaxation. In Proceedings of the IEEE International Conference on Computer Design (ICCD), San Jose, CA, October 1–4, pp. 223–234, 1986. 43. M.J. Cieselski and E. Kinnen. Digraph relaxation for 2-dimensional placement of IC blocks. IEEE Transactions on Computer-Aided Design, CAD-6(1): 55–66, January 1987. 44. C. Sechen and A.L. Sangiovani-Vincentelli. The timberwolf placement and routing package. IEEE Journal of Solid-State Circuits, SC-20(2): 510–522, 1985. 45. M. Rebaudengo and M.S. Reorda. Gallo: A genetic algorithm for floorplan area optimization. IEEE Transactions on Computer-Aided Design, 15(8): 943–951, August 1996. 46. Y.C. Hsu and W.J. Kubitz. A procedure for chip floorplanning. In Proceedings of the International Symposium on Circuits and Systems (ISCAS), Philadelphia, PA, May 4–7, pp. 568–571, 1987. 47. K. Ueda, H. Kitazawa, and I. Harada. Champ: Chip floorplan for hierarchical VLSI layout design. IEEE Transactions on Computer-Aided Design, CAD-4: 12–22, January 1985. 48. C. Ying and J.S. Wong. An analytical approach to floorplanning for hierarchical building blocks layout. IEEE Transactions on Computer-Aided Design, 8(4): 403–412, April 1989. 49. S. Sutanthavibul, E. Shragowitz, and J.B. Rosen. An analytical approach to floorplan design and optimization. IEEE Transactions on Computer-Aided Design, 10(6): 761–769, June 1991. (DAC 1990). 50. G. Vijayan and R.S. Tsay. A new method for floor planning using topological constraint reduction. IEEE Transactions on Computer-Aided Design, 10(12): 1494–1501, December 1991. 51. G. Yeap and M. Sarrafzadeh. A unified approach to floorplan sizing and enumeration. IEEE Transactions on Computer-Aided Design, 12(12): 1858–1867, December 1993. 52. P.S. Dasgupta, S. Sur-Kolay, and B.B. Bhattacharya. A unified approach to topology generation and optimal sizing of floorplans. IEEE Transactions on Computer-Aided Design, 17(2): 126–135, February 1998. Alpert/Handbook of Algorithms for Physical Design Automation AU7242_C009 Finals Page 161 24-9-2008 #2 9 Slicing Floorplans Ting-Chi Wang and Martin D.F. Wong CONTENTS 9.1 9.2 9.3 Introduction.. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Preliminaries . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Slicing Floorplan Representations.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.3.1 Slicing Tree .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.3.2 Polish Expression . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.4 Optimizations on Slicing Floorplans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.4.1 Area Optimization .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.4.1.1 Oriented Slicing Tree .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.4.1.2 Unoriented Slicing Tree .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.4.2 Area/Power Optimization .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.5 Classical Slicing Floorplan Design .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.5.1 Mincut-Based Slicing Floorplan Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.5.2 Point-Configuration Based Slicing Floorplan Design . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.5.3 Simulated Annealing Based Slicing Floorplan Design . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.6 Slicing Floorplan Design Considering Placement Constraints.. . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.6.1 Boundary Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.6.2 Range Constraints . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.6.3 Abutment Constraints .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.6.4 Clustering Constraints.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.7 Other Advances in Slicing Floorplans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.7.1 Theoretical Results for Area-Optimal Slicing Floorplans .. . . . . . . . . . . .. . . . . . . . . . . . . . 9.7.2 Completeness of Slicing Tree Representation . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.7.3 Heterogeneous FPGA Floorplanning .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.7.4 3D Floorplanning .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.8 Conclusion .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 161 162 163 163 164 164 164 164 168 168 169 170 171 171 172 173 174 175 176 177 177 178 179 181 182 183 9.1 INTRODUCTION A floorplan is a dissection of an enveloping rectangle R by horizontal and vertical line segments into a set of nonoverlapping basic rectangles (or rooms) such that each room is large enough to accommodate the module assigned to it. Note that in some situations, there may be some basic rectangles without any modules assigned to them. We call them empty rooms. An important class of floorplans is the set of all slicing floorplans [1,2]. A slicing floorplan is one that can be obtained by recursively cutting a rectangle into two smaller rectangles by either a vertical or horizontal line segment. Typically, a slicing floorplan for n modules has n rooms each of which 161

Handbook of algorithms for physical design automation part 18

Nội dung