Partitioning placement method and apparatus

• US 20030088841A1
• Filed: 12/23/2002
• Published: 05/08/2003
• Est. Priority Date: 12/06/2000
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Ganley, Joseph L.
• Granted Patent: US 6,848,091 B2
• Time in Patent Office: Days
• US Class Current: 716/8
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention are placers that use diagonal lines in calculating the costs of potential placement configurations. For instance, some embodiments estimate the wirelength cost of a placement configuration by (1) identifying, for each net in a list, a bounding box that encloses all the circuit elements of the net, (2) computing an attribute of each bounding box by using a line that can be completely or partially diagonal, and (3) computing the wirelength cost estimate based on the computed attributes. To estimate the wirelength cost of different placement configurations, other embodiments construct connection graphs that model the net interconnect topologies. These connection graphs can have edges that are completely or partially diagonal. 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.

Claims

1. For an electronic design automation placer that defines positions of circuit modules in an integrated circuit (“

IC”

) layout, wherein the placer uses a set of nets and each net specifies a set of circuit elements in the layout, a method for computing placement-configuration costs comprising;

a) defining a plurality of diagonal partitioning cutlines, wherein each diagonal cutline defines two sub-regions of a region of the IC layout;

b) for each particular diagonal cutline, calculating the number of nets that have circuit elements in both the sub-regions defined by the particular diagonal cutline; and

c) computing a cost estimate based on the calculated numbers.

2. The method of claim 1, wherein computing a cost estimate comprises:

a) squaring each calculated number; and

b) summing the squared calculated numbers to obtain a congestion cost estimate.

3. The method of claim 1 further comprising:

a) defining a plurality of Manhattan partitioning cutlines, wherein each Manhattan cutline defines two sub-regions of the region of the IC layout;

b) for each Manhattan cutline, calculating the number of nets that have circuit elements in both the sub-regions defined by the particular Manhattan cutline;

c) computing a cost estimate based on the calculated numbers.

4. The method of claim 1 further comprising changing the positions of a set of circuit elements in said region to reduce the number of nets intersected by said cutlines.

5. The method of claim 4 wherein changing the positions of the circuit elements comprises using a KLFM optimization process.

6. The method of claim 4 wherein changing the positions of the circuit elements comprises using annealing optimization process.

7. The method of claim 4 wherein changing the positions of the circuit elements comprises using a local optimization process.

8. The method of claim 1, wherein the layout is to be routed by the Manhattan wiring model.

9. The method of claim 1, wherein the layout is to be routed by the Manhattan and diagonal wiring models.

10. The method of claim 1, wherein the layout is to be routed by using preferred-direction diagonal interconnect lines.

11. The method of claim 10, wherein the direction of at least some of the diagonal cutlines matches the direction of at least some of the diagonal interconnect lines.

12. For a placer that defines positions of circuit modules in an integrated circuit (“

IC”

) layout, wherein the placer defines a set of nets, and each net specifies a set of circuit elements in the layout, a method of computing cost estimates for placement configurations, the method comprising;

a) defining a plurality of cutlines, wherein each cutline partitions the IC layout into two sub-regions, wherein at least one of said cutlines is diagonal and one of said cutlines is not diagonal,

b) for each particular cutline, counting the number of nets that have circuit elements in both the sub-regions defined by the particular cutline;

c) computing a cost estimate based on the counted numbers.

13. The method of claim 12, wherein computing a cost estimate comprises:

a) squaring each calculated number; and

b) summing the squared calculated numbers to obtain a congestion cost estimate.

14. The method of claim 12 further comprising changing the positions of a set of circuit elements in said layout to reduce the number of nets intersected by said cutlines.

15. For an electronic design automation application, a placement method for defining the positions of circuit modules in an integrated circuit (“

IC”

) layout, wherein the application defines a set of nets, and each net specifies a set of circuit elements in the layout, the method comprising

a) defining a plurality of diagonal cutlines and a plurality of non-diagonal cutlines, wherein each cutline partitions the IC layout into two sub-regions;

b) for each cutline, computing the number of nets that have circuit elements in both the sub-regions defined by the particular cutline;

c) squaring each computed number;

d) adding the squared computed numbers to obtain a congestion cost estimate;

e) changing the positions of the circuit modules in the IC layout to reduce the congestion cost estimate.

16. The method of claim 15, wherein said plurality of non-diagonal cutlines includes horizontal lines.

17. The method of claim 15, wherein said plurality of non-diagonal cutlines includes vertical lines.