Element placement method

• US 4,630,219 A
• Filed: 11/23/1983
• Issued: 12/16/1986
• Est. Priority Date: 11/23/1983
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Khokhani, Kantilal H., DiGiacomo, Angela
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Cosimano, Edward R.
• Application Number:
  US06/554,855
• Time in Patent Office: 1,119 Days
• Field of Search: 364/300, 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

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.

Claims

1. 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.

3. 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.

4. The method of claim 1 or 2 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.

5. 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.

2. 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.

6. 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.

7. 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.

8. The method of claim 6 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.

9. 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.

10. 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.

13. 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.

14. 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.

11. 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.

12. 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.

15. 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.

17. 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.

18. The method of claim 15 or 16 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.

19. 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.

20. 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.

21. 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.

22. 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.

16. 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.

23. 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.

24. 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.

25. The method of claim 23 wherein said method is practiced by an element placement program operating in conjunction with a digital computer.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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.

40. The method of claim 39 wherein said scale factor is the most common horizontal or vertical dimension of said actual size elements.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.