US4630219A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Element placement method
Assignee: International Business Machines Corp
•
Filing: 1983-11-23
•
Granted: 1986-12-16
•
Expires: 2003-11-23
Abstract
Abstract A method for placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having an array of element placement positions thereon determines optimum placement in a three pass process. In the first pass, all of the elements are treated as if they are the same size, defined as a unit size, and are assigned to element positions on a unit size next level package, then their placement is optimized. These unit size elements are then replaced by macro size elements, which are approximately the actual size of the corresponding electronic elements. The macro size elements are then rearranged for optimal placement on a macro model image, taking their sizes and shapes into account. Finally, the macro size elements are replaced by actual size elements which are placed on an actual size next level package in element positions, and their placement is again optimized. By optimizing element placement in a three pass process, i.e., unit, macro and actual size, a more efficient placement process is obtained because the element placement program need not take all of the dimensional characteristics of the elements into account at once.
Inventors
- 👤 Angela DiGiacomo
- 👤 Kantilal H. Khokhani
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:41
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 54
Claim 1
Independent Claim
181 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong to element positions in an array of element positions, comprising the steps of: forming unit and actual size models of said plurality of different size elements, and unit and actual size models of said array of element positions, each unit size model element having an identical size, each actual size model element having the same size as its corresponding one of said plurality of different size elements, the unit size model array being sufficiently large to accommodate all the unit size model elements, and the actual size model array being the same size as said array of element positions; assigning said unit size model elements to element positions on the unit size model array according to said predetermined interconnection requirements; replacing the assigned unit size model elements with corresponding actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the actual sizes thereof.
Claim 2
Independent Claim
181 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong to element positions in an array of element positions, comprising the steps of: forming unit and actual size models of said plurality of different size elements, and unit and actual size models of said array of element positions, each unit size model element having an identical size, each actual size model element having the same size as its corresponding one of said plurality of different size elements, the unit size model array being sufficiently large to accommodate all the unit size model elements, and the actual size model array being the same size as said array of element positions; assigning said unit size model elements to element positions on the unit size model array according to said predetermined interconnection requirements; replacing the assigned unit size model elements with corresponding actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the actual sizes thereof.
Claim 3
Independent Claim
197 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong to element positions in an array of element positions, comprising the steps of: forming macro and actual size models of said plurality of different size elements, and macro and actual size models of said array of element positions, each macro size model element having a size which is approximately proportional to that of the corresponding one of said plurality of different size elements, each actual size model element having the same size as the corresponding one of said plurality of different size elements, the macro size model array being sufficiently large to accommodate all the macro size model elements, and the actual size model array being the same size as said array of element positions; assigning said macro size model elements to element positions on the macro size model array according to said predetermined interconnection requirements; replacing the assigned macro size model elements with corresponding actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the actual sizes thereof.
Claim 4
Independent Claim
197 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong to element positions in an array of element positions, comprising the steps of: forming macro and actual size models of said plurality of different size elements, and macro and actual size models of said array of element positions, each macro size model element having a size which is approximately proportional to that of the corresponding one of said plurality of different size elements, each actual size model element having the same size as the corresponding one of said plurality of different size elements, the macro size model array being sufficiently large to accommodate all the macro size model elements, and the actual size model array being the same size as said array of element positions; assigning said macro size model elements to element positions on the macro size model array according to said predetermined interconnection requirements; replacing the assigned macro size model elements with corresponding actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the actual sizes thereof.
Claim 5
Dependent Claim
55 words
The method of claim 1 or 2 wherein the step of rearranging the assigned positions of said actual size model elements is followed by steps of: placing said plurality of different size elements on said array of element positions in the rearranged positions of said actual size model elements on said actual size model array.
Claim 6
Dependent Claim
24 words
The method of claim 1 or 2 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.
Claim 7
Dependent Claim
31 words
The method of claim 1 or 2 wherein said plurality of different size elements are electronic elements and wherein said array of element positions is on a next level electronic package.
Claim 8
Independent Claim
267 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong, to element positions in an array of element positions, comprising the steps of: forming unit, macro and actual size models of said plurality of different size elements, and unit, macro and actual size models of said array of element positions, each unit size model element having an identical size, each macro size model element having size which is roughly proportional to that of the corresponding one of said plurality of different size elements, each actual size model element having the same size as the corresponding one of said plurality of different size elements, the unit size model array being sufficiently large to accommodate all the unit size model elements, the macro size model array being sufficiently large to accommodate all the macro size model elements, and the actual size model array being the same size as said array of element positions; assigning said unit size model elements to element positions on the unit size model array according to said predetermined interconnection requirements; replacing the assigned unit size model elements with corresponding macro size model elements, assigned to corresponding positions on said macro size model array; rearranging the assigned positions of said macro size model elements on said macro size model array to accommodate the macro sizes thereof; replacing the assigned macro size model elements with actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the acutal sizes thereof.
Claim 9
Independent Claim
267 words
A method of assigning a plurality of different size elements having predetermined interconnection requirements thereamong, to element positions in an array of element positions, comprising the steps of: forming unit, macro and actual size models of said plurality of different size elements, and unit, macro and actual size models of said array of element positions, each unit size model element having an identical size, each macro size model element having size which is roughly proportional to that of the corresponding one of said plurality of different size elements, each actual size model element having the same size as the corresponding one of said plurality of different size elements, the unit size model array being sufficiently large to accommodate all the unit size model elements, the macro size model array being sufficiently large to accommodate all the macro size model elements, and the actual size model array being the same size as said array of element positions; assigning said unit size model elements to element positions on the unit size model array according to said predetermined interconnection requirements; replacing the assigned unit size model elements with corresponding macro size model elements, assigned to corresponding positions on said macro size model array; rearranging the assigned positions of said macro size model elements on said macro size model array to accommodate the macro sizes thereof; replacing the assigned macro size model elements with actual size model elements, assigned to corresponding positions on said actual size model array; and rearranging the assigned positions of said actual size model elements on said actual size model array to accommodate the acutal sizes thereof.
Claim 10
Dependent Claim
54 words
The method of claim 6 wherein the step of rearranging the assigned positions of said actual size model elements is followed by the steps of: placing said plurality of different size elements on said array of element positions in the rearranged positions of said actual size model elements on said actual size model array.
Claim 11
Dependent Claim
22 words
The method of claim 6 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.
Claim 12
Dependent Claim
29 words
The method of claim 6 wherein said plurality of different size elements are electronic elements and wherein said array of element positions is on a next level electronic package.
Claim 13
Independent Claim
103 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of indentical unit size elements each corresponding to one of said plurality of different size elements; assigning said unit size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned unit size elements with said corresponding different size elements; and rearranging the assigned different size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 14
Independent Claim
103 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of indentical unit size elements each corresponding to one of said plurality of different size elements; assigning said unit size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned unit size elements with said corresponding different size elements; and rearranging the assigned different size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 15
Independent Claim
108 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of macro size elements each having a size approximately proportional to that of a corresponding one of said different size elements; assigning said macro size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned macro size elements with said corresponding different size elements; and rearranging the assigned different size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 16
Independent Claim
108 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of macro size elements each having a size approximately proportional to that of a corresponding one of said different size elements; assigning said macro size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned macro size elements with said corresponding different size elements; and rearranging the assigned different size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 17
Independent Claim
140 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of identical unit size elements each corresponding to one of said plurality of different size elements; assigning said unit size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned unit size elements with a plurality of macro size elements each having a size approximately proportional to that of a corresponding one of said different size elements; rearranging the assigned unit size element positions in said array of element positions to accommodate said macro size elements; and rearranging the assigned macro size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 18
Independent Claim
140 words
A method of assigning a plurality of different size elements having a predetermined relationship thereamong to element positions in an array of element positions, comprising the steps of: forming a plurality of identical unit size elements each corresponding to one of said plurality of different size elements; assigning said unit size elements to element positions in said array of element positions in accordance with said predetermined relationship; replacing said assigned unit size elements with a plurality of macro size elements each having a size approximately proportional to that of a corresponding one of said different size elements; rearranging the assigned unit size element positions in said array of element positions to accommodate said macro size elements; and rearranging the assigned macro size element positions in said array of element positions to accommodate the exact sizes of said different size elements.
Claim 19
Dependent Claim
25 words
The method of claim 10, 11, or 12 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.
Claim 20
Dependent Claim
32 words
The method of claim 10, 11 or 12 wherein said plurality of different size elements are electronic elements and wherein said array of element positions is on a next level electronic package.
Claim 21
Independent Claim
191 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming unit and actual size models of said electronic elements, and unit and actual size models of said next level electronic package, each unit size element having an identical size, each actual size element having the same size as its corresponding electronic element, the unit size model of said next level package being sufficiently large to accommodate all the unit size elements, and the actual size model of said next level package being the same size as said next level electronic package; optimizing the placement of said unit size elements on the unit size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the unit size elements of the unit size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 22
Independent Claim
191 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming unit and actual size models of said electronic elements, and unit and actual size models of said next level electronic package, each unit size element having an identical size, each actual size element having the same size as its corresponding electronic element, the unit size model of said next level package being sufficiently large to accommodate all the unit size elements, and the actual size model of said next level package being the same size as said next level electronic package; optimizing the placement of said unit size elements on the unit size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the unit size elements of the unit size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 23
Independent Claim
200 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming macro and actual size models of said electronic elements, and macro and actual size models of said next level electronic package, each macro size element having a size which is approximately proportional to that of the corresponding electronic element, each actual size element having the same size as its corresponding electronic element, the macro size model of said next level package being sufficiently large to accommodate all the macro size elements, and the actual size model of said next level package being the same size as said next level package; optimizing the placement of said macro size elements on the macro size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the macro size elements on the macro size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 24
Independent Claim
200 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming macro and actual size models of said electronic elements, and macro and actual size models of said next level electronic package, each macro size element having a size which is approximately proportional to that of the corresponding electronic element, each actual size element having the same size as its corresponding electronic element, the macro size model of said next level package being sufficiently large to accommodate all the macro size elements, and the actual size model of said next level package being the same size as said next level package; optimizing the placement of said macro size elements on the macro size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the macro size elements on the macro size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 25
Dependent Claim
62 words
The method of claim 15 or 16 wherein the step of optimizing the placement of said actual size elements is followed by the step of: placing said plurality of different size electronic elements on said next level electronic package in element positions corresponding to the optimized positions of said actual size elements on said actual size model of said next level package.
Claim 26
Dependent Claim
24 words
The method of claim 15 or 16 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.
Claim 27
Dependent Claim
36 words
The method of claim 15 or 16 wherein said plurality of different size electronic elements are discrete and integrated circuit electronic components and wherein said next level electronic package is a single or multiple layer card.
Claim 28
Dependent Claim
39 words
The method of claim 15 or 16 wherein said plurality of different size electronic elements are single or multiple layer cards upon which discrete and integrated circuits are mounted and wherein said next level electronic package is a motherboard.
Claim 29
Dependent Claim
33 words
The method of claim 15 or 16 wherein said plurality of different size electronic elements are groups of interrelated electronic circuits and wherein said next level electronic package is an integrated circuit chip.
Claim 30
Dependent Claim
32 words
The method of claim 15 or 16 wherein said plurality of different size electronic elements are groups of interrelated electronic circuits and wherein said next level electronic package is a semiconductor wafer.
Claim 31
Independent Claim
286 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming unit, macro and actual size models of said electronic elements, and unit, macro and actual size models of said next level electronic package, each unit size element having an identical size, each macro size element having a size which is approximately proportional to that of the corresponding electronic element, each actual size element having the same size as its corresponding electronic element, the unit size model of said next level package being sufficiently large to accommodate all the unit size elements, the macro size model of said next level package being sufficiently large to accommodate all the macro size elements, and the actual size model of said next level package being the same size as said next level package; optimizing the placement of said unit size elements on the unit size model of said next level package; placing the macro size elements on the macro size model of said next level package in element positions corresponding to the optimized placement positions of the unit size elements on the unit size model of said next level package; optimizing the placement of said macro size elements on said macro size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the macro size elements on the macro size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 32
Independent Claim
286 words
A method of placing a plurality of different size electronic elements having predetermined interconnection requirements thereamong, on a next level electronic package having a plurality of element positions thereon, comprising the steps of: forming unit, macro and actual size models of said electronic elements, and unit, macro and actual size models of said next level electronic package, each unit size element having an identical size, each macro size element having a size which is approximately proportional to that of the corresponding electronic element, each actual size element having the same size as its corresponding electronic element, the unit size model of said next level package being sufficiently large to accommodate all the unit size elements, the macro size model of said next level package being sufficiently large to accommodate all the macro size elements, and the actual size model of said next level package being the same size as said next level package; optimizing the placement of said unit size elements on the unit size model of said next level package; placing the macro size elements on the macro size model of said next level package in element positions corresponding to the optimized placement positions of the unit size elements on the unit size model of said next level package; optimizing the placement of said macro size elements on said macro size model of said next level package; placing the actual size elements on the actual size model of said next level package in element positions corresponding to the optimized placement positions of the macro size elements on the macro size model of said next level package; and optimizing the placement of said actual size elements on said actual size model of said next level package.
Claim 33
Dependent Claim
60 words
The method of claim 23 wherein the step of optimizing the placement of said actual size elements is followed by the step of: placing said plurality of different size electronic elements on said next level electronic package in element positions corresponding to the optimized positions of said actual size elements on said actual size model of said next level package.
Claim 34
Dependent Claim
22 words
The method of claim 23 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.
Claim 35
Dependent Claim
34 words
The method of claim 23 wherein said plurality of different size electronic elements are discrete and integrated circuit electronic components and wherein said next level electronic package is a single or multiple layer card.
Claim 36
Dependent Claim
37 words
The method of claim 23 wherein said plurality of different size electronic elements are single or multiple layer cards upon which discrete and integrated circuits are mounted and wherein said next level electronic package is a motherboard.
Claim 37
Dependent Claim
31 words
The method of claim 23 wherein said plurality of different size electronic elements are groups of interrelated electronic circuits and wherein said next level electronic package is an integrated circuit chip.
Claim 38
Dependent Claim
30 words
The method of claim 23 wherein said plurality of different size electronic elements are groups of interrelated electronic circuits and wherein said next level electronic package is a semiconductor wafer.
Claim 39
Dependent Claim
87 words
The method of claim 23 wherein the actual size model of said next level electronic package is formed from input data including the horizontal and vertical dimensions of said next level electronic package, and the location of input/output vias in a grid, the grid of vias defining said plurality of element placement positions on the next level electronic package, and wherein the actual size model of each electronic element is formed from input data including the horizontal and vertical dimensions and pin locations for each electronic element.
Claim 40
Dependent Claim
50 words
The method of claim 23 wherein the step of placing the macro size elements on the macro size model of said next level package is followed by the step of sliding the placed macro size elements in the horizontal and vertical directions to eliminate overlap of adjacent macro size elements.
Claim 41
Dependent Claim
50 words
The method of claim 23 wherein the step of optimizing the placement of said macro size elements on said macro size model of said next level package comprises the step of rearranging the initial placement of the macro size elements by means of superpositioning and pairwise interchange iterative improvement techniques.
Claim 42
Dependent Claim
48 words
The method of claim 23 wherein the step of optimizing the placement of said actual size elements on said actual size model of said next level package comprises the step of rearranging the initial placement of the actual size elements by means of pairwise interchange iterative improvement techniques.
Claim 43
Dependent Claim
63 words
The method of claim 33 wherein the step of forming unit, macro and actual size models of said electronic elements, and unit, macro and actual size models of said next level electronic package are preceded by the step of: deleting small elements from the set of actual size elements from which the unit and macro size models of said electronic elements are formed.
Claim 44
Dependent Claim
54 words
The method of claim 34 wherein the step of optimizing the placement of said actual size elements on said actual size model of said next level package includes the step of optimizing the placement of said small elements along with the actual size elements on said actual size model of said next level package.
Claim 45
Dependent Claim
50 words
The method of claim 23 wherein the step of placing the actual size elements on the actual size model of said next level package is followed by the step of sliding the placed actual size elements in the horizontal and vertical directions to eliminate overlap of adjacent actual size elements.
Claim 46
Dependent Claim
25 words
The method of claim 36 wherein the sliding step is followed by the step of spreading the actual size elements to distribute unused space therebetween.
Claim 47
Dependent Claim
73 words
The method of claim 23 wherein the unit size model for each electronic element is formed by assigning each unit size element the horizontal and vertical dimension of one unit, and wherein the unit size model for said next level electronic package is formed by dividing the horizontal and vertical dimension of the actual size next level electronic package by the average horizontal and vertical dimension, respectively, of the actual size electronic elements.
Claim 48
Dependent Claim
83 words
The method of claim 38 wherein the macro size model for each electronic element is formed by assigning each macro size element the horizontal and vertical dimensions of its corresponding actual size electronic element, divided by a scale factor, and wherein the macro size model for said next level electronic package is formed by multiplying the horizontal and vertical dimensions of said unit size model of said next level package by the average horizontal and vertical dimension, respectively, of the macro size elements.
Claim 49
Dependent Claim
22 words
The method of claim 39 wherein said scale factor is the most common horizontal or vertical dimension of said actual size elements.
Claim 50
Dependent Claim
77 words
The method of claim 23 wherein the step of optimizing the placement of said unit size elements on the unit size model of said next level package comprises the steps of: ordering the unit size elements as a function of their connectivity to other elements; and constructively placing the unit size elements on the unit size model of said next level package in the order of their connectivity, with the most highly connected element being placed first.
Claim 51
Dependent Claim
93 words
The method of claim 41 wherein the step of constructively placing the unit size elements comprises the steps of: placing the most highly connected element at a predetermined location on the unit size model of said next level package; calculating the cost of placing the second most highly connected element at an element position near the already placed element; placing the second most highly connected element at the element position where cost is lowest; and repeating the calculating and placing steps for the remaining unit size elements; in the order of their connectivity.
Claim 52
Dependent Claim
40 words
The method of claim 41 wherein the step of optimizing the placement of said unit size model of said elements on the unit size next level package further comprises the step of: rearranging the constructive placement by means of superpositioning.
Claim 53
Dependent Claim
89 words
The method of claim 43 wherein the step of superpositioning comprises performing the following steps for each unit size element, in the order of their connectivity: forming a window on a blank unit image, the window being centered around the zero center of gravity of the placed unit size element on the unit size model of said next level package; calculating the cost of placing the unit size element at element positions in said window; and placing the unit size element at the element position where cost is lowest.
Claim 54
Dependent Claim
43 words
The method of claim 43 wherein the step of optimizing the placement of said unit size elements on the unit size model of said next level package further comprises the step of: rearranging the constructive placement by means of pairwise interchange iterative improvement.
References Cited (Backward Citations)
US3654615A
Cited
US3653072A
Cited
US3653071A
Cited
US3702004A
Cited
US3681782A
Cited
US4093990A
Cited
US4377849A
Cited
US4500963A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-12-15 | 1990-06-16 | 1990-12-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-12-15 | 1994-06-16 | 1994-12-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-12-15 | 1998-06-16 | 1998-12-16 | $7700.00 | Window Closed / Lapsed |