Method and apparatus for automated circuit design

• US 20040243964A1
• Filed: 05/27/2004
• Published: 12/02/2004
• Est. Priority Date: 05/30/2003
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synplicity, Inc. (Synopsys Incorporated)
• Inventors: McElvain, Kenneth S., Ramachandran, Champaka, Crews, Andrew
• Granted Patent: US 7,251,800 B2
• Time in Patent Office: Days
• US Class Current: 716/12
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36

Abstract

Methods and apparatuses to automatically modify a circuit design according to the possible deviation in the subsequent implementation of the circuit. In one aspect, a method to design a circuit includes: determining whether a design constraint is likely to be violated during a subsequent routing implementation of a design of the circuit; and, modifying the design of the circuit to reduce likelihood of the design constraint being violated during a subsequent implementation. For example, a route for a net with a number of fanout larger than two and on a timing critical or near-critical path may be considered sensitive to route topology such that an alternative routing path may lead to a violation in timing constraint; to reduce the possibility of a timing problem in a subsequent routing solution, a transformation can be selectively applied to the circuit design to an extent not worsening a cost function.

Claims

1. A method to design a circuit, the method comprising:

determining whether or not a design constraint is likely to be violated during a subsequent routing implementation of a design of the circuit; and

modifying the design of the circuit to reduce likelihood of the design constraint being violated during a subsequent routing implementation of the design.

2. The method of claim 1, wherein the likelihood of the design constraint being violated in a subsequent routing implementation of the design is due to uncertainty in estimating route topology.

3. The method of claim 1, wherein the likelihood of the design constraint being violated in a subsequent routing implementation of the design is due to uncertainty in estimating a parameter for a route topology.

4. The method of claim 3, further comprising:

determining whether or not a route topology in the design of the circuit causes reduced accuracy in determining a parameter associated with the design constraint.

5. The method of claim 1, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined based at least on a bounding box enclosing load elements of a drive element.

6. The method of claim 5, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined further based on a number of fanout of a net on a timing critical or near-critical path;

wherein the net connects the drive element to the load elements.

7. The method of claim 1, wherein said modifying comprises:

replicating a first drive element to insert a second drive element; and

reconnecting a portion of load elements of the first drive element as load elements of the second drive element.

8. The method of claim 1, wherein said modifying comprises:

inserting a buffer element as a load element of a first drive element; and

reconnecting a portion of load elements of the first drive element as load elements of the buffer element.

9. The method of claim 1, wherein said modifying comprises:

rearranging placement of load elements of a drive element to reduce a ratio of a short side over a long side of a bounding box of the drive element and the load elements.

10. The method of claim 1, wherein said modifying comprises:

transforming a portion of load elements of a first element as load elements of a second element.

11. The method of claim 1, wherein the design constraint comprises a timing constraint.

12. The method of claim 11, wherein the timing constraint comprises one of:

a) worst negative slack of the circuit;

b) a slack for an instance of a logic element in the design of the circuit;

c) a delay on a path in the design of the circuit; and

d) a total negative slack of the circuit.

13. The method of claim 1, wherein the design constraint comprises a design rule.

14. The method of claim 13, wherein the design rule comprises one of:

a) maximum capacitance; and

b) maximum length of wire between a driver element and a load element.

15. The method of claim 1, wherein said modifying comprises:

determining a number of net candidates each of which may cause a violation in the design constraint when alternative route topology is used; and

selectively modifying the design for a subset of the number of net candidates.

16. The method of claim 15, wherein said selectively modifying comprises:

selecting one from the number of net candidates according to flow, the flow representing a weighted count of a number of paths passing through a net candidate.

17. The method of claim 16, wherein the number of paths are one of:

all paths passing through the net candidate;

negative slack paths passing through the net candidate;

congested paths passing through the net candidate; and

paths with sensitive nets passing through the net candidate.

18. The method of claim 15, wherein said selectively modifying comprises:

performing a min-cut on a graph with the number of net candidates to determine the subset for modification.

19. A machine implemented method to design a circuit, the method comprising:

estimating a first distance between a drive element and a load element of the drive element according to a design of the circuit;

verifying whether or not a timing constraint is satisfied using the first distance;

estimating a second distance between the drive element and the load element according to the design of the circuit, the second distance being longer than the first distance; and

determining whether or not a timing constraint is satisfied using the second distance.

20. The method of claim 19, wherein the first distance is according to a first route topology;

and the second distance is according to a second route topology.

21. The method of claim 19, further comprising:

in response to a determination that a timing constraint is not satisfied when the second distance is used, determining whether or not a transformation can be performed on the design of the circuit to reduce the second distance without worsening a design cost function.

22. The method of claim 21, wherein the transformation comprises at least one of:

replicating the drive element;

sizing up the drive element;

inserting a buffer element between the drive element and the load element; and

adjusting placement of at least one element of;

the drive element and load elements of the drive element.

23. The method of claim 19, wherein the second distance is estimated only when a net connecting the drive element and the load element is selected for reduction of route topology sensitivity.

24. The method of claim 23, wherein the net is selected only when the net is on a timing critical or near-critical path and a number of fanout of the net is larger than two.

25. The method of claim 24, wherein the net is further selected according to an aspect ratio of a bounding box enclosing load elements of the drive element.

26. A machine implemented method to estimate a path delay, the method comprising:

determining a shape of a region of;

a drive element, and

a plurality of load elements of the drive element; and

estimating a distance between the drive element and a first one of the plurality of load elements based at least on the shape of the region.

27. The method of claim 26, wherein said determining the shape of the region comprises:

determining a bounding box enclosing the plurality of load elements;

wherein the distance is estimated based at least on the bounding box.

28. The method of claim 27, wherein said estimating comprises:

determining a Manhattan distance between the drive element and the first one of the plurality of load elements;

wherein the distance is estimated as a function of the Manhattan distance and a length of a short side of the bounding box.

29. The method of claim 28, wherein the bounding box is rectangular.

30. A machine readable medium containing executable computer program instructions which when executed by a data processing system cause said system to perform a method to design a circuit, the method comprising:

determining whether or not a design constraint is likely to be violated during a subsequent routing implementation of a design of the circuit; and

modifying the design of the circuit to reduce likelihood of the design constraint being violated during a subsequent routing implementation of the design.

31. The medium of claim 30, wherein the likelihood of the design constraint being violated in a subsequent routing implementation of the design is due to uncertainty in estimating route topology.

32. The medium of claim 30, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined based at least on a bounding box enclosing load elements of a drive element.

33. The medium of claim 32, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined further based on a number of fanout of a net on a timing critical or near-critical path;

wherein the net connects the drive element to the load elements.

34. The medium of claim 30, wherein said modifying comprises:

replicating a first drive element to insert a second drive element; and

reconnecting a portion of load elements of the first drive element as load elements of the second drive element.

35. The medium of claim 30, wherein said modifying comprises:

inserting a buffer element as a load element of a first drive element; and

reconnecting a portion of load elements of the first drive element as load elements of the buffer element.

36. The medium of claim 30, wherein said modifying comprises:

rearranging placement of load elements of a drive element to reduce a ratio of a short side over a long side of a bounding box of the drive element and the load elements.

37. The medium of claim 30, wherein said modifying comprises:

transforming a portion of load elements of a first element as load elements of a second element.

38. The medium of claim 30, wherein the design constraint comprises a timing constraint.

39. The medium of claim 38, wherein the timing constraint comprises one of:

a) worst negative slack of the circuit;

b) a slack for an instance of a logic element in the design of the circuit;

c) a delay on a path in the design of the circuit; and

d) a total negative slack of the circuit.

40. The medium of claim 30, wherein said modifying comprises:

determining a number of net candidates each of which may cause a violation in the design constraint when alternative route topology is used; and

selectively modifying the design for a subset of the number of net candidates.

41. The medium of claim 40, wherein said selectively modifying comprises:

selecting one from the number of net candidates according to flow, the flow representing a weighted count of a number of paths passing through a net candidate.

42. The medium of claim 41, wherein the number of paths are one of:

all paths passing through the net candidate;

negative slack paths passing through the net candidate;

congested paths passing through the net candidate; and

paths with sensitive nets passing through the net candidate.

43. The medium of claim 40, wherein said selectively modifying comprises:

performing a min-cut on a graph with the number of net candidates to determine the subset for modification.

44. A machine readable medium containing executable computer program instructions which when executed by a data processing system cause said system to perform a method to design a circuit, the method comprising:

estimating a first distance between a drive element and a load element of the drive element according to a design of the circuit;

verifying whether or not a timing constraint is satisfied using the first distance;

estimating a second distance between the drive element and the load element according to the design of the circuit, the second distance being longer than the first distance; and

determining whether or not a timing constraint is satisfied using the second distance.

45. The medium of claim 44, wherein the first distance is according to a first route topology;

and the second distance is according to a second route topology.

46. The medium of claim 44, wherein the method further comprises:

in response to a determination that a timing constraint is not satisfied when the second distance is used, determining whether or not a transformation can be performed on the design of the circuit to reduce the second distance without worsening a design cost function.

47. The medium of claim 46, wherein the transformation comprises at least one of:

replicating the drive element;

sizing up the drive element;

inserting a buffer element between the drive element and the load element; and

adjusting placement of at least one element of;

the drive element and load elements of the drive element.

48. The medium of claim 44, wherein the second distance is estimated only when a net connecting the drive element and the load element is selected for reduction of route topology sensitivity.

49. The medium of claim 48, wherein the net is selected only when the net is on a timing critical or near-critical path and a number of fanout of the net is larger than two.

50. The medium of claim 49, wherein the net is further selected according to an aspect ratio of a bounding box enclosing load elements of the drive element.

51. A machine readable medium containing executable computer program instructions which when executed by a data processing system cause said system to perform a method to estimate a path delay, the method comprising:

determining a shape of a region of;

a drive element, and

a plurality of load elements of the drive element; and

estimating a distance between the drive element and a first one of the plurality of load elements based at least on the shape of the region.

52. The medium of claim 51, wherein said determining the shape of the region comprises:

determining a bounding box enclosing the plurality of load elements;

wherein the distance is estimated based at least on the bounding box.

53. The medium of claim 52, wherein said estimating comprises:

determining a Manhattan distance between the drive element and the first one of the plurality of load elements;

wherein the distance is estimated as a function of the Manhattan distance and a length of a short side of the bounding box.

54. The medium of claim 53, wherein the bounding box is rectangular.

55. A data processing system to design a circuit, the data processing system comprising:

means for determining whether or not a design constraint is likely to be violated during a subsequent routing implementation of a design of the circuit; and

means for modifying the design of the circuit to reduce likelihood of the design constraint being violated during a subsequent routing implementation of the design.

56. The data processing system of claim 55, wherein the likelihood of the design constraint being violated in a subsequent routing implementation of the design is due to uncertainty in estimating route topology.

57. The data processing system of claim 55, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined based at least on a bounding box enclosing load elements of a drive element.

58. The data processing system of claim 57, wherein whether or not the design constraint is likely to be violated during a subsequent routing implementation of the design is determined further based on a number of fanout of a net on a timing critical or near-critical path;

wherein the net connects the drive element to the load elements.

59. The data processing system of claim 55, wherein said means for modifying comprises:

means for replicating a first drive element to insert a second drive element; and

means for reconnecting a portion of load elements of the first drive element as load elements of the second drive element.

60. The data processing system of claim 55, wherein said means for modifying comprises:

means for inserting a buffer element as a load element of a first drive element; and

means for reconnecting a portion of load elements of the first drive element as load elements of the buffer element.

61. The data processing system of claim 55, wherein said means for modifying comprises:

means for rearranging placement of load elements of a drive element to reduce a ratio of a short side over a long side of a bounding box of the drive element and the load elements.

62. The data processing system of claim 55, wherein said means for modifying comprises:

means for transforming a portion of load elements of a first element as load elements of a second element.

63. The data processing system of claim 55, wherein the design constraint comprises a timing constraint.

64. The data processing system of claim 63, wherein the timing constraint comprises one of:

a) worst negative slack of the circuit;

b) a slack for an instance of a logic element in the design of the circuit;

c) a delay on a path in the design of the circuit; and

d) a total negative slack of the circuit.

65. The data processing system of claim 55, wherein said means for modifying comprises:

means for determining a number of net candidates each of which may cause a violation in the design constraint when alternative route topology is used; and

means for selectively modifying the design for a subset of the number of net candidates.

66. The data processing system of claim 65, wherein said means for selectively modifying comprises:

means for selecting one from the number of net candidates according to flow, the flow representing a weighted count of a number of paths passing through a net candidate.

67. The data processing system of claim 66, wherein the number of paths are one of:

all paths passing through the net candidate;

negative slack paths passing through the net candidate;

congested paths passing through the net candidate; and

paths with sensitive nets passing through the net candidate.

68. The data processing system of claim 65, wherein said means for selectively modifying comprises:

means for performing a min-cut on a graph with the number of net candidates to determine the subset for modification.

69. A data processing system to design a circuit, the data processing system comprising:

means for estimating a first distance between a drive element and a load element of the drive element according to a design of the circuit;

means for verifying whether or not a timing constraint is satisfied using the first distance;

means for estimating a second distance between the drive element and the load element according to the design of the circuit, the second distance being longer than the first distance; and

means for determining whether or not a timing constraint is satisfied using the second distance.

70. The data processing system of claim 69, wherein the first distance is according to a first route topology;

and the second distance is according to a second route topology.

71. The data processing system of claim 69, further comprising:

means for, in response to a determination that a timing constraint is not satisfied when the second distance is used, determining whether or not a transformation can be performed on the design of the circuit to reduce the second distance without worsening a design cost function.

72. The data processing system of claim 71, wherein the transformation comprises at least one of:

replicating the drive element;

sizing up the drive element;

inserting a buffer element between the drive element and the load element; and

adjusting placement of at least one element of;

the drive element and load elements of the drive element.

73. The data processing system of claim 69, wherein the second distance is estimated only when a net connecting the drive element and the load element is selected for reduction of route topology sensitivity.

74. The data processing system of claim 73, wherein the net is selected only when the net is on a timing critical or near-critical path and a number of fanout of the net is larger than two.

75. The data processing system of claim 74, wherein the net is further selected according to an aspect ratio of a bounding box enclosing load elements of the drive element.

76. A data processing system to estimate a path delay, the data processing system comprising:

means for determining a shape of a region of;

a drive element, and

a plurality of load elements of the drive element; and

means for estimating a distance between the drive element and a first one of the plurality of load elements based at least on the shape of the region.

77. The data processing system of claim 76, wherein said means for determining the shape of the region comprises:

means for determining a bounding box enclosing the plurality of load elements;

wherein the distance is estimated based at least on the bounding box.

78. The data processing system of claim 77, wherein said means for estimating comprises:

means for determining a Manhattan distance between the drive element and the first one of the plurality of load elements;

wherein the distance is estimated as a function of the Manhattan distance and a length of a short side of the bounding box.

79. The data processing system of claim 78, wherein the bounding box is rectangular.