17th
Force directed placement
An attempt is made to place cells in their ideal locations by using a mechanical analogy.
Two cells separated by a distance D and connected by a net of length L are said to have a force D x L acting upon them.
The averaged sum of all such forces on a single cell yields the zero-force target location of the cell.The net weights are treated like spring constants, and the net lengths are treated like spring lengths in this analogy to Hooke’s Law.
Once a cell’s zero-force target location is calculated, we must decide where it will be placed in the layout.If the target location is empty, simply place it in the empty location.If the target location is already occupied, we must determine how to proceed.
The selected cell is moved to the free location nearest to its zero-force target location.
The selected cell is swapped with the cell at its zero-force location if the swap will reduce the solution cost.
The selected cell replaces the cell at its zero-force location and the replaced cell has its zero-force location computed. The replaced cell is then placed in a similar fashion, inciting a “ripple” of replacements until an end condition is met.
fdpl( iterations, cells, nets, width, type )
Initialize the layout according to the layout type
and layout width.
Sort the cells in decreasing order by total weight of connected nets. i = 0
while (i < iterations) {
for each net apply force-directed heuristic
i = i + 1
}
