Method and apparatus for considering diagonal wiring in placement

Description of equivalent WO 0247165 A2

METHOD AND APPARATUS FOR CONSIDERING DIAGONAL WIRING IN PLACEMENT

FIELD OF THE INVENTION

0003The invention is directed towards method and apparatus for considering

0004diagonal wiring in placement.

BACKGROUND OF THE INVENTION

0006An integrated circuit ("IC") is a device that includes many electronic

0007components (e.g., transistors, resistors, diodes, etc.). These components are often

0008interconnected to form multiple circuit components (e.g., gates, cells, memory units,

0009arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit

0010components of IC's are jointly referred to below as "components."

0011An IC also includes multiple layers of wiring ("wiring layers") that interconnect

0012its electronic and circuit components. For instance, many IC's are currently fabricated with metal or polysilicon wiring layers (collectively referred to below as "metal layers")

0013that interconnect its electronic and circuit components. One common fabrication

0014model uses five metal layers. In theory, the wiring on the metal layers can be all-angle

0015wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is

0016commonly referred to as Euclidean wiring. In practice, however, each metal layer

0017typically has a preferred wiring direction, and the preferred direction alternates

0018between successive metal layers. Many IC's use the Manhattan wiring model, which

0019specifies alternating layers of preferred-direction horizontal and vertical wiring. In this

0020wiring model, the majority of the wires can only make 90° turns. However, occasional

0021diagonal jogs are sometimes allowed on the preferred horizontal and vertical layers.

00221 Atty.DocketNo.:SPLX.P0125 Design engineers design IC's by transforming circuit description of the IC's into

0023geometric descriptions, called layouts. To create layouts, design engineers typically

0024use electronic design automation ("EDA") applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.

0025EDA applications create layouts by using geometric shapes that represent

0026different materials and devices on IC's. For instance, EDA tools commonly use

0027rectangular lines to represent the wire segments that interconnect the IC components.

0028These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. For the sake of simplifying the discussion, these

0029geometric objects are shown as rectangular blocks in this document.

0030Also, in this document, the phrase "circuit module" refers to the geometric representation of an electronic or circuit IC component by an EDA application. EDA

0031applications typically illustrate circuit modules with pins on their sides. These pins connect to the interconnect lines.

0032A net is typically defined as a collection of pins that need to be electrically connected. A list of all or some of the nets in a layout is referred to as a net list. In

0033other words, a net list specifies a group of nets, which, in turn, specify the

0034interconnections between a set of pins.

0035Figure 1 illustrates an example of an IC layout 100. This layout includes five

0036circuit modules 105, 110, 115, 120, and 125 with pins 130-160. Four interconnect

0037lines 165-180 connect these modules through their pins. In addition, three nets specify

0038the interconnection between the pins. Specifically, pins 135, 145, and 160 define a

00392 Atty.Docket No.:SPLX.P0125 three-pin net, while pins 130 and 155, and pins 140 and 150 respectively define two two-pin nets. As shown in Figure 1, a circuit module (such as 105) can have multiple pins on multiple nets.

0040The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit modules; (4) routing, which completes the interconnects between the circuit modules; (5) compaction, which compresses the layout to decrease the total IC area; and (6) verification, which checks the layout to ensure that it meets design and functional requirements.

0041Placement is a key operation in the physical design cycle. It is the process of arranging the circuit modules on a layout, in order to achieve certain objectives, such as reducing layout area, wirelength, wire congestion, etc. A poor placement configuration not only can consume a large area, but it also can make routing difficult

0042and result in poor performance.

0043Numerous EDA placers have been proposed to date. Certain placers are constrained-optimization placers, which (1) use cost-calculating functions to generate placement scores (i.e., placement costs) that quantify the quality of placement configurations, and (2) use optimization algorithms to modify iteratively the placement configurations to improve the placement scores generated by the cost-calculating

0044functions.

00453 Atty.Docket No.:SPLX.P0125 A constrained-optimization placer typically receives (1) a list of circuit modules, (2) an initial placement configuration for these modules, and (3) a net list that specifies the interconnections between the modules. The initial placement configuration can be random (i.e., all the modules can be positioned randomly). Alternatively, the initial configuration can be partially or completely specified by a previous physical-design operation, such as the floor planning.

0046A constrained-optimization placer then uses a cost-calculating function to measure the quality of the initial placement configuration. The cost function generates a metric score that is indicative of the placement quality. Different cost-calculating functions measure different placement metrics. For mstance, as further described below, some functions measure wirelength (e.g., measure each net's minimum spanning tree, Steiner tree, or bounding-box perimeter, etc.), while others measure congestion (e.g., measure number of nets intersected by cut lines).

0047After calculating the metric cost of the initial placement configuration, a

0048constrained-optimization placer uses an optimization algorithm to modify iteratively the placement configuration to improve the placement score generated by its cost- calculating function. Different optimization techniques modify the placement configuration differently. For instance, at each iteration, some techniques move one circuit module, others swap two modules, and yet others move a number of related modules. Also, at each iteration, some optimization techniques (e.g., KLFM and tabu search algorithms) search for the best move, while others (e.g., simulated annealing and local optimization) select random moves. In addition, some techniques (e.g.,

0049Atty.Docket No.:SPLX.P0125 simulated annealing) accept moves that make the metric score worse, whereas others (e.g., local optimization) do not.

0050Four types of constrained-optimization placement techniques are described

0051below.

0052A. Min-Cut Bipartitioning.

0053Some placers use min-cut bipartitioning. This technique uses horizontal and vertical cut lines to partition the IC layout recursively into successive pairs of regions. At each level of the recursion, this technique then moves the circuit modules between the regions at that level, in order to reduce the number of nets intersected by the cut line for that level. By minimizing the net-cut cost at each level of the recursion, these techniques reduce the wire congestion across the cut lines.

0054Figures 2 and 3 illustrate one example of min-cut bipartitioning. Figure 2 illustrates an IC layout 200 that is partitioned initially in two regions 210 and 215 by a vertical cut line 205. After defining this initial cut line, the min-cut bipartitioning method calculates the number of nets that are intersected by this cut line. This number is indicative of the wire congestion about this cut line. An optimization algorithm (such as KLFM) is then used to modify the initial placement iteratively (i.e., to move the circuit modules iteratively), in order to minimize the net-cut cost across the initial cut line 205.

0055Once the congestion across the initial cut line is minimized, the min-cut bipartitioning method is applied recursively to the two regions created by the initial cut line, and then it is applied to the resulting regions created by the succeeding cut lines,

00565 Atty.Docket No.:SPLX.P0125 and so on. Figure 3 illustrates the IC layout 200 after it has been recursively partitioned by seven cut lines 205 and 220-245.

0057B. Semi-Perimeter Method.

0058The semi-perimeter method is another cost-calculating function used by some constrained-optimization techniques. This method quickly generates an estimate of the wirelength cost of a placement. For each net, this method typically (1) finds the smallest bounding-box rectangle that encloses all the net's pins, and (2) computes half the perimeter of this bounding rectangle.

0059Figure 4 illustrates a bounding box 400 for a net that contains pins 135, 145, and 160 of Figure 1. The computed semi-perimeter value of this box 400 equals the sum of its width 405 and height 410. This computed semi-perimeter value provides a lower bound estimate on the amount of wire required to route a net.

0060The semi-perimeter method sums the semi-perimeter values of all the bounding rectangles of all the nets to obtain an estimated wirelength cost for a placement configuration. An optimization technique can then be used to modify iteratively the placement configuration to reduce this wirelength cost estimate, and thereby obtain an acceptable placement configuration.

0061C. Minimum Spanning Tree.

0062To estimate the wirelength cost of placement configurations, some constrained- optimization placement techniques compute and add the length of the rectilinear minimum spanning tree ("RMST") for each net. A net's RMST is typically defined as a

00636 Atty.Docket No.:SPLX.P0125 tree that connects (i.e., spans) the net's pins through the shortest Manhattan wiring

0064route that only branches at the pin locations.

0065More specifically, the RMST for an N-pin net includes (1) N nodes (also called

0066points or vertices) corresponding to the N pins, and (2) N-l edges that connect its N

0067nodes. In addition, the edges of the RMST are either horizontal or vertical, and these

0068edges start and end at one of the N nodes of the tree. Figure 5 illustrates a RMST

0069505 for the net that contains pins 135, 145, and 160 of Figure 1.

0070The sum of the length of the RMST for each net provides an estimate of the

0071wirelength cost of a placement. An optimization algorithm can then be used to modify

0072iteratively the placement configuration to minimize this wirelength cost.

0073D. Steiner Tree.

0074Rectilinear Steiner trees are another type of tree structure that constrained-

0075optimization placement techniques generate to estimate the wirelength cost of

0076placement configurations. Rectilinear Steiner trees are similar to RMST's except that Steiner trees do not restrict branching to only pin locations. In rectilinear Steiner trees,

0077a horizontal or vertical edge can branch from a point on an edge that connects two

0078other net pins.

0079To construct a Steiner tree for an N-pin net, additional points, called Steiner

0080points, are typically added to the net. If R Steiner points are added to the net, the

0081rectilinear Steiner tree for the N-pin net is the RMST on the N +R points. Figure 6

0082illustrates a Steiner tree 605 for the net that contains pins 135, 145, and 160 of

0083Figure 1. In this example, the Steiner point that has been added is point 610.

00847 Atty.Docket No.:SPLX.P0125 Heuristic techniques are often used to select the R Steiner points and construct

0085the Steiner tree, since these problems cannot be solved in polynomial time. A heuristic

0086technique is a clever algorithm that only searches inside a subspace of the total search space for a good rather than the best solution that satisfies all design constraints.

0087Hence, to get an estimate of the wirelength cost of a placement, some

0088constrained-optimization placement techniques use heuristic approximations to identify

0089rectilinear Steiner trees for the nets. The sum of the length of the heuristic Steiner trees

0090for all the nets provides an estimate of the wirelength cost of a placement. An

0091optimization algorithm can then be used to modify iteratively the placement

0092configuration to minimize this wirelength cost.

0093E. Recursive Grid Partitioning.

0094Recursive grid partitioning is another technique for calculating the wirelength

0095cost of placement configurations. A recursive-grid-partitioning placer typically uses

0096sets of crossing horizontal and vertical lines to divide an IC layout recursively into

0097several sub-regions. At each recursion level, the placer then uses an optimization

0098algorithm to move the circuit modules between the sub-regions defined at that,

0099recursion level, in order to reduce the wirelength cost. After minimizing the wirelength

0100cost at a particular recursion level, the placer recursively partitions that level's sub-

0101regions that meet certain criteria, in order to optimize further the wirelength cost

0102within those partitioned sub-regions.

0103For examples, once recursive partitioning technique recursively divides an IC

0104layout into quadrisections (i.e., into four regions). Under this approach, minimum

01058 Atfy.Docket No.:SPLX.P0125 spanning trees are typically used to estimate the wirelength cost for connecting modules in different quadrisections. Another recursive partitioning technique

0106recursively divides an IC layout into nine regions. This style of partitioning is

0107sometimes referred to as "sharp" partitioning. For this type of partitioning, Steiner

0108trees are typically used to estimate the wirelength cost for connecting modules in

0109different regions.

0110The above-described placement techniques do not consider diagonal wiring in

0111calculating their placement-configuration cost. Hence, when diagonal routes are

0112selected for the interconnect lines, these techniques result in poor placement configurations, which inefficiently consume the layout area, utilize too much wire,

0113and/or have poor wire congestions. Consequently, there is a need in the art for placers

0114that consider diagonal wiring in calculating their placement-configuration costs.

0115Atty.Docket No.:SPLX.P0125 SUMMARY OF THE INVENTION

0116The invention is directed towards method and apparatus that consider diagonal

0117wiring in placement. Some embodiments of the invention are placers that use diagonal

0118lines in calculating the costs of potential placement configurations. For instance, some

0119embodiments estimate the wirelength cost of a placement configuration by (1) identifying, for each net in a net list, a bounding box that encloses all the circuit

0120elements of the net, (2) computing an attribute of each bounding box by using a line

0121that can be completely or partially diagonal, and (3) computing the wirelength cost estimate based on the computed attributes.

0122To estimate the wirelength cost of different placement configurations, other

0123embodiments construct connection graphs that model the net interconnect topologies. These connection graphs can have edges that are completely or partially diagonal.

0124These embodiments might also compute other attributes of the connection graphs.

0125Yet other embodiments partition the circuit region at issue into a several sub-

0126regions. For a net in the circuit region, these embodiments identify the set of sub-

0127regions that contain the net's set of circuit elements, and then identify an attribute (e.g.,

0128wirelength) of a connection graph that traverses the identified set of sub-regions. The identified connection graph has at least one completely or partially diagonal edge.

0129These embodiments then use the identified attribute to compute a placement metric.

0130For a placement configuration, some embodiments compute a delay cost that

0131accounts for potential diagonal wiring. For instance, some embodiments compute such

0132a delay cost for a net from a wirelength placement cost for the net.

013310 Atty.Docket No.:SPLX.P0125 Other embodiments use diagonal lines to measure congestion costs of potential placement configurations. For instance, some placers use diagonal lines as cut lines that divide the IC layout into regions. These placers then generate congestion-cost estimates by measuring the number of nets cut by the diagonal cut lines.

013411 Atty.Docket No.:SPLX.P0125 BRIEF DESCRIPTION OF THE DRAWINGS

0135The novel features of the invention are set forth in the appended claims.

0136However, for purpose of explanation, several embodiments of the invention are set

0137forth in the following figures.

0138Figure 1 illustrates an example of an IC layout.

0139Figure 2 illustrates an IC layout that is partitioned initially in two regions by a vertical cut line.

0140Figure 3 illustrates the IC layout of Figure 2 after it has been recursively partitioned by seven cut lines.

0141Figure 4 illustrates a bounding box for a net that contains pins 135, 145, and

0142160 of Figure 1.

0143Figure 5 illustrates a RMST for the net that contains pins 135, 145, and 160 of

0144Figure 1.

0145Figure 6 illustrates a Steiner tree for the net that contains pins 135, 145, and

0146160 of Figure 1.

0147Figure 7 illustrates the wiring architecture of an IC layout that not only uses

0148diagonal lines, but also uses horizontal and vertical lines.

0149Figure 8 illustrates one manner of implementing the wiring architecture

0150illustrated in Figure 7.

015112 Atty.Docket No.:SPLX.P0125 Figure 9 provides an example of a bounding-box for the net represented by

0152pins 135, 145, and 160 of Figure 1.

0153Figure 10 illustrates a process for generating a wirelength estimate according to a bounding-box method of the invention.

0154Figure 11 presents a minimum spanning tree with diagonal edges.

0155Figure 12 illustrates a process for generating a wirelength estimate by

0156constructing MST's that include horizontal, vertical, and 45° edges.

0157Figure 13 illustrates a heuristically constructed Steiner tree with 45° edges for

0158the net represented by pins 135, 145, and 160 of Figure 1.

0159Figure 14 illustrates a process for generating a wirelength estimate by

0160constructing Steiner trees with 45° diagonal edges.

0161Figure 15 illustrates an IC layout that has been recursively partitioned into a

0162number of regions by only diagonal cut lines.

0163Figures 16 and 17 illustrate two IC layouts that are recursively partitioned by combinations of diagonal, horizontal, and vertical cut lines.

0164Figure 18 is a process that defines a cut line that partitions a layout region into

0165two smaller regions.

0166Figure 19 illustrates a process that generates a congestion cost estimate, and

0167partitions a set of nets, about a cut line.

016813 Atty.DocketNo.:SPLX.P0125 Figures 20, 21, and 22 illustrate three processes for identifying a region for a pin.

0169Figure 23 illustrates a process that generates a length estimate for a

0170partitioning placement approach.

0171Figure 24 illustrates an IC layout that has been divided into sixteen sub-regions

0172by sets of three horizontal and vertical partitioning lines.

0173Figures 25-27 illustrate three Steiner trees for a net illustrated in Figure 24.

0174Figure 28 illustrates a process that constructs Steiner trees for each possible net configuration with respect to a partitioning grid, and stores the length of each

0175constructed Steiner tree in a look-up table ("LUT").

0176Figure 29 pictorially illustrates sixteen Steiner-tree nodes for sixteen slots

0177created by a 4-by-4 partitioning grid.

0178Figure 30 illustrates a process for identifying potential Steiner nodes.

0179Figure 31 illustrates a process that the process of Figure 28 uses to construct

0180minimum spanning trees.

0181Figure 32 illustrates a process that computes delay costs.

0182Figure 33 illustrates one example of a local optimization process.

0183Figure 34 illustrates one example of a simulated annealing process.

0184Figure 35 illustrates one example of a KLFM process.

018514 Atty.DocketNo.:SPLX.P0125 Figure 36 illustrates a computer system used by some embodiments of the

0186invention.

018715 Atty.Docket No.:SPLX.P0125 DETAILED DESCRIPTION OF THE INVENTION

0188The invention is directed towards method and apparatus for considering

0189diagonal wiring in placement, hi the following description, numerous details are set

0190forth for purpose of explanation. However, one of ordinary skill in the art will realize that the invention may be practiced without the use of these specific details. In other

0191instances, well-known structures and devices are shown in block diagram form in order

0192not to obscure the description of the invention with unnecessary detail.

0193Some embodiments of the invention are placers that consider diagonal lines in calculating the costs of potential placement configurations. For instance, some embodiments estimate the wirelength cost of placement configurations by

0194(1) identifying, for each net, a bounding box that encloses all the circuit elements (i.e.,

0195pins or circuit modules) of the net, (2) computing an attribute of each bounding box by

0196using a line that can be completely or partially diagonal, and (3) generating a placement

0197cost based on the computed attributes. Section II below discusses several embodiments that use such a bounding-box method.

0198Other embodiments model potential interconnect topologies to estimate the

0199wirelength cost of different placement configurations. These embodiments construct

0200connection graphs that can have edges that are completely or partially diagonal.

0201Examples of such connection graphs include minimum spanning trees and Steiner trees.

0202Section III presents several such embodiments.

0203Other embodiments use diagonal lines as cut lines that divide the IC layout into

0204regions. These embodiments then generate congestion-cost estimates by measuring the

020516 Atty.Docket No.:SPLX.P0125 number of nets cut by the diagonal cut lines. Section IN discusses several such

0206embodiments that use min-cut bipartitioning with diagonal cut lines.

0207Other embodiments use partitioning lines to divide the IC regions into sub-

0208regions and then measure wirelength costs based on the configuration of the nets with

0209respect to the sub-regions. Section N discusses several such embodiments. Also,

0210some embodiments calculate placement delay costs that account for potential diagonal

0211wiring during routing. Section NI discusses several such embodiments.

0212Before discussing the embodiments presented in Sections II-NI, several

0213diagonal-wiring architectures that can be used in conjunction with the invention's cost-

0214calculating methods are described in Section I. Also, Section Nil presents several

0215optimization techniques that can be used for optimizing the costs calculated by the

0216cost-calculating methods described in Sections II-NI. Section NIII then illustrates a computer system used in some embodiments of the invention. Finally, Section IX

0217describes the advantages of considering diagonal wiring during placement.

I. DIAGONAL WIRING ARCHITECTURE

0219Some embodiments of the invention calculate the cost of placement configurations for IC layouts that have diagonal interconnect lines (i.e., diagonal

0220wiring). In some of these embodiments, the IC layouts not only have diagonal

0221interconnect lines, but also have horizontal and vertical interconnect lines.

0222As used in this document, an interconnect line is "diagonal" if it forms an angle

0223other than zero or ninety degrees with respect to one of the sides of the layout

022417 Atty.Docket No.:SPLX.P0125 boundary. On the other hand, an interconnect line is "horizontal" or "vertical" if it

0225forms an angle of 0° or 90° with respect to one of the sides of the layout.

0226Figure 7 illustrates the wiring architecture (i.e., the interconnect-line

0227architecture) of an IC layout 700 that utilizes horizontal, vertical, and 45° diagonal

0228interconnect lines. In this document, this architecture is referred to as the octagonal

0229wiring model, in order to convey that an interconnect line can traverse in eight separate

0230directions from any given point.

0231The horizontal lines 705 are the lines that are parallel (i.e., are at 0°) to the x-

0232axis, which is defined to be parallel to the width 710 of the layout. The vertical lines 715 are parallel to the y-axis, which is defined to be parallel to the height 720 of the

0233layout. In other words, the vertical interconnect lines 715 are perpendicular (i.e., are

0234at 90°) to the width of the IC layout. In this architecture, one set 725 of diagonal lines

0235are at +45° with respect to the width of the IC layout, while another set 730 are at -

023645° with respect to the width of the IC layout.

0237Figure 8 illustrates one manner of implementing the wiring architecture

0238illustrated in Figure 7 on an IC. Specifically, Figure 8 illustrates five metal layers for

0239an IC. The first three layers 805-815 are Manhattan layers. In other words, the

0240preferred direction for the wiring in these layers is either the horizontal direction or the

0241vertical direction. The preferred wiring direction in the first three layers typically

0242alternates so that no two consecutive layers have the same direction wiring. However,

0243in some cases, the wiring in consecutive layers is in the same direction.

024418 Atty.Docket No.:SPLXP0125 The next two layers 820 and 825 are diagonal layers. The preferred direction

0245for the wiring in the diagonal layers is ±45°. Also, as in the first three layers, the

0246wiring directions in the fourth and fifth layer are typically orthogonal (i.e., one layer is

0247+45° and the other is -45°), although they do not have to be.

0248Even though some embodiments of the invention are described below to work

0249with IC layouts that utilize the above-described octagonal wiring model, one of

0250ordinary skill will understand that the invention can be used with any wiring model.

0251For instance, the invention can be used with wiring architectures that are strictly

0252diagonal (i.e., that do not have horizontal and vertical preferred direction wiring).

0253Also, some embodiments are used with non-45 ° diagonal wiring. For example,

0254some embodiments are used with IC layouts that have horizontal, vertical, and ±120°

0255diagonal interconnect lines.

II. BOUNDING-BOX METHOD

0257For IC layouts that utilize horizontal, vertical, and diagonal interconnect lines,

0258some embodiments of the invention compute a wirelength-cost estimate for each net in

0259a net list, by (1) identifying a bounding box that encloses all the circuit elements of the net, and (2) computing an attribute of the bounding box by using a line that is at least

0260partially diagonal. These embodiments then generate a wirelength-cost estimate based

0261on the computed attributes of all the nets in the net list. For instance, some

0262embodiments sum the computed attributes to obtain the wirelength-cost estimate for a

0263placement configuration.

026419 Atty.Docket No.:SPLX.P0125 In some embodiments, the computed attribute of a net's bounding box is the minimum distance between opposing comers of the bounding box. Figures 9 and 10 illustrate one such embodiment of the invention. Figures 9 presents an example of a bounding-box 905 for the net represented by pins 135, 145, and 160 of Figure 1. Line 910 traverses the shortest distance between two opposing comers 935 and 940 of the box 905. As shown in Figure 9, this line is partially diagonal. Specifically, in this example, one segment 920 of this line is diagonal, while another segment 915 is horizontal.

0265Equation (A) below provides the minimum distance between the two opposing comers 935 and 940 of the bounding box 905.

0266Distance = [L - {S (cos A / sin A)}] + S/sin A (A)

0267In this equation, "L" is the box's long side, which in this example is the box's width 925, while "S" is the box's short side, which in this example is its height 930. Also, in this equation, "A" is the angle that the diagonal segment 915 makes with respect to the long side of the bounding box.

0268In some embodiments, this angle A corresponds to the direction of some of the diagonal interconnect lines in the IC layout. For instance, in some embodiments, the

0269angle A equals 45° when the IC layout uses the octagonal wiring model. In this

0270manner, the diagonal cut 920 across the bounding box represents a diagonal interconnect line that forms the connection between two opposing comers of the bounding box.

027120 Atty.Docket No.:SPLX.P0125 Equations (B)-(D) illustrate how Equation (A) was derived. The length of the line 910 equals the sum of the lengths of its two segments 915 and 920. Equation (B)

0272provides the length of the horizontal segment 915, while Equation (C) provides the

0273length of the diagonal segment 920.

0274Length of 915 = L - (Length of 920) * (cos A) (B)

0275Length of 920 = S/sin A (C)

0276Equations (B) and (C) can be combined to obtain Equation (D) below, which when simplified provides Equation (A) above.

0277Distance = Length of 915 + Length of 920

0278= L - S/sin A * (cos A) + S/sin A (D)

0279When the angle A equals 45°, Equation (A) simplifies to Equation (E) below.

0280Distance = L + S * (sqrt(2) - 1) (E)

0281If the bounding box has no width or height, then the bounding box is just a line,

0282and the minimum distance between the opposing comers of this line is provided by the

0283long (and only) side of the bounding box, which will be a horizontal or vertical line.

0284Alternatively, when the bounding box is a square and the angle A is 45°, a line that is

0285completely diagonal specifies the shortest distance between the box's two opposing

0286comers.

0287When the angle A corresponds to the direction of some of the diagonal

0288interconnect lines in the IC layout, the minimum distance computed by Equation (A)

028921 Atty.Docket No.:SPLX.P0125 corresponds to the shortest length of wiring required to connect two hypothetical net

0290circuit-elements located at opposing comers of the bounding box. In these situations, the distance computed by Equation (A) might not be indicative of the wirelength

0291needed for nets with three or more circuit elements. Moreover, this distance might be

0292shorter than the actual wiring path necessary for even a two-element net, as it may not

0293be possible to route the net along line 910. The distance value computed by Equation

0294(A) simply provides a lower-bound estimate on the amount of wire required to route a

0295net in a wiring architecture that utilizes horizontal, vertical, and diagonal wiring. Some embodiments also use this equation for other arbitrary wiring models. However, some

0296of these embodiments select the angle A among several choices so that the distance

0297quantified by this equation is minimized.

0298Figure 10 illustrates a cost-calculating process 1000 that uses the above- described bounding box method. A placer can use this cost-calculating process to generate a wirelength cost estimate for a set of nets on a net list. In some

0299embodiments, the process 1000 starts whenever it receives a net list that specifies a

0300number of nets.

0301Each received net has several circuit elements associated with it (i.e., each net

0302is defined to include several circuit elements), other words, the nets on the net list specify the interconnection between some or all the circuit elements in the IC layout.

0303In the embodiments described below, the circuit elements associated with the nets are

0304the pins of the circuit modules in the IC layout. Other embodiments, however, treat

0305the circuit modules as the circuit elements of the nets. Some of these embodiments

0306treat the circuit modules as the net circuit elements and obviate the need to distinguish

030722 Atty.Docket No.:SPLX.P0125 between the different pin locations, by assuming that the pins of each module are all located at uniform locations (e.g., located at the origin of the modules).

0308In some embodiments, the positions of the net circuit elements before the

0309process 1000 starts define an initial placement configuration. In some of these

0310embodiments, the initial circuit-element positions are random. In other embodiments, a previous physical-design operation, such as the floor planning, partially or completely

0311specifies the initial positions of these elements. Other embodiments use another placer to specify the initial positions of the circuit elements, and then use process 1000 to

0312optimize the placement configuration for a wiring architecture that uses diagonal wiring.

0313The process 1000 initially (at 1005) sets the wirelength cost estimate

0314(WL_Cost) to zero, and selects a first net from the received net list. Each net has a set

0315N of pins. At 1005, the process also defines a set P of pins equal to the set N of pins

0316of the selected net. At 1010, the process selects a pin from the defined set P of pins, and removes this selected pin from the set P. The process then uses (at 1015) the x- and y-coordinates of the selected pin to initialize the maximum and minimum x- and y-

0317coordinates of a bounding box for the current net.

0318Next, the process selects (at 1020) another pin from the set P of pins for the

0319current net. At 1025, the process examines the x- and y-coordinates of the pin

0320selected at 1020 (i.e., the current pin) to determine whether it needs to modify the

0321maximum and minimum x- and y-coordinates of the bounding box for the current net.

0322Specifically, if the maximum x-coordinate (X_MAX) of the bounding box is less than the

0323x- coordinate of the current pin, the process sets the maximum x-coordinate (X_MAX) of

032423 Atty.DocketNo.:SPLX.P0125 the bounding box equal to the x-coordinate of the current pin. Alternately, if the

0325minimum x-coordinate (X_MIN) of the bounding box is greater than the x-coordinate of

0326the current pin, the process sets the minimum x-coordinate (X_MIN) of the boundmg box

0327equal to the x-coordinate of the current pin. Similarly, if the minimum y-coordinate

0328(Y_MIN) of the bounding box is greater than the y-coordinate of the current pin, the process sets the minimum y-coordinate (Y_MIN) of the bounding box equal to the y-

0329coordinate of the current pin. On the other hand, if the maximum y-coordinate (Y_MAX)

0330of the bounding box is less than the y-coordinate of the current pin, the process sets

0331the maximum y-coordinate (Y_MAX) of the bounding box equal to the y-coordinate of the current pin.

0332After 1025, the process determines (at 1030) whether there are any pins in set

0333P (i.e., whether there are any pins in the current net that it has not yet examined). If

0334so, the process transitions back to select (at 1020) another pin, and to determine (at 1025) whether it needs to use the selected pin's coordinates to modify the x- and y-

0335coordinates of the boundmg box. If the process determines (at 1030) that it has

0336examined all the pins of the current net, the process defines (at 1035) the four

0337coordinates of the current net's bounding box as (XMIN, YMIN), (XMIN, YMAX), (XMAX,

0338YMIN), and (XMAX, YMAX).

0339Next, the process determines (at 1040) the bounding-box's width and height.

0340The process determines (1) the width by taken the difference between the maximum

0341and minimirai x-coordinates of the bounding box, and (2) the height by taking the

0342difference between the maximum and minimum y-coordinates of the bounding box.

0343The process then determines (at 1045) whether the computed width is greater than the

034424 Atty.Docket No.:SPLX.P0125 computed height. If so, the process defines (1050) the width as the long side and the height as the short side. Otherwise, the process defines (at 1055) the width as the

0345short side and the height as the long side.

0346The process then computes (at 1060) a wirelength cost estimate

0347(Net_WL_Cost) for the current net, by computing the distance between two opposing

0348comers of the bounding box by using the above-described Equation (A). The process

0349next (at 1065) (1) adds the computed net wirelength cost (Net_WL_Cost) to the total

0350wirelength cost (WL_Cost), and (2) stores the net wirelength cost (Net_WL_Cost).

0351At 1070, the process determines whether it has examined all the nets in the net list. If

0352not, at 1075, it selects another net from the net list, and defines a set P of pins equal to the set N of pin of this selected net. The process then transitions back to 1010 to

0353compute the bounding-box cost for this selected net.

0354When the process has calculated the bounding-box cost for all the nets, the

0355process determines (at 1070) that it has examined all the nets in the net list. At this

0356point, the process returns the value of the wirelength cost variable (WL_Cost) as the estimated wirelength cost for the received net list, and then ends.

0357In some embodiments of the invention, the process 1000 generates a wirelength

0358cost estimate (WL_Cost) for an initial placement configuration, when it receives a net

0359list that specifies the initial placement configuration (i.e., a net list that identifies all the

0360nets in the IC layout before any modifications to the positions of the modules in the

0361layout).

036225 Atty.DocketNo.:SPLX.P0125 After obtaining the wirelength cost of the initial placement configuration, some

0363embodiments use an optimization process that iteratively modifies the placement configuration to improve the placement-configuration cost. In some embodiments, the

0364optimization process uses the process 1000 to calculate the placement-configuration cost for each possible iterative modification to the placement configuration. This is

0365further described below in Section Nn, which presents several suitable optimization

0366techniques.

III. CONNECTION GRAPHS WITH POTENTIAL DIAGONAL LINES

0368Some embodiments of the invention construct connection graphs that model

0369potential intercoimect (i.e., wiring) topologies, in order to estimate the wirelength cost

0370of different placement configurations. Generally, a connection graph for a net models

0371(1) each net element (i.e., pin or module) as a node (also called a vertex or point), and

0372(2) each potential interconnect line that connects two net elements as an edge (also

0373called a line).

0374The connection graphs of the invention can include edges that are completely

0375or partially diagonal. Such connection graphs include minimum spanning trees ("MST") and Steiner trees, which are described below. One of ordinary skill will

0376understand that other embodiments of the invention use other connection graphs (such

0377as complete graphs, minimum chain graphs, source-to-sink graphs, etc.) to model the

0378potential interconnect topologies.

037926 Atty.Docket No.:SPLX.P0125 A. Minimum Spanning Trees.

0380Some embodiments generate wirelength cost estimate for placement configurations by (1) constructing, for each net, a MST that can have diagonal edges,

0381(2) computing the length of each MST, and (3) summing the computed lengths. A

0382minimum spanning tree for a net is a tree that connects (i.e., spans) the net's elements

0383through the shortest route that only branches at the elements. The length of a

0384minimum spanning tree provides a lower-bound estimate of the amount of wire needed

0385to interconnect the net's elements (i.e., the net's pins or modules).

0386More specifically, a spanning tree for an N-element net includes (1) N nodes corresponding to the N elements, and (2) N-1 edges that connect its N nodes. The

0387edges of a minimum spanning tree can only start and end at one of the N nodes of the

0388tree. Also, in a MST, the edges are typically selected to provide the shortest achievable route to connect its nodes.

0389In some embodiments of the invention, the edges of the MST's can be

0390horizontal, vertical, or diagonal. The diagonal edges can be completely or partially

0391diagonal. Also, when the IC layouts use diagonal interconnect lines (e.g., ±120°

0392interconnect lines), the diagonal edges of the MST's can be in the same direction (e.g.,

0393can be in ±120° directions) as some of the diagonal interconnect lines in the layout.

0394For instance, when the IC layout uses an octagonal wiring model (i.e., uses

0395horizontal, vertical, and 45° diagonal lines), some embodiments const ct MST's that

0396have horizontal, vertical, and 45° diagonal edges. Figure 11 illustrates an example of

0397such a MST. This tree 1105 is the MST of the net that contains pins 135, 145, and

039827 Atty.Docket No.:SPLX.P0125 160 of Figure 1. This tree has two edges 1110 and 1115, with the first edge 1110

0399having a horizontal segment 1120 and a +45° diagonal segment 1125, while the second

0400edge 1115 has a vertical segment 1130 and a -45° diagonal segment 1135.

0401By treating the two nodes of each MST edge as two opposing comers of a

0402box, the length of each MST edge can be obtained by using the above-described Equation (A).

0403Distance = [L - { S (cos A / sin A)}] + S/sin A (A)

0404As described above, in this equation, "L" is the box's long side, "S" is the box's short side, and "A" is the angle that the diagonal segment of the edge makes with respect to

0405the long side of the bounding box.

0406Figure 12 illustrates a cost-calculating process 1200 that computes the length of MST's that model the interconnect topologies of several nets. A placer can use this

0407process to generate a wirelength cost estimate for a set of nets on a net list. In some

0408embodiments, the process 1200 starts whenever it receives a net list that specifies a

0409number of nets.

0410Each received net has several circuit elements associated with it (i.e., each net

0411is defined to include several circuit elements). In other words, the nets on the net list

0412specify the interconnection between some or all the circuit elements in the IC layout.

0413In the embodiments described below, the circuit elements associated with the nets are the pins of the circuit modules in the IC layout. Other embodiments, however, treat

0414the circuit modules as the circuit elements of the nets. Some of these embodiments

0415treat the circuit modules as the net circuit elements and obviate the need to distinguish

041628 Atty.DocketNo.:SPLX.P0125 between the different pin locations, by assuming that the pins of each module are all

0417located at uniform locations (e.g., located at the origin of the modules).

0418In some embodiments, the positions of the net circuit elements before the

0419process 1200 starts define an initial placement configuration. In some of these

0420embodiments, the initial circuit-element positions are random. In other embodiments, a

0421previous physical-design operation, such as the floor planning, partially or completely

0422specifies the initial positions of these elements. Other embodiments use another placer

0423to specify the initial positions of the circuit elements, and then use process 1200 to

0424optimize the placement configuration for a wiring architecture that uses diagonal wiring.

0425The process 1200 initially (at 1205) sets the wirelength cost estimate

0426(WL_Cost) to zero, and selects a first net from the received net list. Next, the process

0427defines (at 1210) a set P of pins equal to the selected net's set of pins. The process

0428then (at 1215) sets the minimum-spanning-tree cost (MST_Cost) of the selected net to

0429zero.

0430Next, the process (at 1220) (1) selects a pin from the retrieved set of pins as

0431the first node of the spanning tree, and (2) removes this pin from this set. The process

0432then defines (at 1225) a remainder set R of pins equal to the current set P of pins. At

04331230, the process selects a pin from the remaining pin set R, and removes the selected

0434pin from this pin set.

0435The process then computes and stores (at 1235) the distance between the pin

0436selected at 1230 and each current node of the spanning tree. The distance between the

043729 Atty.Docket No.:SPLX.P0125 selected pin and each node can be traversed by an edge that is completely or partially

0438diagonal. Hence, the process uses (at 1235) Equation (A) to compute the minimum distance between the selected pin and each node.

0439The process next determines (at 1240) whether there is any pin remaining in set R. If so, the process returns to 1230 to select another pin from this set, so that it can

0440compute at 1235 the distance between this pin and the current nodes of the spanning

0441tree. Otherwise, the process (at 1245) identifies the smallest distance recorded at 1235, and identifies the pin and node combination that resulted in this distance. The

0442process then adds (at 1250) the identified smallest distance to the minimum-spanning-

0443tree cost (MST_Cost). The process also (at 1255) (1) defines a tree node

0444corresponding to the pin identified at 1245, (2) removes the identified pin from the pin

0445set P, and (3) links the defined tree node to the node identified at 1245.

0446The process then determines (at 1260) whether the pin set P is empty. If not,

0447the process transitions back to 1225 to identify the next pin that is closest to the current nodes of the tree. Otherwise, the process (at 1265) (1) adds the minimum-

0448spanning-tree cost (MST_Cost) of the current net to the wirelength cost (WL_Cost),

0449and (2) stores the current net's mimmmn-spanning-tree cost (MST_Cost). The process then determines (at 1270) whether it has constructed the minimum spanning tree of all

0450the received nets. If not, the process selects (at 1275) another net, and transitions back

0451to 1210 to constmct the minimum spanning tree for this net.

0452Otherwise, if the process deteπnines that it has constructed the MST of all the

0453nets, the process returns the value of the wirelength cost variable (WL_Cost) as the

045430 Atty.DocketNo.:SPLX.P0125 estimated wirelength cost of the current placement configuration. The process then ends.

0455In some embodiments of the invention, the process 1200 generates a wirelength cost estimate (WL_Cost) for an initial placement configuration, when it receives a net list that specifies the initial placement configuration (i.e., a net list that identifies all the nets in the IC layout before any modifications to the positions of the modules in the layout).

0456After obtaining the wirelength cost of the initial placement configuration, some

0457embodiments use an optimization process that iteratively modifies the placement configuration to improve the placement-configuration cost. In some embodiments, the optimization process uses the process 1200 to calculate the placement-configuration cost for each possible iterative modification to the placement configuration. This is further described below in Section Nil, which presents several suitable optimization techniques.

0458B. Steiner Tree with Diagonal Edges.

0459Some embodiments generate wirelength cost estimate for placement configurations by (1) constructing, for each net, a Steiner tree that can have diagonal edges, (2) computing the length of each Steiner tree, and (3) summing the computed lengths. Steiner trees are similar to minimum spanning trees except that Steiner trees do not restrict branching to only the locations of the elements of the nets. In some embodiments, Steiner trees can have edges that branch off (i.e., start or terminate)

0460from points in the middle of other edges.

046131 Atty.Docket Νo.:SPLXP0125 In some embodiments of the invention, the edges of the Steiner tree can be

0462horizontal, vertical, or diagonal. The diagonal edges can be completely or partially

0463diagonal. Also, when the IC layouts use diagonal interconnect lines (e.g., ±120°

0464interconnect lines), the diagonal edges can be in the same direction (e.g., can be in

0465±120° directions) as some of the diagonal intercomiect lines in the layout.

0466To constmct a Steiner tree for an N-element net, additional points, called

0467Steiner points, can be added to the net. Heuristic techniques are often used to select

0468the Steiner points. Figure 13 illustrates one heuristic technique that is used in some

0469embodiments of the invention, for IC layouts that use the octagonal wiring model (i.e.,

0470that use horizontal, vertical, and 45° intercomiect lines). This figure presents a Steiner

0471tree 1305 for the net that contains pins 135, 145, and 160 of Figure 1. In this

0472example, the Steiner tree 1305 includes three original nodes 1335, 1345, and 1360

0473corresponding to the pins 135, 145, and 160.

0474Also, in this example, a set of potential Steiner points are identified by passing four lines through each original node of the Steiner tree. Of these four lines, one 1310

0475is horizontal, one 1315 is vertical, one 1320 is a +45° diagonal line, and one 1325 is a

0476-45° diagonal line. As shown in Figure 13, the intersection of the lines that pass

0477through each original node defines a set of potential Steiner points 1330. A few of

0478these potential points can then be added as nodes in the Steiner tree, in order to

0479minimize the length of the tree. In Figure 13, the Steiner point 1340 has been added

0480as nodes in the tree.

048132 Atty.Docket No.:SPLX.P0125 Figure 14 illustrates a cost-calculating process 1400 that computes the length

0482of Steiner trees that model the interconnect topologies of several nets. A placer can use this process to generate a wirelength cost estimate for a set of nets on a net list. In

0483some embodiments, the process 1400 starts whenever it receives a net list that specifies

0484a number of nets.

0485Each received net has several circuit elements associated with it (i.e., each net

0486is defined to include several circuit elements). In other words, the nets on the net list specify the interconnection between some or all the circuit elements in the IC layout.

0487In the embodiments described below, the circuit elements associated with the nets are

0488the pins of the circuit modules in the IC layout. Other embodiments, however, treat

0489the circuit modules as the circuit elements of the nets. Some of these embodiments treat the circuit modules as the net circuit elements and obviate the need to distinguish between the different pin locations, by assuming that the pins of each module are all

0490located at uniform locations (e.g., located at the origin of the modules).

0491In some embodiments, the positions of the net circuit elements before the

0492process 1400 starts define an initial placement configuration. In some of these

0493embodiments, the initial circuit-element positions are random. In other embodiments, a

0494previous physical-design operation, such as the floor planning, partially or completely specifies the initial positions of these elements. Other embodiments use another placer

0495to specify the initial positions of the circuit elements, and then use process 1400 to

0496optimize the placement configuration for a wiring architecture that uses diagonal wiring.

049733 Atty.DocketNo.:SPLX.P0125 The process 1400 is a modification of the One- Steiner process. Like the traditional One-Steiner process, this process 1400 constmcts a heuristic Steiner tree by

0498adding Steiner nodes that minimize the MST of the original and added pin nodes.

0499However, unlike the traditional One-Steiner process, this modified process allows the

0500edges of the heuristic Steiner tree to be partially or completely diagonal.

0501This process initially (at 1405) sets the wirelength cost estimate (WL_Cost) to

0502zero, and selects a first net from the received net list. Next, the process defines (at

05031410) a set P of pins equal to the selected net's set of pins. The process then (at 1415)

0504sets the wirelength cost (WL_Cost) of the selected net to zero. After 1415, the process constmcts (at 1420) the minimum spanning tree of the selected net, and computes the cost (MST_Cost) of this tree. This minimum spanning tree can have edges that are

0505completely or partially diagonal. The process can constmct the MST by performing

0506the operations 1210 to 1260 of Figure 12.

0507After constructing the MST for the selected net, the process identifies (at

05081425) a set S of candidate Steiner points. As described above by reference to Figure

050913, the process can identify these points by passing a pair of diagonal lines and a pair

0510of Manhattan lines through each pin in the net and identifying the intersection of these

0511lines. When the IC layouts use diagonal interconnect lines (e.g., ±120° interconnect

0512lines), the diagonal lines passed through each pin can be in the same direction (e.g., can

0513be in ±120° directions) as some of the diagonal interconnect lines in the layout.

0514Next, the process defines (at 1430) a remainder set R of nodes equal to the

0515current set S of potential Steiner points. At 1435, the process selects a node from the

0516remaining node set R, and removes the selected node from this set. The process then

051734 Atty.DocketNo.:SPLX.P0125 (at 1440) (1) constmcts a minimum spanning tree (MST^!) for the node selected at 1435

0518and the nodes of the current MST for the selected net, and (2) computes and stores the cost (MST_Cosf) of this mimmum spanning tree (MST'). The process constructs this

0519minimum spanning tree (MST') by using edges that are completely or partially

0520diagonal. Also, the process can constmct this tree MST' by performing the operations

05211210 to 1260 of Figure 12.

0522Next, the process determines (at 1445) whether there is any node remaining in set R. If so, the process returns to 1435 to select another node from this set, so that it

0523can constmct a minimal spanning tree for this other node and the nodes of the current

0524MST.

0525Otherwise, the process (at 1450) identifies the smallest minimum-spanning-tree cost (MST_Cosf) computed at 1440. The process then determines (at 1455) whether

0526the identified smallest minimum-spanning-tree cost (MST_Cosf) is less than the cost

0527(MST_Cost) of the current minimum spanning tree (MST) created at 1420. If not, the

0528process transitions to 1480, which will be described below. Otherwise, from the set S

0529of potential Steiner nodes, the process removes (at 1460) the Steiner node that

0530resulted in the smallest mimmum-spanning-tree cost (MST_Cosf) identified at 1450. The process then identifies (at 1465) the minimum spanning tree (MST') that resulted

0531in the identified smallest minimum-spanning-tree cost (MST_Cosf) as the current

0532minimum spanning tree (MST). The process also sets (at 1470) the minimum- spanning-tree cost (MST_Cost) equal to the identified smallest ntinimum-spanning-tree

0533cost (MST_Cosf).

053435 Atty.DocketNo.:SPLX.P0125 The process next determines (at 1475) whether the set S of candidate Steiner

0535points is empty. If not, the process returns to 1430 to see if it can find another potential Steiner point that would further reduce the length of the current minimum

0536spanning tree (MST).

0537If the process 1400 determines (at 1475) that all the candidate Steiner points have been examined and set S is empty, it (at 1480) (1) defines the Steiner tree as the

0538current MST, (2) adds this MST's cost (MST_Cost) to the estimated wirelength cost

0539(WL_Cost), and (2) stores this MST's cost (MST_Cost) as the cost of the current net.

0540After 1480, the process determines (at 1485) whether it has constructed Steiner trees

0541for all the nets in the received net list. If not, the process selects (at 1490) another net and returns to 1410 to constmct a Steiner tree for this net. Otherwise, the process

0542returns (at 1495) the wirelength cost (WL_Cost) of the current placement

0543configuration, and then ends.

0544In some embodiments of the invention, the process 1400 generates a wirelength cost estimate (WL_Cost) for an initial placement configuration, when it receives a net list that specifies the initial placement configuration (i.e., a net list that identifies all the

0545nets in the IC layout before any modifications to the positions of the modules in the

0546layout).

0547After obtaining the wirelength cost of the initial placement configuration, some

0548embodiments use an optύnization process that iteratively modifies the placement

0549configuration to improve the placement-configuration cost. In some embodiments, the

0550optimization process uses the process 1400 to calculate the placement-configuration

0551cost for each possible iterative modification to the placement configuration. This is

055236 Atty.Docket No.:SPLX.P0125 further described below in Section VII, which presents several suitable optimization

0553techniques.

IV. MIN-CUT BIPARTITONING WITH DIAGONAL LINES

0555Some embodiments of the invention are min-cut bipartitioning techniques that

0556utilize diagonal cut lines. As further described below by reference to Figures 15-17, some embodiments only utilize diagonal cut lines, while other embodiments use

0557diagonal, horizontal, and vertical cut lines.

0558The cut lines are used to partition the IC layout recursively into successive

0559pairs of regions. After defining the cut line at each level of the recursion, the

0560invention's min-cut bipartitioning method calculates the number of nets that are

0561intersected by the cut line of the particular level. This number is indicative of the wire

0562congestion about this cut line. Next, at each recursion level, an optimization technique is used to move the circuit modules between the regions at that level, in order to

0563reduce the number of nets intersected by the cut line of that level. The minimization of

0564the net-cut cost at each level of the recursion reduces wire congestion across the cut

0565line at that level.

0566The invention's min-cut bipartitioning technique can be used with IC layouts

0567that only use the Manhattan wiring model (i.e., IC layouts that only have preferred

0568horizontal and vertical direction wiring). In other instances, the invention's min-cut

0569bipartitioning technique is used with IC layouts that have diagonal interconnect lines.

0570In some of these instances, the diagonal cut lines are in the same direction as some or

0571all of the diagonal interconnect lines. For instance, for IC layouts that use the

057237 Atty.Docket No.;SPLX.P0125 octagonal wiring model (i.e., that use horizontal, vertical, and 45° diagonal lines),

0573some embodiments use 45° diagonal cut lines.

0574Figure 15 illustrates an IC layout 1500 that has been recursively partitioned

0575into a number of regions by only diagonal cut lines. Such a strict diagonal-partitioning approach is typically used when the IC layout uses only diagonal interconnect lines.

0576However, such an approach can be taken when the IC layout uses diagonal and

0577Manhattan interconnect lines.

0578Figures 16 and 17 illustrate two IC layouts that are recursively partitioned by

0579_ combinations of diagonal, horizontal, and vertical cut lines. In Figure 16, diagonal cut

0580lines are used at all levels of the recursion. On the other hand, in Figure 17, the diagonal cut lines are only used at the higher recursion levels, and Manhattan cut lines

0581are used at the lower levels of the recursion.

0582In other words, the partitioning scheme illustrated in Figure 17 stops using

0583diagonal cut lines once it reaches some of the lower levels of the recursion process. Such a partitioning scheme (i.e., a scheme that stops using diagonal cut lines at the

0584lower recursion levels) is useful in connection with IC layouts that have their diagonal

0585layers as their top metal layers. Such a partitioning scheme is useful for such layouts

0586because the first set of cut lines reduce the congestion of longer wires, and the longer

0587wires are likely to be diagonal wires. In octagonal wiring models that have the diagonal layers as the top metal layers, the diagonal wires tend to be long, because

0588otherwise it would be wasteful to incur the delay costs associated with the vias

0589necessary for performing the routing on the higher layers.

059038 Atty.DocketNo.:SPLX.P0125 Figures 18 and 19 illustrate two processes 1800 and 1900 that a placer can use

0591to perform min-cut bipartitioning with diagonal cut lines. The placer can repeatedly

0592use these processes 1800 and 1900 to minimize congestion across the IC layout.

0593Specifically, the placer can repeatedly perform the process 1800 of Figure 18 to define

0594a series of cut lines that recursively partition the IC layout into smaller and smaller

0595regions. After defining the cut line at a particular level of the recursion, the placer can

0596then use the process 1900 of Figure 19 to obtain congestion cost estimates, and to partition nets, across the cut line of that level.

0597The process 1800 starts whenever it receives the coordinates of a region of the

0598IC layout. As shown in Figure 18, this process initially defines (at 1805) a horizontal,

0599vertical, or diagonal cut line that divides the received region into two sub-regions.

0600After defining the cut line, the process 1800 defines (at 1810) two regions created by the cut line. Some embodiments use the following convention to define the regions:

0601(1) when the cut line is horizontal or diagonal, the first region is above the cut line,

0602while the second region is below the cut line, and (2) when the cut line is vertical, the

0603first region is to the right of the cut line, and the second region is to the left of the cut

0604line.

0605Finally, the process 1800 initializes two net lists for the two regions created by

0606the cut line defined at 1805. As further described below, the first time the process

06071900 is performed for all the nets in the received region, the process 1900 adds the

0608nets in this received region and the pins of these net to these two net lists. Also, as

0609further described below, the placer and the process 1900 might remove and add nets

0610and pins to these two net lists during the optimization process.

061139 Atty.DocketNo.:SPLX.P0125 Figure 19 illustrates a process 1900 that a placer can use to partition a set of

0612nets, and to calculate the congestion cost of these nets, about a cut line that can be diagonal. The process 1900 starts whenever it receives (1) a list of nets, and (2) a cut

0613line for partitioning the nets.

0614Each net on the received net list has several circuit elements associated with it

0615(i.e., each net is defined to include several circuit elements). In other words, the nets on the net list specify the interconnection between some or all the circuit elements in

0616the IC layout. In the embodiments described below, the circuit elements associated

0617with the nets are the pins of the circuit modules in the IC layout. Other embodiments,

0618however, treat the circuit modules as the circuit elements of the nets. Some of these embodiments treat the circuit modules as the net circuit elements and obviate the need

0619to distinguish between the different pin locations, by assuming that the pins of each

0620module are all located at uniform locations (e.g., located at the origin of the modules).

0621In some embodiments, an initial placement configuration is defined by the positions of the net circuit elements before the process 1900 is performed for the first

0622cut line. In some of these embodiments, the initial placement configuration is random.

0623In other embodiments, a previous physical-design operation, such as the floor planning, partially or completely specifies the initial placement configuration. Other

0624embodiments use another placer to specify the initial placement configuration, and then use processes 1800 and 1900 to optimize the placement configuration for a wiring

0625architecture that uses diagonal wiring.

0626As shown in Figure 19, the process 1900 initially sets (at 1905) the congestion

0627cost (Cost) equal to 0. The process then selects (at 1910) a net from the received net

062840 Atty.Docket No.:SPLX.P0125 list. It then sets (at 1915) a net-cut variable (C) to 0. The process next selects (at

06291920) a first pin of the selected net. After selecting the pin, the process determines (at

06301925) which of the two regions defined by the cut line contains the pin. The process

06311900 identifies the region for the pin by using one of three processes, which are

0632illustrated in Figures 20, 21, and 22.

0633The process 1900 calls the process 2000 of Figure 20 when the cut line is

0634horizontal. As shown in Figure 20, the process 2000 determines (at 2005) whether the y-coordinate of the pin is greater than the y-coordinate of the horizontal cut line. If

0635so, the process specifies (at 2010) that the pin is in the first region defined by the cut

0636line. Otherwise, the process specifies (at 2015) that the pin is in the second region

0637defined the cut line.

0638The process 1900 uses the process 2100 of Figure 21 when the cut line is

0639vertical. As shown in Figure 21, the process 2100 determines (at 2105) whether the x-coordinate of the pin is greater than the x-coordinate of the vertical cut line. If so,

0640the process specifies (at 2110) that the pin is in the first region defined by the cut line.

0641Otherwise, the process specifies (at 2115) that the pin is in the second region defined

0642the cut line.

0643The process 1900 calls the process 2200 of Figure 22 when the cut line is

0644diagonal. As shown in Figure 22, the process 2200 inserts (at 2205) the x-coordinate

0645of the pin in the linear equation (y = mx + b) that represents the cut line. This equation

0646expresses the y-coordinate value of the cut line in terms of its slope (m), x-coordinate,

0647and y-intersect (b). The process then determines (2210) whether the derived y- value of the diagonal line at the inserted x-location is greater than the y-coordinate of the

064841 Atty.DocketNo.:SPLX.P0125 pin. If not, the process specifies (at 2215) that the pin is in the first region defined by

0649the cut line. Otherwise, the process specifies (at 2220) that the pin is in the second region defined the cut line.

0650After identifying the region for the pin, the process adds (at 1930) the selected net and pin to the net list for the identified region. The process then selects (at 1935)

0651the next pin in the net. At 1940, the process identifies the region for the pin selected at 1935 by calling the same processes described above for 1 25.

0652The process then determines (at 1945) whether the current pin (i.e., the pin

0653selected at 1935) falls in the same region as the first pin. If so, the process adds the current pin to the net previously added (at 1930) to the net list for the identified

0654region. The process then transitions to 1970, which will be described below.

0655On the other hand, if the process determines (at 1945) that the current pin does

0656not fall in the same region as the first pin, the process determines whether the

0657intersection variable C equals 0. If so, the process realizes that it has detected a net cut. Hence, it changes the value of the intersection variable C to 1, and adds the net

0658and the current pin to the net list for the identified region of the current pin. However,

0659if the process determines (at 1955) that the intersection variable is not 0, the process

0660realizes that it has previously detected the net cut. Therefore, the process simply adds

0661(at 1960) the current pin to the net list for the identified region.

0662From 1960 and 1965, the process transitions to 1970, where it determines

0663whether it has examined the last pin in the current net. If not, the process transitions

0664back to 1935 to examine the next pin in the net. Otherwise, the process (at 1975)

066542 Atty.Docket No.:SPLX.P0125 (1) adds the intersection cost C to the congestion cost (Cost), and (2) stores the

0666intersection cost C as the cost of the current net.

0667Next, the process determines (at 1980) whether it has examined the last net. If

0668not, the process returns to 1910 to (1) select another net, (2) partition this net about the cut line, and (3) determine whether this net crosses the cut line. Otherwise, the

0669process returns (at 1985) (l) the congestion cost of the current placement

0670configuration, and (2) the two net lists that represent the partitioning of the received net list about the received cut line.

0671As mentioned above, a placer can repeatedly perform the process 1800 of

0672Figure 18 to define a series of cut lines that recursively partition the IC layout into

0673smaller and smaller regions. At each level of the recursion, the placer can then use the

0674process 1900 of Figure 19 to obtain congestion cost estimate, and to partition nets, across the cut line of that level.

0675Specifically, for each recursion level, the placer initially supplies the process

06761900 with (1) the cut line for that level, and (2) a list of all the nets in that level's

0677region. The process 1900 then (1) partitions the nets in that region about the cut line

0678(i.e., as described above, the process adds the nets and their corresponding pins to the

0679appropriate net lists for the sub-regions created by the cut line), and (2) calculates a

0680cost for the congestion across the cut line.

0681After receiving from the process 1900 the congestion cost of the initial net

0682configuration within a recursion level's region, the placer then uses an optimization algorithm that iteratively modifies the net configuration within this region to improve

068343 Atty .Docket No.:SPLX.P0125 the congestion cost generated by the process 1900. In some embodiments, the

0684optimization process uses the process 1900 to calculate the placement-configuration cost for each possible iterative modification to the placement configuration. This is

0685further described below in Section Nil, which presents several suitable optimization techniques.

V. PARTITIONING PLACEMENT TECHNIQUE

0687Some embodiments of the invention use a partitioning technique that

0688(1) partitions a design region into a number of sub-regions (also called slots), (2) for at

0689least one net, identifies the set of sub-regions (i.e., the set of slots) that contain the

0690net's circuit elements, (3) identifies a route that connects the identified set of sub- regions for the net, where the route has at least one partial or complete diagonal edge, and (4) for the net, computes a placement cost based on the identified route.

0691Figure 23 conceptually illustrates one such placement process 2300. This

0692process starts each time it receives the coordinates for a region of an IC layout. The

0693received region can be the entire IC layout, or a portion of this layout. In some

0694embodiments, this process also receives a net list that specifies all the net's that have

0695circuit elements in the received IC region. In other embodiments, the process receives

0696a list of all the circuit elements in the received IC region, and from this list identifies

0697the nets that have circuit elements in the received IC region.

0698Each received or identified net has a set of circuit elements associated with it

0699(i.e., each net is defined to include a set of circuit elements). In some embodiments,

0700the circuit elements associated with the nets are the pins of the circuit modules in the

070144 Atty.Docket No.:SPLX.P0125 IC layout. However, in the embodiments described below, the circuit elements are the circuit modules. Some of these embodiments treat the circuit modules as the net

0702circuit elements and obviate the need to distinguish between the different pin locations,

0703by assuming that the pins of each module are all located at uniform locations (e.g., located at the origin of the modules).

0704Also, in some embodiment, the locations of the circuit elements in the received

0705IC region define a placement configuration within this region. In some embodiments,

0706the initial circuit-element positions before the process 2300 starts are random. Alternatively, some embodiments use a previous physical-design operation, such as the floor planning, to partially or completely specify the initial positions of these elements.

0707Still other embodiments use another placer to specify the initial positions of the circuit

0708elements in the received IC region, and then use process 2300 to optimize the

0709placement configuration for a wiring architecture that uses diagonal wiring.

0710Before the start of the process 2300, a set of partitioning lines is defined. This

0711set divides the received IC region into several sub-regions (also called slots). In the

0712embodiments described below, the partitioning lines are intersecting lines that define a

0713partitioning grid. In some of these embodiments, the intersecting partitioning lines are

0714N horizontal and M vertical lines that divide the received IC region into (N+1)(M+1)

0715sub-regions, where N and M can equal any integer. For instance, these horizontal and

0716vertical lines divide the received IC region into (1) four sections when N and M equal

07171, (2) nine sections when N and M equal 2, (3) sixteen sections when N and M equal 3,

0718or (4) twenty sections when either N or M equals 4 and the other equals 5.

071945 Atty.DocketNo.:SPLX.P0125 Figure 24 illustrates an IC layout 2400 that has been divided into sixteen sub- regions by sets of three horizontal and vertical partitioning lines. This figure also

0720shows a net 2405 that includes five circuit modules 2410, 2415, 2420, 2425, and 2430,

0721which fall into four of the sixteen sub-regions. These four sub-regions are slots 1, 2, 8, and 9.

0722Once the partitioning grid has been defined, the process 2300 initially identifies (at 2305), for each received or identified net, the set of sub-regions (i.e., the set of

0723slots) that contain the circuit modules of that net. The identified set of sub-regions for

0724each net represents the net's configuration with respect to the defined grid.

0725For each received or identified net, the process next identifies (at 2310) the length of a connection graph that includes a set of interconnect lines (also called interconnect edges) that connect the slots that contain the net's circuit modules.

0726Specifically, the connection graph of each net represents a route that traverses the set

0727of sub-regions that contain the net's circuit elements. According to the invention, the

0728connection graph can have edges that are completely or partially diagonal.

0729Different embodiments might use different connection graphs. In the

0730embodiments described below, the connection graphs are Steiner trees. Figures 25-27

0731illustrate three Steiner trees 2505, 2605, and 2705 for the net 2405 in Figure 24.

0732These Steiner trees all have the same length. One of these trees (2505) has a Steiner

0733node (2520). In addition, each of these trees has at least one edge that is partially

0734diagonal. In these examples, the diagonal edges are at 45° degrees with respect to the

0735layout boundary. When the octagonal wiring model is used, the lengths of these

073646 Atty.Docket No.:SPLX.P0125 Steiner trees approximate the route (interconnect-line) length necessary for net 2405 at

0737the level of the partitioning grid.

0738In some embodiments, the process identifies (at 2310) the length of each net's

0739connection graph by constructing this connection graph in real-time and quantifying its length during or after the constmction of the graph. However, the embodiments

0740described below identify the connection-graph length in a different manner. Before the

0741process 2300 starts, these embodiments (1) constmct the connection graphs for each

0742possible net configuration with respect to the partitioning grid, and (2) pre-tabulate the connection-graph lengths in a storage structure. During placement, these pre- tabulating embodiments then retrieve (at 2310) the connection-graph length of each

0743identified net configuration from memory. One manner of constructing and pre-

0744tabulating connection graphs will be described below by reference to Figures 28-31.

0745At 2315, the process 2300 uses the lengths identified at 2310 to calculate the

0746placement cost of the received or identified nets in the layout within the received region. Some embodiments calculate this cost by combining (e.g., summing,

0747multiplying, etc.) each graph's length.

0748In some embodiments of the invention, the process 2300 generates a placement

0749cost estimate for an initial placement configuration, when it receives a net list that

0750specifies the initial placement configuration (i.e., a net list that identifies all the nets in

0751the IC layout region before any modifications to the positions of the modules in the

0752layout).

075347 Atty.DocketNo.:SPLX.P0125 After obtaining the delay cost of the initial placement configuration, some embodiments use an optimization algorithm that iteratively modifies the placement configuration in the received IC region, in order to improve the placement cost. Different embodiments of the invention use different optimization techniques, such as annealing, local optimization, KLFM, tabu search, etc. Also, different optimization techniques modify the placement configuration differently. For instance, at each iteration, some techniques move one circuit module, others swap two modules, and yet others move several related modules, between the sub-regions defined by the partitioning grid. Also, at each iteration, some optimization techniques (e.g., KLFM and tabu search algorithms) search for the best move, while others (e.g., simulated annealing and local optimization) select random moves. In addition, some techniques (e.g., simulated annealing) accept moves that make the metric score worse, whereas others (e.g., local optimization) do not. Several suitable optimization processes are discussed below in Section VII.

0754After each iterative modification during optimization, the placement configuration is re-calculated by repeating the process 2300 for all the nets or for just the nets on which the moved circuit module or modules reside. After optimizing the placement configuration, some embodiments terminate their placement operations. Other embodiments recursively repeat the process 2300 and the optimization operation on each defined sub-region (i.e., each sub-region defined by the partitioning grid) that meets one or more criteria. For instance, some embodiments recursively perform the partitioning and optimization operations on each sub-region that contains more than a specified number of circuit modules.

075548 Atty.Docket No.:SPLX.P0125 Some embodiments use different shaped partitioning grids for different levels in the recursion process. Other embodiments use same shaped partitioning grids for all

0756the recursion levels. At each recursion level, these embodiments simply adjust the

0757coordinates of the partitioning grid to match the coordinates of the IC region at that recursion level. Using the same shaped partitioning grids for all the recursion levels

0758has several advantages. For instance, it allows the pre-tabulating embodiments to store

0759only net configuration lengths for one partitioning grid; these lengths can be re-used at

0760all the recursion levels because they can be used to define the relative costs of the net

0761configurations at any one level.

0762Figures 28-31 illustrate one manner of pre-tabulating Steiner-tree lengths that

0763model possible net configurations with respect to a partitioning grid. Specifically,

0764Figure 28 illustrates a process 2800 that (1) constmcts Steiner trees for each possible

0765net configuration with respect to a partitioning grid, and (2) stores the length of each

0766constructed Steiner tree in a look-up table ("LUT").

0767The process 2800 initially starts (at 2805) by defining a Steiner-tree node for

0768each sub-region (also called slot) defined by a particular partitioning grid. Figure 29

0769pictorially illustrates sixteen Steiner-tree nodes 2905 for sixteen slots created by a 4-

0770by-4 partitioning grid. These nodes represent all the potential nodes of Steiner trees

0771that model the interconnect topologies of all the net configurations. In Figure 29, the

0772identified nodes are positioned at the center of each slot. In other embodiments, the

0773nodes can uniformly be defined at other locations in the slots (e.g., can be uniformly

0774positioned at one of the comers of the slots).

077549 Atty.DocketNo.:SPLX.P0125 Next, the process 2800 defines (at 2810) a set N of possible node

0776configurations. When the grid partitioning defines Y (e.g., four, nine, sixteen, twenty, etc.) sub-regions, set N includes 2^Y node configurations. Node configurations with

0777less than two nodes do not have Steiner trees. Accordingly, the process sets the

0778lengths of these configurations to zero.

0779After 2810, the process 2800 select (at 2815) one of the possible node configurations N_τ that has more than two nodes from the set defined at 2810. The process then constmcts (at 2820) a minimum spanning tree ("MST") for the node

0780configuration selected at 2815, and computes this tree's length (MST_Cost). The

0781process constmcts this minimum spanning tree by using edges that can be completely

0782or partially diagonal. One mam er of constructing such a MST and computing its

0783length will be described below by reference to Figure 31.

0784After constmcting the MST for the selected node configuration, the process

07852800 identifies (at 2825) potential Steiner nodes. Figure 30 illustrates a process 3000

0786for identifying potential Steiner nodes. This process starts (at 3005) by initializing a

0787set P of potential Steiner nodes equal to all the nodes defined at 2805 that are not part

0788of the node configuration selected at 2815. This process then selects (at 3010) one of

0789the potential Steiner nodes.

0790Next, the process 3000 determines (at 3015) whether the node (Q) selected at 3010 is on a shortest path between any two nodes in the selected node configuration.

0791To make this determination, the process determines whether any two nodes (B and C)

0792exist in the node configuration such that the distance between the two nodes (B and C)

0793equals the sum of (1) the distance between the first node (B) and the selected node

079450 Atty.Docket No.:SPLX.P0125 (Q), and (2) the distance between the second node (C) and the selected node (Q). In

0795some embodiments, the process calculates the distance between any pair of nodes by

0796using the above-described bounding box approach and Equation (A).

0797If the process determines that the node Q selected at 3010 lies on a shortest path between any two nodes in the node configuration, the process keeps (at 3020) the

0798selected node in the set P of potential Steiner nodes, flags this node as a node that it

0799has examined, and transitions to 3030, which is described below. On the other hand, if

0800the selected node (Q) is not on the shortest path between any two nodes in the selected

0801node configuration, the process removes (at 3025) the selected node from the set P of potential Steiner nodes, and transitions to 3030.

0802At 3030, the process determines whether it has examined all the nodes in the

0803set of potential Steiner nodes. If not, the process returns to 3010 to select another

0804node in this set so that it can determine at 3015 whether this node is on a shortest path

0805between any two nodes in the selected node configuration. When the process determines (at 3030) that it has examined all the nodes in the set of potential Steiner

0806nodes, it ends.

0807Once the process 2800 performs (at 2825) the process 3000 of Figure 30 to

0808identify potential Steiner nodes, the process 2800 defines (at 2830) all possible sets of

0809Steiner nodes. Each defined set of Steiner nodes includes one or more of the Steiner

0810nodes identified at 2825. Also, each defined set of Steiner nodes has a maximum size

0811that is two nodes less than the number of nodes in the selected node configuration.

081251 Atty.Docket No.:SPLX.P0125 The process 2800 then selects (at 2835) one of the Steiner-node sets defined at

08132830. The process then (at 2840) (1) constmcts a minimum spanning tree (MST) for the nodes in the selected node configuration and the selected Steiner-node set, and

0814(2) computes and stores this MST's length (MST_Cost). The process constmcts this MST by using edges that can be completely or partially diagonal. One manner of

0815constmcting such a MST and computing its length will be described below by

0816reference to Figure 31.

0817Next, the process determines (at 2845) whether, in the Steiner node sets

0818defined at 2830, there are any additional Steiner-node sets that it has not yet examined.

0819If so, the process returns to 2835 to select another Steiner-node set, so that it can

0820constmct a MST for the nodes of this set and the nodes in the selected node

0821configuration.

0822When the process determines (at 2845) that it has generated MST's of the selected node configuration and each Steiner-node set, the process identifies (at 2850)

0823the smallest MST_Cost that it computed at 2820 and 2840. The process then stores

0824(at 2855) in a LUT the MST_Cost identified at 2850 as the length of the Steiner-tree

0825route for the node configuration selected at 2815. During the placement operation, a placer can then quicldy identify the Steiner-tree length for the current node

0826configuration by retrieving the stored length from the storage structure.

0827The process next determines (at 2860) whether it has examined all node

0828configurations in the set defined at 2810 that have two or more nodes. If not, the process returns to 2815 to select an unexamined node configuration that has two or

082952 Atty.Docket No.:SPLX.P0125 more nodes, and then repeat operations 2820-55 to determine and store the Steiner

0830length for this node configuration. Otherwise, the process ends.

0831Figure 31 illustrates a process 3100 that the process 2800 of Figure 28 uses at 2820 and 2840 to construct minimum spanning trees. A minimum spanning tree for a node configuration is a tree that has N-1 edges that connect (i.e., span) the N nodes of

0832the configuration through the shortest route, which only branches (i.e., starts or ends)

0833at the nodes. The length of a MST for a net configuration provides a lower-bound

0834estimate of the amount of wiring needed to interconnect the nodes associated with the

0835net configuration.

0836According to the embodiments described below, the edges of the MST's can be horizontal, vertical, or diagonal. The diagonal edges can be completely or partially

0837diagonal. Also, when the IC layouts use diagonal interconnect lines (e.g., ±120°

0838interconnect lines), the diagonal edges of the MST's can be in the same direction (e.g.,

0839can be in ±120° direction) as some of the diagonal interconnect lines in the layout.

0840For instance, when the IC layout uses an octagonal wiring model that specifies

0841horizontal, vertical, and 45° diagonal lines, some embodiments constmct MST's that

0842have horizontal, vertical, and 45° diagonal edges. The above-described Figure 11

0843illustrates an example of such a MST. Also, as discussed above, by treating the two

0844nodes of each edge of an MST as two opposing comers of a bounding box, the length

0845of each edge can be obtained by using the above-described boundmg-box approach and

0846Equation (A).

084753 Atty.Docket No.:SPLX.P0125 The process 3100 starts whenever the process 2800 calls it (at 2820 or 2840)

0848(1) to constmct an MST for a set M of nodes, and (2) to calculate this MST's length.

0849This process initially (at 3105) sets the MST length (MST_Cost) to zero. Next, the

0850process (at 3110) (1) selects a node from the received set M of nodes as the first node of the spanning tree, and (2) removes this node from this set M.

0851The process then defines (at 3115) a remainder set R of nodes equal to the

0852current set M of nodes. At 3120, the process selects a node from the remaining node set R, and removes the selected node from the set of remaining nodes. The process

0853then computes and stores (at 3125) the distance between the node selected at 3120 and

0854each current node of the spanning tree. The distance between the selected node and

0855each node can be traversed by an edge that is completely or partially diagonal. Hence,

0856in some embodiments, the process uses the above-described bounding-box approach and Equation (A) to compute the minimum distance between the selected node and

0857each node.

0858Next, the process determines (at 3130) whether there is any node remaining in

0859set R. If so, the process returns to 3120 to select another node from this set, so that it can compute (at 3125) the distance between this node and the current nodes of the

0860spanning tree. Otherwise, the process (at 3135) identifies the smallest distance

0861recorded at 3125, and identifies the node combination (i.e., the node in set M and the

0862MST's node) that resulted in this distance. The process then (at 3140) adds the

0863identified smallest distance to the MST length (MST_Cost).

0864The process next (at 3145) (1) defines a tree node corresponding to the node

0865identified at 3135, (2) removes the identified node from the node set M, and (3) links

086654 Atty.Docket No.:SPLX.P0125 the defined tree node to the MST node identified at 3135. The process then determines (at 3150) whether the node set M is empty. If not, the process transitions back to 3115 to identify the next node (in this set M) that is closest to the current nodes of the MST. Otherwise, the process determines that it has constructed the MST for the received set M of nodes, returns the computed MST length (MST_Cost) for this set, and then ends.

VI. DELAY METRIC

0868Several embodiments described above compute length metrics to cost different placement configurations. These length metrics account for the use of a wiring model that includes diagonal wiring. One of ordinary skill will realize that other embodiments might use other types of placement metrics.

0869For instance, some embodiments compute placement delay costs that account for the use of diagonal wiring. Some of these embodiments derive the delay cost for a placement of a net from the net's length cost that was derived for such a placement. For example, some embodiments derive the delay cost from the length cost by using a linear equation, such as Equation (F) recited below:

0870Delay_Cost = A * Wirelength_Cost + B, (F)

0871where A and B are scalar constants. Other embodiments derive the delay cost from the length cost by using a non-linear equation, such as Equation (G) recited below:

0872Delay_Cost = A * Wirelength_Cost^D + A'* Wirelength_Cost^D"1 + ... + B, (G)

087355 Atty.Docket No.:SPLX.P0125 where A, A', B, and D are scalar constants. In the equation above, D can be any value

0874greater than one. Also, the equation can have multiple components that are dependent

0875on the length. In these equations, the length cost can be computed according to any of

0876the above-described approaches.

0877Also, when the length cost is computed according to the pre-tabulating

0878partitioning approach described above, the delay cost can be pre-tabulated along with

0879the length cost. For instance, the process 2800 can calculate and store the delay cost

0880at 2855 when it identifies the length cost of a net configuration with respect to the partitioning grid. Specifically, at 2855, the process 2800 could use the above Equation

0881(F) or (G) to calculate the delay cost from the length cost identified at 2850, and then

0882could store the delay cost along with the length cost in the LUT.

0883Figure 32 illustrates a process 3200 that computes delay costs. A placer can

0884use this process to generate a delay cost estimate for a set of nets on a net list. In

0885some embodiments, the process 3200 starts whenever it receives a net list that specifies

0886a number of nets .

0887Each received net has a set of circuit elements associated with it (i.e., each net

0888is defined to include several circuit elements). In other words, the nets on the net list specify the interconnection between some or all the circuit elements in the IC layout.

0889In the embodiments described below, the circuit elements associated with the nets are

0890the pins of circuit modules in the IC layout. Other embodiments, however, treat the

0891circuit modules as the circuit elements of the nets. Some of these embodiments treat the circuit modules as the net circuit elements and obviate the need to distinguish

089256 Atty .Docket No.:SPLX.P0125 between the different pin locations, by assuming that the pins of each module are all located at uniform locations (e.g., located at the origin of the modules).

0893In some embodiments, the positions of the net circuit elements before the

0894process 3200 starts define an initial placement configuration. In some of these

0895embodiments, the initial circuit-element positions are random. In other embodiments, a

0896previous physical-design operation, such as the floor planning, partially or completely specifies the initial positions of these elements. Other embodiments use another placer

0897to specify the initial positions of the circuit elements, and then use process 3200 to

0898optimize the placement configuration for a wiring architecture that uses diagonal wiring.

0899The process 3200 initially selects (at 3205) a net. For the selected net, it then identifies (at 3210) a delay cost that is based on a length cost of the net. The length

0900cost can be computed based on any of the above-described processes 1000, 1200,

09011400, 1900, and 2300. Also, the identified delay cost can be derived from the length

0902cost based on any number of mathematical relationships, such as those described by

0903Equations (F) and (G). As mentioned above, the embodiments that use the pre-

0904tabulating partitioning approach can pre-tabulate the delay cost for each net

0905configuration. Accordingly, in these embodiments, the process 3200 identifies (at

09063210) the delay cost by using the selected net's configuration with respect to a

0907partitioning grid to retrieve a pre-computed delay cost from a storage structure.

0908After 3210, the process stores (at 3215) the identified delay cost of the selected

0909net, if necessary. The process 3200 does not have to store the identified delay cost

0910when it uses the above-described partitioning approach that uses pre-tabulated delay

091157 Atty.DocketNo.:SPLX.P0125 costs. In these embodiments, the delay costs have already been stored for each net

0912configuration with respect to the partitioning grid.

0913The process then determines (at 3220) whether it has examined the last net in

0914the received net list. If not, the process returns to 3205 to select another net and then

0915repeats 3210-3215 for the newly selected net. Otherwise, for the received placement

0916configuration, the process computes (at 3225) an overall delay cost based on the delay costs identified at 3210. In some embodiments, the process computes the overall delay

0917cost as a sum of the delay costs identified at 3210. After 3225, the process ends.

0918In some embodiments of the invention, the process 3200 generates a delay cost

0919estimate for an initial placement configuration, when it receives a net list that specifies

0920the initial placement configuration (i.e., a net list that identifies all the nets in the IC

0921layout before any modifications to the positions of the modules in the layout).

0922After obtaining the delay cost of the initial placement configuration, some

0923embodiments use an optimization process that iteratively modifies the placement

0924configuration to improve the placement-configuration cost. In some embodiments, the

0925optimization process uses the process 3200 to calculate the placement-configuration

0926cost for each possible iterative modification to the placement configuration. This is

0927further described below in Section VII, which presents several suitable optimization

0928techniques.

VII. OPTIMIZATION TECHNIQUES

0930As mentioned above, the invention's cost-calculating methods can be used with a variety of optimization techniques. Three suitable optimization techniques are

093158 Atty.Docket No.:SPLX.P0125 described below. These three are: (1) local optimization, (2) simulated annealing, and (3) KLFM.

0932A. Local Optimization.

0933Local optimization is a technique that iteratively modifies the placement

0934configuration to improve the placement score generated by a cost-calculating function.

0935At each iteration, this technique might move one circuit module, swap two modules, or move a number of related modules, etc. Also, at each iteration, this technique

0936randomly selects moves. In addition, this techniques does not accept moves that make

0937the calculated cost worse.

0938Figure 33 illustrates one example of a local optimization process 3300. This

0939process initially receives (at 3305) an initial placement configuration. In some embodiments, the process receives the initial configuration by receiving a list of circuit

0940modules, a starting placement configuration for these modules, and a net list that specifies the interconnection between these modules.

0941After receiving the initial placement configuration, the process 3300 calls (at

09423310) a cost-calculating method, like one of the cost-calculating methods described

0943above in Sections II- VI. In response, this cost-calculating method computes and

0944returns the cost (C) of the initial placement configuration.

0945When the process 3300 calls the cost-calculating method, it supplies this method with a net list that specifies the initial placement configuration (i.e., a net list

0946that identifies all the nets in the IC layout before any modifications to the positions of

0947the modules in the layout).

094859 Atty .Docket No.:SPLX.P0125 Also, when the cost-calculating method is the bipartitioning process 1900

0949described above, the process 3300 calls the process 1800 before calling the process 1900. As described above, the process 1800 defines a cut line for the current IC

0950region being optimized by the optimization process 3300. The process 3300 supplies the congestion-calculating process 1900 with this cut line along with the initial-

0951configuration's net list, in order to receive from the process 1900 the net-cut

0952congestion cost (C) of the initial placement configuration. From the process 1900, the

0953process 3300 also receives two net lists that specify the nets and the pins in the two regions defined by the current cut line.

0954After obtaining cost of the initial placement configuration at 3310, the process

0955sets (at 3315) a futile-iteration counter (F) equal to 1. As further described below, the

0956process uses counter to determine whether it needs to terminate its operation as it has

0957performed a predetermined number of iterations without improving the score.

0958The process then selects (at 3320) a random move that requires the

0959modification of the coordinates of one or more circuit modules in the IC layout. When

0960the process 3300 uses either of the partitioning processes 1900 or 2300, the random

0961move repositions one or more of the circuit modules with respect to the partitioning

0962lines. For instance, for process 2300, the random move might specify a change of

0963position for a circuit module from one slot to another.

0964The process next identifies (at 3325) all the nets affected by this random move.

0965Depending on how nets are defined, these nets are the nets that either (1) contain the

0966circuit module or modules selected for the move, or (2) contain the pins of these

0967circuit modules.

096860 Atty.DocketNo.:SPLX.P0125 At 3330, the process computes the current cost for the nets identified at 3325. As mentioned above, the cost calculating processes 1000, 1200, 1400, 1900, 2300, and

09693200 store the cost for each net. Hence, the process 3300 can compute the current

0970cost for the identified nets by summing the stored cost values for these nets.

0971According to the selected random move, the process 3300 modifies (at 3335)

0972the coordinates of each circuit module and/or pin affected by the move. In other words, at 3335, the process makes the move by modifying the coordinates of the

0973affected circuit module or modules and/or their associated pins to match the random

0974location identified at 3320.

0975The process then calls the cost-calculating process and supplies this process

0976with a net list that specifies the identified nets that are affected by the selected move. This net list specifies the configuration of the identified nets after the selected move,

0977since the process 3300 modified the coordinates of the affected circuit modules and/or pins at 3335. In the embodiments where the cost-calculating process is the

0978bipartitioning process 1900, the process 3300 supplies this process 1900 with the cut

0979line for the current IC region being optimized, along with the list of the identified nets.

0980In response to the call at 3340, the cost-calculating method computes and

0981returns the cost (C) for the configuration of the identified nets after the potential

0982modification. When the cost-calculating method is the bipartitioning process 1900,

0983this process also partitions the identified nets about the cut line, and returns two net

0984lists that reflect this partitioning.

098561 Atty.Docket No.:SPLX.P0125 After receiving (at 3340) the cost for the identified nets after the potential

0986modification, the process generates (at 3345) a delta cost by subtracting the cost for

0987the identified nets after the potential modification (i.e., the cost calculated at 3340)

0988from the cost for the identified nets before the potential modification (i.e., the cost calculated at 3330)

0989At 3350, the process determines whether the delta cost is less than zero. If so,

0990the selected move reduces the placement cost, and the process decides to retain the

0991move. Specifically, when the delta cost is less than zero, the process sets (at 3355) the cost of the current placement configuration (i.e., the placement configuration with the selected move) equal to the cost of the previous placement configuration (i.e., the

0992placement configuration without the selected move) plus the delta cost. The delta cost is negative and thereby reduces the overall placement configuration cost C.

0993The process 3300 then resets (at 3360) the futile-iteration counter F to 1.

0994Also, when the cost-calculating method is the bipartitioning method 1900, the process

09953300 uses the two net lists returned by the method 1900 at 3340 to modify the two net

0996lists for the two sub-regions defined by the current cut line. The process then returns to 3320 to select another random move.

0997One of ordinary skill will realize that in some embodiments the process 3300 does not base its decision to retain the move solely on the value of the delta computed

0998at 3345. For instance, when the process 3300 uses the partitioning process 2300, the

0999process 3300 in some embodiments also computes a balance cost that quantifies the

1000congestion of each sub-region defined by the partitioning grid of the process 2300. In

100162 Atty.DocketNo.:SPLX.P0125 these embodiments, the process 3300 might not retain a move that reduces the delta cost computed at 3345, when such a move increases the balance cost.

1002If the process determines (at 3350) that the delta cost is not less than zero, the

1003process realizes that the selected move does not reduce the placement cost.

1004Consequently, the process changes (at 3370) the coordinates of the affected circuit

1005module or modules and/or their corresponding pins back to their original coordinates before the move (i.e., their coordinates before 3335). The process also changes the

1006cost of each of the identified nets back to its original value (i.e., back to the cost stored

1007for the net before 3340), if necessary. When the process 3300 uses the partitioning

1008length or delay costing process 2300 or 3200 that uses pre-tabulated length or delay

1009costs, the process does not need to change the costs of each of the identified nets back to the original value because, in these embodunents, the process 2300 or 3200 did not

1010modify these costs in the first place.

1011The process then increments (at 3375) the futile-iteration counter by one. The

1012process then determines (at 3380) whether the futile-iteration count equals a pre-

1013specified maximum. If not, the process returns to 3320 to select another random

1014move. Otherwise, the process realizes (at 3380) that it has performed a pre-specified

1015maximum number of iterations without improving the placement score. Hence, the

1016process returns (at 3385) a net list specifying the current placement configuration, and

1017then ends.

101863 Atty .Docket No.:SPLX.P0125 B. Simulated Annealing.

1019Simulated annealing is an optimization technique that iteratively modifies the

1020placement configuration to improve the placement score generated by a cost- calculating function. At each iteration, this technique might move one circuit module,

1021swap two modules, move a number of related modules, etc. Also, at each iteration, this technique randomly selects moves. It also accepts moves that make the calculated cost

1022worse, but its tolerates fewer bad moves as the number of iterations increases.

1023Figure 34 illustrates one example of a local optimization process 3400. This

1024process initially receives (at 3405) an initial placement configuration. In some

1025embodiments, the process receives the initial configuration by receiving a list of circuit

1026modules, a starting placement configuration for these modules, and a net list that

1027specifies the interconnection between these modules.

1028After receiving the initial placement configuration, the process 3400 calls (at 3410) a cost-calculating method, like one of the cost-calculating methods described

1029above in Sections II- VI. In response, this cost-calculating method computes and

1030returns the cost (C) of the initial placement configuration.

1031When the process 3400 calls the cost-calculating method, it supplies this

1032method with a net list that specifies the initial placement configuration (i.e., a net list that identifies all the nets in the IC layout before any modifications to the positions of

1033the modules in the layout).

1034Also, when the cost-calculating method is the bipartitioning process 1900

1035described above, the process 3400 calls the process 1800 before calling the process

103664 Atty.DocketNo.:SPLX.P0125 1900. As described above, the process 1800 defines a cut line for the current IC

1037region being optimized by the optimization process 3400. The process 3400 supplies

1038the congestion-calculating process 1900 with this cut line along with the initial- configuration's net list, in order to receive from the process 1900 the net-cut

1039congestion cost (C) of the initial placement configuration. From the process 1900, the

1040process 3400 also receives two net lists that specify the nets and the pins in the two

1041regions defined by the current cut line.

1042After obtaining cost of the initial placement configuration at 3410, the process

1043sets (at 3415) a futile-iteration counter (F) equal to 1. As further described below, the

1044process uses counter to determine whether it needs to terminate its operation as it has

1045performed a predetermined number of iterations without improving the score.

1046At 3415, the process also sets an annealing "temperature" T and iteration

1047counter N. As further described below, the annealing temperature determines how

1048likely the process 3400 will accept bad moves. The iteration counter is used to

1049decrease this temperature over time, so as to make process 3400 less and less willing

1050to accept bad moves.

1051At 3420, the process then (1) selects a random move that requires the

1052modification of the coordinates of one or more circuit modules in the IC layout, and

1053(2) increments the iteration counter N. When the process 3400 uses either of the

1054partitioning processes 1900 or 2300, the random move repositions one or more of the

1055circuit modules with respect to the partitioning lines. For instance, for process 2300, the random move might specify a change of position for a circuit module from one slot

1056to another.

105765 Atty.Docket No.:SPLX.P0125 The process next identifies (at 3425) all the nets affected by this random move. Depending on how nets are defined, these nets are the nets that either (1) contain the

1058circuit module or modules selected for the move, or (2) contain the pins of these

1059circuit modules.

1060At 3430, the process computes the current cost for the nets identified at 3425.

1061As mentioned above, the cost calculating processes 1000, 1200, 1400, 1900, 2300, and

10623200 store the cost for each net. Hence, the process 3400 can compute the current

1063cost for the identified nets by summing the stored cost values for these nets.

1064According to the selected random move, the process 3400 modifies (at 3435)

1065the coordinates of each circuit module and/or pin affected by the move. In other words, at 3435, the process makes the move by modifying the coordinates of the

1066affected circuit module or modules and/or their associated pins to match the random

1067location identified at 3420.

1068The process then calls the cost-calculating process and supplies this process

1069with a net list that specifies the identified nets that are affected by the selected move.

1070This net list specifies the configuration of the identified nets after the selected move,

1071since the process 3400 modified the coordinates of the affected circuit modules and/or pins at 3435. In the embodiments where the cost-calculating process is the

1072bipartitioning process 1900, the process 3400 supplies this process 1900 with the cut

1073line for the current IC region being optimized, along with the list of the identified nets.

1074In response to the call at 3440, the cost-calculating method computes and

1075returns the cost (C) for the configuration of the identified nets after the potential

107666 Atty.Docket No.:SPLX.P0125 modification. When the cost-calculating method is the bipartitioning process 1900, this process also partitions the identified nets about the cut line, and returns two net

1077lists that reflect this partitioning.

1078After receiving (at 3440) the cost for the identified nets after the potential

1079modification, the process generates (at 3445) a delta cost by subtracting the cost for

1080the identified nets after the potential modification (i.e., the cost calculated at 3440)

1081from the cost for the identified nets before the potential modification (i.e., the cost calculated at 3430)

1082At 3450, the process determines whether the delta cost is less than zero. If so,

1083the selected move reduces the placement cost, and the process decides to retain the

1084move. Specifically, when the delta cost is less than zero, the process resets (at 3455) the futile-iteration counter F to 1. The process then sets (at 3460) the cost of the

1085current placement configuration (i.e., the placement configuration with the selected move) equal to the cost of the previous placement configuration (i.e., the placement

1086configuration without the selected move) plus the delta cost. The delta cost is negative

1087and thereby reduces the overall placement configuration cost C. Also, when the cost- calculating method is the bipartitioning method 1900, the process 3400 uses (at 3465)

1088the two net lists returned by the method 1900 at 3440 to modify the two net lists for

1089the two sub-regions defined by the current cut line.

1090The process next determines (at 3470) whether the iteration counter N has

1091reached a maximum. If not, the process returns to 3420 to select another random move. Otherwise, the process decreases the annealing temperature and resets the

1092iteration counter at 3475, and then returns to 3420 to select another random move.

109367 Atty.Docket No.:SPLX.P0125 One of ordinary skill will realize that in some embodiments the process 3400

1094does not base its decision to retain the move solely on the value of the delta computed

1095at 3345. For instance, when the process 3400 uses the partitioning process 2300, the

1096process 3400 in some embodiments also computes a balance cost that quantifies the

1097congestion of each sub-region defined by the partitioning grid of the process 2300. In

1098these embodiments, the process 3400 might not retain a move that reduces the delta cost computed at 3345, when such a move increases the balance cost.

1099If the process determines (at 3450) that the delta cost is not less than zero, the

1100process computes (at 3480) a probability between 0 and 1. In some embodiments, the

1101equation for computing the probability equals _e^~(Delta)/T, where Delta is the value

1102computed at 3445 and T is the annealing temperature.

1103Next, the process picks (at 3482) a random number between 0 and 1. At 3484,

1104the process then determines whether the random number is less than the computed

1105probability. If so, the process decides to make the move, and thereby transitions to

11063460 to perform the other operations associated with the move, as described above.

1107If the selected random number is not less than the computed probability, the

1108process changes (at 3486) the coordinates of the affected circuit module or modules

1109and/or their corresponding pins back to their original coordinates before the move (i.e., their coordinates before 3435). At 3486, the process also changes the cost of each of

1110the identified nets back to its original value (i.e., back to the cost stored for the net

1111before 3440), if necessary.

111268 Atty.DocketNo.:SPLX.P0125 When the process 3400 uses the partitioning length or delay costing process

11132300 or 3200 that uses pre-tabulated length or delay costs, the process does not need

1114to change the costs of each of the identified nets back to the original value because, in these embodiments, the process 2300 or 3200 did not modify these costs in the first place.

1115The process then increments (at 3488) the futile-iteration counter by one. The

1116process then determines (at 3490) whether the futile-iteration count equals a pre-

1117specified maximum. If not, the process transitions to 3470, which was described

1118above. Otherwise, the process realizes (at 3490) that it has performed a pre-specified maximum number of iterations without improving the placement score. Hence, the

1119process returns (at 3492) a net list specifying the current placement configuration, and

1120then ends.

1121C. KLFM.

1122KLFM is an optimization technique that iteratively modifies the placement

1123configuration to improve the placement score generated by a cost-calculating function.

1124At each iteration, this technique might move one circuit module, swap two modules, move a number of related modules, etc. Unlike local optimization and simulated

1125annealing, KLFM does not randomly select moves. Instead, at each iteration, it selects

1126the best move over all the possible moves that it can make. KLFM will make moves

1127that make the placement cost worse. Over an entire sweep, it then identifies the best

1128placement configuration that it sees, and if that best placement configuration has a better cost than the original placement configuration, KLFM starts over with the

1129improved solution.

113069 Atty.Docket No.:SPLX.P0125 Figure 35 illustrates one example of a KLFM process 3500. This process initially receives (at 3505) an initial placement configuration. In some embodiments,

1131the process receives the initial configuration by receiving a list of circuit modules, a

1132starting placement configuration for these modules, and a net list that specifies the

1133interconnection between these modules.

1134After receiving the initial placement configuration, the process 3500 calls (at 3510) a cost-calculating method, like one of the cost-calculating methods described

1135above in Sections II- VI. In response, this cost-calculating method computes and

1136returns the cost (C) of the initial placement configuration.

1137When the process 3500 calls the cost-calculating method, it supplies this method with a net list that specifies the initial placement configuration (i.e., a net list

1138that identifies all the nets in the IC layout before any modifications to the positions of

1139the modules in the layout).

1140Also, when the cost-calculating method is the bipartitioning process 1900

1141described above, the process 3500 calls the process 1800 before calling the process 1900. As described above, the process 1800 defines a cut line for the current IC

1142region being optimized by the optimization process 3500. The process 3500 supplies

1143the congestion-calculating process 1900 with this cut line along with the initial- configuration's net list, in order to receive from the process 1900 the net-cut

1144congestion cost (C) of the initial placement configuration. From the process 1900, the

1145process 3500 also receives two net lists that specify the nets and the pins in the two

1146regions defined by the current cut line.

114770 Atty.Docket No.:SPLX.P0125 After obtaining cost of the initial placement configuration at 3510, the process

1148sets (at 3515) a flag (F) equal to false. As further described below, the process uses

1149this flag after performing a number of moves to determine whether any of the moves improved the placement-configuration score. At 3515, the process also (1) identifies the initial placement configuration as the current and best placement configurations,

1150and (2) initializes the costs of the current and best configurations to the cost of the

1151initial configuration.

1152Next, the process defines (at 3520) a set M of all moves in the current

1153placement configuration (Pc_urrent). When the process 3500 uses either of the partitioning processes 1900 or 2300, each move repositions one or more of the circuit

1154modules with respect to the partitioning lines. For instance, for process 2300, a move might specify a change of position for a circuit module from one slot to another.

1155For each move in M, the process computes (at 3525) the cost (C) of the placement configuration after the move. To compute the cost of each move, the

1156process performs the following six operations. First, the process (1) identifies all the

1157nets affected by the move, and (2) computes the current cost for the identified nets by summing the stored cost values for these nets. Second, the process modifies the

1158coordinates of each circuit element affected by the move according to the move.

1159Third, it supplies the cost-calculating process with a net list that specifies the

1160identified nets that are affected by the selected move. When the cost-calculating

1161process is the bipartitioning process 1900, the process 3500 also supplies the cost-

1162calculating process with the cut line for the current IC region. From the cost- calculating process, the process 3500 receives the cost for the identified nets after the

116371 Atty.Docket No.:SPLX.P0125 potential move. When the cost-calculating process is the bipartitioning process 1900, the process 3500 also receives two net lists that represent the partitioning of the

1164identified net list by the process 1900.

1165Fourth, after receiving the cost for the identified nets after the potential

1166modification, the process generates a delta cost by subtracting the cost for the

1167identified nets after the potential modification from the cost for the identified nets before the potential modification.

1168Fifth, the process generates the cost of the move by adding the computed delta

1169cost to the cost of the current placement configuration. Sixth, the process (1) changes

1170the coordinates of the affected circuit elements (modules and/or pins) back to their original coordinates before the move, and (2) changes the cost of each of the identified

1171nets back to its original value before the move, if necessary. As described above, the

1172process does not need to change the costs of each of the identified nets back to the original value when the process 3500 uses the partitioning length or delay costing

1173process 2300 or 3200 that uses pre-tabulated length or delay costs. In addition, when

1174the process 3500 uses the partitioning process 2300, the process 3500 might also use

1175another process to compute a balance cost that quantifies the congestion of each sub-

1176region defined by the partitioning grid of the process 2300. In these embodiments, the

1177process 3500 combines the computed length and balance costs to obtain an overall

1178cost.

1179At 3530, the process makes the move with the lowest placement-configuration

1180cost to obtain a new current placement configuration Pc_urrent- At this stage, the process

1181also removes the selected move from the set M of possible moves. The process also

118272 Atty.Docket No.:SPLX.P0125 sets the cost of the current placement configuration equal to the cost of the placement after the move. Also, when the cost-calculating method is the bipartitioning method 1900, the process modifies (at 3530) the two net lists for the two sub-regions defined by the current cut line by using the two net lists returned by this method at 3525 for the move.

1183The process then determines (at 3535) whether the cost of the current placement configuration (i.e., the configuration obtained at 3530) is less than the lowest placement-configuration cost yet seen. If not, the process transitions to 3545, which will be described below. Otherwise, the process (at 3540) (1) defines the best placement configuration to be the current placement configuration, (2) sets the cost of the best placement configuration to the cost of the current placement configuration, and (3) sets the flag (F) to true to indicate that at least one of the performed moves improved the placement cost. The process then transitions to 3545.

1184At 3545, the process determines whether the set M of possible moves is empty.

1185If not, the process transitions back to 3525 to compute, for each remaining move in the set, the cost (C) of the placement configuration after the move. The process recomputes the cost associated with the moves because the previous move might have affected the placement configuration costs for the remaining moves.

1186If the process determines (at 3545) that the set M is empty, the process

1187determines that it has performed all the moves in the set defined at 3520. Consequently, the process determines (at 3550) whether one of the performed moves improved the placement cost by determining whether the flag (F) is set to tme.

118873 Atty.Docket No.:SPLX.P0125 If the flag is tme, the process (at 3555) (1) sets the current placement

1189configuration equal to the best placement configuration identified in the last sweep

1190through the moves, (2) define the cost of the current placement configuration equal to

1191the cost of the best placement configuration, and (3) sets the flag (F) to tme. The

1192process then returns to 3520 to repeat for the current placement configuration, in order

1193to determine whether it can improve on this configuration.

1194If the process determines (at 3550) that the flag is false, the process returns (at 3560) the best placement configuration that it identified as the final placement

1195configuration. The process then ends.

VIII. THE COMPUTER SYSTEM

1197Figure 36 presents a computer system with which one embodiment of the

1198present invention is unplemented. Computer system 3600 includes a bus 3605, a

1199processor 3610,. a system memory 3615, a read-only memory 3620, a permanent

1200storage device 3625, input devices 3630, and output devices 3635.

1201The bus 3605 collectively represents all system, peripheral, and chipset buses

1202that communicatively connect the numerous internal devices of the computer system

12033600. For instance, the bus 3605 communicatively connects the processor 3610 with

1204the read-only memory 3620, the system memory 3615, and the permanent storage

1205device 3625.

1206From these various memory units, the processor 3610 retrieves instructions to

1207execute and data to process in order to execute the processes of the invention. The

1208read-only-memory (ROM) 3620 stores static data and instructions that are needed by

120974 Atty.Docket No.:SPLX.P0125 the processor 3610 and other modules of the computer system. The permanent storage device 3625, on the other hand, is read-and-write memory device. This device is a non-volatile memory unit that stores instruction and data even when the computer system 3600 is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device 3625. Other embodiments use a removable storage device (such as a floppy disk or zip® disk, and its corresponding disk drive) as the permanent storage device.

1210Like the permanent storage device 3625, the system memory 3615 is a read- and- write memory device. However, unlike storage device 3625, the system memory is a volatile read-and-write memory, such as a random access memory. The system memory stores some of the instructions and data that the processor needs at runtime. In some embodiments, the invention's processes are stored in the system memory 3615, the permanent storage device 3625, and/or the read-only memory 3620.

1211The bus 105 also connects to the input and output devices 3630 and 3635. The input devices enable the user to communicate information and select commands to the computer system. The input devices 3630 include alphanumeric keyboards and cursor- controllers.

1212The output devices 3635 display images generated by the computer system. For instance, these devices display IC design layouts. The output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD).

121375 Atty.Docket No.:SPLX.P0125 Finally, as shown in Figure 36, bus 3605 also couples computer 3600 to a network 3665 through a network adapter (not shown). In this manner, the computer

1214can be a part of a network of computers (such as a local area network ("LAN"), a

1215wide area network ("WAN"), or an Intranet) or a network of networks (such as the Internet).

1216Any or all of the components of computer system 3600 may be used in conjunction with the invention. However, one of ordinary skill in the art would

1217appreciate that any other system configuration may also be used in conjunction with the present invention.

1218IX. ADVANTAGES.

1219The embodiments of the invention that factor diagonal, horizontal, and vertical

1220wiring during placement, result in the better distribution of the nets when such wiring

1221is used to route the nets. When the router uses diagonal, horizontal, and vertical wiring but the placer is optimized only for Manhattan wiring, the placer poorly

1222positions the nets in the IC layout. Specifically, in these situations, the placer has a

1223tendency to ignore diagonal positions, since it is inclined to place all circuit elements related to a particular circuit element directly above or below, or directly to the right or left, of the particular circuit element.

1224On the other hand, when a placer is optimized for diagonal, horizontal, and

1225vertical wiring, such a placer is less inclined to ignore diagonal positions. Hence, such

1226a placer places related circuit elements in horizontal, vertical, or diagonal positions

122776 Atty.Docket No.:SPLX.P0125 with respect to each other. This, in turn, provides for a more uniform distribution of related circuit elements.

1228In other words, a placer that is optimized for horizontal, vertical, and diagonal wiring can position the circuit modules in more locations that cost the same. This ability, in turn, opens up more positions to place the circuit modules, and thereby reduces wirelength.

1229While the invention has been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. For instance, while the above-described wirelength calculating processes compute their total costs by summing the wirelength cost for each net, other embodiments might compute their total wirelength costs by combining the net wirelength costs in a different manner (e.g., they might multiply their computed net wirelength costs).

1230Also, some embodiments were described above by only reference to the identification of the wirelength of various connection graphs with potential diagonal edges. One of ordinary skill will realize that other embodiments might identify other attributes of such connection graphs. For instance, some embodiments might identify the number of bends (i.e., the number of changes in wiring direction) of each graph. Thus, one of ordinary skill in the art would understand that the invention is not to be limited by the foregoing illustrative details, but rather is to be defined by the appended claims.

123177 Atty.Docket No.:SPLX.P0125