Min-time / race margins in digital circuits

• US 6,698,005 B2
• Filed: 02/19/2002
• Issued: 02/24/2004
• Est. Priority Date: 02/19/2002
• Status: Expired due to Term

• Current Assignee: Lexmark International Incorporated (Ninestar Corporation), Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lindkvist, Hans
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): LEVIN, NAUM B
• Application Number:
  US10/076,434
• Publication Number:
  US 20030159118A1
• Time in Patent Office: 735 Days
• Field of Search: 716/4-6, 716/16, 703/19, 703/23
• US Class Current: 716/108
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

Abstract

A preferred timing change is automatically selected from a set of candidate timing changes that can be made to address a short path violation in a circuit design. This involves determining an associated cost metric for each of the candidate timing changes, and identifying a lowest cost metric from the associated cost metrics. The candidate timing change associated with the lowest cost metric is selected from the set of candidate timing changes, for use as the preferred timing change. The associated cost metric may represent a cost per resolved source or destination register. Candidate timing changes may variously involve any of a number of techniques for introducing additional delays into a short path of the circuit.

Claims

1. A method of automatically selecting a preferred timing change from a set of candidate timing changes that can be made to address a timing problem in a circuit design, the method comprising:

determining an associated cost metric for each of the candidate timing changes, wherein the associated cost metric is based upon a number of timing problems resolved by the candidate timing change;

identifying a lowest cost metric from the associated cost metrics; and

selecting for use as the preferred timing change, from the set of candidate timing changes, the candidate timing change associated with the lowest cost metric.

2. The method of claim 1, wherein the timing problem is associated with signals that are associated with a normal operation of the circuit.

3. The method of claim 1, wherein the associated cost metric represents a cost per resolved source or destination register.

4. The method of claim 1, wherein determining the associated cost metric for one of the candidate timing changes comprises:

determining a total cost of implementing said one of the candidate timing changes;

determining a first number that represents a sum of how many source registers supply a signal to one or more circuit paths whose timing violations would be resolved by said one of the candidate timing changes and how many destination registers receive a signal from one or more circuit paths whose timing violations would be resolved by said one of the candidate timing changes; and

generating the associated cost metric for said one of the candidate timing changes by dividing the total cost of implementing said one of the candidate timing changes by the first number.

5. The method of claim 1, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing one or more cascaded buffers between the one or more logic elements and the destination register.

6. The method of claim 5, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

7. The method of claim 5, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many destination registers receive a signal from one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

8. The method of claim 1, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths that are associated with short path violations; and

the set of candidate timing changes includes a first candidate timing change that involves interposing one or more cascaded buffers between one or more of the one or more source registers and one or more of the short paths.

9. The method of claim 8, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

10. The method of claim 8, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many destination registers receive a signal from one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

11. The method of claim 1, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a lockup latch between the one or more logic elements and the destination register.

12. The method of claim 11, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

13. The method of claim 11, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

14. The method of claim 1, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a trailing edge-triggered flip-flop between the one or more logic elements and the destination register.

15. The method of claim 14, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

16. The method of claim 14, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

17. The method of claim 1, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves replacing the destination register by a register that samples on a trailing edge and outputs on a leading-edge of a clock signal.

18. The method of claim 17, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

19. The method of claim 17, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

20. The method of claim 1, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a lockup latch between one or more of the one or more source registers and one or more of the short paths.

21. The method of claim 20, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

22. The method of claim 20, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

23. The method of claim 1, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a trailing edge-triggered flip-flop between one or more of the one or more source registers and one or more of the short paths.

24. The method of claim 23, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

25. The method of claim 23, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

26. The method of claim 1, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves replacing one or more of the one or more source registers by one or more registers that each sample on a leading edge and output on a trailing edge of a clock signal.

27. The method of claim 26, wherein determining the associated cost metric for the first candidate timing change comprises:

determining a total cost of implementing the first candidate timing change;

determining a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

generating the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

28. The method of claim 26, wherein determining the associated cost metric for the first candidate timing change comprises:

tagging the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

29. A method of automatically selecting a set of preferred timing changes from a set of candidate timing changes that can be made to address a set of timing problems in a circuit design, the method comprising:

for each of the timing problems, determining an associated cost metric for each of the candidate timing changes;

identifying a least expensive set of candidate timing changes that address the entire set of timing problems and whose combined cost metrics are a lowest combined cost metric;

selecting for use as the set of preferred timing changes, from the set of candidate timing changes, the least expensive set of candidate timing changes.

30. An apparatus that automatically selects a preferred timing change from a set of candidate timing changes that can be made to address a timing problem in a circuit design, the apparatus comprising:

logic that determines an associated cost metric for each of the candidate timing changes, wherein the associated cost metric is based upon a number of timing problems resolved by the candidate timing change;

logic that identifies a lowest cost metric from the associated cost metrics; and

logic that selects for use as the preferred timing change, from the set of candidate timing changes, the candidate timing change associated with the lowest cost metric.

31. The apparatus of claim 30, wherein the timing problem is associated with signals that are associated with a normal operation of the circuit.

32. The apparatus of claim 30, wherein the associated cost metric represents a cost per resolved source or destination register.

33. The apparatus of claim 30, wherein the logic that determines the associated cost metric for one of the candidate timing changes comprises:

logic that determines a total cost of implementing said one of the candidate timing changes;

logic that determines a first number that represents a sum of how many source registers supply a signal to one or more circuit paths whose timing violations would be resolved by said one of the candidate timing changes and how many destination registers receive a signal from one or more circuit paths whose timing violations would be resolved by said one of the candidate timing changes; and

logic that generates the associated cost metric for said one of the candidate timing changes by dividing the total cost of implementing said one of the candidate timing changes by the first number.

34. The apparatus of claim 30, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing one or more cascaded buffers between the one or more logic elements and the destination register.

35. The apparatus of claim 34, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

36. The apparatus of claim 34, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many destination registers receive a signal from one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

37. The apparatus of claim 30, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths that are associated with short path violations; and

the set of candidate timing changes includes a first candidate timing change that involves interposing one or more cascaded buffers between one or more of the one or more source registers and one or more of the short paths.

38. The apparatus of claim 37, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

39. The method of claim 37, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many destination registers receive a signal from one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

A logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

40. The apparatus of claim 30, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a lockup latch between the one or more logic elements and the destination register.

41. The apparatus of claim 40, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

42. The apparatus of claim 40, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

43. The apparatus of claim 30, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a trailing edge-triggered flip-flop between the one or more logic elements and the destination register.

44. The apparatus of claim 43, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

45. The apparatus of claim 43, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

46. The apparatus of claim 30, wherein:

the circuit design includes one or more short paths, each short path being associated with a short path violation and comprising one or more logic elements that generate a signal to be supplied to a destination register; and

the set of candidate timing changes includes a first candidate timing change that involves replacing the destination register by a register that samples on a trailing edge and outputs on a leading-edge of a clock signal.

47. The apparatus of claim 46, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many source registers supply a signal to one or more of the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

48. The apparatus of claim 46, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

49. The apparatus of claim 30, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a lockup latch between one or more of the one or more source registers and one or more of the short paths.

50. The apparatus of claim 49, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

51. The apparatus of claim 49, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

52. The apparatus of claim 30, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves interposing a trailing edge-triggered flip-flop between one or more of the one or more source registers and one or more of the short paths.

53. The apparatus of claim 52, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

54. The apparatus of claim 52, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

55. The apparatus of claim 30, wherein:

the circuit design includes one or more source registers, each of which supplies a signal to one or more short paths, wherein each short path is associated with a short path violation; and

the set of candidate timing changes includes a first candidate timing change that involves replacing one or more of the one or more source registers by one or more registers that each sample on a leading trailing edge and output on a trailing edge of a clock signal.

56. The apparatus of claim 55, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that determines a total cost of implementing the first candidate timing change;

logic that determines a first number that represents how many destination registers receive a signal from the one or more short paths whose timing violations would be resolved by the first candidate timing change; and

logic that generates the associated cost metric for the first candidate timing change by dividing the total cost of implementing the first candidate timing change by the first number.

57. The apparatus of claim 55, wherein the logic that determines the associated cost metric for the first candidate timing change comprises:

logic that tags the associated cost metric as infinite if it is not possible to implement the first candidate timing change in the circuit design.

58. An apparatus that automatically selects a set of preferred timing changes from a set of candidate timing changes that can be made to address a set of timing problems in a circuit design, the apparatus comprising:

logic that determines, for each of the timing problems, an associated cost metric for each of the candidate timing changes;

logic that identifies a least expensive set of candidate timing changes that address the entire set of timing problems and whose combined cost metrics are a lowest combined cost metric; and

logic that selects for use as the set of preferred timing changes, from the set of candidate timing changes, the least expensive set of candidate timing changes.