Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-12-18
2002-05-28
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06397370
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever
BACKGROUND
1. Field of the Invention
This invention pertains generally to digital circuit design and particularly to the technology independent optimization stage of the design process.
2. Background of the Invention
Modem logic circuits are so complex that circuit designers must use computer-based techniques to help them in their task. The designers first abstractly represent the circuit as multiple combinatorial blocks (e.g., single-output, multiple-input Boolean equations) separated by sequential states. The combinatorial blocks are described by Directed Acyclic Graphs (“DAGs”, also referred to as Boolean networks or trees). In general, the computer-based techniques transform the abstract representation of the circuit design into a technology-dependent netlist representing the same circuit design.
Before converting the abstract representation of the circuit into a technology-dependent netlist, it is desirable to optimize the technology independent circuit design. There are three phases of optimization that are executed in sequence: flattening, minimization, and factorization. The flattening phase tries to remove intermediate functions in the Boolean network, the minimization phase tries to simplify the Boolean functions, and the factorization phase tries to reduce the number of literals in the “product of sum” form. These optimizations are often very successful.
However, the above-mentioned optimizations sometimes cannot be performed if the Boolean network is too complex. In practical terms, a Boolean network is “too complex” if the network is impossible to optimize in a reasonable amount of time using modern optimization algorithms implemented on state of the art computers.
Selective flattening is performed before the other two phases and is used to control the effect of the minimization phase. The selective flattening removes non-useful intermediate functions but avoids completely flattening the Boolean network. Since the flattening process may produce more complex Boolean functions than were previously present in the network, the first goal of the flattening phase is to guarantee that the other two phases of the Boolean optimization can be completed. Thus, the flattening process will not flatten a function if it estimates that the flattened function will be too hard to optimize.
However, some functions are already flat or are too complex for Boolean optimization even if the flattening phase is skipped. Therefore, the three-phase optimization approach does not work with such functions.
For example, consider the following Boolean function:
f
=
(
a
0
+
b
0
+
c
0
+
d
0
+
e
0
+
f
0
+
g
0
+
h
0
+
i
0
+
j
0
)
*
(
a
1
+
b
1
+
c
1
+
d
1
+
e
1
+
f
1
+
g
1
+
h
1
+
i
1
+
j
1
)
*
(
a
2
+
b
2
+
c
2
+
d
2
+
e
2
+
f
2
+
g
2
+
h
2
+
i
2
+
j
2
)
*
⋯
(
a
15
+
b
15
+
c
15
+
d
15
+
e
15
+
f
15
+
g
15
+
h
15
+
i
15
+
j
15
)
.
This network is already flat and, therefore, the flattening phase will have no effect. Moreover, the minimization phase, which aims to reduce the number of cubes of the on-set of a function, is unable to optimize the network because there are (a
0
*a
1
*a
2
. . . a
15
)+(a
0
*a
1
*a
2
. . . a
14
*b
15
)+ . . . +(j
0
*j
1
*j
2
. . . j
15
)=10
16
cubes to consider. The memory and processing time needed to minimize a network having such a huge number of cubes is far above the acceptable limits for an integrated circuit design automation tool.
Therefore, there is a need to modify the optimization process to allow the minimization phase to effectively process complex Boolean networks. More specifically, there is a need to add a new optimization phase before the flattening phase that detects a complex Boolean network and modifies the network so that it can be processed in the subsequent phases.
SUMMARY OF THE INVENTION
The above needs are met by a method and system for reducing the complexity of certain nodes in the Boolean network. In one embodiment, the present invention is a “network breaker” or a “network breaking phase” of the optimization process that executes just before the flattening phase. The network breaker reduces the complexity of nodes in the network by adding additional nodes to the network.
The network breaker preferably visits each node (i.e., Boolean function) of the Boolean network. In one embodiment, the network breaker considers the nodes in a depth-first order. In an alternative embodiment, the network breaker first visits those nodes having the largest support intersection.
The network breaker estimates the complexity of each node it visits. In a preferred embodiment of the present invention, the estimation of a node's complexity is measured with two components: the on-set complexity and the off-set complexity. For an AND node, the on-/off-set complexity is estimated as the minimum of:
the product of the estimated on-/off-set complexities of the children of the AND node; and
the maximum number of cubes that can be created from the AND node. For an OR node, the on-/off-set complexity is estimated as the minimum of:
the sum of the estimated on-/off-set complexities of the children of the OR node; and
the maximum number of cubes that can be created from the OR node. The complexities of a NOT node are estimated by swapping its estimated on-set and off-set complexities. In addition, the on-set and off-set complexities of a leaf node (a node without any children) are by definition equal to one.
Alternative embodiments of the present invention use different complexity estimates. For example, one embodiment also estimates the don't care complexity. An alternative embodiment used with binary decision diagram minimization uses a cost function based on the ordering of variables.
If the estimated on-set complexity of a node exceeds an on-set limit or the estimated off-set complexity of the node exceeds an off-set limit, the network breaker “breaks” the network by creating a new node of the same type (i.e., AND, OR, NOT) as the too-complex node. Child nodes are removed from the too-complex node and are appended to the new node. In addition, a new intermediate node is created having the formerly too-complex node as its parent and the new node as its child. Under certain circumstances, the network breaker inverts the function rather than inserting a new intermediate node. In addition, the limits used in the network breaker should also be used in the flattening phase to avoid destroying the effects of the breaking phase.
REFERENCES:
patent: 5297150 (1994-03-01), Clark
patent: 5432707 (1995-07-01), Leung
patent: 5487017 (1996-01-01), Prasad et al.
patent: 5774369 (1998-06-01), Horstmann et al.
patent: 5913101 (1999-06-01), Murofushi et al.
patent: 5926804 (1999-07-01), Tufts et al.
patent: 6212669 (2001-04-01), Jain
K. Keutzer, DAGON: Technology Binding and Local Optimization by DAG Matching, 24th ACM/IEEE Conference Proceedings on Design Automation, pp. 341-347, Jun. 1987.*
H. Cho et al., BEATNP: A Tool for Partitioning Boolean Networks, IEEE International Conference on Computer-Aided Design, pp. 10-13, Nov. 1988.
Fernandez Jean-Michel
Tarroux Gerard
Candence Design Systems, Inc.
Thompson A. M.
LandOfFree
Method and system for breaking complex Boolean networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for breaking complex Boolean networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for breaking complex Boolean networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851232