VLSI Cell Placement Techniques
Force-Directed placement — introduction
The implementation specifics of Force-Directed placement algorithms vary significantly. The method of determining the position where a module should be positioned in order to achieve its optimal placement is the common denominator in these algorithms. This is how it is achieved:
Take a look at any initial placement. Assume that the modules linked by nets have an enticing force between them (Fig 1).
The distance between any two modules is directly proportional to the magnitude of the force between them. The constant of proportionality is the sum of the weights of all nets directly linking them, as in Hooke’s Law for the force exerted by stretched springs.
If the modules in such a system were free to move, they would obey the force until the system reached equilibrium in a minimum energy state, with the springs in minimum tension (equivalent to minimum wire length) and a zero resultant force on each module. As a result, force-directed placement methods operate by shifting the modules in the direction of the total force applied to them until it reaches zero.
Assume that a net nᵢⱼ with weight wᵢⱼ binds a module Mᵢ to a module Mⱼ. Let sᵢⱼ be the distance between Mᵢ and Mⱼ. The net force on the module is then determined as follows (Refer figure 2) :
Say, If the force’s x- and y-components are all equalled to zero,
As a result, the coordinates for module Mᵢ’s zero force goal point are as follows:
These equations are identical to centre-of-gravity equations; that is, if the modules connected to Mᵢ are considered to be masses with weight wᵢⱼ then the zero-force target position of Mᵢ is the centre of gravity of these modules.
