ELEMENT PLACEMENT SYSTEM

• US 3,654,615 A
• Filed: 12/01/1965
• Issued: 04/04/1972
• Est. Priority Date: 12/01/1965
• Status: Expired due to Term

• Current Assignee: Harlow Freitag
• Original Assignee: Harlow Freitag
• Inventors: Freitag, Harlow
• Primary Examiner(s): Henon, Paul J.
• Assistant Examiner(s): Chapuran, Ronald F.
• Application Number:
  US04/510,767
• Time in Patent Office: 2,316 Days
• Field of Search: 340/172.5 235/151,151.1,151.11
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: H01L 27/00 Devices consisting of a plurality of semiconductor or other solid-state components formed in or on a common substrate details thereof H01L23/00, H01L29/00 - H10K10/00; assemblies consisting of a plurality of individual solid state devices H01L25/00
• CPC Class Codes: H01L 27/0207 Geometrical layout of the components, e.g. computer aided design; custom LSI, semi-custom LSI, standard cell technique

Abstract

The disclosure describes a system for assigning a plurality of interrelated circuit elements to element positions in an array of element positions on a circuit board. The system includes means for storing an indication of the interrelationship of the elements being assigned and the order in which the elements are to be assigned. Apparatus is provided for assigning the first element to be assigned to a selected position in the array, selecting candidate positions related in a predetermined manner to the position which has just had an element assigned to it; determining the best candidate position for the next element to be assigned and assigning the next element to be assigned to the position determined above; the system repeats the above three steps until all elements have been assigned.

Claims

1. A system for fabricating an interconnected circuit on a substrate having a plurality of circuit element positions comprising:

means for applying to the system information as to the interconnected circuit including the relationship of the elements of the circuit to each other;

means for utilizing the relationship of the elements of the circuit to determine the order in which the elements of the circuit are to be assigned to circuit element positions on the substrate;

means for assigning the first element to be assigned to a selected element position on said substrate;

means operative after each element is assigned to an element position on the substrate for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them;

means for determining the best candidate position for the next element to be assigned; and

means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.

2. A system of the type described in claim 1 including:

means operative when all the elements of said interconnected circuit have been assigned to element positions for initiating the interconnecting of the element positions having elements assigned to them into said interconnected means, means operative in response to said interconnecting initiating means for determining a suitable wiring pattern for interconnecting the element positions having elements assigned to them into said interconnected circuit;

AND means for interconnecting said element positions in accordance with said suitable pattern.

3. A system of the type described in claim 1 further including means operative when all the elements of said interconnected circuit have been assigned to element positions for initiating the interconnecting of the element positions having elements assigned to them into said interconnected circuit.

4. A system of the type described in claim 1 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position on said substrate;

and said means for selecting candidate positions operate to select elements positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.

5. A system of the type described in claim 1 wherein said means for assigning the next element to said best candidate position operated to assign the candidate position for which the eventual interconnections between the next element to be assigned and the elements to which it is connected which have already been assigned is, on the average, the shortest and the simplest.

6. A system of the type described in claim 1 wherein it is possible that less than 100 percent of the element positions will be useable including:

means for applying to the system information as to the useable condition of each of the element positions on the substrate; and

means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.

7. A system of the type described in claim 6 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position on said substrate;

and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.

8. A system of the type described in claim 7 wherein said means for determining the best candidate position includes:

means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the relationship of the next element to be assigned to the element assigned to the position; and

means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.

9. A system for assigning a plurality of interrelated elements to element positions in an array of element positions comprising:

means for storing a coefficient of interrelationship between each of said elements;

means for utilizing said coefficients of interrelationship to determine the order in which the elements are to be assigned to element positions in said array;

means for assigning the first element to be assigned to a selected element position in said array;

means operative after each element is assigned to an element position for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them;

means for determining the best candidate position for the next element to be assigned; and

means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.

10. A system of the type described in claim 9 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position in said array;

and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.

11. A system of the type dEscribed in claim 9 wherein said means for determining the best candidate position includes:

means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the coefficient of interrelationship of the next element to be assigned to the element assigned to the position; and

means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.

12. A system of the type described in claim 11 including:

means operative when two or more candidate positions have the same minimum-determined-sum for determining for which of those candidate positions the average distance in each coordinate direction between the candidate position and the positions having elements related to the next element to be assigned to them are most nearly equal; and

means for selecting the candidate position determined to have the minimum average distance difference, by the above means, as the best candidate position.

13. A system of the type described in claim 10 wherein it is possible that less than 100 percent of the element positions will be useable including:

means for applying to the system information as to the useable condition of each of the element positions of the array; and

means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.

14. A system of the type described in claim 13 including:

means operative after said candidate position selecting means for determining if there are any candidate positions; and

means operative in response to a determination by said above means that there are no candidate positions, for making all useable positions in said array available as candidate positions.

15. A system for assigning a plurality of interrelated elements to element positions in an array of element positions wherein the interrelated elements are circuit elements of an interconnected circuit and wherein the element positions are circuit positions on a substrate, said system comprising:

means for storing a coefficient of interrelationship between each of said elements;

means for storing a list of said interrelated elements in the order in which they are to be assigned;

means for assigning the first element to be assigned to a selected element position in said array;

means operative after each element is assigned to an element position in said array for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them;

means for determining the best candidate position for the next element to be assigned; and

means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.

16. A system of the type described in claim 15 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position of said array;

and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.

17. A system of the type described in claim 15 wherein said means for determining the best candidate position includes:

means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the relationship of the next element to be assigned to the element assigned to the position; and

means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.

18. A system of the type described iN claim 17 including:

means operative when two or more candidate positions have the same minimum determined sum for determining for which of those candidate positions the average distance in each coordinate direction between the candidate position and the positions having elements, related to the next element to be assigned, assigned to them are most nearly equal; and

means for selecting the candidate position determined to have the minimum average distance difference by the above means as the best candidate position.

19. A system of the type described in claim 15 wherein it is possible that less than 100 percent of the element positions will be useable including:

means for applying to the system information as to the useable condition of each of the element positions; and

means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.

20. A system of the type described in claim 19 including:

means operative after said candidate position selecting means for determining if there are any candidate positions; and

means operative in response to a determination by said above means that there are no candidate positions, for making all useable positions in said array available as candidate positions.