System and method for restructuring of logic circuitry

• US 6,460,166 B1
• Filed: 12/16/1998
• Issued: 10/01/2002
• Est. Priority Date: 12/16/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Reddy, Lakshmi Narasimha, Rosser, Thomas Edward
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/213,322
• Time in Patent Office: 1,385 Days
• Field of Search: 716/2, 716/3, 716/6
• US Class Current: 716/132
• 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

An algorithm for efficient restructuring of logic circuitry to improve selected characteristics (delay and/or area). Along a path through the logic circuitry, the logic is converted to equivalent implementations with the same Boolean function using specific choices from the library of available cells, such that these conversions provide an improvement in the cost/benefit for the selected characteristics.

Claims

1. A computer program product adaptable for storage on a computer storage medium, the computer program product operable for redesigning dynamic logic circuitry, comprising the program steps of:

comparing portions of the logic circuitry to a library of books;

building a list of matches between the portions of the logic circuitry and the library of books;

selecting the matches that provide a specified cost benefit, wherein selected ones of the matches have a higher cost benefit; and

removing inverting nodes from the portions of the logic circuitry so that the portions only comprise AND and OR books, wherein the removing program step is performed before the comparing program step.

2. The computer program product as recited in claim 1, wherein each of the portions of the list includes one or more OA and/or AO books from the library.

3. The computer program product as recited in claim 2, wherein the building program step further comprises the program steps of:

for each of the portions, sorting the list by cost benefit, taking into account the higher cost benefit associated with the selected ones of the matches; and

for each of the portions, eliminating all of the books in the list except the one with the best cost benefit.

4. The computer program product as recited in claim 3, wherein the portions and the books are represented by Boolean functions.

5. The computer program product as recited in claim 3, wherein the selecting program step further comprises the program step of regenerating the list after each substitution of one of the books for one of the portions.

6. The computer program product as recited in claim 5, wherein the portions lie along a critical path through the logic circuitry.

7. A method for redesigning dynamic logic circuitry, comprising the steps of:

removing inverting nodes from portions of the logic circuitry so that the portions only comprise AND and OR books;

comparing portions of the logic circuitry to a library of books;

building a list of matches between the portions of the logic circuitry and the library of books; and

selecting the matches that provide a specified cost benefit, wherein selected ones of the matches have a higher cost benefit.

8. A data processing system for redesigning logic circuitry, comprising:

circuitry for removing inverting nodes from portions of the logic circuitry so that the portions only comprise AND and OR books;

circuitry for comparing portions of the logic circuitry to a library of books;

circuitry for building a list of matches between the portions of the logic circuitry and the library of books; and

circuitry for selecting the matches that provide a specified cost benefit, wherein selected ones of the matches have a higher cost benefit.