Browse Prior Art Database

Force Directed Interchange (FDI) for the Module Placement Problem and the Quadratic Assignment Problem

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

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 "Placement Techniques", referenced below) with the total distance (wire length) used as the cost function. Generally, the pairwise interchange methods work as follows:

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

Page 1 of 1

Force Directed Interchange (FDI) 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 "Placement Techniques", referenced below) with the total distance (wire length) used as the cost function. Generally, the pairwise interchange methods work as follows:

An initial placement is given and a pair of modules is chosen for a "trial interchange". If the objective or cost function is reduced by this interchange, it is accepted, otherwise the initial placement is retained and another pair of modules chosen for trial interchange.

There are several schemes available to choose the pair of modules (see 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., 1972.), but in all of these essentially 1/2n(n-1) pairs must be examined, where n is the number of modules. Typically only a small subset of trial interchanges result in a reduction of the objective function. The force-directed interchange (FDI) method delimits the number of trial interchanges, and hence drastically reduces the computation time. Of course, there is a trade-off between results and computation time.

If C = [c(ij)] is the connection matrix and D = (d(KL)] is the distance matrix, then a force F on each pair of modules is defined by F=ks, where s is the distance d between the modules and k is the weight c(ij). T...