Method and apparatus for considering diagonal wiring in placement

• US 20020133798A1
• Filed: 12/06/2000
• Published: 09/19/2002
• 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 7,024,650 B2
• Time in Patent Office: Days
• US Class Current: 716/10
• 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, the method comprising using a diagonal line to measure a placement metric.

2. The method of claim 1, wherein using the diagonal line to measure a placement metric comprises using a diagonal cut line to measure congestion in the IC layout.

3. The method of claim 1, wherein a set of nets represents the interconnection between a set of circuit elements, each net having a number of circuit elements, wherein using the diagonal line to measure a placement metric comprises:

a) using a diagonal cut line to partition a region of the IC layout into two sub-regions;

b) measuring the number of nets that have circuit elements in both the sub-regions created by the diagonal cut line.

4. The method of claim 1, wherein the IC layout has a number of circuit elements, a net having a set of circuit elements, 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, wherein the calculation measures the length of at least one line that is at least partially diagonal.

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

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

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

8. The method of claim 6, wherein the diagonal line is 45°

line.

9. The method of claim 4, 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.

10. The method of claim 9, wherein calculating the estimate further comprises calculating the length of the edges of the graphs.

11. The method of claim 10, 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 comers of the bounding box;

b) calculating the distance (D) between the two comers 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.

12. The method of claim 9, 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.

13. The method of claim 9, 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.

15. The method of claim 14, wherein using the diagonal line to measure a placement cost comprises using a diagonal cut line to measure congestion of interconnect lines that connect the circuit elements.

16. The method of claim 15, wherein said congestion measurement quantifies the placement cost of an initial placement configuration.

17. The method of claim 15 further comprising:

a) modifying the position of at least one circuit element in the IC layout; and

b) using the diagonal cut line to measure the placement cost of the placement configuration after said modification.

18. The method of claim 14, wherein using the diagonal line to measure a placement cost comprises measuring the length of interconnect lines that connect the circuit elements by using Manhattan lines and diagonal lines.

19. The method of claim 18, wherein said length measurement quantifies the placement cost of an initial placement configuration.

20. The method of claim 18 further comprising:

a) modifying the position of at least one circuit element in the IC layout; and

b) after said modification, measuring the length of interconnect lines that connect the circuit elements by using Manhattan lines and diagonal lines.

21. The method of claim 14, wherein the circuit elements include pins of circuit modules.

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

24. The method of claim 23, wherein said attribute is the distance between two opposing comers of the bounding box, said diagonal line traversing at least a portion of said distance.

25. The method of claim 24, wherein the bounding box has a long side with a length L and a short side with a length S, said diagonal line forming an angle A with a side of the IC layout, wherein measuring the distance (D) between the two comers of the bounding box comprises using the equation D=[L−

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

26. The method of claim 25, 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.

27. The method of claim 24, wherein said distance provides an estimate of interconnect-line length needed to connect the circuit elements of the net.

28. The method of claim 27, wherein said estimate is a lower-bound estimate.

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

30. The method of claim 27 further comprising:

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

b) after said modification,

constructing a second bounding box that encompasses the circuit elements of the net; and

using a diagonal line to measure the distance between two corners of the second bounding box to obtain a second estimate of the interconnect-line length needed to connect the circuit elements of the net.

31. The method of claim 23, wherein the diagonal line forms a 45°

angle with respect to a side of the IC layout.

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

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

36. The method of claim 35, wherein the combining of said attribute measurements comprises adding said measurements.

37. The method of claim 35, wherein measuring the attribute of each particular bounding box comprises measuring the distance between two opposing corners of the particular bounding box, wherein at least a portion of said distance for some of the constructed bounding boxes is traversed by a diagonal line.

38. The method of claim 37, wherein measuring the distance between the two corners of a bounding box comprises using the equation D=[L−

{S(cos A/sin A)}]+S/sin A, wherein D is the measured distance, L is the length of a long side of the bounding box, S is zero or the length of a short side of the bounding box, and A is an angle formed by a diagonal line with a side of the IC layout when S is not zero.

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

40. The method of claim 39, wherein the wiring model further includes Manhattan lines.

41. The method of claim 35, wherein the circuit elements include pins of circuit modules.

42. The method of claim 35, wherein the circuit elements include circuit modules.

14. For an electronic design automation application, a method of placing circuit elements in an integrated circuit layout, said layout using a wiring model that includes Manhattan and diagonal lines, the method comprising using a diagonal line to measure a cost of a placement configuration.

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

IC”

) layout, wherein said IC layout includes a net and a plurality of circuit elements, said net representing interconnections between a set of circuit elements in the IC layout, the method comprising;

a) constructing a bounding box that encompasses the circuit elements of the net; and

b) using a diagonal line to measure an attribute of the bounding box.

32. The method of clam 23, wherein the diagonal line forms a 120°

angle with respect to a side of the IC layout.

35. 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 and uses a wiring model that includes diagonal lines, each net including a plurality of circuit elements in the IC layout, the method comprising;

a) for each particular net, constructing a bounding box that encompasses the circuit elements of the particular net;

b) for each particular bounding box, measuring an attribute of the particular bounding box, wherein the method uses diagonal lines to measure the attributes of some of the constructed bounding boxes; and

c) combining said attribute measurements to obtain an estimate of interconnect-line length necessary to connect the circuit elements of the nets in the IC layout.

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

IC”

) layout, wherein said IC layout includes a net and a plurality of circuit elements, wherein the net represents interconnections between a set of circuit elements, the method comprising;

constructing a connection graph that models the topology of interconnect lines for connecting the circuit elements of the net,

said connection graph having edges, each edge connecting two circuit elements of the net, wherein at least one of the edges is at least partially diagonal.

44. The method of claim 43 further comprising:

calculating the length of the edges of the graph; and

combining the length calculations of the edges of the graph.

45. The method of claim 44, wherein the combining of said length calculations comprises adding said measurements.

46. The method of claim 44, 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;

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

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

47. The method of claim 46, 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.

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

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

50. The method of claim 48 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 models the topology of interconnect lines for connecting the circuit elements of the net, said second graph having a number of edges, each edge connecting two circuit elements, 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;

calculating the length (D) of the edge by using the equation D=[L−

{S(cos A/sin A)}]+S/sin A. d) combining the length calculations of the edges of the graph.

51. The method of claim 44, 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 models the topology of interconnect lines for connecting 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.

52. The method of claim 43, wherein the diagonal edge forms a 45°

angle with respect to a side of the IC layout.

54. The method of claim 43, wherein the circuit elements include pins of circuit modules.

55. The method of claim 43, wherein the circuit elements include circuit modules.

56. The method of claim 43, wherein the connection graph is a minimum spanning tree.

57. The method of claim 43, wherein the connection graph is a Steiner tree.

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

60. The method of claim 58 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 trees having edges, wherein at least one of the edges of at least one of the minimum spanning trees is at least partially diagonal,

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

53. The method of clam 43, wherein the diagonal edge forms a 120°

angle with respect to a side of the IC layout.

58. 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; and

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

61. 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 trees 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; and

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

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

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

64. The method of claim 61 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 trees having edges, wherein at least one of the edges of at least one of the new Steiner trees is at least partially diagonal,

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

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

IC”

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

a) partitioning a region of the IC layout into two sub-regions by using a diagonal cut line;

b) measuring the number of nets that have circuit elements in both the sub-regions created by the diagonal cut line.

66. The method of claim 65 further comprising changing the positions of the circuit elements in said region to reduce the number of nets that have circuit elements in both sub-regions.

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

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

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

70. The method of claim 66 further comprising:

a) partitioning one of the sub-regions into two smaller sub-regions by using a second cut line;

b) measuring the number of nets that have circuit elements in both of the smaller sub-regions created by the second cut line.

71. The method of claim 70 wherein the second cut line is a diagonal line.

72. The method of claim 70 wherein the second cut line is a vertical line.

73. The method of claim 70 wherein the second cut line is a horizontal line.

74. The method of claim 70 further comprising changing the positions of the circuit elements in the sub-region to reduce the number of nets that have circuit elements in both of the smaller sub-regions.

75. The method of claim 65, wherein said region was defined by partitioning a bigger region by using a third cut line.

76. The method of claim 75, wherein the third cut line is a diagonal line.

77. The method of claim 75, wherein the third cut line is a vertical line.

78. The method of claim 75, wherein the third cut line is a horizontal line.

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

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

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

83. The method of claim 79 further comprising:

a) defining a second cut line that partitions one of the sub-regions into two smaller sub-regions;

b) determining the number of nets intersected by the second cut line; and

c) changing the positions of the circuit modules between the smaller sub-regions to minimize the number of nets intersected by the diagonal cut line.

84. The method of claim 83 wherein the second cut line is one of a diagonal line, a horizontal line, and a vertical line.

85. The method of claim 83 further comprising changing the positions of the circuit elements in the sub-region partitioned by the second cut line to reduce the number of nets that have circuit elements in both of the smaller sub-regions.

86. The method of claim 79, wherein said region was defined by partitioning a bigger region by using a third cut line.

87. The method of claim 86, wherein the third cut line is one of a diagonal line, a vertical line, and a horizontal line.

79. For an electronic design automation application, a method of placing circuit modules in an integrated circuit layout, wherein the application uses a set of nets, and each net specifies a set of circuit elements in the layout, the method comprising:

a) defining a diagonal cut line that partitions a region of the IC layout into two sub-regions;

b) determining the number of nets intersected by the diagonal cut line;

c) changing the positions of the circuit modules between the sub-regions to minimize the number of nets intersected by the diagonal cut line.