Browse Prior Art Database

Force Directed Relaxation (FDR) for the Module Placement Problem and the Quadratic Assignment Problem

IP.com Disclosure Number: IPCOM000079669D
Original Publication Date: 1973-Aug-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Gracer, F: AUTHOR [+3]

Abstract

In the following discussion attention is restricted to the quadratic assignment problem (the transformation of the placement problem to the quadratic assignment problem is given in M. Hanan and J. M. Kurtzberg, "Placement Techniques", Chap. 5 in Design Automation of Digital Systems: Theory and Techniques, vol. 1, Prentice-Hall, N. J., copyright 1972.) The total distance (wire length) is used as the cost function. First basic definitions are presented:

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Force Directed Relaxation (FDR) for the Module Placement Problem and the Quadratic Assignment Problem

In the following discussion attention is restricted to the quadratic assignment problem (the transformation of the placement problem to the quadratic assignment problem is given in M. Hanan and
J. M. Kurtzberg, "Placement Techniques", Chap. 5 in Design Automation of Digital Systems: Theory and Techniques, vol. 1, Prentice-Hall, N.
J., copyright 1972.) The total distance (wire length) is used as the cost function. First basic definitions are presented:

If C = [c(ij)] is the connection matrix and D = [d(kl)] is the distance matrix, then a force F is defined on each pair of modules by f=ks, where s is the distance d(kl) between the modules and k is the weight c(ij). The target point for any module is defined as the point where the force on it is zero. The location containing that point is called the target location. In addition, a Q-list is computed which orders all modules i according

The module with the largest Q-value is selected and its zero-tension vector computed. It is then positioned in its target location. If no other module had occupied that position, then the module with the next largest Q-value is chosen for relaxation. If the target location had been occupied by a module, then that one is chosen and, with a sole pathological exception, treated exactly like the initial module; the exception being that the nearest location to its target location is used if the previously placed module now occupies that equilibrium point. An open location is preferred, in the event of choice of two or more candidate locations of equal distance from the target position.

A new module for relaxation is chosen on the same basis as before. A displaced module is relocated next, and if none...