Information Technology Reference
In-Depth Information
A
B
A
B
A
B
A
B
A
B
p
4
p
p
q
4
p
1
p
p
p
q
3
q
1
q
1
q
2
q
1
q
1
C
D
C
D
C
D
C
D
C
D
(a)
2
pin
(b) Edge selec-
tion from C.
(c) Edge selec-
tion from
q
1
.
(d) Edge selec-
tion from
p
2
.
(e) Edge selec-
tion from
p
3
.
points.
p
p
7
A
B
A
B
A
B
A
B
A
B
p
5
p
5
p
5
p
5
p
5
q
6
q
6
q
7
q
6
q
7
q
6
q
7
p
p
p
p
p
q
q
5
q
q
q
q
p
p
p
p
p
q1
D
q1
D
q1
D
q1
D
q1
D
C
C
C
C
C
(f) Edge selec-
tion from
q
4
.
(g) Edge selec-
tion from
p
5
.
(h) Edge selec-
tion from
q
6
.
(i) Join
q
7
and
D
.
(j) Path se-
lected between
CandB.
Fig. 2.
Path laying between C and B using
CongestionSensing
algorithm
in the second step becomes more feasible. The congestion should be minimized
so that the electric load on one channel is reduced, since more wires or more
current flow through one channel may increase the heat and sometime damage
the circuit. Hence the focus is on congestion minimization rather than wire length
minimization.
The internal working principle of the
CongestionSensing
algorithm is de-
scribed in Algo 1. Fig. 2(a) shows the FLUTE generated bi-pins B and C to
be connected. Our task is to create a connection between these two pins and
the algorithm senses congestion while making this connection and subsequently
adjusts the laying out of path. In this context congestion represents the number
of Steiner trees that have used the edge for laying their path. A virtual box
ABCD is conceptualized to bound the path between B and C. While laying out
path from the lower pin C, the algorithm senses the congestion(use) of the two
possible edges
cp
1
and
cq
1
and then chooses the least used edge. This process
continues until the two pins get connected, as shown in Fig. 2(a) to 2(j). This
is to ensure that one particular edge does not get chosen over and over again,
thereby keeping congestion to a minimum.
2.2 Congestion Minimization by Rerouting the Most Congested
Edge
This section describes the second step of congestion minimization technique that
uses rerouting of the tree segment having path through the most congested grid
edge, to minimize congestion. This phase does not focuses only on overflow re-
duction but also controls the wire length of each individual net and hence the
signal delay. Most of the existing technique controls congestion and wire length,
but some nets become lengthy and increase their signal delay. Initially the the
