Patent GB-1307261-A (GB)
Title: Optimising component interconnection
IPC: H05K1/14
Filed: 1970-04-10
Abstract: 1307261 Interconnecting sets of components WESTERN ELECTRIC CO Inc 10 April 1970 [15 April 1969] 17148/70 Heading G4A The cost of interconnecting a number of (electronic circuit) components is minimized using a digital computer by minimizing the number of connections required between different supporting structures (circuit boards). Digital representations of the components involved are arbitrarily divided into two sets, the cost of interconnecting the components so divided being computed. The reductions achieved by interchanging pairs of digital representations between the two sets are computed, the pair giving the greatest reduction being removed from further consideration. The process is repeated until all the components have been eliminated and the interchanges resulting in the largest partial sum of the greatest cost reductions previously determined are performed. Each set represents the components on a single supporting structure and the number of interconnections between the two structures is therefore minimized. As described a cost matrix each element d ij  of which represents the cost of interconnecting the components i and j which are to be connected and which are members of two arbitrarily chosen sets A and B is set up and the problem becomes one of partitioning the total set of points i, j into two sets A<SP>1</SP> and B<SP>1</SP> to minimize the cost function: The external cost of connecting a point in, say, set A to each of the points in set B to which it is to be connected is: and the internal cost of connecting a point in, say, set B to all other points in the same set to which it is to be connected is: The difference between external and internal costs for every element is D z  = E z  - I z  and the reduction in connection costs (gain) resulting from exchanging any a#A and b#B is: The D value for each component is computed and the values are sorted into decreasing order in two lists, one for each set. The gains produced by interchanging a given component in one set with the components corresponding to successive D's in the sorted list of the other set are then calculated until the sum Da+Db becomes less than or equal to the best previously found gain. The computation is then stopped since the D's become successively smaller and the third term in the equation above is negative so that no better gain will be found. The components so selected are then not considered further. The process is then repeated until no components are left. Some of the gains calculated are 0 or negative since exchanging the two sets entirely produces no gain. The total gain is then maximized by selecting the value of k giving a maximum for G. The exchanges corresponding to the gains g 1  - g k  are then effected to produce two new sets A<SP>1</SP> and B<SP>1</SP>. These new sets may then be regarded as the initial sets A and B and the process repeated. It will be seen that the expression for G max  may contain individual negative g's so long as the sum including these g's is a maximum. Thus the process can identify subsets in the initially chosen sets A and B which produce a maximum gain while permitting individual exchanges which increase the cost and the process does not terminate when a negative g is encountered. The process however does not inevitably find the optimum partition and modifications to assist in finding the optimum partition are described. In one modification the initial sets are further divided into A 1 , A 2 , B 1 , B 2  and the process applied to the set pairs A 1  and B 1 , and A 2  and B 2 . The resulting sets are recombined as: and the process repeated on the sets A 0  and B 0 . In a further modification is calculated after each cycle and if it is positive a maximum value is chosen and the process continues. However if no positive Gi is located the process terminates. The maximum Gi is located by scanning the Gi's to find a peak, interchanging the corresponding components, and continuing. The interchange may temporarily increase the total cost but will perturb the partition sufficiently to permit the next cycle to make a reduction. If the next cycle returns to the same point no further improvement can be achieved. The process may be used to divide a set of components into two subsets each containing at least N 0  or at most N 1  components. Dummy elements are used and the total size of the complete set is increased to 2N 1  elements. The process may also be adapted to handle partitioned sets of different sizes. This situation arises physically when a particular component occupies a greater normal amount of space on the supporting structure. The process may also be extended to perform a k-way partition of kn objects. This may be achieved with an initial arbitrary partition into k subsets and repeatedly applying the process to pairs of subsets. Alternatively the k subsets may be subdivided and further subdivided such that k = r.s ... t. and the process applied to each pair of sets at each stage of the subdivision.