Method and apparatus for adaptive timing optimization of an integrated circuit design

• US 7,020,589 B1
• Filed: 09/26/2001
• Issued: 03/28/2006
• Est. Priority Date: 09/29/2000
• Status: Expired due to Fees

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Grinchuk, Mikhail I., Raspopovic, Pedja, Datta Ray, Partha P.
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US09/964,030
• Time in Patent Office: 1,644 Days
• Field of Search: 703/2, 703/13, 716/6, 716/7, 716/9, 716/10
• US Class Current: 703/2
• 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
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

An optimization apparatus and method optimizes a functional block within a netlist of an integrated circuit design. A corresponding delay value is assigned to each of a plurality of pins of the block. Each pin corresponds to a respective signal path through the block. The delay values together form a delay value combination, which is selected from a continuous set of possible combinations in which each combination in the set satisfies a predetermined criteria. A circuit configuration for the block is then generated with a plurality of logic cells that are interconnected in the netlist such that the respective signal paths have delays through the block that are based on the corresponding delay values.

Claims

1. A method of optimizing a functional block within a netlist of an integrated circuit design, the method comprising:

(a) defining a continuous set of possible combinations in which each combination in the set satisfies a predetermined criteria and assigning a corresponding delay value to each of a plurality of pins of the block, wherein each pin corresponds to a respective signal path through the block and wherein the delay values together form a delay value combination that is selected from the continuous set of possible combinations; and

(b) generating a circuit configuration for the block with a plurality of logic cells that are interconnected in the netlist such that the respective signal paths through the block have delays based on the corresponding delay values assigned in step (a).

2. The method of claim 1 wherein:

each of the logic cells in step (b) has an estimated base delay D₁;

each delay value, d_i, in the delay value combination in step (a) satisfies a first inequality in which,

d_i≧

D₁

wherein i is an integer variable from 1 to N and N is the number of the plurality of pins; and

the delay value combination in step (a) satisfies a second inequality in which, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>\frac{1}{2^{d_i/D_1}}\le <br><br>1.$

3. The method of claim 1, wherein the method is performed to optimize a plurality of functional blocks within the netlist and the method further comprises:

(c) for each of the plurality of functional blocks, assigning a current penalty value to each of the plurality of pins of that block;

(d) assigning, in step (a), a corresponding delay value to each of the plurality of pins of each of the plurality of functional blocks based on the current penalty value for that pin;

(e) identifying at least one of the pins of at least one of the plurality of blocks as a critical pin in the netlist;

(f) updating the current penalty value of the at least one critical pin based on a history of that pin being identified as the critical pin in step (e);

(g) repeating step (d) using the current penalty value updated in step (f); and

(h) performing step (b) for each of the plurality of functional blocks based on the corresponding delay values assigned in step (d) for that block.

4. The method of claim 3 wherein step (d) of assigning a corresponding delay value comprises, for each of the plurality of blocks:

(d) (1) filtering the current penalty values of the block according to a filter function to produce a filtered penalty value for each of the plurality of pins of the block; and

(d)(2) assigning the current delay values of the block based on the corresponding filtered penalty values of the block.

5. The method of claim 4 wherein step (d)(1) comprises:

(d) (1) (i) adding the plurality of current penalty values of the block to produce a penalty sum; and

(d) (1) (ii) for each of the current penalty values of the block, replacing that current penalty value with the minimum of that current penalty value and one-half of the penalty sum.

6. The method of claim 3 wherein step (d) of assigning a current delay value comprises for each of the plurality of blocks:

(d)(1) adding the plurality of current penalty values of the block to produce a penalty sum; and

(d) (2) for each of the plurality of pins of the block, (i) calculating the current delay value for that pin based on a log function of the penalty sum divided by the current penalty value corresponding to that pin, and

(ii) multiplying a result of the log function by an estimated delay through an individual one of the logic cells within the block.

7. The method of claim 3 wherein step (e) comprises identifying at least one of the pins of at least one of the plurality of blocks as a critical pin in the netlist based on estimated timing data associated with the plurality of pins of the plurality of blocks, given the delay values assigned to the plurality of pins of the plurality of blocks in step (d).

8. The method of claim 3 wherein the updating step (f) comprises, for each of the plurality of blocks, applying the current penalty value of the at least one critical pin to a function to generate a new penalty value, which replaces the current penalty value of that pin.

9. The method of claim 8 wherein the function monotonically changes the current penalty value of the at least one critical pin by a selected update value.

10. The method of claim 9 wherein the selected value is a value selected randomly from a range of update values.

11. The method of claim 1 wherein the functional block comprises a logic block having multiple inputs, which are logically coupled to at least one common output of the block through the respective signal paths, and wherein the multiple inputs define the plurality of pins at which the corresponding delay values are assigned in step (a).

12. The method of claim 1 wherein the functional block comprises a fanout distribution block having multiple outputs, which are logically coupled to a common input of the block through the respective signal paths, and wherein the multiple outputs define the plurality of pins at which the corresponding delay values are assigned in step (a).

13. A method of optimizing a functional block within a netlist of an integrated circuit design, the method comprising:

(a) assigning a current penalty value to each of a plurality of pins of the block, wherein each pin corresponds to a respective signal path through the block;

(b) assigning a current delay value to each of the plurality of pins of the block based on the corresponding current penalty value;

(c) identifying at least one of the pins as a critical pin in the netlist;

(d) updating the current penalty value of the at least one critical pin based on a history of the respective pin being identified as the critical pin in step (c);

(e) repeating step (b) using the current penalty value updated in step (d); and

(f) generating an internal circuit configuration for the block with logic cells that are interconnected in the netlist such that the respective signal paths through the block have delays that are based on the current delay values.

14. The method of claim 13 wherein step (b) of assigning a current delay value comprises:

(b) (1) selecting a combination of the delay values for the plurality of pins of the block from a continuous set of possible delay combinations that satisfy a predetermined criteria.

15. The method of claim 14 wherein each of the logic cells has an estimated base delay D₁ and wherein:

(b) (1) (i) each delay value, d_i, in the combination satisfies a first inequality in which,

d_i≧

D_1i

 

wherein i is an integer variable from 1 to N and N is the number of the plurality of pins; and

(b) (1) (ii) the combination of the delay values satisfies a second inequality in which, $\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>\frac{1}{2^{d_i/D_1}}\le <br><br>1.$

16. The method of claim 13 wherein step (b) of assigning a current delay value comprises:

(b) (1) filtering the current penalty values of the block according to a filter function to produce a filtered penalty value for each of the plurality of pins of the block; and

(b)(2) assigning the current delay values of the block based on the corresponding filtered penalty values.

17. The method of claim 16 wherein step (b)(1) comprises:

(b)(1)(i) adding the plurality of current penalty values for the block to produce a penalty sum; and

(b)(1)(ii) for each of the current penalty values, replacing the current penalty value with the minimum of the current penalty value and one-half of the penalty sum.

18. The method of claim 13 wherein step (b) of assigning a current delay value comprises:

(b) (1) adding the plurality of current penalty values for the block to produce a penalty sum; and

(b) (2) for each of the plurality of pins, (i) calculating the current delay value for that pin based on a log function of the penalty sum divided by the current penalty value corresponding to that pin, and (ii) multiplying a result of the log function by an estimated delay through an individual one of the logic cells within the block.

19. The method of claim 13 wherein step (c) comprises identifying at least one of the pins as a critical pin in the netlist based on estimated timing data associated with the plurality of pins.

20. The method of claim 13 wherein the updating step (d) comprises applying the current penalty value of the critical pin to a function to generate a new penalty value, which replaces the current penalty value of that pin.

21. The method of claim 20 wherein the function monotonically changes the current penalty value of the critical pin by a selected update value.

22. The method of claim 21 wherein the selected value is a value selected randomly from a range of update values.

23. The method of claim 21 wherein steps (h), (i), (j), and (k) are repeated until a predetermined criteria is met before performing step (l).

24. The method of claim 13, wherein the method is performed to optimize a plurality of functional blocks within the netlist and the method further comprises:

(g) assigning, in step (a), for each of the plurality of functional blocks, a current penalty value to each of the plurality of pins of that block;

(h) assigning, in step (b), for each of the plurality of functional blocks, a current delay value to each of the plurality of pins of that block based on the corresponding penalty value for that pin;

(i) identifying, in step (c), at least one of the pins of at least one of the plurality of blocks as a critical pin in the netlist;

(j) updating, in step (d), the current penalty value of the at least one critical pin based on a history of that pin being identified as the critical pin in step (i);

(k) repeating step (h) using the current penalty value updated in step (j); and

(l) performing step (f) for each of the plurality of functional blocks based on the corresponding current delay values for that block.

25. The method of claim 13 wherein the functional block comprises a logic block having multiple inputs, which are logically coupled to at least one common output of the block through the respective signal paths, and wherein the multiple inputs define the plurality of pins at which the current penalty values and the current delay values are assigned in steps (a) and (b), respectively.

26. The method of claim 13 wherein the functional block comprises a fanout distribution block having multiple outputs, which are logically coupled to a common input of the block through the respective signal paths, and wherein the multiple outputs define the plurality of pins at which the current penalty values and the current delay values are assigned in steps (a) and (b), respectively.

27. A computer-readable medium comprising instructions readable by a computer-aided design tool for optimizing a functional block within a netlist of an integrated circuit which, when executed, cause the tool to perform steps comprising:

(a) assigning a current penalty value to each of a plurality of pins of the block, wherein each pin corresponds to a respective signal path through the block;

(b) assigning a current delay value to each of the plurality of pins of the block based on the corresponding current penalty value;

(c) identifying at least one of the pins as a critical pin in the netlist;

(d) updating the current penalty value of the at least one critical pin based on a history of the respective pin being identified as the critical pin in step (c);

(e) repeating step (b) using the current penalty value updated in step (d); and

(f) generating a circuit configuration for the block with logic cells that are interconnected in the netlist such that the respective signal paths through the block have delays that are based on the current delay values.

28. An integrated circuit netlist comprising a functional block, which is optimized by a process comprising:

(a) assigning a current penalty value to each of a plurality of pins of the block, wherein each pin corresponds to a respective signal path through the block;

(b) assigning a current delay value to each of the plurality of pins of the block based on the corresponding current penalty value;

(c) identifying at least one of the pins as a critical pin in the netlist;

(d) updating the current penalty value of the at least one critical pin based on a history of the respective pin being identified as the critical pin in step (c);

(e) repeating step (b) using the current penalty value updated in step (d); and

(f) generating a circuit configuration for the block with logic cells that are interconnected in the netlist such that the respective signal paths through the block have delays that are based on the current delay values.