Method and apparatus for utilizing long-path and short-path timing constraints in an electronic-design-automation tool for routing

• US 7,308,664 B1
• Filed: 02/09/2004
• Issued: 12/11/2007
• Est. Priority Date: 02/09/2004
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Fung, Ryan, Betz, Vaughn, Chow, William
• Primary Examiner(s): Chiang, Jack
• Assistant Examiner(s): TAT, BINH C
• Application Number:
  US10/774,857
• Time in Patent Office: 1,401 Days
• Field of Search: 716 1- 6, 716 8- 12, 716/18
• US Class Current: 716/114
• CPC Class Codes: G06F 2119/12 Timing analysis or timing optimisation
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method for designing a system includes determining minimum and maximum delay budgets for connections. Routing resources are selected for connections in response to the minimum and maximum delay budgets.

Claims

1. A method for designing a system, comprising:

determining minimum and maximum delay budgets for connections along a path by finding a set of connection delays that satisfy a short-path timing constraint for the path, which indicates that the delay from one end of the path to an other end must be no smaller than a first value, and a long-path timing constraints for the path, which indicates that the delay from one end of the path to the other end must be no larger than a second value; and

selecting routing resources for implementing the connections in the system in response to the minimum and maximum delay budgets.

2. The method of claim 1, wherein determining minimum and maximum delay budgets comprises considering lower and upper delay limits of routed connections based on potential routing possibilities.

3. The method of claim 2, wherein, lower delay limits of the routed connections are determined based on an initial selection of routing resources that minimizes connection delays and ignores shorted signals.

4. The method of claim 1, wherein determining minimum and maximum delay budgets comprises starting with initial estimates of final routed delay.

5. The method of claim 4, wherein estimates of final routed delay are determined based on an initial selection of routing resources for connections that minimizes connection delay.

6. The method of claim 4, wherein estimates of final routed delay are determined based on an initial selection of routing resources for connections that ignores shorted signals.

7. The method of claim 1, wherein the short-path and long-path timing constraints are provided by a user.

8. The method of claim 1, wherein determining minimum and maximum delay budgets for the connections comprises allocating short-path and long-path slack.

9. The method of claim 8, wherein allocating comprises:

performing short-path timing analysis to determine short-path slack values;

fixing any short-path violations determined by the short-path timing analysis;

performing long-path timing analysis to determine long-path slack values; and

fixing any long-path violations determined by the long-path timing analysis.

10. The method of claim 9, wherein fixing any short-path violations comprises adding delay in response to the short-path slack values and connection weightings.

11. The method of claim 9, wherein the connection weightings are determined by a unit weighting scheme.

12. The method of claim 9, wherein the connection weighting is determined based on how much delay can be added before a practical limit is reached or all relevant violations are resolved.

13. The method of claim 9, wherein fixing any long-path violations comprises subtracting delay in response to the long-path slack values and connection weightings.

14. The method of claim 8, wherein allocating the long-path and short-path slack comprises:

performing long-path timing analysis to determine long-path slack values;

allocating long-path slack determined by the long-path timing analysis;

performing short-path timing analysis to determine short-path slack values; and

allocating short-path slack determined by the short-path timing analysis.

15. The method of claim 14, wherein allocating long-path slack comprises adding delay to temporary delays in response to the long-path slack values and connection weightings.

16. The method of claim 15, wherein the connection weightings are determined by a unit weighting scheme.

17. The method of claim 15, wherein the connection weighting is determined based on how much delay can be added before a practical limit is reached or all relevant slack is allocated.

18. The method of claim 14, wherein allocating short-path slack comprises subtracting delay from temporary delays in response to the short-path slack values and connection weightings.

19. The method of claim 1, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises re-selecting the routing resources for connections whose current proposed routes do not meet the minimum and maximum delay budgets.

20. The method of claim 1, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises re-selecting the routing resources for connections that are shorted.

21. The method of claim 1, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises decreasing minimum delay budgets based on the number of routing iterations that have occurred.

22. The method of claim 21, wherein decreasing minimum delay budgets based on the number of routing iterations that have occurred comprises decreasing the minimum delay budgets of connections that are competing for routing resources other connections want.

23. The method of claim 1, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises increasing maximum delay budgets based on the number of routing iterations that have occurred.

24. The method of claim 23, wherein increasing maximum delay budgets based on the number of routing iterations that have occurred comprises increasing the maximum delay budgets of connections that are competing for routing resources other connections want.

25. The method of claim 1, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises utilizing a cost function.

26. The method of claim 25, wherein the cost function scores routing resources as candidates for selection in completing a connection route.

27. The method of claim 26, wherein the lowest cost routing resource is efficiently tracked via use of a heap.

28. The method of claim 26, wherein the cost function for a routing resource is based, in part, on the delay of the respective routing resource.

29. The method of claim 26, wherein the cost function for a routing resource is based, in part, on a prediction of the delay to reach the destination from the respective routing resource.

30. The method of claim 29, wherein the prediction of the delay to reach the destination from the respective routing resource is based, in part, on the minimum and maximum delay budget.

31. The method of claim 26, wherein the cost function for a routing resource is based, in part, on how the total estimated routing delay of the connection if the routing resource is used compares with the minimum and maximum delay budget of the connection.

32. The method of claim 26, wherein the cost function for a routing resource is based, in part, on the number of competing signals that want to use the respective routing resource.

33. The method of claim 32, further comprising increasing the penalty associated with several competing signals wanting to use the same resource in the cost function as connection re-routing attempts occur.

34. The method of claim 33, further comprising increasing the penalty associated with several competing signals wanting to use the same resource in the cost function, based, in part, on how many signals wanted to use the resource in previous routing attempts.

35. The method of claim 33, further comprising increasing the penalty associated with several competing signals wanting to use the same resource in the cost function, based, in part, on how many routing iterations have occurred.

36. The method of claim 26, wherein the cost function for a routing resource is based, in part, on the delay incurred reaching the respective routing resource from the connection source.

37. The method of claim 1, wherein the short-path timing constraints comprises a hold time requirement.

38. The method of claim 1, wherein the short-path timing constraints comprises a minimum propagation delay.

39. The method of claim 1, wherein the short-path timing constraints comprises a minimum clock-to-output requirement.

40. The method of claim 1, wherein selecting routing resources for the connections in response to the minimum and maximum delay budgets increases delay for the connections.

41. The method of claim 1, wherein the routing resources are programmable logic device routing resources.

42. A machine-readable medium having stored thereon sequences of instructions, the sequences of instructions including instructions which, when executed by a processor, causes the processor to perform:

determining minimum and maximum delay budgets for connections along a path by finding a set of connection delays that satisfy a short-path timing constraint for the path, which indicates that a delay from one end of the path to an other end must be no smaller than a first value, and a long-path timing constraint for the path, which indicates that a delay from one end of the path to an other end must be no larger than a second value; and

selecting routing resources for implementing the connections in the system in response to the minimum and maximum delay budgets.

43. The machine-readable medium of claim 42, wherein determining minimum and maximum delay budgets comprises considering lower and upper delay limits of routed connections based on potential routing possibilities.

44. The machine-readable medium of claim 43, wherein lower delay limits of the routed connections are determined based on an initial selection of routing resources that minimizes connection delays and ignores shorted signals.

45. The machine-readable medium of claim 42, wherein determining minimum and maximum delay budgets comprises starting with initial estimates of final routed delay.

46. The machine-readable medium of claim 45, wherein estimates of final routed delay are determined based on an initial selection of routing resources for connections that minimizes connection delay.

47. The machine-readable medium of claim 45, wherein estimates of final routed delay are determined based on an initial selection of routing resources for connections that ignores shorted signals.

48. The machine-readable medium of claim 42, wherein the short-path and long-path timing constraints are provided by a user.

49. The machine-readable medium of claim 42, wherein determining minimum and maximum delay budgets for the connections comprises allocating short-path and long-path slack.

50. The machine-readable medium of claim 49, wherein allocating comprises:

performing short-path timing analysis to determine short-path slack values;

fixing any short-path violations determined by the short-path timing analysis;

performing long-path timing analysis to determine long-path slack values; and

fixing any long-path violations determined by the long-path timing analysis.

51. The machine-readable medium of claim 49, wherein allocating the long-path and short-path slack comprises;

performing long-path timing analysis to determine long-path slack values;

allocating long-path slack determined by the long-path timing analysis;

performing short-path timing analysis to determine short-path slack values; and

allocating short-path slack determined by the short-path timing analysis.

52. The machine-readable medium of claim 42, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises re-selecting the routing resources for connections whose current proposed routes do not meet the minimum and maximum delay budgets.

53. The machine-readable medium of claim 42, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises re-selecting the routing resources for connections that are shorted.

54. The machine-readable medium of claim 42, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises decreasing minimum delay budgets based on the number of routing iterations that have occurred.

55. The machine-readable medium of claim 42, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises increasing maximum delay budgets based on the number of routing iterations that have occurred.

56. The machine-readable medium of claim 42, wherein selecting routing resources for connections in response to the minimum and maximum delay budgets comprises utilizing a cost function.

57. A system designer, comprising:

a slack allocator unit that generates minimum and maximum delay budgets for connections along a path from a long-path timing constraint, which indicates that a delay from one end of the path to an other end must be no larger than a first value, and a short-path timing constraint for the path, which indicates that a delay from one end of the path to an other end must be no smaller than a second value; and

a routing unit that selects routing resources to implement the connections in a system in response to the minimum and maximum delay budgets.

58. The system designer of claim 57, wherein the slack allocator comprises a timing analysis unit that generates long-path and short-path slack values for the connections in response to connection delays and the long-path and short-path timing constraints.

59. The system designer of claim 57, wherein the slack allocator comprises a delay adjustment unit that modifies a set of temporary connection delays in order to attempt to satisfy the long-path and short-path timing constraints.

60. The system designer of claim 57, wherein the slack allocator comprises a delay adjustment unit that modifies a set of temporary connection delays to allocate long-path and short-path slack.