Information Technology Reference
In-Depth Information
Algorithm 2.
CongestionReduction
Input:
Most congested edge
e
in the graph
Output:
Less congested edge
e
Find the set of trees
T
e
=
{
t
0
,t
1
,t
2
, ...
}
having path through
e
;
while
(
Capacity
(
e
)
<
)
do
t
i
=
MaxWireLength
(
T
e
);
if
(
e
is vertical edge)
then
V
|
T
e
|
≡
Left
,
P
≡
Right
;
end if
if
(
e
is horizontal edge)
then
V
≡
Up
,
P
≡
Down
;
end if
if
(Atleast two horizontal or vertical incident edges on opposite sides of
e
)
then
e
1
=
e
;
e
2
=
e
;
Repeat
e
1
=
e
1
.V, e
2
=
e
2
.P
;
if
(!
Marked
(
e
1
)&
Cong
(
e
1
)
≤ Cong
(
e
2
)&
Bound
(
e
1
))
then
e
new
=
Lock
(
e
1
);
Break;
else if
(!
Marked
(
e
2
)&
Bound
(
e
2
)))
then
e
new
=
Lock
(
e
2
);
Break;
else if
(!
Marked
(
e
1
)&
Bound
(
e
1
)))
then
e
new
=
Lock
(
e
1
);
Break;
else if
(!
Bound
(
e
1
)&
Bound
(
e
2
)))
then
Break;
end if
}
else if
(only
V
side horizontal or vertical incident edge(s) on one side of
e
)
then
e
1
=
e
;
Repeat
e
1
=
e
1
.V
;
if
(!
Marked
(
e
1
)&
Bound
(
e
1
))
then
enew
=
Lock
(
e
1
);
Break;
end if
}
else if
(only
P
side horizontal or vertical incident edge(s) on one side of
e
)
then
e
1
=
e
;
Repeat
e
1
=
e
1
.P
;
if
(!
Marked
(
e
1
)&
Bound
(
e
1
))
then
e
new
=
Lock
(
e
1
);
Break;
end if
}
end if
new path for
e
through
e
new
is set up
Remove
t
i
from
T
e
;
end while
Mark
e
;
edge with maximum congestion is selected and further
CongestionReduction
Algorithm 2 is applied to this edge until the congestion comes down to the edge
capacity. In some cases it may not be so and hence the algorithm might keep
running on and on. For such cases, a check of preset limit on the number of
iteration is made. Whenever this iteration goes beyond the limit, the algorithm
moves on to the next net. The final output of this procedure is either a con-
gestion free routing or routing with overflow. The selection of most congested
edge as mentioned above is made irrespective of the edge being vertical or hori-
zontal. Fig. 3(a) to 3(g) show all possible position of a congested vertical edge
and corresponding new layout for the tree segments running through that edge,
after the proposed technique is applied. Analogous procedure can be applied for
reducing congestion of horizontal edges. Possible scenarios of congested edges
with the possible tree structures are shown. Fig. 3(a) shows a net containing a
congested edge
AB
. Since, for this particular net, there are two horizontal edges
