Method and apparatus for a hedge analysis technique for performance improvements of large scale integrated circuit logic design

• US 6,412,096 B1
• Filed: 04/30/1999
• Issued: 06/25/2002
• Est. Priority Date: 04/30/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Ventrone, Sebastian T.
• Primary Examiner(s): Nelms, David
• Assistant Examiner(s): LE, THONG QUOC
• Application Number:
  US09/303,154
• Time in Patent Office: 1,152 Days
• Field of Search: 716/2, 716/17, 716/18, 364/489, 395/500
• US Class Current: 716/108
• 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/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation

Abstract

An apparatus and method for performing a Hedge Technique Analysis are used to enhance the performance of the functional logic design of a large scale integrated circuit while simplifying the underlying logic. The methodology first runs performance tests on the logic circuitry to assess the timing and characterize the logic paths; next, functional paths are identified and listed; common logic path leaves, twigs, and branches are then identified and ranked by the number of critical paths associated with each; all high ranking common logic path leaves, twigs, and branches are then collapsed; and, timing paths are re-run to characterize the final performance rating of the functional design.

Claims

1. A method of designing a logic circuit comprising the steps of:

a) identifying functional paths in said logic circuit that include multiple elements in common with other functional paths;

b) grouping the identified functional paths into groups having functional paths with the same elements in common;

2. A method of designing a logic circuit having a plurality of logic functions, and logic paths having logic path elements, comprising the steps of:

a) running performance tests on said logic circuit;

b) listing all of said logic paths in said logic circuit;

c) finding said logic path elements of said logic paths that are common to one another;

d) ranking the common logic path elements by the number of critical paths associated with each, assigning a higher ranking value to said common logic path elements with the greater number of said critical paths;

e) collapsing said higher ranking common logic path elements to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions; and

,

f) re-running said performance tests on said logic circuit.

3. A method of designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, comprising the steps of:

a) providing a computer processing system;

b) generating a data structure to identify each of said logic path leaves in said logic circuit;

c) running a performance test using said computer processing system on said logic circuit to characterize critical paths of said logic paths;

d) cross-referencing said logic path leaves to the number of said critical paths associated with each of said logic path leaves;

e) sorting and grouping said logic path leaves according to said number of said critical paths associated with each of said logic path leaves; and

,

f) performing a first level performance screen on said sorted and grouped logic path leaves.

4. The method of claim 3 further comprising:

g) cross-referencing said logic path twigs to the number of said critical paths associated with each of said logic path twigs;

h) sorting and grouping said logic path twigs according to said number of said critical paths associated with each of said logic path twigs;

i) customizing and optimizing common logic path twig groups of said step (h) to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions; and

,

j) converting one or more of said common logic path twig groups into logic path leaves.

5. The method of claim 4 further comprising:

k) cross-referencing said logic path branches to the number of said critical paths associated with each of said logic path branches;

l) sorting and grouping said logic path branches according to said number of said critical paths associated with each of said logic path branches;

m) customizing and optimizing common logic path branch groups of said step (l) to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions; and

,

n) converting one or more of said common logic path branch groups into logic path twigs.

6. The method of claim 3, wherein said step (c), running a performance test, includes listing said logic paths within said logic circuit.

7. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, said method steps comprising:

a) running performance tests on said logic circuit;

b) listing all logic paths;

c) finding said logic path leaves, twigs, and branches of said logic paths that are common to one another;

d) ranking the common leaves, twigs, and branches of said logic paths by the number of critical paths associated with each, assigning a higher ranking value to the common logic path leaves, twigs, and branches with the greater number of said critical paths;

e) collapsing the higher ranking common logic path leaves, twigs, and branches, to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions; and

,

f) re-running said performance tests on said logic circuit.

8. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, said method steps comprising:

a) generating a data structure to identify each of said logic path leaves in said logic circuit;

b) running a performance test on said logic circuit to characterize critical paths of said logic paths;

c) cross-referencing said logic path leaves to the number of said critical paths associated with each of said logic path leaves;

d) sorting and grouping said logic path leaves according to said number of said critical paths associated with each of said logic path leaves;

e) performing a first level performance screen on said sorted and grouped logic path leaves;

f) cross-referencing said logic path twigs to the number of said critical paths associated with each of said path logic path twigs;

g) sorting and grouping said logic path twigs according to said number of said critical paths associated with each of said logic path twigs;

h) customizing and optimizing common logic path twig groups of said step (g) to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions;

i) converting one or more of said common logic path twig groups into logic path leaves;

j) cross-referencing said logic path branches to the number of said critical paths associated with each of said logic path branches;

k) sorting and grouping said logic path branches according to said number of said critical paths associated with each of said logic path branches;

l) customizing and optimizing common logic path branch groups of said step (k) to minimize propagation times of said logic circuit and eliminate redundancy in said logic functions; and

,

m) converting one or more of said common logic path branch groups into logic path twigs.

9. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, said method steps comprising:

a) identifying functional paths in said logic circuit that include multiple elements in common with other functional paths;

b) grouping the identified functional paths into groups having functional paths with the same elements in common;

c) ranking said groups according to a number of elements that said functional paths in each group have in common; and

,

d) optimizing a performance of a first group of functional paths into a second group of functional paths by customizing and collapsing said functional paths, wherein a number of common elements in the functional paths of the second group is less than a number of common elements in the functional paths of the first group.