26th ACIIii/IEEE
`N AUTOMAT. ON
`FIENcE®
`
`JUNE 2" JUNE 2J, 1989
`1 VEGAS CONVEX MON CENT
`
`ACM Order Number 477890
`Library of Congress Catalog Card Number 85-644924
`IEEE Catalog Number 89CH2734-2
`IEEE Computer Society Order Number 1961
`ISBN 0-89791-310-8
`ISSN 0738-100X
`
`SIGDA® (cid:9)
`
`IEEE COMPUTER SOCIETY
`
`THE INSTITUTE OF ELECTRICAL
`AND ELECTRONICS ENGINEERS, INC.
`
`IEEE
`
`XILINX, EX. 1010
`Page 1 of 8
`
`

`
`PROCEEDINGS OF THE ACM/IEEE DESIGN AUTOMATION CONFERENCE®
`
`9th (1972) Contains 47 Papers 379 Pages
`10th (1973) Contains 36 Papers 288 Pages
`11th (1974) Contains 47 Papers 379 Pages
`12th (1975) Contains 57 Papers 448 Pages
`13th (1976) Contains 63 Papers 501 Pages
`14th (1977) Contains 70 Papers 507 Pages
`15th (1978) Contains 72 Papers 493 Pages
`16th (1979) Contains 94 Papers 586 Pages
`17th (1980) Contains 81 Papers 656 Pages
`18th (1981) Contains 134 Papers 917 Pages
`19th (1982) Contains 125 Paper 928 Pages
`20th (1983) Contains 122 Papers 832 Pages
`21st (1984) Contains 116 Papers 736 Pages
`22nd (1985) Contains 124 Papers 838 Pages
`23rd (1986) Contains 124 Papers 835 Pages
`24th (1987) Contains 138 Papers 840 Pages
`25th (19 ) Contains 125 Papers 730 Pages
`26th (1989) Contains 156 Papers 835 Pages
`
`Prices (1989) ACM or IEEE Members: $42.00
`All Others: $56.00
`
`© 1989 by the Association for Computing Machinery, Inc. Copying without fee is permitted provided that the copies
`are not made or distributed for direct commercial advantage and credit to the source is given. Abstracting with credit
`is permitted. For other copying of articles that carry a code at the bottom of the first page, copying is permitted provided
`that the per-copy fee indicted in the code is paid through the Copyright Clearance Center, 27 Congress Street, Salem,
`MA 01970. For permission to republish write to: Director of Publications, Association for Computing Machinery, 11
`West 42nd Street. New York, NY 10036. To copy otherwise, or republish, requires a fee and/or specific permission.
`
`ACM Order Number 477890
`ISBN 0-89791-310-8
`Library of Congress Catalog Card Number 85-644924
`IEEE Catalog Number 89CH2734-2
`ISBN 0-8186-8961-7 (case)
`ISBN 0-8186-5961-0 (microfiche)
`ISSN 0738-100X
`IEEE Computer Society Order Number 1961
`
`Additional copies of 1989 or prior Proceedings may be ordered prepaid from:
`
`ACM
`Order Department
`P.O. Box 64145
`Baltimore, MD 21264
`
`IEEE Computer Society
`Publications Office
`10662 Los Vaqueros Circle
`Los Alamitos, CA 90720
`
`IEEE Computer Society
`European Office
`13, avenue de L'Aquilon
`B-1200 Brussels, Belgium
`
`IEEE Computer Society
`2-19-1 Minami Aoyama
`Minato-Ku
`Tokyo 107, Japan
`
`IEEE Service Center
`445 Hoes Lane
`P.O. Box 1331
`Piscataway, NJ 08855-133
`
`These organizations should be contacted before placing an order to determine availability and cost of past
`Proceedings.
`
`ii
`
`XILINX, EX. 1010
`Page 2 of 8
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`PERFORMANCE OPTIMIZED FLOOR PLANNING
`BY GRAPH PLANARIZATION
`
`Badri Lokanathan and Edwin Kinnen
`
`Dept. of Electrical Engineering
`University of Rochester, Rochester NY 14627
`
`Abstract
`A new procedure for VLSI floor planning that minimizes
`routing parasitics is presented. The procedure, based on
`rectangular dualization, maximizes adjacency of modules
`that are heavily connected or connected by critical nets.
`1Viring macros are introduced to provide routing area for
`those modules that cannot be located adjacent to one
`another; these macros are located by planarizing the system
`interconnectivity graph using an edge crossing strategy that
`minimizes the cost of intersection. The rectangular dual is
`compacted using heuristics to approximate a quadratic area
`constraint by one or more linear constraints, thereby reduc-
`ing the complexity of compaction from that of quadratic pro-
`gramming to linear programming.
`
`1. Introduction
`Floor planning in VLSI is a procedure for allocat-
`ing adequate area and shapes to system modules and
`their interconnections while conserving overall chip lay-
`out area. An extension of this floor planning problem is
`obtained if, in addition, performance criteria such as
`critical nets, routing area and power dissipation are
`included. The rapid growth in complexity, size and den-
`sity of VLSI systems has made floor planning a chal-
`lenging task. Even with computer assistance, manual
`floor planning is a lengthy and error prone process.
`Hence there is considerable interest in finding efficient
`ways to automate the procedure.
`Currently, a widely accepted methodology for sys-
`tem layout is to place and interconnect pre-designed
`standard cells or modules whose dimensions and inter-
`connection terminals have been fixed. This method has
`proven to be fast and easily amenable to automation,
`particularly when these modules have been crafted for a
`family of applications. The drawback of this method is
`that space may be used inefficiently for both layout and
`wiring, resulting in larger layout area and slower speed
`of operation than necessary. This is inevitable since
`most area planning and routing problems are known to
`be NP-hard.
`
`Permission to copy without fee all or part of this material is granted provided
`that the copies are not made or distributed for direct commercial advantage,
`the ACM copyright notice and the title of the publication and its date appear,
`and notice is given that copying is by permission of the Association for
`Computing Machinery. To copy otherwise, or to republish, requires a fee
`and/or specific permission.
`
`An alternative to a bottom-up fixed cell or stan-
`dard cell methodology for layout is a top-down
`custom/semi-custom floor planning strategy. Here the
`final layout of modules is performed after compartmen-
`talizing the surface of the chip into cells, each cell to
`contain no more than one module. The objective in
`floor planning is both to determine individual cell
`dimensions for the efficient use of layout area and to
`locate cells that contain heavily connected modules
`either adjacent or in proximity to one another. The
`module designer can use positional information pro-
`vided by floor planning to locate terminals on the peri-
`phery of the module such that interconnect distances
`are reduced. Floor planning subsumes the placement
`problem and a major part of the routing problem.
`A design procedure for custom VLSI floor plan-
`ning is presented here. The emphasis is on maximizing
`adjacency between cells containing modules that are
`either heavily connected or connected by critical nets,
`thereby reducing parasitics due to wire length. Since it
`is generally impossible to locate every pair of connected
`modules in adjacent cells, wiring macros are introduced
`in the layout to provide space for the connections of
`non-adjacent modules. Locations for these wiring mac-
`ros are identified by planarizing the system interconnec-
`tivity graph (SIG) using an edge-crossing algorithm that
`minimizes the cost of intersection. The design objective
`is to reduce potential routing parasitics, crosstalk and
`high frequency reflection sites at vias and jogs by
`minimizing the routing of critical nets and the number
`of nets in wiring macros. The method of rectangular
`dualization has proven to be a powerful algorithmic pro-
`cedure for constructing topologies that are based upon
`adjacent rectangles;' it is used to construct a floorplan
`from the interconnectivity graph of the system. A com-
`pacting procedure is applied to the rectangular dual to
`obtain the best cell dimensions.
`The design procedure can be described briefly as
`follows. The system is initially modeled by a hypergraph
`whose vertices represent the modules and edges the
`interconnections or nets. A SIG is generated from this
`hypergraph by an algorithm described in Section 3. The
`SIG is simple, that is, its edges are weighted but it does
`not have multiple edges or loops. In order to apply the
`method of rectangular dualization, the SIG must be
`planar and triangulated but without non-facial triangles.
`Algorithms for planarization and triangulation are
`described in Sections 4 and 5. A graph that satisfies
`
`Paper 8.3
`
`116
`
`26th ACM/IEEE Design Automation Conference®
`
`© 1989 ACM 0-89791-310-8/89/0006/0116 $1.50
`
`XILINX, EX. 1010
`Page 3 of 8
`
`

`
`conditions for rectangular dualization generally yields a
`family of rectangular duals. In Section 6, procedures
`are described for obtaining a rectangular dual and com-
`pacting it to yield the best floor plan.
`The steps of the procedure presented here are
`similar to those of a floor planning procedure presented
`earlier.2 However the strategies adopted at each of the
`stages differ, in part by avoiding branch and bound pro-
`cedures. Included is a new algorithm for deriving the
`SIG and a new procedure for dual compaction.
`
`2. Model
`For the purpose of floor planning, a VLSI system
`can be regarded as a set of rectangles that represents the
`modules of the system. The floor planning procedure
`dissects the chip surface into cells for these rectangles,
`whose minimum area and aspect ratio are given. All
`connections between adjacent modules, that is, modules
`located in abutting cells are assumed to be made
`through the edges of adjacency. This procedure is best
`suited for custom VLSI design where the final module
`dimensions and module pin locations are not fixed prior
`to the time of floor planning. However this procedure
`also has applications to pre-designed modules or stan-
`dard cells with the assumption that additional area is
`allowed for routing nets along the edges of adjacency.
`For custom modules, it is assumed that the
`designer has some means of estimating areas and aspect
`ratio limits of modules based on their complexity. A
`strategy for this is to examine existing libraries for
`modules of similar architecture. A study performed on
`a library of standard cells in a particular technology has
`indicated that the area of the module can be estimated
`from the number of transistors. The aspect ratio limits
`are dependent upon the architecture of the module and
`can often be predicted by an experienced designer.
`
`3. Generating a System Interconnectivity Graph
`To obtain a SIG, nets are assumed to connect or
`span a set of modules rather than a set of terminals.
`This is equivalent conceptually to making all connec-
`tions between module centers rather than among the
`pins. Then the system can be modeled by a hypergraph
`II whose vertices and edges represent the modules and
`the interconnecting nets. This hypergraph can be
`transformed into a simple graph G in several ways. The
`most direct transformation is to represent each module
`as a vertex in G and each net by a clique on the vertices
`corresponding to the modules connected by the net.
`However, this often results in a dense graph that can be
`hard to planarize. Hence a clustering method is
`adopted, wherein the vertices of G represent clusters of
`modules that are heavily connected. The intent of this
`clustering, in the limit, is that within a cluster each net
`connects all modules, indicating no preferred relative
`placement of these modules. Therefore, good heuristics
`for area efficiency, such as 2-D bin-packing algorithms
`and their extensions, can be used to place the modules
`within a cluster.3, 4
`To begin the procedure for generating a SIG, the
`nets are ordered by the decreasing number of connected
`blocks. Then clustering is performed sequentially on
`each net, partitioning the set of vertices into non-
`overlapping subsets. This process is referred to in the
`algorithm as mitotic division due to its similarity to bio-
`logical cell division. The output of the algorithm is a
`
`SIG, each edge of which represents one or more con-
`nections between the clusters at the endpoints of the
`edge. These clusters are either groups of modules or
`wiring macros that connect other clusters. Clusters that
`contain more than one module are treated as a single
`super-module for the purpose of floor planning.
`Algorithm_cluster is given in detail in the appendix.
`
`4. Planarizing the System Interconnectivity Graph
`Algorithm_cluster generally results in a SIG that
`is non-planar. The method of rectangular dualization,
`however, is applicable only to a planar graph.
`Algorithm_planarize derives a planar interconnectivity
`graph by introducing vertices for edge crossings that
`represent wiring macros or busses in the layout of the
`system. The problem of finding an embedding of a
`graph in a plane with a minimum number of edge cross-
`ings has been shown to be NP-complete.5 Therefore a
`greedy heuristic is adopted wherein the edges are
`ordered by decreasing weight and the graph is incremen-
`tally tested for planarity. If the graph tests for non-
`planarity, then a set of crossings by the current edge
`with other edges is obtained such that the sum of the
`weights of the other edges is minimum. The objective
`is to introduce a wiring macro at the intersection of a
`cheap edge and an expensive edge rather than at the
`intersection of low weighted edges, where the weighting
`is some measure of criticality. Experiments indicate
`that this heuristic generally results in smaller wiring
`macros.
`The planarization is performed by a procedure,
`crossing_edges, that identifies a subset of edges of
`minimum cost in a connected subgraph C with which an
`edge (a,b) can intersect such that the resulting graph is
`planar. The procedure is based on selecting the shortest
`path between two vertices in the geometric dual of C
`that represent faces adjacent to vertices a and b in com-
`ponent C. Crossing_edges is a modified version of an
`earlier algorithm° that did not always identify the
`minimum cost intersection due to the existence of non-
`isomorphic duals of biconnected graphs. The new algo-
`rithm is based on partitioning the graph into triconnected
`components. A triconnected component has a unique
`embedding in the plane and hence has a unique dual.?
`Algorithm_cluster and procedure crossing_edges are
`given in the appendix.
`
`(b)
`
`5. Periphery Identification and Graph Completion
`The planar interconnectivity graph resulting from
`algorithm_planarize must satisfy certain conditions for
`the rectangular dualization procedure to be applicable:8
`all faces of the graph must be triangulated, i.e.,
`(a)
`have degree 3, except the unbounded outer face,
`whose degree must be greater than 3, and
`all non-facial cycles must have degree greater than
`3.
`Physically the outer face corresponds to the periphery of
`the layout. If the planar graph can be embedded in the
`plane such that it has several faces with degree greater
`than 3, then each of these faces is a potential outer face.
`If the original specification includes pads as modules,
`then the outer face must contain vertices representing
`the pad modules. However if pads were not included in
`the specification, then the choice of the outer face can
`be based on other considerations. For example, a face
`may be chosen that is incident on vertices representing
`
`Paper 8.3
`
`117
`
`XILINX, EX. 1010
`Page 4 of 8
`
`

`
`may be chosen that is incident on vertices representing
`modules with maximal connectivity to the exterior.
`Other considerations may be area, connectivity or ther-
`mal dependent.
`If the SIG is triconnected, then it has a unique
`embedding in a plane once the periphery is fixed,7 that
`is, the relative placement of cells is determined once the
`periphery is selected. However, this is not true if the
`SIG is a biconnected graph, since there may be several
`ways of placing cells without violating adjacency require-
`ments. These several ways represent choices that the
`user can exploit based on additional information. A
`biconnected graph usually results if some of the
`modules are sparsely connected to the rest of the sys-
`tem.
`
`The final step before rectangular dualization is to
`triangulate all faces except the outer face and eliminate
`any non-facial triangle. It can be proved that a graph
`that does not contain a non-facial triangle can always be
`triangulated without creating a non-facial triangle, either
`by adding new edges within the face or by adding
`exactly one new vertex in the face and connecting it to
`the vertices on the periphery. Hence triangulation is
`performed after eliminating existing non-facial triangles.
`These non-facial triangles are removed by introducing
`an additional vertex in each triangle using a heuristic
`that locates the vertex between the vertices that
`represent the two largest blocks in the triangle. Physi-
`cally, this heuristic attempts to balance the adjacency
`requirements with areas in order to reduce stretching of
`the new macro that represents the added vertex.
`
`0. Compaction of Rectangular Duals
`A graph satisfying all conditions for rectangular
`dualization generally yields a family of rectangular duals.
`A good floor plan is obtained by selecting a dual that
`yields the most compact dual. Several methods have
`been proposed for enumerating rectangular duals.°
`Experiments have shown that the method of sequen-
`tially turning turnable structures yields solutions that are
`close to the global optimum relatively quickly. The
`dimensions of rectangles in the dual are constrained by
`the physical dimensions of the corresponding modules
`as well as the common edges among adjacent rectangles
`that are necessary for the interconnections between
`abutting modules. If the dimensional constraints are
`only on the perimeter of the rectangle, then a straight-
`forward constructive procedure is sufficient to obtain the
`most compact layout.g However, if the dimensional con-
`straints include area or aspect ratios, then the layout can
`be sized by a quadratic programming procedure. Since
`the number of duals to be enumerated could be large, a
`new more efficient optimization procedure is proposed
`below to prevent the computation cost from becoming
`prohibitive.
`
`0.1. Formulation of the New Optimization Problem
`To obtain the physical layout of the rectangular
`dissection, it is necessary to compute the dimensions of
`each rectangle and its location. In addition, two rectan-
`gles can abut either horizontally or vertically; this spatial
`relationship in a rectangular dual is represented by
`assigning orientations and directions to the edges of the
`SIG.t Once the topology of the layout is determined by
`
`t This description can be given formally in terms of a 4-
`completion and turnable structures.9
`
`orienting all the edges, the only variables are the x and
`y dimensions of each rectangle. The physical location of
`the rectangle can then be determined by adding the
`dimensions of rectangles to the left to give the x coordi-
`nate of the lower left corner, and the dimension of the
`rectangles below to give the y coordinate.
`Let the variables (xi , yi, 0< i< n), where n is
`the number of modules, denote the x and y dimensions
`of the i'th module and (x0, yo) denote the x and y
`dimensions of the entire rectangular dual. The objec-
`tive function chosen is the perimeter of the rectangular
`dual
`
`P = 2(x o (cid:9)
`
`yo).
`
`Four types of constraints imposed upon the module
`dimensions are:
`(1) Area constraints expressed as
`
`x; y; > (cid:9)
`
`= 1, . . . , n
`
`where a_mini is the minimum area required for
`the i'th module.
`(2) Perimeter constraints expressed as
`
`xi > x_mini
`> y_mini (cid:9)
`
`= (cid:9)
`
`' • ' ' n
`
`where x_mini denotes the minimum x dimension
`of the i'th module and y_mini its minimum y
`dimension. The perimeter constraints together
`with the area constraints can be used to incor-
`porate aspect ratio constraints on the modules.
`(3) Adjacency constraints: These depend upon the
`orientation of the corresponding edge in the SIG
`and its immediate neighbors incident at either
`endpoint of the edge. Each edge of the SIG in
`general contributes one adjacency constraint.
`There are eight possible cases; these are shown in
`Fig. 1.
`(4) Rectangular dual constraints: These are equality
`constraints that specify the topology of the rec-
`tangular dual and arise from the horizontal and
`vertical digraphs (Fig. 2) corresponding to the rec-
`tangular dual. It can be shown that exactly
`(n+ 1) equations are necessary to completely
`specify the rectangular dual constraints. This fol-
`lows from the fact that the rectangles are sized
`using Kirchhoff's laws and (n+ 1) equations are
`required to independently solve for the analogous
`current and voltage in each branch.")
`
`0.2. Relaxation of Quadratic Area Constraints
`The quadratic area constraints (1) of the perime-
`ter optimization problem are computationally expensive.
`However, the quadratic optimization problem can be
`transformed into a linear program if each area constraint
`is approximated by one or more linear constraints,
`depending on the accuracy desired.
`The approximation heuristic is described by a
`graph of the x-y dimensions of the i'th module in Fig.
`3, where the feasible dimensions of the module lie in
`the shaded region. Let
`
`0, =
`
`, (cid:9)
`
`i = 1, . . . , n
`
`Paper 8.3
`118
`
`XILINX, EX. 1010
`Page 5 of 8
`
`

`
`The case of interest is 0 ;> I. Let the region of the
`curve between points 1 and 2 be approximated by k
`linear segments, whose endpoints in sequence are given
`by
`
`k=2-
`R (cid:9)
`{x_mini O f k , y_mini 0; k }, p = 0, . . . ,k
`It is easily shown that each endpoint lies on the curve
`xi yi = a_mini.
`The maximum error in area due to the approxi-
`mation is given by
`
`C
`
`An; (cid:9)
`[
`2 10g, 0
`sin
`11
`a_m (cid:9)
`ini =
`2k
`
`I
`where Da; is the difference between a_mini and the
`area at the most distant point on any segment from the
`constant area curve
`
`i = 1, . . . , n
`
`=
`
`Thus the maximum error due to the approximation is a
`function of the minimum dimensions of the module
`and the number of segments that approximate the
`curve. e computed for different values of 0 and k is
`plotted in Fig. 4.
`It is convenient to make the following transfor-
`mation in variables:
`ui = (cid:9)
`— (cid:9)
`= — y_mini
`
`.
`= 1, . . . ,n
`
`to render the perimeter constraints implicit; i.e. they
`need not be given explicitly in the linear program. The
`endpoints of the linear segments can be rewritten as
`
`{X_Mini(0 ik — 1), y_Mini(0 k — 1)}
`where p = 0, . . . ,k . Thus each quadratic inequality
`constraint
`
`x1 y; >
`
`is rewritten as k linear inequalities of the form
`
`Vi > y_mini f0 ; k — 1}
`k —2p +1
` 0 •
`k (cid:9)
`
`X__711iTli
`
`— x_mind0 —11]
`
`where p = 1, . . . , k. k depends on the desired accu-
`racy of computation and can be computed for the i'th
`module:
`
`k
`
`= (cid:9)
`
`loge 0
`
`It has been found convenient to specify the same value
`of the maximum error in the approximation (i.e.
`ci=c, i =1, . . . , n) and then compute the number
`of linear constraints k necessary for each module.
`
`6.3. Compaction Strategy
`The process of computing the minimum perime-
`ter using the proposed optimization procedure could get
`expensive if it is repeated for all possible orientations of
`the SIG, since the number of linear approximation con-
`straints grows, depending upon the specified accuracy.
`As an alternative to reduce the computational effort, a
`
`dual enumeration procedure can be applied to modules
`with only perimeter constraints by assigning each
`module equal minimum x and y dimensions
`
`= (cid:9)
`Vr; (cid:9)
`,
`where ri is the aspect ratio of module i. A constructive
`method is used to compute dimensions of the cells dur-
`ing enumeration.9 The final rectangular dual obtained,
`however, may violate area constraints, since the lower
`limit of the x and y dimensions of each rectangle is
`smaller than the maximum dimension of the module.
`Application of the proposed optimization procedure at
`this point will correct this violation.
`
`7. Implementation and Results
`The algorithms presented here have been encoded
`in the C programming language and tested indepen-
`dently. The dual enumeration and compaction pro-
`cedures have been packaged into a single program
`IFPLAN (Interactive Floor PLANner) that currently
`operates under BSD Unix on Sun 3 workstations or
`AED512's. Most of the tests have been performed on
`benchmark examples with modules having fixed dimen-
`sions and pins. The example illustrated in Fig. 5 is one
`of the MCNC benchmarks, ami33. The modules were
`placed in the cells generated by IFPLAN and routed
`using UR-Wire,11 a locally developed straight wire
`router.
`
`References
`
`3.
`
`4.
`
`1. W.R. Heller, G. Sorking, and K. Maling, "The
`Planar Package Planner for System Designers,"
`Proc. 19th Design Automation Conference, pp. 253-
`260, 1982.
`2. M.A. Jabri, "Automatic Building of Graphs Rec-
`tangularly Dualisable for use in IC Floorplan-
`ning," Proc. International Symposium on Circuits
`and Systems, pp. 1683-1686, 1988.
`E.G. Coffman, M.R. Garey, D.S. Johnson, and
`R.E. Tarjan, "Performance Bounds for Level-
`Oriented Two-Dimensional Packing Algorithms,"
`Siam J Computing, vol. 9, no. 4, pp. 808-826,
`1980.
`S.L. Hakimi, "A Problem on Rectangular Floor-
`plans," Proc. International Symposium on Circuits
`and Systems, pp. 1533-1535, 1988.
`5. M.R. Garey and D.S. Johnson, "Crossing
`Number is NP-Complete," Siam J. Alg. Disc.
`Meth., vol. 4, no. 3, pp. 312-316, 1983.
`B. Lokanathan and E. Kinnen, "Planarization of
`VLSI Interconnectivity Graphs for Floorplanning
`using Rectangular D ualization, " Proc. Seventh
`Biennial UGIM Symposium, pp. 115-119, 1987.
`S. MacLane, "A Structural Characterization of
`Planar Combinatorial Graphs," Duke Math. J.,
`vol. 3, pp. 460-472, 1937.
`8. K. Kozminski and E. Kinnen, "Rectangular Duals
`of Planar Graphs," Networks, vol. 15, pp. 145-
`157, Jan. 1985.
`9. K. Kozminski and E. Kinnen, "Rectangular Dual-
`ization and Rectangular Dissections,"
`IEEE
`Trans. Circuits and Systems, vol. 35, no. 11, pp.
`1401-1416, 1988.
`
`6.
`
`7.
`
`Paper 8.3
`119
`
`XILINX, EX. 1010
`Page 6 of 8
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`10. R.L. Brooks, C.A.B. Smith, A.II. Stone, and W.T.
`Tutte, The Dissection of Rectangles into
`Squares," Duke Mathematical Journal, pp. 312-
`340, 1940.
`James.P. Coene, ''Detailed Routing for a VLSI
`Layout Based on Net Ordering," EL 88-07,
`Department of Electrical Engineering, University
`of Rochester, 1988.
`
`11.
`
`Figure 1(a): Possible cases of alignment for a
`horizontal edge directed from i to j
`
`I (cid:9)
`
`i (cid:9) II (cid:9)
`I
`i (cid:9)
`i (cid:9) I (cid:9)
`I (cid:9)
`1
`i (cid:9)
`I (cid:9)
`Figure 1(b): Possible cases of alignment for a
`vertical edge directed from I to j
`
`Vertical digraph
`
`Horizontal digraph
`
`Figure 2: Digraphs of a
`rectangular dual
`
`Shaded area indicates
`feasible region of
`quadratic constraint.
`
`Heavily shaded area
`indicates feasible region of
`one segment approximation.
`
`y_min
`
`x_min
`
`yi (cid:9)
`
`a_mini
`
`Figure 3: Approximation by one segment of
`quadratic region between points 1 and 2
`
`Paper 8.3
`120
`
`0 2
`
`6 8 10 12
`0 i
`
`Figure 4: Plot of error in approximation against
`0 for 1, 2 and 3 segment approximations
`
`bk15b
`
`bk17aT
`
`bk20
`
`bk19 bk8b
`
`• k 21
`
`bk13
`
`bk1411
`
`bk8a
`
`I1t31
`
`bk9b bk4
`
`bk9clizk_15___i2k18___
`
`k14a_
`
`k5b
`
`•k5____bk2bk14c bk5c
`
`bk1
`
`bk9s—___bk10a
`
`bk1511_
`
`ii7____
`
`bk5a
`
`bk11 (cid:9)
`
`bk1013
`
`.k12
`
`bki 7b
`
`k a
`
`Figure 5(a): Floor plan of ami33
`generated by IFPLAN
`
`kisb
`
`
`lull (cid:9)
`1,..m.mlio
`--iii ...--.1%.... —.E '00-iii...
`'111
` 1,f211 (cid:9)
`Mil
`1 (cid:9)
`il (cid:9)
`lit
`(cid:9) g L
`lownalumMula
`II (cid:9)
`....:,
`
` ii
`iiir (cid:9)
`Iti
`.... 1 i (cid:9)
`Is
` i
`III
`.m, 01011411..WIRMa
`TS ••••,,1
`
`•
`
`elemIM!
`
`l 4J
`,, non (cid:9)
`==,
`
`I
` I 1 ot r „
`Ill
`
`Figure 5(b): Layout after placement and routing
`
`XILINX, EX. 1010
`Page 7 of 8
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`
`Appendix
`algorithm_cluster:
`This algorithm takes as input a hypergraph H and
`generates a system interconnectivity graph F as
`output.
`Let C be an array of clusters and c the number of clus-
`ters and let the hyperedges of hypergraph H be sorted
`by the decreasing number of vertices;
`
`algorithm cluster(H);
`begin
`
`Initialize each vertex to belong to no cluster and
`C to be empty;
`0;
`C (cid:9)
`while there is a hyperedge h in H do
`begin
`
`Delete h from H;
`Let V be the set of vertices incident with h
`and 170 the vertices of V that do not belong
`to any cluster;
`if 170 (cid:9)
`then
`c +— c+1, C[c] (cid:9)
`C[c] (cid:9)
`0;
`
`Vu, weight of
`
`Partition V into n non-empty subsets
`each containing vertices belonging to the
`same cluster Ci;
`for i = 1 to n do
`begin
`
`end cluster;
`
`algorithm_planarize: This algorithm planarizes a system
`interconnectivity graph G.
`Sort the edges of graph G by decreasing weight, let E be
`the sorted list of edges;
`
`algorithm planarize(E);
`begin L +—
`while there is an edge e in E do
`begin
`
`Delete e from E and add to L;
`Let G' be the incremental graph composed
`of edges in L;
`for each biconnected component C of G' do
`if C is non-planar then
`begin
`
`C — e;
`C" (cid:9)
`Let a and b be the vertices
`incident with e;
`if C" can be separated into
`biconnected components then
`begin
`
`Let the biconnected com-
`ponents containing a and
`b be C2, and C2b and
`the articulation point be
`x;
`
`if (cid:9)
`begin
`
`end
`else
`
`— V, (cid:9)
`
`then
`
`c (cid:9)
`c+1, C[c] 4— V,.;
`weight of C[c] (cid:9)
`weight of
`C1 + weight of net represented
`by h;
`Connect clusters C[c] and
`by an edge of weight = weight
`of C,.;
`Let the mitotic child of .17; be
`C[c];
`
`end
`
`end
`end planarize;
`
`crossing_edges C2a ,a,x);
`crossing_edges C2 6
`,x);
`
`end
`else crossing_edges( C", a ,b);
`Introduce new vertices on the
`edges returned by the calls to
`crossing_edges and embed the
`augmented component C with
`edge crossings at these vertices;
`
`let the mitotic child of V; be vi
`(i.e., no division);
`
`end
`if n = 1 then
`weight of C1 4-- weight of Cl +
`weight of net represented by h;
`else if n = 2 then
`connect the mitotic children of V1
`and V2 by an edge of weight =
`weight of net represented by h;
`else if n > 2 then
`begin
`
`Create an empty vertex v (this
`represents a feeder node to connect 3
`or more clusters in a star topology);
`c+1, C[c] +— v;
`c (cid:9)
`Connect C[c] to the mitotic children
`of 17s., i = 1, . . . , n by edges of
`weight = weight of net represented
`by h;
`
`end
`
`end
`Represent each cluster by a vertex and each con-
`nection between clusters by an edge in G;
`Output G;
`
`procedure_crossing_edges:
`This procedure identifies a subset of edges of a
`biconnected component C, with which an edge
`between two vertices a and b in C can intersect at
`minimum cost such that the resulting graph is
`planar.
`procedure crossing_edges(C,a,b);
`begin
`
`Replace all triconnected components C3; of C
`except those that contain a and b by a virtual
`edge, whose endpoints are the separation pair
`(p;,q;) of the component and weight is the
`minimum cut in C3; from pi to gi;
`Replace parallel edges by a single edge whose
`weight is their sum and edges incident at vertices
`of degree 2 by a single edge whose weight is the
`minimum of the two. Do this recursively until
`the resulting graph C' is triconnected;
`Identify the set of edges of minimum cost that
`need to be intersected in a plane embedding of
`C'. If any of these edges are virtual edges, recur-
`sively identify the original edges of C that were
`combined to form it;
`Output the set of edges identified;
`end crossing_edges;
`
`Paper 8.3
`121
`
`XILINX, EX. 1010
`Page 8 of 8