Information Technology Reference
In-Depth Information
Q
Q
Q
A
A
P
P
P
P
C
P
A
A
A
C
F
C
B
B
D
B
E
B
D
E
B
D
Q
Q
R
S
R
S
R
S
R
S
R
S
(a) AB most
congested edge.
(b) Rerouting
paths.
(c) New rerout-
ing path.
(d) AB most
congested edge.
(e)
Rerouting
path.
Q
Q
P
R
P
R
C
A
E
C
A
D
B
F
D
B
S
S
(f) CD already
marked.
(g)
Rerouting
path.
Fig. 3.
Congestion minimization using
CongestionReduction
algorithm
CA
and
BD
incident on
AB
. The two options for the tree detouring will be
either through
CE
or
FD
as shown in Fig. 3(b). Among them, the edge with
minimum existing congestion is selected for rerouting the net segment
AB
.In
the figure, we assume,
CE
haslesscongestionthan
FD
and thereby detour our
net through this edge as depicted in Fig. 3(c). After detouring we check whether
the edge
AC
is part of the net under consideration and if found to be part of
the original net
AC
is retained else removed. The depiction in the above figure
assumes
AC
to be not a part of the original net, and hence has been removed.
Similarly some other situation may happen with the most congested edge and a
different net structure. Fig. 3(d) shows a net containing a congested edge
AB
.
Since, for this particular net, the horizontal edges are incident only from right
side, we detour the net through
CD
as shown in Fig. 3(e). The next step is to
check for
AC
being part of the net. If the removal of
AC
makes no effect to the
connected net under consideration, remove it. We assume, it is not part of the
net and subsequently remove it. For the third case, we assume
CD
was previ-
ously congested edge, which gets uncongested now, after applying our technique
and marked, is shown in Fig. 3(f). The figure also shows that a segment of a
net is passing through the most congested edge
AB
in the grid graph in this
moment. Since, for this particular net, the horizontal edge is incident only from
left we try to detour this net through
CD
.But,
CD
being already marked the
detouring does not takes place and we move forward to the adjacent edge
EF
and on finding it unmarked, detour our net through this edge.
3 Experimental Results
All experiments were performed on a Linux workstation with AMD A8 2.2Ghz
CPU and 4GB memory. ISPD98 2D benchmark circuits have been used to im-
plement our algorithms. The circuits are given in the form of grid graph along
with number of nets, defined by terminal or pin coordinates in the graph.
