Force-Directed Placement Techniques

The force guided positioning algorithm was first used in the 1960s. There are several variants available today. Some are positive, and others are focused on incremental development. The coordinates of each module are considered as variables in constructive methods, and the net force imposed on each module by all other modules is equal to zero.

We get the coordinates of both modules by simultaneously solving these equations. In such a case, caution must be exercised to prevent the trivial solution, xᵢ = xⱼ and yᵢ = yⱼ, for all i, j which, given the spring model, clearly satisfies the zero-force condition. Another concern with this form is that the zero-force equations are nonlinear since the force is proportional to distance, and the Euclidean distance metric requires a square root, while the Manhattan distance metric uses absolute values.

An initial solution is generated in iterative methods either spontaneously or by some other constructive method. Then, one module at a time, the zero-force target point for that module is calculated using the aforementioned calculations, and an effort is made to transfer the module to the target point or swap it with the module that was previously occupying the target point. These algorithms are also known as force-directed pairwise relaxation algorithms or force-directed relaxation algorithms.

One issue here is determining the order in which the modules should be selected for moving to the target site. The module or seed module with the highest force vector is usually chosen in most implementations. The modules are chosen at random in other implementations. In certain cases, the modules are chosen based on an approximate approximation of their connectivity. Another issue is determining where to position the chosen module if the slot closest to the zero-force goal location is already filled, which it would almost definitely be.

Moving it to the closest accessible free place is one solution. However, in some situations, the closest free spot might be very far away. This is an approximate method and, at best, will need further iterations to arrive at a reasonable outcome.

The second option is to compute the target position of a module as mentioned above, then assess the difference in wire length or cost when the module is swapped out for the module at the target location. The interchange is approved if the wire length is reduced; otherwise, it is refused. It’s important to assess the wire length because it’s likely that by attempting to swap the selected module with the module that was previously at the target point, we’ll be shifting the other module far away from its own target point, resulting in a loss rather than a gain.

The third option is to use a ripple move, which involves selecting the module that was previously occupying the target point as the next move. This process is repeated until a module’s goal point lands in an empty slot. After that, a new seed is chosen.

The fourth approach is to calculate each module’s target point, then search for pairs of modules where one module’s target point is very close to the current position of the other. If such modules are switched, they can both enter their desired locations in a mutually beneficial manner.

Repeated trial interchanges are used in the fifth approach. An interchange is approved if it lowers the cost; otherwise, it is refused. The sum of the forces acting on the modules, in this case, is the cost function.