Information Technology Reference
In-Depth Information
3 Detailed Placement Phase
In Detailed placement phase we perform bin swapping based simulated annealing
and cell swapping based simulated annealing followed by greedy cell swapping.
3.1 Bin Swapping Based Simulated Annealing
In bin swapping phase, we use a simulated annealing algorithm (see Algorithm
1) with two objectives. These are (A) reduction of wire length, and (B) balancing
row width, respectively.
To implement Multi-Objective Simulated Annealing, the objective function,
C
, has to be equal to a sum of two objective functions
C
=
ʱA
+
ʲB
. It is dicult
to determine the ratio
ʱ
and
ʲ
as these values may not be the same for different
designs. We overcome this problem by selecting the moves in such a way that
any move that causes an imbalance is not accepted. We swap coordinates of the
bins to achieve HPWL reduction along with the condition that row imbalance
should not occur. The minimization function,
F
(
x
), is the x-direction HPWL
estimate and is given by Equation (1) from [14], where
n
H
and
e
H
are the node
and edge sets of the hypergraph
H
, respectively.
F
(
x
)=
e
k
∈
∀i,j∈n
H
|
max
x
i
−
x
j
|
(1)
e
H
Algorithm 1.
Multi Objective Simulated Annealing
while
init temp
≥
final temp
do
P=
e
δ
WL
/
init temp
Perturb
Will cause swapping of bin coordinates
if
δ
WL
≤
0androwimbalance
≤
0
then
Accept the perturbation
else
if
random number
≤
Pandrowimbalance
≤
0
then
Accept the perturbation
else
Revert the perturbation
end if
if
sucient number of perturbations
then
Decrease init temp
end if
end if
end while
3.2 Cell Swapping Based Simulated Annealing
We do not perform terminal propagation therefore it is important for us to
improve the cuts obtained during global placement phase. This is achieved by
