Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-07-26
2002-05-14
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
Reexamination Certificate
active
06389376
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for generating one or more n-segment Steiner trees, the trees representing minimal manhattan-space distance connections avoiding obstacles.
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., 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 around until their arrangement is optimized. As part of this layout process, an arrangement for the interconnections of the components must also be determined.
For example, in submicrocircuit design, electronic gates are connected with microstrips. The speed of the circuit is at least partially dependent upon the length of the microstrips between gates, as in general the electronic signal time delay of a particular gate is approximately equal to the delay associated with the traversal of the signal through the interconnect between gates. As such, in the design of such a circuit, an objective is to arrange the gates or terminals of the circuit so that they are connected with a minimum length of microstrip lines.
The network of microstrips or lines which connects the components or gates is generally referred to as a Steiner tree. As stated above, it is desirable for the Steiner tree to have a minimum total length. Generally, the Steiner tree is developed in real Euclidian space, with the limitation that the lines forming the tree and connecting the components follow rectilinear coordinates.
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 destroyed 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.
SUMMARY OF THE INVENTION
The invention is a method and apparatus for generating n-segment Steiner trees connecting two or more points. In one or more embodiments, the Steiner tree represents an interconnect of two or more points in space, such as a microstrip connection of terminals of a component.
One embodiment of the invention comprises a method comprising the following steps: generating a Boolean network function representing a network of interconnects, each interconnect having as an end point one of said at least two points; determining a binary decision diagram for the Boolean network function; and determining a Steiner tree by determining solution values for the Boolean network function in accordance with the binary decision diagram. In one or more embodiments, the Boolean network function represents a network of interconnects having “n” segments.
In one or more embodiments, the step of determining a binary decision diagram includes the step of determining a number of vertices corresponding to at least one variable node of the diagram, and the step of determining solution values comprises the step of selecting a path from a root of the binary decision diagram to a variable node. In one embodiment, an optimal Steiner tree solution is determined by determining solution values from a path from the root to a variable node having the least number of vertices.
In one or more embodiments, the Boolean network function is generated from individual Boolean interconnect function for interconnects corresponding to each point to be connected, the interconnects all joining at a common joint. In one or more embodiments, the solution value yielded is the coordinates of the joint of the interconnects and the Steiner tree is determined from the joint and coordinate points.
One or more embodiments of the invention comprise a hardware and/or software for generating one or more Steiner trees forming the connection of two or more points.
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: 5491641 (1996-02-01), Scepanovic et al.
patent: 5587923 (1996-12-01), Wang
patent: 5717229 (1998-02-01), Zhu
patent: 5805462 (1998-09-01), Poirot et al.
patent: 6086626 (2000-07-01), Jain et al.
patent: 6132980 (2001-11-01), Rostoker et al.
Huibo Hou et al., “Non-Hanan routing”, Transactions on Computer aided design of Integrated circuits and systems, Apr. 1999.*
Haiyun Bao, et al., “A new global routing algorithm independent of net ordering”, Design Automation Conference, 1999.*
Shin-ichi Minato et al., “Shared Binary decision diagram with attribute edges for efficient Boolean function manipulation”, 27th ACM/IEEE Design Automation Conference, 1990.*
Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, Aug. 1986, pp. 677-691, vol. C-35, No. 8.
Lam William
Xing Zhaoyun
Sun Microsystems Inc.
The Hecker Law Group
LandOfFree
Method and apparatus for generating n-segment steiner trees 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 generating n-segment steiner trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating n-segment steiner trees will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2911220