Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-09-21
2001-12-11
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06330707
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to an improved automatic routing method utilized for designing an LSI through routing. More particularly, the present invention relates to an improved routing method for eliminating design rule errors by removing/re-routing and to an improved method for searching for wiring routes. Specifically, the present invention searches for wiring routes by applying a maze algorithm to a wiring region divided into a plurality of grids. In particular, the method of the present invention is adapted to search for a wiring route satisfying a constraint applied on the height or the lateral width of a wiring region irrespective of the number of grids of the wiring region.
Removing/re-routing is a conventionally known routing method attaining satisfactory results. In accordance with this re-routing method, if one of the wires already routed prevents a predetermined net from being routed, then the wire is removed, the predetermined net is routed and the wire removed is re-routed.
Such a re-routing method is disclosed, for example, by Youn-Long Lin et al., “A Detailed Router Based on Simulated Evolution”, 1988 International Conference on Computer Aided Design, in which design rule errors (i.e., shortcircuit of a wire) resulted from initial routing is eliminated by removing/re-routing. Hereinafter, the processing procedure of this conventional method will be described.
First, in order to meet a given hardwiring request, initial routing is performed independently on respective nets. That is to say, wiring routes are once determined without taking design rule errors caused with other wiring routes into consideration. In the above-described document, initial routing is carried out in accordance with a greedy algorithm by moving a column from left to right.
Next, if no design rule errors exist in any of the currently routed wires, then it is determined that the routing process should end. However, if any obstructive wire causing a design rule error exists, then the wire is extracted as a wire to be removed. Specifically, this extraction step is performed in the following manner.
First, the score of a net is evaluated by the following Equation 1:
Score of net=
a
×(number of design rule errors)+
b
×(number of contacts−number of terminals)+
c
×(real wire length/estimated wire length) (1)
(where a, b and c are parameters)
the “estimated wire length” is herein equal to one half of the entire peripheral length of a minimum rectangle surrounding a plurality of terminals to be interconnected.
Thereafter, it is determined based on a comparison between the score of a net and a random number whether or not the net should be removed. For example, if the net has a score larger than the random number, then the net is extracted as a wire to be removed.
Subsequently, the extracted wire is removed, a target net is routed and then the wire removed is re-routed.
On the other hand, a maze algorithm has conventionally been used for searching for a route interconnecting a plurality of terminals. Such a maze algorithm is disclosed, for example, by Frank Rubin et al., “The Lee Path Connection Algorithm”, 1974 IEEE Transactions on Computers, Vol. c-23, No.9. In accordance with this maze algorithm, a wiring route cost given by the following Equation 2 is used:
Wiring route cost=
a
×(wire length)+
b
×(number of contacts)+
c
×(number of design rule errors) (2)
(where a, b and c are also parameters)
If a cost regarding a design rule error is defined for a wiring route cost in accordance with Equation 2, then the design rule errors can be gradually eliminated by repeatedly performing removing/re-routing.
In recent years, in order to enhance the performance of a MOSFET, fabrication technologies for reducing the diffusion resistance of the MOSFET by utilizing silicide and/or salicide process techniques have been commonly used. Before such fabrication technologies were developed, source/drain electrodes
81
and
82
of a conventional MOSFET with high diffusion resistance shown in FIG.
9
(
a
), including gate, source and drain electrodes
80
,
81
and
82
, had to be extended as metal wires
71
from a diffusion region
70
via a large number of contacts
72
. However, since the diffusion resistance of a MOSFET is reduced by utilizing such fabrication technologies, the number of contacts
72
in the source/drain electrodes
81
and
82
can be considerably reduced as shown in FIG.
9
(
b
). Thus, as can be understood from FIG.
9
(
b
), source/drain terminals
71
A and
71
B, each having a small number (e.g., one in FIG.
9
(
b
)) of contacts
72
, may be formed at any arbitrary positions in the source/drain regions.
The present inventors carried out intensive analysis on an automatic routing/designing method of an LSI, in view of such progress in fabrication technologies. And we paid special attention to the fact that if the positions of the source/drain terminals
71
A and
71
B are appropriately moved within the source/drain regions, then a metal wire
71
C can be placed over a part of the diffusion region
70
where the source/drain terminals
71
A and
71
B are not placed as shown in FIG.
9
(
b
). From this point of view, we found that if the presence of freely movable terminals within a certain region is taken into consideration and if the freely movable terminals are appropriately placed in accordance with the situations of surrounding wires, then high-density routing results can be obtained.
However, according to the conventional removing/re-routing method, the positions of terminals are fixed and therefore cannot be appropriately moved in accordance with the situations of wires.
An exemplary conventional method for searching for wiring routes in accordance with the maze algorithm as disclosed by Frank Rubin et al. in the above-identified document will be described with reference to the flow chart illustrated in FIG.
24
.
First, in Step S
10
, hardwiring information is input. Next, in Step S
20
, currently searchable grids are extracted. Searchable grids adjacent to a grid in a list L, i.e., available grids other than grids specified as being located in a wiring forbidden region and grids in which terminals are located, are put into a list L
1
. At the same time, search directions from the grid in the list L to the respective searchable grids are saved. The grids in the list L
1
are extracted as searchable grids.
Then, in Step S
40
, wire length costs are added while the searchable grids, extracted in Step S
20
, are being searched for. Every time one grid is passed, a wire length cost of “1” is added. Next, a particular grid having a minimum cost is selected from the grids in the list L
1
and inserted into the list L.
Subsequently, in Step S
50
, it is determined whether or not an end point has been reached. If the end point has been reached, then the process advances to the next step. Otherwise, the process returns to Step S
20
. In other words, if a grid to be reached is included among the grids in the list L, then the process advances to the next Step S
60
of selecting a route having a minimum cost. Otherwise, the process returns to Step S
20
.
In Step S
60
, a wiring route having a minimum cost is extracted by tracing back the route using the search directions saved in Step S
20
.
Hereinafter, this process will be described in more detail with reference to FIG.
25
. Herein, the number of wiring layers is assumed to be one for the sake of simplicity. A wiring region
20
is divided into a large number of grids
30
. In the wiring region
20
, terminals
10
A,
10
a,
10
B,
10
b,
10
C and
10
c
and a wiring forbidden region
21
are present.
In Step S
10
, hardwiring information is input. The numerals of the terminals
10
A,
10
a,
10
B,
10
b,
10
C and
10
c
denote the number of respective nets and a pair of terminals having the same number (e.g., the terminals
10
A and
10
a
) should be hardwired to each other.
A case of routing Net
1
will
Fukui Masahiro
Shinomiya Noriko
Matsushita Electric - Industrial Co., Ltd.
Peabody LLP Nixon
Robinson Eric J.
Smith Matthew
Thompson A. M.
LandOfFree
Automatic routing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Automatic routing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automatic routing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2585865