Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-07-26
2003-08-19
Niebling, John F. (Department: 2812)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06609237
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to an improved routing path finding method for use in the automatic routing/designing process of an LSI. More specifically, the present invention relates to a method for finding a routing path by applying a maze algorithm to a routing region partitioned into a plurality of grid points. In particular, the method of the present invention is adapted to find a routing path while satisfying a height or width constraint, imposed on a routing region, irrespective of the number of grid points included in the routing region.
A maze algorithm is one of known routing path finding techniques. The maze algorithm is disclosed, for example, by Frank Rubin in “The Lee Path Connection Algorithm”, 1974 IEEE Transactions on Computers, Vol. c-23, No.9. Hereinafter, a known routing path finding method by the maze algorithm will be described with reference to FIG.
6
.
First, in Step S
10
, interconnection information is input. Next, in Step S
20
, currently available grid points are extracted. Available grid points adjacent to a grid point in a list L, i.e., non-occupied grid points other than those specified as being located in a routing forbidden region and grid points in which terminals are located, are put into a list L
1
. At the same time, search directions from the grid point in the list L toward the respective available grid points are saved. And the grid points in the list L
1
are extracted as available grid points.
Then, in Step S
40
, wire length costs are added while the available grid points, extracted in Step S
20
, are being searched. Every time one grid point is passed, a wire length cost of “1” is added. Next, a particular grid point, which can be reached from the source grid point at a minimum cost, is selected from the grid points in the list L
1
and inserted into the list L.
Subsequently, in Step S
50
, it is determined whether or not a sink terminal has been reached. If the answer is YES, then the process advances to the next step S
60
. Otherwise, the process returns to Step S
20
. In other words, if the sink grid point is included in the list L, then the process advances to the next Step S
60
of selecting a minimum cost path. Otherwise, the process returns to Step S
20
.
In Step S
60
, a minimum cost path is selected by tracing back the path in the search directions saved in Step S
20
.
Hereinafter, this process will be described in more detail with reference to FIG.
7
. In the illustrated example, the number of interconnection layers is assumed to be one for the sake of simplicity. A routing region
20
is partitioned into a large number of grid points
30
. In the routing region
20
, terminals
10
A,
10
a
,
10
B,
10
b
,
10
C and
10
c
and a routing forbidden region
21
are present.
In Step S
10
, interconnection information is input. The three enclosed numerals “1”, “2” and “3” attached to the terminals
10
A,
10
a
,
10
B,
10
b
,
10
C and
10
c
indicate the numbers of respective nets and a pair of terminals with the same number (e.g., the terminals
10
A and
10
a
with “1”) should be interconnected together.
For example, Net
1
can be routed in the following manner. The source terminal of Net
1
is the terminal
10
A and the sink terminal thereof is the terminal
10
a
. In Step S
20
, first, the grid point where the source terminal
10
A is placed is put into the list L. Then, available grid points adjacent to the source terminal
10
A are put into the list L
1
. In this example, four grid points vertically and horizontally adjacent to the source terminal
10
A are put into the list L
1
. At the same time, the search directions indicated by the arrows in
FIG. 7
are saved. And the four grid points in the list L
1
are extracted as available grid points.
Next, in Step S
40
, every time a single grid point has been passed, a wire length cost of “1” is added.
Then, at least one grid point with a minimum cost is/are selected from the list L
1
and put into the list L. Since all of the four grid points currently present in the list L
1
have the same cost of “1”, all of these four grid points are transferred into the list L.
Subsequently, since it is determined in Step S
50
that the sink terminal
10
a
has not been reached yet, the process returns to Step S
20
. Thereafter, until the sink terminal
10
a
is reached, the same processing steps S
20
, S
40
and S
50
will be performed repeatedly.
In
FIG. 7
, the numbers in respective grid points represent the results obtained by adding the wire length costs together.
Suppose it is determined in Step S
50
that the sink terminal grid
10
a
is included in the list L after the same set of process steps have been performed several times. Then a path, starting from the sink terminal
10
a
, is traced back in the search directions represented by the arrows in
FIG. 7
in Step S
60
, thereby extracting a minimum cost path
40
.
The routing results are illustrated in FIG.
8
(
a
). FIG.
8
(
b
) illustrates the results obtained by compacting downward the nets shown in FIG.
8
(
a
). By performing compaction, not only nets but also terminals or routing forbidden region can be moved downward if there are any spaces available. Thus, the terminals
10
A and
10
c
have been moved downward.
In a conventional routing path finding method, if routing is performed on a routing region partitioned into an insufficient number of grid points, then nets already routed sometimes prevent routing. Thus, to complete routing, a sufficient number of grid points should be prepared by adding grid points either from the beginning or after it has been determined that routing cannot be completed.
However, if height or width constraint is imposed on a routing region, the insertion of additional grid points possibly causes failure to comply with the constraint. A situation like this will be described with reference to
FIGS. 9 through 11
. The following example is a method for routing and designing a standard cell applicable to the design of an ASIC.
In
FIGS. 9 through 11
, a height constraint
101
is normally imposed on a standard cell
100
. In the cell
100
, transistors
50
A and
50
B, terminals
10
and power lines
60
are present. In the illustrated example, even though the cell actually has a multilevel interconnection structure, only the nets in the first layer (a first metallization layer
71
for a standard cell) are illustrated for the sake of simplicity.
In
FIG. 9
, a grid unit
32
is defined by uniformly partitioning the cell by the routing pitch of the first interconnection layer
71
. If maze routing is completed on the grid with a uniform routing pitch, then the height constraint on the cell will be satisfied automatically. In other words, to complete routing successfully, a space should be provided beforehand for the nets passing between the transistors
50
A and
50
B.
However, it is very difficult to accurately estimate the space between the transistors before the routing is started. In fact, in an actual routing/designing process carried out manually, trials and errors are inevitable because routing and transistor spacing should be performed in parallel.
For example, if the space between the transistors
50
A and
50
B, obtained by pre-routing estimation, is too narrow as shown in
FIG. 10
, then routing should fail or cannot be completed because of the shortage in number of grid points. As can be seen, the terminals
10
A and
10
B cannot be interconnected together because there are no grid points available between them.
To solve this problem, according to a conventional method, a grid row with a height
32
B narrower than the routing pitch (i.e., the normal grid unit
32
A) is provided between the transistors
50
A and
50
B as shown in
FIG. 11
, thereby completing routing. Thereafter, spaces between transistors and between nets are adjusted through compaction to obtain the same results as those illustrated in FIG.
9
.
However, if such a narrow grid row is inserted as shown in
FIG. 11
, then the number of grid points increases vertically. Thus
Fukui Masahiro
Hamawaki Koji
Matsushita Electric - Industrial Co., Ltd.
McDermott & Will & Emery
Niebling John F.
Whitmore Stacy A
LandOfFree
Routing path finding method for automated routing/designing... 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 path finding method for automated routing/designing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing path finding method for automated routing/designing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3086981