Method and system for breaking complex Boolean networks

• US 6,397,370 B1
• Filed: 12/18/1998
• Issued: 05/28/2002
• Est. Priority Date: 12/18/1998
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Candence Design Systems Incorporated
• Inventors: Fernandez, Jean-Michel, Tarroux, Gerard
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/216,357
• Time in Patent Office: 1,257 Days
• Field of Search: 716/2
• 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 method and system reduces the complexity of functions within a Boolean network by breaking the network at certain nodes. Before the flattening phase of a technology independent optimization, the present invention estimates the on-set and off-set complexities of each node of the network. The complexities are estimated by considering the type of function represented by the node, the estimated complexities of any child nodes, and the number of variables in the support of the node. If a node'"'"'s estimated complexity exceeds a defined complexity limit, then the network is preferably broken at that node. A new node of the same type as the complex node is created, and child nodes of the complex node are appended to the newly created node. In addition, an intermediate node is created as a child of the complex node and the child nodes are removed from the complex node. Removing the child nodes from the complex node reduces the complexity of the node and allows the minimization phase to better optimize the network.

Claims

1. A method of processing a network having one or more nodes representing Boolean functions, comprising the steps of:

estimating the complexity of the one or more nodes of the network;

determining whether the complexity of the one or more nodes exceeds a complexity limit; and

reducing the complexity of the one or more nodes if the complexity limit is exceeded by the estimated complexity.

2. The method of claim 1, wherein the network represents an electronic circuit.

3. The method of claim 1, wherein the estimating step comprises the steps of:

for each node in the network;

determining a support of a node;

determining estimated complexities of any child nodes of the node;

and

calculating an estimated complexity for the node based on the support and the estimated complexities of any child nodes.

4. The method of claim 1, wherein the estimating step comprises the steps of:

determining a Boolean function represented by a node;

determining a support of the node; and

calculating an estimated complexity for the node based on the Boolean function represented by the node and the support of the node.

5. The method of claim 4, wherein the calculating step comprises the steps of:

estimating an on-set complexity for the node based on the support of the node and the Boolean function represented by the node; and

estimating an off-set complexity for the node based on the support of the node and the Boolean function represented by the node.

6. The method of claim 1, wherein the step of reducing the complexity of the one or more nodes having the estimated complexity exceeding the complexity limit comprises the step of:

breaking the network at the one or more nodes having the estimated complexity exceeding the complexity limit.

7. The method of claim 6, wherein the step of breaking the network at the one or more nodes having the estimated complexity exceeding the complexity limit breaks the network at a first node and comprises the steps of:

creating a new node representing a same Boolean function as the first node; and

making at least one child node of the first node a child node of the new node.

8. The method of claim 7, wherein the step of creating a new node further comprises the step of:

creating an internal node having the first node as a parent node and the new node as a child node.

9. The method of claim 1, wherein said one or more nodes comprises at least two nodes.

10. A computer system for optimizing an abstract representation of an electronic circuit, the computer system comprising:

a module for receiving a Boolean network having a parent node and a plurality of child nodes logically connected to the parent node, the Boolean network used to abstractly represent an electronic circuit;

a module for determining complexities of the parent node and the plurality of child nodes; and

a module for breaking the Boolean network at the parent node in response to determined complexities of the parent node and the plurality of child nodes.

11. The computer system of claim 10, wherein the module for determining complexities of the parent node and the plurality of child nodes estimates the complexities of the nodes.

12. The computer system of claim 10, wherein the module for determining complexities of the parent node and the plurality of child nodes comprises:

a module for determining one or more on-set complexities of the parent node and the plurality of child nodes; and

a module for determining one or more off-set complexities of the parent node and the plurality of child nodes.

13. The computer system of claim 12, wherein the module for determining the on-set complexity of the parent node comprises:

a module for determining the on-set complexity as the product of the on-set complexities of the plurality of child nodes logically connected to the parent node if the parent node is an AND node; and

a module for determining the on-set complexity as the sum of the on-set complexities of the plurality of child nodes logically connected to the parent node if the parent node is an OR node.

14. The computer system of claim 12, wherein the module for determining the off-set complexity of the parent node comprises:

a module for determining the off-set complexity as the product of the off-set complexities of the plurality of child nodes logically connected to the parent node if the parent node is an OR node; and

a module for determining the off-set complexity as the sum of the off-set complexities of the plurality of child nodes logically connected to the parent node if the parent node is an AND node.

15. The computer system of claim 10, wherein the module for breaking the Boolean network at the parent node in response to determined complexities of the at least one parent node and at least one child node comprises:

a module for breaking the Boolean network at the parent node in response to a determined complexity of the parent node exceeding a predetermined limit.

16. The computer system of claim 10,

wherein said module for determining complexities of the parent node and the plurality of child nodes comprises a module for determining whether an estimated complexity of the parent node and each of the child nodes exceeds a complexity limit, and

wherein said module for breaking the Boolean network at the parent node in response to, determined complexities of the parent node and the plurality of child nodes comprises a module for reducing the complexity of any of the parent node and child nodes whose estimated complexity exceeds the complexity limit.

17. A computer program product having a computer-readable medium having computer program instructions encoded thereon for optimizing a Boolean network comprising one or more nodes representing Boolean functions, the computer program instructions for:

estimating the complexity of a first node of the Boolean network;

determining whether the estimated complexity of said first node exceeds a complexity limit; and

reducing the complexity of the Boolean network at said first node in response to a determination that the estimated complexity of said first node exceeds the complexity limit.

18. The computer program product of claim 17, wherein the computer program instructions for reducing the complexity of the Boolean network comprise instructions for:

inverting the estimated complexity of said first node having the estimated complexity exceeding the complexity limit.

19. The computer program product of claim 18, wherein the estimated complexity comprises an estimated on-set complexity and an estimated off-set complexity, and wherein the computer program instructions for inverting the estimated complexity comprise instructions for:

swapping the estimated on-set complexity with the estimated off-set complexity.

20. The computer program product of claim 18, further comprising instructions for:

choosing between inverting the Boolean network and breaking the Boolean network at said first node having the estimated complexity exceeding the complexity limit.

21. The computer program product of claim 18, wherein the computer program instructions comprise instructions for:

estimating the complexity of at least two nodes of the Boolean network, said at least two nodes including said first node;

determining whether the estimated complexity of said at least two nodes exceeds the complexity limit; and

reducing the complexity of the Boolean network at any of said at least two nodes whose estimated complexity exceeds the complexity limit.

22. The computer program product of claim 17, wherein the computer program instructions for reducing the complexity of the Boolean network comprise instructions for:

breaking the Boolean network at said first node having the estimated complexity exceeding the complexity limit.