Granted Patent B1

US 6,868,535 · App. 09/879,841 · Granted Mar 15, 2005

Abstract

Claims (77)

1. A process of designing an integrated circuit having optimal signal timing comprising steps of:

a) generating a plurality of identities based on logic operations and library cells in technology basis;

b) creating a resynthesis window having less than a predetermined depth of critical variables, by:

b1) forming a plurality of binary trees whose vertices represent logic cells,

b2) defining a logic equation of the resynthesis window from a tree having an output cell having a critical timing, and

b3) expanding the window to include additional trees that have inputs connected to the selected output cell, and

b4) transforming the logic equations;

c) transforming logic equations from the resynthesis window using the identities; and

d) optimizing the resynthesis window area.

2. The process of claim 1 , wherein step (a) includes steps of:

a1) selecting a set of most frequently used logic operations in the integrated circuit,

a2) creating a list of initial identities identifying a union of the axioms of the logic operations of the set and logic cell definitions in the technology basis,

a3) enumerating left parts of the identities, and

a4) generating corresponding right parts for each enumerated left part.

3. The process of claim 2 , wherein the identities have a depth of 2 or 3 and step (a3) includes steps of:

enumerating left parts of the identities having a depth of 2, and

subsequently enumerating left parts of the identities having a depth of 3.

4. The process of claim 2 , wherein step (a4) includes steps of:

a4A) substituting constants for variables in left parts,

a4B) optimizing the results of step (a4A),

a4C) creating an auxiliary system of logic equations based on the results of step (a4B), and

a4D) creating an identity based on the results of steps (a4B) and (a4C).

5. The process of claim 1 , wherein step (b) further includes:

b5) iteratively repeating steps (b3) and (b4) until the variables in the logic equations having critical timing have a maximal depth less than the predetermined depth.

6. The process of claim 1 , wherein step (c) includes steps of:

c1) selecting subexpressions of the logic equations having depths not less than 2,

c2) selecting a variable having a maximal timing operand from an identity associated with one of the subexpressions, and

c3) transforming the selected subexpression to minimize timing of the variable.

7. The process of claim 1 , wherein step (d) includes steps of:

d1) identifying identities having more than one variable, and

d2) transforming the identified identities to remove duplicate variables.

8. The process of claim 7 , wherein step d2) includes steps of:

selecting non-critical subexpressions of the identities, and

optimizing the area of the associated cells to minimize complexity.

9. A computer usable medium having a computer readable program embodied therein for addressing data to cause a computer to design an integrated circuit having an optimal signal timing, the computer readable program in the computer usable medium comprising:

first computer readable program code for causing the computer to generate a plurality of identities based on logic operations and library cells in the technology basis of the integrated circuit;

second computer readable program code for causing the computer to create a resynthesis window having less than a predetermined depth of critical variables;

third computer readable program code for causing the computer to transform logic equations from the resynthesis window using the identities;

fourth computer readable program code for causing the computer to optimize the resynthesis window area;

fifth computer readable program code for causing the computer to select a set of most frequently used logic operations in the integrated circuit;

sixth computer readable program code for causing the computer to create a list of initial identities identifying a union of the axioms of the logic operations of the set and logic cell definitions in the technology basis;

seventh computer readable program code for causing the computer to enumerate left parts of the identities; and

eighth computer readable program code for causing the computer to generate corresponding right parts for each enumerated left part.

10. The computer usable medium of claim 9 , wherein the identities have a depth of 2 or 3 and the seventh computer readable program code includes:

ninth computer readable program code for causing the computer to enumerate left parts of the identities having a depth of 2, and

tenth computer readable program code for causing the computer to subsequently enumerate left parts of the identities having a depth of 3.

11. The computer usable medium of claim 9 , wherein the eighth computer readable program code includes:

eleventh computer readable program code for causing the computer to substitute constants for variables in left parts,

twelfth computer readable program code responsive to the substitution of constants caused by the eleventh computer readable program code for causing the computer to optimize the left parts,

thirteenth computer readable program code responsive to the optimization caused by the twelfth computer readable program code for causing the computer to create an auxiliary system of logic equations, and

fourteenth computer readable program code responsive to the optimization caused by the twelfth computer readable program code and the auxiliary system of logic equations caused by the thirteenth computer readable program code for causing the computer to create an identity.

12. The computer usable medium of claim 9 , wherein the second computer readable program code includes:

fifteenth computer readable program code for causing the computer to form plural binary trees of logic cells,

sixteenth computer readable program code for causing the computer to define a logic equation of a resynthesis window from a tree having an output cell having a critical timing, and

seventeenth computer readable program code for causing the computer to expand the window to include additional trees that have inputs connected to the selected output cell, and

eighteenth computer readable program code for causing the computer to transform the logic equations.

13. The computer usable medium of claim 12 , wherein the second computer readable program code further includes:

nineteenth computer readable program code for causing the computer to iteratively repeat execution of the seventeenth and eighteenth computer readable program codes until the variables in the logic equations having critical timing have a maximal depth less than the predetermined depth.

14. The computer usable medium of claim 9 , wherein the third computer readable program code includes:

twentieth computer readable program code for causing the computer to select subexpressions of the logic equations having a depths not less than 2,

twenty-first computer readable program code for causing the computer to select a variable having a maximal timing operand from an identity associated with one of the subexpressions, and

twenty-second computer readable program code for causing the computer to transform the selected subexpression to minimize timing of the variable.

15. The computer usable medium of claim 9 , wherein the fourth computer readable program code includes:

twenty-third computer readable program code for causing the computer to identify identities having more than one variable, and

twenty-fourth computer readable program code for causing the computer to transform the identified identities to remove duplicate variables.

16. The computer usable medium of claim 15 , wherein the twenty-fourth computer readable program code includes:

twenty-fifth computer readable program code for causing the computer to select non-critical subexpressions of the identities, and

twenty-sixth computer readable program code for causing the computer to optimize the area of the associated cells to minimize complexity.

17. Apparatus for use in designing an integrated circuit having optimal signal timing comprising:

generating means for generating a plurality of identities based on logic operations and library cells in technology basis, wherein the generating means comprises:

means for selecting a set of most frequently used logic operations in the integrated circuit,

means for creating a list of initial identities identifying a union of the axioms of the logic operations of the set and logic cell definitions in the technology basis,

means for enumerating left parts of the identities, and

means for generating corresponding right parts for each enumerated left part;

creating means for creating a resynthesis window having less than a predetermined depth of critical variables;

transforming means for transforming logic equations from the resynthesis window using the identities; and

optimizing means for optimizing the resynthesis window area.

Assignments (9)