Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1996-10-15
2003-01-07
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06505331
ABSTRACT:
TECHNICAL FIELD
This invention relates to the design of electronic devices, such as integrated circuit chips and, more particularly, to the routing of nets in such chips to minimize the interconnection cost and to maximize the speed of operation.
BACKGROUND OF THE INVENTION
From the prior art a number of approaches for designing very large scale integrated (VLSI) circuit chips is known especially as far as the routing of nets between the internal components of a chip are concerned. Channel routing is used extensively in the layout of integrated circuits and printed circuit boards. It is flexible enough to allow its use in various design styles such as gate-arrays, standard cells, and macro cells.
A channel router is designed to route nets that interconnect nodes on two opposite sides of a region called the channel. Criteria for a good channel router are that it routes the interconnections in a minimum area, the added length of the net wiring being also at a minimum. Examples for prior art channel routers are described for example in IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN, VOL. CAD-4, NO. 3, JULY 1985, pages 208-219, by James Reed et al and in “CHAMELEON: A NEW MULTI-LAYER CHANNEL ROUTER”, Douglas Braunt et al. IEEE, 1986, conference proceedings of the 23rd design automation conference.
In order to increase the overall quality of the routing attempts have been made to include information about the so called “feed-throughs” in the process of channel routing. Such approaches are known from “FEED THROUGH RIVER ROUTING”, A. Joseph et al, INTEGRATION, the VLSI Journal 8, pages 41-50, El Revier Science Publishers B.V., 1989 and “MULTI CHANNEL OPTIMIZATION IN GATE-ARRAY LSI LAYOUT”, K. Aoshima and E. S. Kuh, IEEE, 1983.
Since there is a constant need to further increase the wiring density in VLSI technology it is an underlying problem of the invention to devise an improved method for routing of nets for the design of electronic devices.
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 of the invention are given in the dependent claims.
The invention is advantageous in that it allows to design a VLSI layout requiring a minimum of silicon floor space which has a positive effect on chip yield and price. These extreme layout densities can be obtained by a fully automated solution which only requires moderate computing resources in terms of computer memory and run time.
The invention allows to generate separate sub graphs which contain the nodes to be connected both for the so called “cluster areas” and the “channel areas”. These sub graphs are derived from input data which comprise the nodes of each net to be routed as well as the assignment of the nodes to clusters. Additional logical nodes which are defined by means of a minimal Steiner tree are inserted into the input data whereby the subgraphs are found. When the clusters are aligned horizontally it is advantageous to use rectilinear Steiner trees for defining such additional logical nodes.
Each cluster has one subgraph for each net to be wired. Analogously each channel has a dedicated subgraph for each net. As the subgraphs are descriptive of the interconnections to be established any method, including hand crafted design, can be used to actually route the subgraphs—or with other words—to map the subgrahs onto the physical design of the integrated circuit chip.
For routing the channel area a lot of automated prior art methods are known. If such a method is to be employed the subgraphs of the channel areas can be used as input data for such prior art methods.
For routing of the clusters it is advantageous to employ the automated routing method which is described in the dependent method claims. For this method first the actual electrical connectivities which can be established between the nodes in each of the clusters have to be described. This is done by a graph representation which forms the basis of the intra cluster routing method.
According to this method subgraphs which represent the desired electrical interconnections to be established between the nodes in a given cluster are mapped on a graph which represents the potential electrical connectivities within the given cluster. To carry out this procedure no human interaction is required. The steps of the method of the invention can be realized by programming a general purpose digital computer, which is fed with the required design data, i.e. the placement of the clusters, the nets to be wired and the assignment of the nodes of the nets to the clusters.
REFERENCES:
patent: 4577276 (1986-03-01), Dunlop et al.
patent: 4811237 (1989-03-01), Putatunda
patent: 4908772 (1990-03-01), Chi
patent: 5491641 (1996-02-01), Scepanovic et al.
patent: 5923646 (1999-07-01), Mandhyan
patent: 6014507 (2000-01-01), Fujii
patent: WO91/06061 (1991-05-01), None
“A weighted Steiner Tree-Based Global Router with Simultaneous Length and Density Minimization”, by C Chiang, C.K. Wong, M. Sarratzadeh, 8200 IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13 No. 12 Dec. 1994, pp. 1461-1469.
Algor Ilan
Bracha Gabriel
Weisberger Eytan
Do Thuan
Motorola Inc.
LandOfFree
Method for routing of nets in an electronic device 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 routing of nets in an electronic device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for routing of nets in an electronic device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3043178