Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-07-22
2002-06-25
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06412103
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of the design of electronic devices, such as printed circuits boards and semiconductor devices, and more particularly to improvements in routing of a number of nets in tracks of a channel of an electronic devices.
BACKGROUND OF THE INVENTION
Many automatic layout systems, especially VLSI circuits, apply channel routing as the basic interconnection function. However, many routers can only cope with the geometric regularity of standard cell and gate array designs. As a result these prior art automatic layout systems can not route channels with geometric generality, i.e. terminals that can have different width and irregular spacing, and simultaneously guaranteeing completion of all routes.
From Bryan Preas, “Channel Routing With Non-Terminal Doglegs”, Proc. The European Design Automation Conference, Glasgow, Scotland, 1990, pp 451-458, a method for resolving cyclic vertical constrains using a generalized channel model is known. When this method is combined with a constraint based channel router, routing completion can be guaranteed for a large class of channel geometries. This method is implemented with a constrain-based, alternating-edge dogleg channel router. The method resolves cyclic constrains by adding non-terminal doglegs to enough wire segments to break all of the constraint cycles. The altered wire segments and the resulting acyclic constraint graph can be used as input to most constraint-based channel routers.
The common disadvantage of all prior art channel routers is that they can not deal with multi-layer channels having overlapping terminals because vertical constrains can not be resolved. Also, if there are terminals on more than two sides of the channel the prior art routers do not work.
It is therefore an underlying problem of the invention to provide an improved method for routing a number of nets and tracks of a channel, a method for manufacturing an electronic device and an electronic device featuring improved routing.
SUMMARY OF THE INVENTION
The problem of the invention is solved basically by applying the feature laid down in the independent claims. Further preferred embodiments are set out in the dependent claims.
The invention is advantageous in that is allows to deal with channel geometries in which individual terminals can create incoming and outgoing edges in the corresponding vertical constraint graph at the same time. This allows to use the invention for routing of multi-layer channels having overlapping terminals on different layers and also with channels having terminals on every side. The invention is also applicable for other kinds of channels because of its generality.
According to a preferred embodiment of the invention a critical node of the vertical constraint graph of the channel to be routed is split in two or more new nodes in order to resolve vertical constrains. To find the optimum number of new nodes a graph coloring method is employed. This guarantees that only a minimum of new nodes results from the splitting operation and thus a minimum number of row segments to route the same net.
Another advantage of the method of the invention is that it is adopted to be carried out automatically by means of a computer program which requires data descriptive of the channel geometry and the nets to be routed as input data. This allows it to minimize design cycle times.
An electronic device that is routed and produced according to the principles of the invention features improved compactness of design due to the improved routing. The improved routing also results in a minimized overall wiring length as well as minimized requirements for precious silicon floor space in the case of a semiconductor device.
These advantages have a beneficial impact on signal propagation delays and power dissipation. As a consequence the overall operational speed of such an electronic device is improved. For the case of a clocked electronic device the clocking frequency can be increased as compared to prior art devices.
REFERENCES:
patent: 5272645 (1993-12-01), Kawakami et al.
patent: 5295082 (1994-03-01), Chang et al.
patent: 5841664 (1998-11-01), Cai et al.
patent: 6086631 (2000-07-01), Chaudhary et al.
patent: 6099583 (2000-08-01), Nag
Anthony D. Johnson, “On Locally Optimal Breaking of Complex Cyclic Vertical Constraints in VLSI Channel Routing,” IEEE, 1996, pp. 62-95.*
Bryan Preas, “Channel Routing with Non-Terminal Doglegs,” IEEE, 1990, pp. 451-458.*
Antonije D. Jovanovic, “Modeling the Vertical Constraints in VLSI Channel Routing,” IEEE, 1993, pp. 11-13.*
Howard H. Chen, “Breaking Cycles and Vertical Constraints in Deutsch's New and More Different Channel-Routing Problems,” IEEE, 1990, pp. 539-542.
Gopalakrishnan Vijayan
Marchenko Alexander
Plis Andrey P.
Fink Mark J.
Motorola Inc.
Siek Vuthe
LandOfFree
Routing method removing cycles in vertical constraint graph does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing method removing cycles in vertical constraint graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing method removing cycles in vertical constraint graph will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2969102