Method and system for performing timing analysis on a circuit

• US 7,155,692 B2
• Filed: 09/01/2004
• Issued: 12/26/2006
• Est. Priority Date: 09/01/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Tyler, Sean, Asprey, Thomas A.
• Primary Examiner(s): Garbowski, Leigh M.
• Application Number:
  US10/932,452
• Publication Number:
  US 20060048085A1
• Time in Patent Office: 846 Days
• Field of Search: None
• US Class Current: 716/113
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

A method and apparatus for analyzing a circuit are described herein. The circuit may comprise at least two nodes, wherein each of the nodes has timing requirements associated therewith. An embodiment of the method comprises receiving a failure time of first node, wherein the failure time represents the time within which a signal must arrive at the first node from the second node in order to avoid a timing violation of the circuit. The second node is upstream of the first node. A potential slack is determined for the first node based on the failure time of the first node, wherein the potential slack is equal to the failure time minus the sum of the target time and the delay between the first node and the second node. The analysis is terminated if the potential slack is less than a first predetermined value. The target slack at the first node is determined, wherein the target slack is equal to the timing requirement of the first node minus the sum of the timing requirement of the second node and the delay between the first node and the second node. The timing requirement of the first node may be changed or relaxed if the target slack is less than a second predetermined value.

Claims

1. A method of analyzing a circuit, said circuit comprising at least two nodes, each of said at least two nodes have timing requirements associated therewith, said method comprising:

receiving a failure time of first node, wherein said failure time represents the time within which a signal must arrive at said first node from said second node in order to avoid a timing violation of said circuit, said second node being upstream of said first node;

determining a potential slack for said first node based on said failure time of said first node, wherein said potential slack is equal to said failure time minus the sum of a target time and the delay between said first node and said second node;

terminating said analysis if said potential slack is less than a first predetermined value;

determining the target slack at said first node, wherein said target slack is equal to said timing requirement of said first node minus the sum of said timing requirement of said second node and the delay between said first node and said second node; and

changing the timing requirement of said first node if said target slack is less than a second predetermined value.

2. The method of claim 1 and further comprising recalculating said potential slack if said timing requirement is changed and terminating said analysis if said potential slack is less than said first predetermined value.

3. The method of claim 1, wherein a plurality of nodes exist downstream from said first node, and further comprising determining potential slack and target slack for said plurality of nodes.

4. The method of claim 3, wherein said analysis is terminated if said potential slack is less than said first predetermined value.

5. The method of claim 3, and further comprising determining whether said potential slack at one of said plurality of nodes is the lowest value for all the nodes analyzed, and determining timing requirement changes based on said lowest value of potential slack.

6. The method of claim 1, wherein said first predetermined value is zero.

7. The method of claim 1, wherein said second predetermined value is zero.

8. A method of analyzing a circuit, said circuit comprising at least one circuit block and a plurality of nodes, said method comprising:

creating a directed acyclic graph representative of said circuit;

creating a topological sort list from said directed acyclic graph that includes said plurality of nodes;

initializing the plurality of nodes to indicate that they have not been analyzed, wherein said analyzing comprises determining target slack and potential slack at said nodes;

obtaining data representative of timing requirements associated with a first node from said topological sort list;

changing said timing requirements associated with said first node;

determining whether said first node has been analyzed;

analyzing said first node if said first node has not been analyzed, the analyzing comprising;

determining a potential slack of said first node, wherein said potential slack is equal to a failure time associated with said first node minus the sum of a target time associated with said first node and the delay between said first node and a second node, said second node being upstream of said first node;

terminating said analyzing if said potential slack is less than a preselected value; and

determining the target slack at said first node, wherein said target slack is equal to said timing requirements of said first node minus the sum of said timing requirement of said second node and the delay between said first node and said second node;

saving said change to a timing target if said target slack is less than a predetermined value.

9. The method of claim 8, and further comprising recalculating said potential slack if said timing requirement is changed and terminating said analysis if said potential slack is less than said first predetermined value.

10. The method of claim 8, and further comprising indicating that said first node has been analyzed.

11. The method of claim 8, and further comprising determining whether a third node has been analyzed and analyzing said third node if said third node has not been analyzed.

12. The method of claim 8, wherein said first predetermined value is zero.

13. The method of claim 8, wherein said second predetermined value is zero.

14. An apparatus for analyzing a circuit, said circuit comprising at least two nodes, wherein each of said at least two nodes have timing requirements associated therewith, said apparatus comprising:

at least one computer readable medium; and

computer readable program code stored on said at least one computer readable medium, said computer readable program code comprising instructions for;

receiving a failure time of first node, wherein said failure time represents the time within which a signal must arrive at said first node from said second node in order to avoid a timing violation of said circuit, said second node being upstream of said first node;

determining a potential slack for said first node based on said failure time of said first node, wherein said potential slack is equal to said failure time minus the sum of a target time and the delay between said first node and said second node;

terminating said analysis if said potential slack is less than a first predetermined value;

determineing the target slack at said first node, wherein said target slack is equal to said timing requirement of said first node minus the sum of said timing requirement of said second node and the delay between said first node and said second node; and

changing the timing requirement of said first node if said target slack is less than a second predetermined value.

15. The apparatus of claim 14, wherein said computer readable program code further comprises instructions for recalculating said potential slack if said timing requirement is changed and terminating said analysis if said potential slack is less than a first predetermined value.

16. The apparatus of claim 14, wherein a plurality of nodes exist downstream from said first node, and wherein said computer readable program code further comprises instructions for determining potential slack and target slack for said plurality of nodes.

17. The apparatus of claim 16, wherein said computer readable program code further comprises instructions terminating said analysis if said potential slack is less than said first predetermined value.

18. The apparatus of claim 16, said computer readable program code further comprises instructions for determining whether said potential slack at one of said plurality of nodes is the lowest value for all the nodes analyzed, and determining timing requirement changes based on said lowest value of potential slack.

19. The apparatus of claim 14, wherein said first predetermined value is zero.

20. The apparatus of claim 14, wherein said second predetermined value is zero.