Browse Prior Art Database

Natural Selection Method with Least Dip Traffic Jam Mechanism

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

Publishing Venue

IBM

Related People

Dunham, B: AUTHOR [+2]

Abstract

In the execution of an automatic placement program that attempts to find an optimal placement of elements on a module, e.g., circuits on a chip, it often happens that the program becomes "stuck" at a local minimum. The method described herein provides a technique for determining a likely continuation point for reaching the global optimum.

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

Page 1 of 2

Natural Selection Method with Least Dip Traffic Jam Mechanism

In the execution of an automatic placement program that attempts to find an optimal placement of elements on a module, e.g., circuits on a chip, it often happens that the program becomes "stuck" at a local minimum. The method described herein provides a technique for determining a likely continuation point for reaching the global optimum.

An exemplary placement program for placing elements on a module is described in "Design by Natural Selection" by B. Dunham, et al, 1961, RC #476 available from IBM T. J. Watson Research Center, Yorktown Heights, N. Y.

The placement progrsm is designed to optimize the location of cell bites within columns of a module, so that wire routing can be more readily accomplished. Assuming that the placement program uses a scoring mechanism that is tied to line or wire density, the object of the program is to minimize the score.

If during the running of the program, the score settles about some minimum because of unrecognized coalitions of elements, it is not possible to reach the global optimum. Further pair exchanges of elements generally result in higher scores, because of their unrecognized groups.

Although pair exchanges commonly serve for the placement of modules on boards, here we are confronted by a one-dimensional string of cells. It is easy to calculate the effect of repositioning items one at a time. Hence, the question arises whether sliding single moves may not, in fact, be preferable to pair exchanges. Certainly, the latter are roughly included in the former, since any pair exchange can be accomplished by two consecutive single moves. A pair-move success, which combined a single-move failure with a more substantial single- move success, would carry us less far along than the favored single move alone. More important, the position reached as a result of the favored single move might be inaccessible to pair-wise moves (it is easy to construct examples where this is the case). The reverse, however, is not true. Any pair-move success which combines two single-move successes, does define a position which can be realized by consecutive single moves.

Since the ability to reach...