Upper-bound calculation for placed circuit design performance

• US 7,051,312 B1
• Filed: 06/24/2003
• Issued: 05/23/2006
• Est. Priority Date: 06/24/2003
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Rahut, Anirban, Nag, Sudip K.
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): TO, TUYEN P
• Application Number:
  US10/603,219
• Time in Patent Office: 1,064 Days
• Field of Search: 716/12, 716/13, 716/14
• US Class Current: 716/113
• 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/396 Clock trees

Abstract

Within a computer automated tool, a method (400) of estimating an upper-bound of an operational frequency of at least a portion of a placed circuit design can include identifying (405) a clock source within the placed circuit design, wherein the clock source is associated with a clock domain, and determining (410) an initial routing of the clock domain. The method also can include determining (420) a minimum path slack corresponding to each connection of the clock domain. Connections of the clock domain which have a lowest minimum path slack can be marked (430). One or more marked connections which are not routed in delay mode can be identified and routed in delay mode (455) allowing sharing of routing resources by different nets.

Claims

1. Within a computer automated tool, a method of estimating an upper-bound for an operational frequency of at least a portion of a placed circuit design comprising:

(a) identifying a clock source within the placed circuit design, wherein the clock source is associated with a clock domain;

(b) determining an initial routing of connections of the clock domain;

(c) determining a minimum path slack corresponding to each connection of the clock domain;

(d) selecting the connections based on minimum path slack; and

(e) routing one or more of the selected connections in delay mode.

2. The method of claim 1, further comprising:

(f) marking the connections of the clock domain which have a lowest minimum path slack; and

(g) identifying marked connections which are not routed in delay mode as selected.

3. The method of claim 2, wherein the connections having the lowest minimum path slack correspond to a critical path, said method further comprising:

(h) determining an upper-bound estimate of clock frequency for said clock domain as defined by a path delay of the critical path.

4. The method of claim 1, wherein the initial routing is performed in an overlap tolerant resource mode.

5. The method of claim 1, said step (c) further comprising:

assigning to each connection the path slack of the path within which the connection is disposed.

6. The method of claim 5, further comprising:

if more than one path passes through the connection, assigning to the connection the minimum path slack of all paths passing through the connection.

7. The method of claim 1, said step (d) further comprising:

populating a data structure with the connections of the clock domain; and

sorting the connections according to the path slack of each connection.

8. The method of claim 3, further comprising:

iteratively applying steps (a)–

(h) to different clock sources of the placed circuit design, wherein each different clock source is associated with a corresponding and different clock domain.

9. Within a computer automated tool, a method of estimating an upper-bound of an operational frequency of at least a portion of a placed circuit design comprising:

(a) constraining at least two clock sources within the placed circuit design to a same target frequency, wherein each clock source is associated with a different clock domain;

(b) determining an initial routing of connections of the clock domains;

(c) determining a minimum path slack corresponding to each connection of the plurality of clock domains;

(d) marking connections of the plurality of clock domains which have a lowest minimum path slack;

(e) identifying marked connections which are not routed in delay mode; and

(f) routing one or more of the identified connections in delay mode.

10. The method of claim 9, further comprising:

(g) repeating steps (c)–

(f) until all marked connections are routed in delay mode.

11. The method of claim 10, wherein the connections having the lowest minimum path slack correspond to a critical path, said method further comprising:

determining an upper-bound estimate of clock frequency for the clock domains as defined by a path delay of the critical path.

12. The method of claim 10, wherein the initial routing is performed in an overlap-tolerant resource mode.

13. The method of claim 10, said step (c) further comprising:

assigning to each connection the path slack of the path within which the connection is disposed.

14. The method of claim 13, further comprising:

if more than one path passes through the connection, assigning to the connection the minimum path slack of all paths passing through the connection.

15. The method of claim 10, said step (d) further comprising:

populating a data structure with the connections of the plurality of clock domains; and

sorting the connections according to the path slack of each connection.

16. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

(a) identifying a clock source within a placed circuit design, wherein the clock source is associated with a clock domain;

(b) determining an initial routing of connections of the clock domain;

(c) determining a minimum path slack corresponding to each connection of the clock domain;

(d) marking connections of the clock domain which have a lowest minimum path slack;

(e) identifying marked connections which are not routed in delay mode; and

(f) routing one or more of the identified connections in delay mode.

17. The machine readable storage of claim 16, further comprising:

(g) repeating steps (c)–

(f) until all marked connections are routed in delay mode.

18. The machine readable storage of claim 17, wherein the connections having the lowest minimum path slack correspond to a critical path, said machine readable storage further causing the machine to perform the step of:

(h) determining an upper-bound estimate of clock frequency for said clock domain as defined by a path delay of the critical path.

19. The machine readable storage of claim 16, wherein the initial routing is performed in a resource mode.

20. The machine readable storage of claim 16, said step (c) further comprising:

assigning to each connection the path slack of the path within which the connection is disposed.

21. The machine readable storage of claim 20, further comprising:

if more than one path passes through the connection, assigning to the connection the minimum path slack of all paths passing through the connection.

22. The machine readable storage of claim 16, said step (d) further comprising:

populating a data structure with the connections of the clock domain; and

sorting the connections according to the path slack of each connection.

23. The machine readable storage of claim 18, further comprising:

iteratively applying steps (a)–

(h) to different clock sources of the placed circuit design, wherein each different clock source is associated with a corresponding and different clock domain.

24. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

(a) constraining at least two clock sources within a placed circuit design to a same target frequency, wherein each clock source is associated with a different clock domain;

(b) determining an initial routing of connections of the clock domains;

(c) determining a minimum path slack corresponding to each connection of the plurality of clock domains;

(d) marking connections of the plurality of clock domains which have a lowest minimum path slack;

(e) identifying marked connections which are not routed in delay mode; and

(f) routing one or more of the identified connections in delay mode.

25. The machine readable storage of claim 24, further comprising:

(g) repeating steps (c)–

(f) until all marked connections are routed in delay mode.

26. The machine readable storage of claim 25, wherein the connections having the lowest minimum path slack correspond to a critical path, said machine readable storage further causing the machine to perform the step of:

determining an upper-bound estimate of clock frequency for the clock domains as defined by a path delay of the critical path.

27. The machine readable storage of claim 24, wherein the initial routing is performed in an overlap-tolerant mode.

28. The machine readable storage of claim 24, said step (c) further comprising:

assigning to each connection the path slack of the path within which the connection is disposed.

29. The machine readable storage of claim 28, further comprising:

if more than one path passes through the connection, assigning to the connection the minimum path slack of all paths passing through the connection.

30. The machine readable storage of claim 29, said step (c) further comprising:

populating a data structure with the connections of the plurality of clock domains; and

sorting the connections according to the path slack of each connection.

31. A system configured to estimate an upper-bound of an operational frequency of at least a portion of a placed circuit design, comprising:

(a) means for identifying a clock source within the placed circuit design, wherein the clock source is associated with a clock domain;

(b) means for determining an initial routing of connections of the clock domain;

(c) means for determining a minimum path slack corresponding to each connection of the clock domain;

(d) means for marking connections of the clock domain which have a lowest minimum path slack;

(e) means for identifying marked connections which are not routed in delay mode;

(f) means for routing one or more of the identified connections in delay mode; and

(g) means for repeating steps (c)–

(f) until all marked connections are routed in delay mode.

32. The system of claim 31, wherein the connections having the lowest minimum path slack correspond to a critical path, said system further comprising:

means for determining an upper-bound estimate of clock frequency for the clock domain as defined by a path delay of the critical path.

33. A system configured to estimate an upper-bound of an operational frequency of at least a portion of a placed circuit design, comprising:

(a) means for constraining at least two clock sources within the placed circuit design to a same target frequency, wherein each clock source is associated with a different clock domain;

(b) means for determining an initial routing of connections of the clock domains;

(c) means for determining a minimum path slack corresponding to each connection of the plurality of clock domains;

(d) means for marking connections of the plurality of clock domains which have a lowest minimum path slack;

(e) means for identifying marked connections which are not routed in delay mode;

(f) means for routing one or more of the identified connections in delay mode; and

(g) means for repeating steps (c)–

(f) until all marked connections are routed in delay mode.

34. The system of claim 33, wherein the connections having the lowest minimum path slack correspond to a critical path, said system further comprising:

means for determining an upper-bound estimate of clock frequency for the clock domains as defined by a path delay of the critical path.