Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-11-12
2001-04-17
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06219823
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of automatically deciding wiring routes between terminals on a printed-circuit board or the like. The present invention ensures the requisite thicknesses of the wires and the minimum spacing between wires and confirms that a limitation on the capacity of a wiring route is not exceeded.
The capacity of a wiring route between terminals on a printed-circuit board is based on the required width of the wires, the minimum separation distance between wires, the number of wires required and the space available. Some of the wiring routes are predetermined and viewed as “obstacles” during the subsequent process of laying out the remaining wires. Previously known automatic wiring systems can re-position, by a “push-away” operation, a predetermined wiring route to make room for another wire. When the predetermined wire route is 90° or 45° relative to the new wire, it is possible with conventional routing systems to dynamically re-position the predetermined wire route in a reasonable amount of time. However, it-is not practical using conventional routing systems to re-position a predetermined wire route which lies at other, “free” angles relative to the new wire due to complexity of the calculations required.
A “rubber band” model has also been used to determine wire routing where there are previously wired lines. The rubber band model is representative of routes topologically equivalent and is expressed by a series of “critical cuts”. Each critical cut connects two objects in the shortest distance and is considered a line tightly extended between two terminals. If each critical cut does not exceed the wiring capacity, physical positioning of all the wires can be accomplished while meeting the wiring capacity as a whole. See E. Leiserson and F. M. Maley, “Algorithms for Routing and Testing Routability of Planar VLSI layouts,” Proc. STOC, pp. 69-78 (1985). Consequently, in the rubber band model the physical position of a previously wired line is not determined during route search for wiring, but it is determined by checking the physical wiring possibility with detailed wiring process after the position of all other wiring routes has been determined.
It is possible and common to convert another type of route expression to a rubber band model in real time. Then an accurate route capacity can be verified by a visibility graph or mesh structure obtained by region segmentation. However, only an approximate route capacity can be estimated automatically with conventional computer systems in a reasonable amount of time because of the complexity of calculating the capacities of all critical cuts. When there is excess room in a wiring region, the approximate determinations of capacity can obtain viable wiring routes. However, many printed circuit boards today have high density, and wiring is required to the very limit of the capacity. Therefore, for typical high-density wiring requirements, conventional routing systems require too much time to make free-angle adjustments between new wires and previously determined wire routes.
DISCLOSURE OF THE INVENTION
Accordingly, an object of the present invention is to make it possible to execute a wiring route search, meeting an accurate route capacity, in a wiring route whose wiring capacity is limited, by checking the capacity of a critical cut during route search for wiring.
Another object is to remove a wasteful recalculation of routes so that an automatic wiring process can be performed at a high speed.
Still another object is to provide a system which is capable of automatic wiring at a free angle.
A further object is to reduce the number of critical cuts whose wiring capacity is checked.
With the reduction in the number of critical cuts, the object of the present invention is also to improve the high-speed operation of the entire process of the route searching for wiring.
To achieve objects such as described above, the present invention is roughly divided into two parts. That is, the present invention includes a part for deciding a wiring route by accurately checking the capacity of a critical cut during route search for wiring and a process of reducing the number of critical cuts to be checked.
First, the former part is achieved by the following steps of:
(a) segmenting a plane into a plurality of regions whose vertexes are points which include the terminals and generating a route search graph which expresses a connection relationship between the plurality of regions;
(b) recording a line connecting two objects in a shortest distance as a critical cut together with a width of wires that can go through the critical cut, wherein the two objects include the terminals;
(c) recording a corresponding relationship relative to the critical cut and, when necessary, position information relative to the critical cut in edges of regions related to the critical cut and in a necessary terminal;
(d) in deciding the wiring route in the route search graph,
(d1) when it is detected, by using the position information recorded in a terminal or an edge on the wiring route being decided, that-the wiring route has come into one region of the plurality of regions, recording an incoming direction in the critical cut related to the one region by referring to the position information used in the detection;
(d2) when it is detected, from the position information recorded in a terminal or an edge which will be on the wiring route being decided, that the wiring route goes out of a region, judging whether the wiring route crosses the related critical cut, from the position information used where detecting the outgoing wiring route by referring to the incoming direction recorded in the related critical cut; and
(d3) when it is judged that the wring route crosses the critical cut, judging whether the wiring route can be wired by referring to the width of wires that can go through the critical cut.
By including these steps, the crossing of each critical cut can be detected with reliability and accurate capacity checking can be performed, so it is unnecessary to perform processing such as subsequently changing a wiring route later.
Also, the aforementioned step (c) may include the steps of.
(c1) when the critical cut is topologically equivalent to an edge of the plurality of regions, recording a corresponding relationship relative to the critical cut in the edge; and
(c2) when the critical cut crosses the regions, making a union region consisting of the regions that the critical cut crosses and recording a corresponding relationship and position information relative to the critical cut in edges which are a boundary of the union region, and when a terminal is included in the union region, recording a corresponding relationship and position information relative to the critical cut in the terminal.
If done in this way, processing can be performed with less data.
In addition, the aforementioned step (d1) may include the steps of:
(d11) detecting, by using the position information recorded in a terminal or an edge on the wiring route being decided, whether the wiring route has come into one region of the plurality of regions; and
(d12) based on the position information used when detecting that the wiring route has come into one region, recording the incoming direction relative to said critical cut in the critical cut crossing the one region into which the wiring route has come.
Similarly, the aforementioned step (d2) may include the steps of:
(d21) detecting, by using the position information recorded in a terminal or an edge which becomes the wiring route, whether the wiring route goes out of the region into which the wiring route came; and
(d22) by referring to the incoming direction recorded in the critical cut, judging whether the wiring route crosses the critical cut, from the outgoing direction based on the position information used when detecting the outgoing wiring route.
In addition to the aforementioned steps, the method of the present invention may further include a step (d4) of:
when it is detected, at the time
Etoh Hiroaki
Hama Toshiyuki
Do Thuan
Fraley Lawrence R.
International Business Machines - Corporation
Schmeiser Olsen & Watts
Smith Matthew
LandOfFree
Method and apparatus for deciding a wiring route and for... 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 deciding a wiring route and for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for deciding a wiring route and for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443379