Optimization of an organization of many discrete elements

• US 4,495,559 A
• Filed: 11/02/1981
• Issued: 01/22/1985
• Est. Priority Date: 11/02/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kirkpatrick, Edward S., Gelatt, Charles D. Jr.
• Primary Examiner(s): Ruggiero, Joseph F.
• Application Number:
  US06/317,651
• Time in Patent Office: 1,177 Days
• Field of Search: 364/148, 364/130, 364/194, 364/488, 364/489, 364/490, 364/491, 364/300
• US Class Current: 700/28
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

The overall arrangement of a large number of discrete objects may be optimized with relation to the function of or the space occupied by the arrangement by establishing a suitability measure, or score, for each configuration of the arrangement, in relation to the function of or volume occupied, generating random local changes in the arrangement, scoring the effect of the individual changes and subjecting all objects in the arrangement to a random series of incremental changes whose outcome is on average predictable. The procedure lends itself to computer simulation. It may be applied to sequencing and scheduling problems, bin packing types of problems and in complex design problems such as semiconductor chip placement, wiring network routing and logic partitioning.

Claims

1. A method of positioning all the individual elements of an interconnected configuration assembled into a unitary computational entity that satisfies at least one usefulness specification where said individual elements are of the type including semiconductor devices on a semiconductor chip, semiconductor chips on a modular package, modular packages on wiring supporting boards, and circuits in an array and where said usefulness specification includes wiring density and wiring net length

comprising in combination the steps of

providing a representation of the interconnected configuration of elements,

providing a scoring capability capable of providing a measure of acceptability of a particular configuration of said elements with respect to at least one of wiring density and wiring net length and

interdependently

iteratively exchanging the position of subsets of said elements and for each subset accepting or rejecting the resulting arrangement in accordance with a measure provided by said scoring capability and

varying the measure of acceptance of a subset position exchange in accordance with an incremental trend.

2. The method of claim 1 wherein said variation of the measure of acceptance is by modifying a ratio of a first number that is the fraction of subset position exchanges which said scoring capability indicates not to be an improvement which are accepted and a second number that is the fraction of subset position exchanges that said scoring capability indicates are an improvement and are accepted.

3. The method of claim 2 wherein said incremental variation trend is simulated annealing.

4. A method of positioning all the physical elements of an interrelated configuration of said physical elements in a unitary functional entity wherein the interrelated positioning satisfies at least one specification related to the usefulness of said functional entity:

comprising in combination the steps of

providing a representation of all the interrelated individual physical elements in said collection,

providing a scoring capability capable of measuring the acceptability of a particular positioned configuration of said elements with respect to said usefulness specification and

interdependently

iteratively exchanging the physical position occupied in said configuration of successive subsets of said elements and for each repositioned subset of said physical elements accepting or rejecting the resulting arrangement in accordance with a measure provided by said scoring capability, and

varying the measure for acceptance of a subset position exchange in accordance with an incremental trend.

5. The method of claim 4 wherein said varying of the measure of acceptance is by modifying a ratio of a first number that is the fraction of position exchanges that said scoring capability indicates not to be an improvement toward satisfying said usefulness specification and are accepted and a second number that is the fraction of position exchanges that said scoring capability indicates to be an improvement toward satisfying said usefulness specification and are accepted.

6. The method of claim 5 wherein said incremental trend is simulated annealing.