Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-09-02
2002-05-14
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C703S002000
Reexamination Certificate
active
06389576
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for optimizing a real-value function in Boolean domain.
2. Background Art
The design of a circuit involves both identifying circuit components necessary to accomplish one or more functions and determining a physical arrangement of the identified circuit components. It is generally desirable to find an optimal circuit design which minimizes the size and cost of the circuit and maximizes the speed and efficiency of the circuit.
Optimization of the circuit components which are to comprise a circuit is generally accomplished in the Boolean domain. Circuit components for generating the desired circuit function are represented by one or more Boolean operators, such as AND/XOR etc., with each operator or combination of operators representing an electronic “gate” or component. Once the components of a desired circuit have been represented with the appropriate Boolean operators, it is possible to optimize the circuit using the known laws of Boolean algebra.
Application of these laws may permit the various Boolean operators representing the circuit to be reconfigured, such as by lessening the total number of operators (and hence circuit components) needed to create the desired circuit. The various operators of the optimized Boolean operator set are then converted back into corresponding real circuit components, i.e. transistors, diodes, etc.
Once the circuit components are known, the layout of these components is performed in the real domain (i.e. non-Boolean domain). The various components may be mapped into Cartesian coordinates and moved about until their arrangement is optimized. For example, the optimum arrangement of the components may be that where they occupy the least space or have the shortest interconnect distances.
A significant problem associated with this method of circuit design is that the circuit component determination and component layout portions of the design phase are performed independently. As a result, optimal circuit design conditions which are achieved in one portion of the design phase may be unusable in a later portion of the design phase. As an example of this problem, the optimal choice of circuit components might differ if it were possible to consider the layout or arrangement of the components at the same time as the possible combinations of the components.
A source of this problem is that the two portions of the design phase are performed independently, the circuit component portion of the design phase being performed in the Boolean domain and the layout portion performed in the real domain.
It would be advantageous if the two portions of the design phase, i.e. that in the Boolean and real domains, could be merged. It would be advantageous if the domains could be merged and optimization in both domains realized when optimization in the Boolean domain is accomplished.
SUMMARY OF THE INVENTION
The invention is a method and apparatus for optimizing a real function in the Boolean domain.
In accordance with one embodiment of the method, the real function is represented as a Boolean function. A binary decision diagram for the Boolean function is created, the binary decision diagram having a root and at least one variable node. The number of vertices for at least one variable node of the binary decision diagram is determined.
The function is optimized by selecting a path leading from the root to a variable node of the binary decision diagram having the least number of associated vertices. The solution values of one or more variables of the Boolean function are determined in accordance with the path(s) through the binary decision diagram. These values comprise an optimized solution set for the real function.
In one or more embodiments, the method may be utilized to determine the shortest “interconnect” path between two or more points. In this arrangement, the Boolean function represents one or more segments of an interconnect having end-points at the points to be connected. Solution values for the connecting points of the segment of the interconnect are yielded from the path through the binary decision diagram.
In one or more embodiments, computer hardware and/or software is arranged to perform the method of the invention.
Further objects, features and advantages of the invention will become apparent from the detailed description of the drawings which follows, when considered with the attached figures.
REFERENCES:
patent: 5434794 (1995-07-01), Coudert et al.
patent: 5461574 (1995-10-01), Matsunaga et al.
patent: 5469367 (1995-11-01), Puri et al.
patent: 5712792 (1998-01-01), Yamashita et al.
patent: 5748486 (1998-05-01), Ashar et al.
patent: 5805462 (1998-09-01), Poirot et al.
patent: 5966523 (1999-10-01), Uchino
patent: 6035109 (2000-03-01), Ashar et al.
patent: 6308299 (2001-10-01), Burch et al.
NA920662, “Determining the Height of Differential Cascode Voltage Switch Arrays”, IBM Technical Disclosure Bulletin, vol. 35, No. 1A, Jun. 1992, pp. 62-66 (6 pages).*
Gunther et al., “Minimization of free BDDs”, Proceedings of the ASP-DAC '99, Asia and South Pacific Design Automation Conference, vol. 1, Jan. 18, 1999, pp. 323-326.*
Ashar et al., “Boolean satisfiability and equivalence checking using general binary decision diagrams”, Proceedings of the 1991 IEEE International Conference on Computer Design: VLSI in Computers and Processors, Oct. 14, 1991, pp. 259-264.*
Aagaard et al., “Formal verification using parametric representations of Boolean constraints”, Proceedings of 36th design Automation Conference, Jun. 21, 1999, pp. 402-407.*
Bose et al., “Sequential path delay test generation by symbolic analysis”, Proceedings of the Fourth Asian Test Symposium, Nov. 23, 1995, pp. 353-359.*
Yu et al., “BDD-based synthesis of extended burst-mode controllers”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, No. 9, Sep. 1998, pp. 782-792.*
Bechir et al., “Cyclogen: automatic, functional-level test generator based on the cyclomatic complexity measure and on the ROBDD representation”, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 42, No. 7, Jul. 1995.*
Bhattacharya et al., “Test generation for path delay faults using binary decision diagrams”, IEEE Transactions on Computers, vol. 44, No. 3, Mar. 1995, pp. 434-447.*
Bahar et al., “Algebraic decision diagrams and their applications”, 1993 IEEE/ACM International Conference on Computer-Aided Design, ICCAD-93, Digest of Technical Papers, Nov. 7, 1993, pp. 188-191.*
Bryant, Randal E., “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, Aug. 1986, pp. 677-691, vol. C-35, No. 8.
Oliver Coudert, “Solving Graph Optimization Problems with ZBDDs”, European Design and Test Conference, 1997.
Lam William
McWilliams Thomas M.
Kik Phallaka
Smith Matthew
Sun Microsystems Inc.
The Hecker Law Group
LandOfFree
Method and apparatus for optimizing real functions in... 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 apparatus for optimizing real functions in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing real functions in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2908518