Method and apparatus for considering diagonal wiring in placement

• US 7,024,650 B2
• Filed: 12/06/2000
• Issued: 04/04/2006
• Est. Priority Date: 12/06/2000
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Ganley, Joseph L.
• Primary Examiner(s): DO, THUAN V
• Application Number:
  US09/731,891
• Publication Number:
  US 20020133798A1
• Time in Patent Office: 1,945 Days
• Field of Search: 257/401, 716/2, 716/5, 716/7, 716/13, 716/14, 716/10, 716/12, 716/8, 716/9, 716/11
• US Class Current: 716/122
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• 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

The invention is directed towards method and apparatus that consider diagonal wiring in placement. 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 net 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 application, a method of placing circuit modules in an integrated circuit (“

IC”

) layout, wherein the IC layout has a number of circuit elements, a net having a set of circuit elements, the method comprising;

using a diagonal line to measure a placement metric;

wherein using the diagonal line to measure a placement metric comprises calculating an estimate of the length of interconnect lines necessary to connect the circuit elements of said net during a routing operation, wherein the calculation measures the length of at least one line that is at least partially diagonal.

2. The method of claim 1, wherein calculating the estimate comprises constructing a bounding box encompassing all the circuit elements of the net.

3. The method of claim 2, wherein calculating the estimate further comprises using the diagonal line to measure an attribute of the bounding box.

4. The method of claim 3, wherein said attribute is the distance between two opposing corners of the bounding box, and said diagonal line traversing at least a portion of said distance.

5. The method of claim 3, wherein the diagonal line is 45°

line.

6. The method of claim 1, wherein calculating the estimate comprises constructing a connection graph that models the topology of interconnect lines for connecting the circuit elements of the net, said connection graph having edges, wherein at least one of the edges is at least partially diagonal.

7. The method of claim 6, wherein calculating the estimate further comprises calculating the length of the edges of the graphs.

8. The method of claim 7, wherein to calculate the length of each edge that connects two circuit elements, the method further comprises:

a) constructing a bounding box that encompasses the two circuit elements, said bounding box having a long side with a length L and a short side with a length S, wherein the two circuit elements are two corners of the bounding box;

b) calculating the distance (D) between the two corners of the bounding box by the using the equation D=[L−

{S(cos A/sin A)}]+S/sin A,

wherein in said equation, A represents the angle of a diagonal edge of the connection graph.

9. The method of claim 6, wherein the connection graph is a minimum spanning tree that includes a diagonal line and at least one of a horizontal line and a vertical line.

10. The method of claim 6, wherein the connection graph is a Steiner tree that includes a diagonal line and at least one of a horizontal line and a vertical line.

11. A method of placing circuit modules in an integrated circuit (“

IC”

) layout, wherein said IC layout includes a net having a plurality of circuit elements, the method comprising;

a) constructing a connection graph that connects the circuit elements of the net, said connection graph having edges, wherein at least one of the edges is at least partially diagonal;

b) identifying a placement metric based on the connection graph; and

c) using the placement metric to identify a placement of the circuit modules.

12. The method of claim 11 further comprising:

calculating the length of the edges of the graph; and

combining the length calculations of the edges of the graph.

13. The method of claim 12, wherein the combining of said length calculations comprises adding said measurements.

14. The method of claim 12, wherein each edge connects two circuit elements of the net, wherein to calculate the length of each edge that connects two circuit elements, the method further comprises:

a) constructing a bounding box that encompasses the two circuit elements, said bounding box having a long side with a length L and a short side with a length S, said diagonal edge forming an angle A with a side of the IC layout, wherein the two circuit elements are at two corners of the bounding box; and

b) calculating the distance (D) between the two corners of the bounding box by using the equation D=[L−

{S (cos A/sin A)}]+S/sin A.

15. The method of claim 14, wherein the angle A corresponds to the angle of at least one type of interconnect-line in a wiring model used by the IC layout.

16. The method of claim 12, wherein the combined length calculation provides an estimate of interconnect-line length needed to connect the circuit elements of the net.

17. The method of claim 16, wherein said estimate is measured to obtain a placement cost of an initial placement configuration.

18. The method of claim 16, wherein each edge connects two circuit elements of the net, the method further comprising:

a) modifying the position of at least one circuit elements of the net;

b) after said modification, constructing a second connection graph that connects the circuit elements of the net, said second graph having a number of edges, and calculating the length of the edges of the second connection graph;

c) to calculate the length of each edge that connects two circuit elements, constructing a bounding box that encompasses the two circuit elements, said bounding box having a long side with a length L and a short side with a length S, wherein at least one type of interconnect-line in a wiring model used by the IC layout forms an angle A with a side of the IC layout, and calculating the length (D) of the edge by using the equation D=[L−

{S (cos A/sin A)}]+S/sin A; and

d) combining the length calculations of the edges of the graph.

19. The method of claim 12, wherein the IC layout includes a plurality of nets, each net having a plurality of circuit elements, the method comprising:

a) for each particular net, constructing a connection graph that connects the circuit elements of the particular net, said connection graphs having edges, wherein some of the edges are at least partially diagonal;

b) calculating the length of the edges of the graphs; and

c) combining the length calculations to obtain an estimate of the interconnect-line length needed for connecting the circuit elements of the nets.

20. The method of claim 11, wherein the diagonal edge forms a 45°

angle with respect to a side of the IC layout.

22. The method of claim 11, wherein the circuit elements include pins of circuit modules.

23. The method of claim 11, wherein the circuit elements include circuit modules.

24. The method of claim 11, wherein the connection graph is a minimum spanning tree.

25. The method of claim 11, wherein the connection graph is a Steiner tree.

21. The method of clam 11, wherein the diagonal edge forms a 120°

angle with respect to a side of the IC layout.

26. For an electronic design automation application, a method of placing circuit modules in an integrated circuit (“

IC”

) layout, wherein said IC layout includes a plurality of nets each of which includes a plurality of circuit elements in the IC layout, wherein the EDA application includes a wiring model that defines different types of interconnect lines for connecting the circuit elements of the nets, said wiring model having diagonal lines, the method comprising;

a) for each particular net, defining a minimum spanning tree that models the topology of interconnect lines for connecting the circuit elements of the particular net, said minimum spanning trees having edges, wherein at least one of the edges of at least one of the minimum spanning trees is at least partially diagonal;

b) calculating the length of the edges of the minimum spanning trees;

c) combining the length calculations to obtain an estimate of the total interconnect-line length needed for connecting the circuit elements of the nets during a routing operation; and

d) using the combined length calculations to identify a placement of the circuit modules.

27. The method of claim 26, wherein some of the diagonal edges are in the same direction as some of the diagonal lines in the wiring model.

28. The method of claim 26 further comprising:

a) moving a circuit element from a first location in the IC layout to a second location in this layout;

b) for each net containing the moved circuit element, defining a new minimum spanning tree that models the topology of interconnect lines for connecting the circuit elements of the particular net after the move, said minimum spanning tree having edges, wherein at least one of the edges of at least one of the minimum spanning trees is at least partially diagonal; and

c) calculating the length of the new minimum spanning trees to estimate the change in the total interconnect-line length.

29. For an electronic design automation application, a method of placing circuit modules in an integrated circuit (“

IC”

) layout, wherein said IC layout includes a plurality of nets each of which includes a plurality of circuit elements in the IC layout, wherein the EDA application includes a wiring model that defines different types of interconnect lines for connecting the circuit elements of the nets, said wiring model having diagonal lines, the method comprising;

a) for each particular net, defining a Steiner tree that models the topology of interconnect lines for connecting the circuit elements of the particular net, said Steiner tree having edges, wherein at least one of the edges of at least one of the Steiner trees is at least partially diagonal;

b) calculating the length of the Steiner trees;

c) combining the length calculations to obtain an estimate of the total interconnect-line length needed for connecting the circuit elements of the nets during a routing operation; and

d) using the combined length calculations to identify a placement of the circuit modules.

30. The method of claim 29, wherein some of the diagonal edges are in the same direction as some of the diagonal lines in the wiring model.

31. The method of claim 29 further comprising defining a set of Steiner points for at least some of the nets.

32. The method of claim 29 further comprising:

a) moving a circuit element from a first location in the IC layout to a second location in this layout;

b) for each net containing the moved circuit element, defining a new Steiner tree that models the topology of interconnect lines for connecting the circuit elements of the particular net after the move, said new Steiner tree having edges, wherein at least one of the edges of at least one of the new Steiner trees is at least partially diagonal; and

c) calculating the length of the new Steiner trees to estimate the change in the total interconnect-line length.

33. A method of placing circuit modules in an integrated circuit (“

IC”

) layout, wherein said IC layout includes a set of circuit elements, the method comprising;

a) identifying a connection graph that connects the set of circuit elements, wherein said connection graph has a plurality of edges, wherein at least two of the edges are neither parallel nor orthogonal to each other;

b) identifying a placement metric based on the connection graph; and

c) using the placement metric to identify a placement of the circuit modules.

34. The method of claim 33, wherein identifying a placement metric comprises calculating the length of the graph.

35. The method of claim 34, wherein the length provides an estimate of interconnect-line length needed to connect the circuit elements of the net.

36. The method of claim 35, wherein said placement metric estimate is identified to obtain a placement cost of an initial placement configuration.

37. The method of claim 35, wherein said placement metric estimate is identified to obtain a placement cost of a modified placement configuration.

40. The method of claim 33, wherein the connection graph is a minimum spanning tree.

41. The method of claim 33, wherein the connection graph is a Steiner tree.

38. The method of clam 33, wherein the edges that are neither parallel nor orthogonal forms a 45°

angle with respect to each other.

39. The method of clam 33, wherein the edges that are neither parallel nor orthogonal forms a 120°

angle with respect to each other.