Exploiting independent portions of logic designs for timing optimization

• US 8,255,860 B1
• Filed: 03/31/2010
• Issued: 08/28/2012
• Est. Priority Date: 04/03/2009
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Fung, Ryan
• Primary Examiner(s): Garbowski, Leigh
• Assistant Examiner(s): Thompson, A. M.
• Application Number:
  US12/751,809
• Time in Patent Office: 881 Days
• Field of Search: None
• US Class Current: 716/134
• 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

Abstract

Slacks or timing weights are determined during implementation of an electronic design to improve design optimization. Multiple failings paths are optimized simultaneously by generalizing the notion of constraint relaxation used when computing slacks and timing weights to apply to portions of the design that can be independently optimized, rather than strictly adhering to clock domains and other coupled timing constraints used by conventional relaxation-based approaches. Improved calculation of slacks or timing weights better guides optimization algorithms.

Claims

1. A method of implementing an electronic design, comprising:

receiving a design for implementation on an electronic device;

generating a timing graph including a plurality of edges with associated timing data, the timing graph generated using a processor;

identifying a first relaxation group comprising a first plurality of edges in a clock domain, wherein identifying the first relaxation group comprises;

identifying a first edge having a low slack or slack ratio;

traversing the timing graph from the first edge through a first plurality of search paths until a second edge having a high slack or slack ratio is identified, wherein the high slack or slack ratio corresponds to a slack threshold, wherein the slack threshold is selected from the group consisting of an absolute threshold, based on the achieved or required clock period, and a function of the slack ratio of the initial edge being expanded from to guide the search to find a relatively non-critical boundary; and

designating the plurality of edges in the first plurality of search paths from the first edge to the second edge as edges in the first relaxation group;

identifying a second relaxation group comprising a second plurality of edges in the clock domain; and

independently relaxing the timing data corresponding to the first plurality of edges and the timing data corresponding to the second plurality of edges during design optimization.

2. The method of claim 1, wherein the second edge is a boundary in the first relaxation group.

3. The method of claim 1, wherein the first relaxation group is bounded by a plurality of non-critical edges including the second edge.

4. The method of claim 1, wherein the slack threshold is an absolute threshold.

5. The method of claim 1, wherein the slack threshold is based on the achieved or required clock period.

6. The method of claim 1, wherein the slack threshold is a function of the slack ratio of the initial edge being expanded from to guide the search to find a relatively non-critical boundary.

7. The method of claim 1, wherein identifying the second relaxation group comprises:

identifying a third edge having a low slack ratio, wherein the third edge is outside of the first relaxation group;

traversing through the timing graph from the third edge through a second plurality of search paths until a fourth edge having a high slack ratio is identified, wherein the high slack ratio exceeds a slack threshold;

designating the plurality of edges in the second plurality of search paths from the third edge to the fourth edge as edges in the second relaxation group.

8. The method of claim 7, wherein the fourth edge is a boundary in the second relaxation group.

9. The method of claim 7, wherein the second relaxation group is bounded by a plurality of non-critical edges including the fourth edge.

10. The method of claim 1, wherein bottom-up clustering is used to identify the first relaxation group.

11. The method of claim 1, wherein top-down partitioning is used to identify the first relaxation group.

12. The method of claim 1, wherein a plurality of mutually exclusive relaxation groups including the first relaxation group, the second relaxation group, and a third relaxation group are identified.

13. The method of claim 1, wherein independently relaxing the timing data comprises computing slacks or slack ratios based on a relaxed timing constraint for each of the plurality of relaxation groups.

14. The method of claim 1, wherein independently relaxing the timing data comprises linearly interpolating the slacks or slack ratios based on a function of the lowest slack or slack ratio edge in the relaxation group.

15. The method of claim 14, wherein independently relaxing the timing data comprises linearly interpolating the slacks or slack ratios based on a function of the lowest slack or slack ratio edge in the relaxation group and the lowest slack or slack ratio edge in the clock domain or design.

16. The method of claim 1, wherein the identifying a first relaxation group comprises identifying one or more disjoint subsets of edges in a clock domain and identifying the first relaxation group as one of the disjoint subsets.

17. The method of claim 1, wherein the first relaxation group includes a minimum number of edges.

18. The method of claim 1, wherein identifying the first relaxation group comprises calculating a score to quantify whether a suitable boundary was found and adding to the score based on the slacks or slack ratios of edges found by traversing away from a subset of edges in the relaxation group.

19. The method of claim 18, wherein the timing graph is traversed by expanding through the search path having the lowest score computed as a function of edge slacks or slack ratios.

20. The method of claim 1, wherein identifying the first relaxation group comprises adding edges to the relaxation group based on timing-graph adjacency.

21. The method of claim 1, wherein identifying the first relaxation group comprises adding edges to the relaxation group based on adjacency in the optimization problem search space.

22. The method of claim 1, wherein the identifying the first relaxation group comprises pruning edges from the relaxation group based on optimization constraints.

23. An apparatus comprising:

an interface configured to receive a design for implementation on an electronic device;

a processor configured to generate a timing graph including a plurality of edges corresponding to a plurality of slack or slack ratios, the timing graph generated using a processor, and identify a first edge having a low slack or slack ratio;

wherein the processor is further configured to traverse the timing graph from the first edge through a first plurality of search paths until a second edge having a high slack or slack ratio is identified, wherein the high slack or slack ratio corresponds to a slack threshold wherein the slack threshold is selected from the group consisting of an absolute threshold, based on the achieved or required clock period, and a function of the slack ratio of the initial edge being expanded from to guide the search to find a relatively non-critical boundary, and designate the plurality of edges in the first plurality of search paths from the first edge to the second edge as edges in a first relaxation group.

24. A method of implementing an electronic design, comprising:

receiving a design for implementation on an electronic device;

generating a timing graph including a plurality of edges with associated timing data, the timing graph generated using a processor;

identifying a first relaxation group comprising a first plurality of edges in a clock domain;

identifying a second relaxation group comprising a second plurality of edges in the clock domain; and

independently relaxing the timing data corresponding to the first plurality of edges and the timing data corresponding to the second plurality of edges during design optimization;

wherein a plurality of mutually exclusive relaxation groups including the first relaxation group, the second relaxation group, and a third relaxation group are identified.