Optimizing a Netlist Circuit Representation by Leveraging Binary Decision Diagrams to Perform Rewriting

• US 20100050145A1
• Filed: 08/25/2008
• Published: 02/25/2010
• Est. Priority Date: 08/25/2008
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Paruthi, Viresh, Kanzelman, Robert, Baumgartner, Jason, Janssen, Geert
• Granted Patent: US 8,799,837 B2
• Time in Patent Office: Days
• 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

Leveraging existing Binary Decision Diagrams (BDDs) to enhance circuit reductions in a system model representing a state machine as a netlist. The netlist is evaluated to determine the regions with the greatest potential reductions. BDD sweeping is performed to identify redundancies in the netlist. BDD rewriting implements the circuit reductions by replacing gates of the original netlist with more efficient equivalent logic.

Claims

1. A method of redesigning a circuit by reducing a netlist representation of the circuit, the method comprising:

obtaining a plurality of Binary Decision Diagram (BDD) representations associated with a node in the netlist;

identifying a reduction in the netlist by synthesizing one of the plurality of BDD representations as a netlist region associated with the node;

modifying the netlist representation using the identified netlist region associated with the node; and

redesigning the circuit based on the rewritten netlist representation.

2. The method of claim 1, further comprising:

leveraging existing BDDs of nodes available from BDD-sweeping by evaluating said existing BDDs for use in rewriting logic for said nodes.

3. The method of claim 1, wherein predictive heuristics are used to identify portions of the netlist representation to rewrite.

4. The method of claim 3, wherein the predictive heuristics include considering whether a region under consideration has fanouts outside the region.

5. The method of claim 1, wherein said at least one netlist region with redundancy is identified by performing binary decision diagram (BDD) sweeping.

6. The method of claim 5, wherein the BDD sweeping further comprises:

identifying inputs and cut frontiers for the BDD sweep; and

adding elements to build equivalent logic towards an output of the netlist region.

7. A software product comprising a machine readable medium including a program of instructions for redesigning a circuit by reducing a netlist representation of the circuit, wherein the program of instructions upon being executed on a computer causes the computer to perform activities comprising:

obtaining a plurality of Binary Decision Diagram (BDD) representations associated with a node in the netlist;

identifying a reduction in the netlist by synthesizing one of the plurality of BDD representations as a netlist region associated with the node;

modifying the netlist representation using the identified netlist region associated with the node; and

redesigning the circuit based on the rewritten netlist representation.

8. The software product of claim 7, further comprising:

leveraging existing BDDs of nodes available from BDD-sweeping by evaluating said existing BDDs for use in rewriting logic for said nodes.

9. The software product of claim 7, wherein predictive heuristics are used to identify portions of the netlist representation to rewrite.

10. The software product of claim 9, wherein the predictive heuristics include considering whether a region under consideration has fanouts outside the region.

11. The software product of claim 7, wherein said at least one netlist region with redundancy is identified by performing binary decision diagram (BDD) sweeping.

12. The software product of claim 11, wherein the BDD sweeping further comprises:

identifying inputs and cut frontiers for the BDD sweep; and

adding elements to build equivalent logic towards an output of the netlist region.

13. A method of redesigning a circuit by reducing a netlist representation of the circuit, the method comprising:

obtaining a plurality of Binary Decision Diagram (BDD) representations associated with a node in the netlist;

identifying a reduction in the netlist by synthesizing one of the plurality of BDD representations as a netlist region associated with the node;

creating a new netlist representation using the identified netlist region associated with the node; and

redesigning the circuit based on the rewritten netlist representation.

14. The method of claim 13,

wherein predictive heuristics are used to identify portions of the netlist representation to rewrite;

and

wherein the predictive heuristics include considering whether a region under consideration has fanouts outside the region.

15. The method of claim 13, wherein said at least one netlist region with redundancy is identified by performing binary decision diagram (BDD) sweeping.

16. The method of claim 15, wherein the BDD sweeping further comprises:

identifying inputs and cut frontiers for the BDD sweep; and

adding elements to build equivalent logic towards an output of the netlist region.

17. A software product comprising a machine readable medium including a program of instructions for redesigning a circuit by reducing a netlist representation of the circuit, wherein the program of instructions upon being executed on a computer causes the computer to perform activities comprising:

obtaining a plurality of Binary Decision Diagram (BDD) representations associated with a node in the netlist;

identifying a reduction in the netlist by synthesizing one of the plurality of BDD representations as a netlist region associated with the node;

creating a new netlist representation using the identified netlist region associated with the node; and

redesigning the circuit based on the rewritten netlist representation.

18. The software product of claim 17,

wherein predictive heuristics are used to identify portions of the netlist representation to rewrite;

and

wherein the predictive heuristics include considering whether a region under consideration has fanouts outside the region.

19. The software product of claim 17, wherein said at least one netlist region with redundancy is identified by performing binary decision diagram (BDD) sweeping.

20. The software product of claim 17, wherein the BDD sweeping further comprises:

identifying inputs and cut frontiers for the BDD sweep; and

adding elements to build equivalent logic towards an output of the netlist region.