US4495559A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimization of an organization of many discrete elements
Assignee: International Business Machines Corp
•
Filing: 1981-11-02
•
Granted: 1985-01-22
•
Expires: 2001-11-02
Abstract
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.
Inventors
- 👤 Charles D. Gelatt, Jr.
- 👤 Edward S. Kirkpatrick
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 02:42
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
163 words
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.
Claim 2
Independent Claim
163 words
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.
Claim 3
Dependent Claim
66 words
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.
Claim 4
Dependent Claim
13 words
The method of claim 2 wherein said incremental variation trend is simulated annealing.
Claim 5
Independent Claim
139 words
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.
Claim 6
Independent Claim
139 words
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.
Claim 7
Dependent Claim
75 words
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.
Claim 8
Dependent Claim
12 words
The method of claim 5 wherein said incremental trend is simulated annealing.
References Cited (Backward Citations)
US935003A
Cited
US3654615A
Cited
US3617714A
Cited
US3622762A
Cited
US3621208A
Cited
US3653072A
Cited
US3653071A
Cited
US3702004A
Cited
US3629843A
Cited
US3702003A
Cited
US3681782A
Cited
UST935003I4
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-01-22 | 1988-07-23 | 1989-01-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-01-22 | 1992-07-23 | 1993-01-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-01-22 | 1996-07-23 | 1997-01-22 | $7700.00 | Window Closed / Lapsed |