System and method for restructuring of logic circuitry

• US 6,282,695 B1
• Filed: 12/16/1998
• Issued: 08/28/2001
• 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): Smith, Matthew
• Assistant Examiner(s): Speight, Jibreel
• Application Number:
  US09/213,320
• Time in Patent Office: 986 Days
• Field of Search: 703/14, 716/1, 716/2, 716/6, 716/8, 716/17, 716/18, 716/4, 716/11, 716/3
• US Class Current: 716/103
• 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

A redesigning of dynamic logic circuitry inputs into a process implemented in a computer the dynamic logic circuitry to be redesigned as a set of boolean equations. Along a path through the logic circuitry, the logic circuitry is converted into AND and OR books, or blocks of circuitry. Then various portions of these books are compared to a library of AND/OR and OR/AND books. A list of these possible substitutions from the comparison step is produced. From the list, a selection process selects those substitutions providing a best cost benefit.

Claims

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

inputting the dynamic logic circuitry as a set of boolean equations;

comparing portions of the logic circuitry to a library of books, wherein the library of books include two-layer AND/OR (AO) and OR/AND (OA) books;

building a list of matches between the portions of the logic circuitry and the library of books wherein for each of the portions the list includes one or more of the OA and/or AO books from the library; and

selecting the matches that provide a specified cost benefit.

2. The method as recited in claim 1, wherein the specified cost benefit is a best cost benefit.

3. The method as recited in claim 1, wherein the building step further comprises the step of:

for each set of matches between a portion of the logic circuitry and the library of books, keeping in the list only the match having the best cost benefit.

4. The method as recited in claim 1, further comprising the step of:

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

5. The method as recited in claim 4, wherein for each of the portions the list includes one or more of the OA and/or AO books from the library.

6. The method as recited in claim 5, wherein the building step further comprises the steps of:

for each of the portions, sorting the list by cost benefit; and

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

7. The method as recited in claim 6, wherein the portions and the books are represented by boolean functions.

8. The method as recited in claim 1, wherein the selecting step further comprises the step of regenerating the list after each substitution of one of the books for one of the portions.

9. The method as recited in claim 1, wherein the portions lie along a critical path through the dynamic logic circuitry.

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

circuitry for inputting into the data processing system the dynamic logic circuitry as a set of boolean equations;

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

circuitry for comparing each of the portions of the logic circuitry to a library of AO and OA books;

circuitry for building a list of matches between each of the portions of the logic circuitry and the library of books, wherein for each of the portions the list includes one or more of the OA and/or AO books from the library; and

circuitry for selecting the matches that provide a best cost benefit.

11. The data processing system as recited in claim 10, wherein the building circuitry further comprises:

circuitry for sorting each list by cost benefit; and

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

12. The data processing system as recited in claim 10, wherein the selecting circuitry further comprises circuitry for regenerating the list after each substitution of one of the books for one of the portions.

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

inputting the dynamic logic circuitry as a set of boolean equations;

comparing portions of the logic circuitry to a library of books, wherein the library of books include two-layer AND/OR (AO) and OR/AND (OA) books;

building a list of matches between the portions of the logic circuitry and the library of books wherein for each of the portions the list includes one or more of the OA and/or AO books from the library; and

selecting the matches that provide a specified cost benefit.

14. The computer program product as recited in claim 13, wherein the specified cost benefit is a best cost benefit.

15. The computer program product as recited in claim 13, wherein the building program step further comprises the program step of:

for each set of matches between a portion of the logic circuitry and the library of books, keeping in the list only the match having the specified cost benefit.

16. The computer program product as recited in claim 15, further comprising the program step of:

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.

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

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

for each of the portions, sorting the list by cost benefit; and

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

19. The computer program product as recited in claim 18, wherein the portions and the books are represented by boolean functions.

20. The computer program product as recited in claim 18, 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.

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