Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-03-06
2002-11-05
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06477693
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of the design and manufacture of electronic devices, such as printed circuit boards and semiconductor devices, and more particularly to improvements in designing the wiring of a channel.
BACKGROUND OF THE INVENTION
For the design of the wiring of a channel numerous approaches are known from the prior art. In the reference book by Naveed Sherwani, “Algorithms for VLSI Physical Design Automation”, Second Edition, 1995, Kluwer Academic Publishers, an overview of prior art routing approaches is given, especially on pages 267 to 339.
One approach which is commonly used in the prior art for channel routing is the modeling of the routing problem by means of a vertical constraint graph. In a vertical constraint graph each net to be routed is represented by one node in the graph. If a vertical constraint exists between any terminal of a net and any terminal of another net the two corresponding nodes in the vertical constraints graph are connected by a directed edge in order to represent the vertical constraint. This way initially each net to be routed is assumed to be routable by just one horizontal trunk in the channel.
If any cycles exist in the vertical constraints graph these must be removed by a technique called “doglegging” prior to the actual assignment of trunks. The doglegging technique is also described in the above cited reference by Naveed Sherwani, in Chapter 7.4.2.2, pages 299-301. A more detailed description of the doglegging technique is given in D. N. Deutsch,“A dogleg channel router”, Proceedings of 13th ACM/IEEE Design Automation Conference, page 425-433, 1976 and in Preas, “Channel Routing with Non—Terminal Doglegs”, Proceedings of the European Design Automation Conference, March 1990, Glasgow, UK, pages 451-458.
With reference to
FIG. 1. a
common prior art approach of using a vertical constraint graph and doglegging for channel routing is explained in more detail:
In step
100
all the terminals of the same net to be routed are logically unified into one single imaginary trunk in the channel. In step
102
a vertical constraints graph is built according to this abstraction.
In step
104
it is decided whether the vertical constraints graph built in step
102
has cycles. If no cycles exist this means that the channel can in fact be routed by making usage of the imaginary trunks as defined in step
100
. In this case the trunks are in fact assigned to the channel in step
106
in order to produce the wiring layout.
If there are cycles in the vertical constraint graph the control goes from step
104
to step
108
. In step
108
cycles in the vertical constraints graph are removed by means of doglegging. By doglegging the imaginary trunks as defined in step
100
are broken up into segments in order to remove conflicting vertical constraints. Next in step
106
the assignment of trunks to the channel is done.
The main disadvantages of this prior art approach are the computational requirements which increase by the power of four with the number of nets and the fact that it is not guaranteed that—even after lengthy computation—all cycles can be removed in step
108
before the trunks are assigned to the channel for all classes of channel routing problems encountered in practice. Therefore a need exists for an enhanced method for designing and manufacturing an electronic device.
SUMMARY OF THE INVENTION
The underlying problem of the invention is solved basically by applying the features laid down in the independent claims. Preferred embodiments are given in the dependent claims.
The method of the invention is advantageous in that it allows the design and manufacture of an electronic apparatus, such as an integrated circuit chip or printed circuit board which has conflicting vertical constraints for which no solution could be found by any prior art design method.
The classes of problems which can be solved by the method of the invention include the following classes for which known prior art design methods fail:
1. Conflicting vertical constraints which can not be resolved by splitting of a node in the vertical constraints graph because splitting does not result in reducing the number of cycles; and
2. Conflicting vertical constraints which can not be resolved because splitting of the respective node does not create a cycle.
The invention is advantageous in that it uses a compositional approach. Initially all the terminals of the channel to be routed are represented individually in the terminal vertical constraints graph and also the vertical constraints which exist between individual terminals are represented in the terminal vertical constraint graph. This way the complete information about the routing problem to be solved is included in the terminal vertical constraint graph.
Further the compositional approach of the invention is advantageous in that it requires far less computing time; the computational requirements only increase with the power of three with the number of nets. Further, unnecessary computing time is saved because according to the invention the existence of a solution can be predicted at an early stage.
Further, the method of the invention can be applied under weaker restrictions as compared to the prior art so that the channel routing quality can be improved thereby.
This leads to the design and production of enhanced electronic devices which feature a more compact channel wiring design and therefore require less silicon floor space and less power dissipation. The more compact channel wiring design which results from the method of the invention also positively impacts signal propagation delays and therefore the overall operational speed of the electronic device and/or the electronic apparatus, such as a digital radio or audio device, in which it is integrated.
Further, the invention is advantageous in that it can be readily implemented by means of a computer program which is stored on an computer readable storage medium.
REFERENCES:
patent: 5793643 (1998-08-01), Cai
patent: WO97/34245 (1997-09-01), None
S-C Fang et al., A New Efficient Approach to Multilayer Channel Routing Problem, 29thACM/IEEE Design Automation Conference, pp. 579-584, Jul. 1992.*
Koji Sato et al., A Grid-Free Channel Router, 17thACM/IEEE Design Automation Conference, pp. 22-31, Jun. 1980.*
T. Yoshimura, An Efficient Channel Router, 21stDesign Automation Conference, pp. 38-44, Jun. 1984.*
M. Wada, A Dogleg “Optimal” Channel Router with Completion Enhancements, 18thDesign Automation Conference, pp. 762-768, Jun. 1981.*
Jovanovic A D: “Modeling the Vertical Constraints in VLSI Channel Routing”, Proceedings Great Lakes Symposium on VlSI Design Automation of High Performance VLSI Systems, Mar. 5, 1993, pp. 11-13, XP002042126.
Bryan Preas: “Channel Routing with Non-Terminal Doglegs”, Proceedings of the European Design Automation Conference, Mar. 1990, Glasgow, UK, pp. 451-458.
David N. Deutsch: “A Dogleg Channel Router”, Proceedings of 13thACM/IEEE Design Automation Conference, 1976, pp. 425-433.
Naveed Sherwani: “Algorithms for VLSI Physical Design Automation”, Second Edition, 1995, Kluwer Academic Publishers, pp. 267-344.
Marchenko Alexander
Plis Andrey
Vijayan Gopal
Motorola Inc.
Siek Vuthe
Thompson A. M.
LandOfFree
Method for manufacturing and designing a wiring of a channel... 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 for manufacturing and designing a wiring of a channel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for manufacturing and designing a wiring of a channel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2987433