Information Technology Reference
In-Depth Information
performing cell swapping between the bins. In this step all cells within a bin are
placed on top of each other, that is, there exists overlap between the cells. All
the cells of a bin have the same coordinates. After completion of cell swapping
between the bins, all the cells are spread out to remove overlap. Spreading is
placing of the cells of the bins adjacent to each other in such a way that there
is no overlap between them. It is important that the wire length obtained after
spreading out all the cells must correlate with the changes that are done during
cell swapping phase. Cell swapping and cell movement between the bins is studied
by [15] and implemented in Dragon version 2.1. They attempt to achieve a bin
width balance by swapping of cells. By doing this they achieve a correlation
between the wire length of spread out cells and wire length during cell swapping.
We tried two approaches for doing annealing based on cell swapping.
Algorithm 2.
Perturbation Method 1
Randomly Select Two Bins in suciently close vicinity
Select one Cell from Each Bin
Calculate Incremental Cost = Cost1
Swap the Cell coordinates
Calculate Incremental Cost = Cost2
Return
δWL
=
Cost
1
− Cost
2
Algorithm 3.
Perturbation Method 2
Randomly Select Two Bins in suciently close vicinity
Select one Cell from Each Bin
Calculate Incremental Cost = Cost1
Swap the Cell coordinates and arrange all Bins to the right of the selected Bins
separated by a distance equal to their widths
Calculate Incremental Cost = Cost2
Return
δWL
=
Cost
1
−
Cost
2
In the first approach we did not move the bin location ie, all the bins have
fixed coordinates. Here the bin coordinates are not changed and there exists even
spacing between the bins. Here we randonly select the bins which are within a
distance of
numberofrows
/
3 bins. For us this method does not correlate well with
the spread out wire length.
In the second approach Figure 2, bins are placed at a distance equal the their
widths and we shift the bins towards right by the difference in cell widths. Let
Cell A belongs to Bin A and Cell B belongs to Bin B, then after swapping the
cells, all the bins to the right of Bin A will be moved by a difference amount
(Width(cellB)-width(cellA)) where as all the bins to the right of Bin B Bin B
will be moved to right with a difference amount (Width(cellA)-width(cellB)). If
we spread out the cells after the first method, we get worse wire length. This is
