Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-05-12
2003-03-11
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06532583
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to global routing determination methods and storage mediums, and more particularly to a global routing determination method for determining a global routing of a circuit, and to a computer-readable storage medium which stores a program for causing a computer to determine a global routing of a circuit according to such a global routing determination method.
When designing an integrated circuit such as an LSI circuit by CAD, it is possible to roughly categorize the design stage into a logic design and a physical design. The logic design determines how to realize the logic of the circuit which is to be designed. The physical design determines the arrangement (also referred to as layout or placement) of elements such as cells and gates, wirings and the like which form the circuit, based on the result of the logic design. When making the physical design, the layout of the wirings is basically determined by a global routing and a local (or detailed) routing. The global routing determines the general arrangement of the wirings together with the general arrangement of the elements and the like. On the other hand, the local routing determines the actual detailed arrangement of the wirings depending on the actual arrangement of the elements and the like.
The present invention relates to a global routing method used to make the global routing described above, and also relates to a computer-readable storage medium which stores a program for causing the computer to determine the global routing.
2. Description of the Related Art
Due to the progresses made in the circuit technology, the integration density of the integrated circuit has improved considerably and the circuit scale of the integrated circuit has increased notably in recent years. Conventionally when designing the circuit by CAD, the circuit delay taken into consideration was primarily the delays caused by gates which form the circuit. However, as the integration density of the integrated circuit improved, delays caused by the wirings have increased and are becoming no longer negligible in order to further improve the circuit performance. For this reason, there are demands to realize a method of designing the wirings by taking into consideration the delays caused by the wirings.
Conventionally, as a method of designing the wirings by taking into consideration the delays caused by the wirings, there was a method which determines the wirings so that each wiring length becomes a minimum. However, this conventional method did not accurately consider the delay of the actual wiring from one terminal to another terminal, as explained in the following.
First, a description will be given of the Elmore delay. It is assumed for the sake of convenience that a tree T has a source s
0
. If an edge from a node v towards the source s
0
is denoted by ev, a resistance of the edge ev is denoted by r
ev
, a capacitance of the edge ev is denoted by C
ev
, a subtree of the node v is denoted by Tv, a capacitance of the subtree Tv is denoted by Cv, an ON-resistance of an output driver of the source s
0
is denoted by rd, and a sum total of the wiring lengths is denoted by C
s0
, the Elmore delay from the source s
0
to the target v can be described by the following formula (1).
D
(
v
)
=
rdC
s0
+
∑
ev
∈
path
(
s0
,
v
)
r
ev
(
C
ev
/
2
+
Cv
)
(
1
)
In the formula (1), the first term indicates that the delay from the source s
0
to the target v becomes shorter as the sum total C
s0
of the wiring lengths becomes shorter. In addition, in the formula (1), the second term indicates that the delay becomes shorter as the wiring length from the source s
0
to the target v becomes shorter, and that the delay becomes shorter as the capacitance Cv of the subtree Tv connected to the target v becomes smaller.
Next, a description will be given of the mechanism by which the wiring delays become different even for the same wiring length.
FIGS. 1A and 1B
respectively are diagrams showing a case where a region including cells which form a circuit is successively divided into a plurality of blocks, and the global routing among the cells is hierarchically determined while arranging the cells in the blocks. In this particular case, the region is formed by 2×2 blocks, and there exist 3 terminals which are to be connected by the wirings. In
FIGS. 1A and 1B
, a black circular mark indicates the terminal, and a straight line connecting the terminals indicates the wiring.
In
FIGS. 1A and 1B
, it is assumed for the sake of convenience that each block has a side with a resistance R, a terminal s
0
has an ON-resistance rd, a terminal v
1
has a capacitance C
1
, and a terminal v
2
has a capacitance C
2
. The wiring delay caused by the wiring from the terminal s
0
to the terminals v
1
and v
2
can be described as follows.
In the case shown in
FIG. 1A
, a wiring delay Da(v
1
) from the terminal s
0
to the terminal v
1
can be described by the following formula (2), and a wiring delay Da(v
2
) from the terminal s
0
to the terminal v
2
can be described by the following formula (3).
Da
(
v
1
)=
rd×
(
C+C
1
+
C
2
)+
R×
(
C/
2
+C
1
+
C
2
) (2)
Da
(
v
2
)=
rd×
(
C+C
1
+
C
2
)+
R×
(
C/
2
+C
1
+
C
2
)+
R×C
2
(3)
On the other hand, in the case shown in
FIG. 1B
, a wiring delay Db(v
1
) from the terminal s
0
to the terminal v
1
can be described by the following formula (4), and a wiring delay Db(v
2
) from the terminal s
0
to the terminal v
2
can be described by the following formula (5).
Db
(
v
1
)=
rd×
(3
C/
2+
C
1
+
C
2
)+
R×C
1
(4)
Db
(
v
2
)=
rd×
(3
C/
2+
C
1
+
C
2
)+2
R×C
2
(5)
As may be seen from a comparison of
FIGS. 1A and 1B
, the wiring length in the case shown in
FIG. 1A
is shorter than the wiring length in the case shown in
FIG. 1B
when the total wiring length is considered. However, with respect to the delay at the terminal v
1
, a difference described by the following formula (6) exists between the cases shown in
FIGS. 1A and 1B
.
Da
(
v1
)
-
Db
(
v1
)
=
{
r
d
×
(
C
+
C1
+
C2
)
+
R
×
(
C
/
2
+
C1
+
C2
)
}
-
{
r
d
×
(
3
C
/
2
+
C1
+
C2
)
+
R
×
C1
}
=
r
d
×
(
-
C
/
2
)
+
R
×
C2
(
6
)
As may be seen from the above formula (6), in a relationship R×C
2
>rd×(−C/2) stands, the wiring delay at the terminal v
1
in the case shown in
FIG. 1B
is shorter than the wiring delay at the terminal v
1
in the case shown in FIG.
1
A.
Therefore, it is not necessarily the case that the wiring delay for a shortest total wiring length is always the shortest wiring delay. For this reason, there was a problem in that, according to the conventional method which determines the wiring so that the wiring length becomes the shortest, it is impossible to determine the wiring by accurately taking into consideration the delay of the actual wiring from one terminal to another terminal. In addition, even if the shortest wiring is determined according to the conventional method, a rerouting of the wiring is made depending on the wiring density or disorder which occurs thereafter, and there was another problem in that the wiring which is determined does not accurately take into account the delay of the actual wiring which is finally obtained.
SUMMARY OF THE INVENTION
Accordingly, it is a general object of the present invention to provide a novel and useful global routing determination method and storage medium, in which the problems described above are eliminated.
Another and more specific object of the present invention is to provide a global routing determination method which can determine a global routing of a circuit by accurately taking into account
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Global routing determination method and storage medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Global routing determination method and storage medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Global routing determination method and storage medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038124