Method and apparatus for interconnecting processors in a hyper-dimensional array

• US 4,805,091 A
• Filed: 06/04/1985
• Issued: 02/14/1989
• Est. Priority Date: 06/04/1985
• Status: Expired due to Fees

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Clayton, Richard, Hillis, W. D., Feyman, Carl, Thiel, Tamiko, Kahle, Brewster
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Lynt, Christopher H.
• Application Number:
  US06/740,943
• Time in Patent Office: 1,351 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300 MS File, 370/60, 370/94
• US Class Current: 712/12
• CPC Class Codes: G06F 13/409 Mechanical coupling back panels H05K7/1438
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15

Abstract

A massively parallel processor comprising 65,534 (=2¹⁶) individual processors is organized so that there are 16 (=2⁴) individual processors on each of 4,096 (=2¹²) integrated circuits. The integrated circuits are interconnected in the form of a Boolean cube of 12 dimensions for routing of message packets. Each circuit board carries 32 (=2⁵) integrated circuits and each backplane carries 16 (=2⁴) circuit boards. There are eight (=2³) backplanes advantageously arranged in a cube that is 2×2×2. Each integrated circuit on a circuit board is connected to five integrated circuits on the same board which are its nearest neighbors in the first five dimensions. Further, each integrated circuit is also connected to four other integrated circuits on different circuit boards, but on the same backplane. Finally, each integrated circuit is also connected to three other integrated circuits, each on a different backplane. As a result of this arrangement, all message packets are first routed to nearest neighbor ICs located on the same circuit board; all message packets are then routed to nearest neighbor ICs located on the same backplane; and finally, all message packets are then routed to nearest neighbor ICs located on different backplanes.

Claims

1. In a parallel processor having an array of integrated circuits, each of said circuits comprising at least one processor and being interconnected to each of its nearest neighbors in a hyper-dimensional pattern of N dimensions, a method of making such interconnections on a plurality of circuit boards and backplanes comprising the steps of:

interconnecting on each circuit board the integrated circuits which are nearest neighbors in dimensions one through L;

interconnecting on each backplane the integrated circuits which are nearest neighbors in dimensions L+1 through M; and

interconnecting from one backplane to another the integrated circuits which are nearest neighbors in dimensions M+1 through N.

2. The method of claim 1 wherein each integrated circuit contains a plurality of processors.

3. The method of claim 1 wherein the integrated circuits are connected in the form of a Boolean cube of N dimensions.

4. In a parallel processor having an array of integrated circuits, each of said circuits being addressed by a multibit binary address and comprising at least one processor and being interconnected to each of its nearest neighbors in a pattern of a Boolean cube of more than three dimensions, a method of making such interconnections on a plurality of circuit boards and backplanes comprising the steps of:

interconnecting on each circuit board the integrated circuits which are nearest neighbors in a first consecutive number of dimensions;

interconnecting on each backplane the integrated circuits which are nearest neighbors in a second consecutive number of dimensions; and

interconnecting from one backplane to another the integrated circuits which are nearest neighbors in a third consecutive number of dimensions;

wherein the nearest neighbors of a particular integrated circuit are those other integrated circuits whose addresses differ by the Hamming distance one from that of the particular integrated circuit.

5. The method of claim 4 wherein each integrated circuit contains a plurality of processors.

6. In a parallel processor having an array of integrated circuits, each of said circuits comprising at least one processor and being interconnected to each of its nearest neighbors in a hyper-dimensional pattern of N dimensions, apparatus for interconnecting said integrated circuits on a plurality of boards and backplanes comprising:

means for interconnecting on each circuit board the integrated circuits which are nearest neighbors in dimensions one through L;

means for interconnecting on each backplane the integrated circuits which are nearest neighbors in dimensions L+1 through M; and

means for interconnecting from one backplane to another the integrated circuits which are nearest neighbors in dimensions M+1 through N.

7. The apparatus of claim 6 wherein each integrated circuit contains a plurality of processors.

8. The apparatus of claim 6 wherein the integrated circuits are connected in the form of a Boolean cube of N dimensions.

9. The apparatus of claim 6 wherein the means for interconnecting integrated circuits on a backplane comprises means for interconnecting integrated circuits on each board connected to a backplane to integrated circuits on other boards connected to the same backplane.

10. The apparatus of claim 6 wherein at least eight integrated circuits are mounted on a circuit board with each integrated circuit being connected to an least three nearest neighbors on that board, said eight integrated circuits being arranged in an array of two columns and four rows with each integrated circuit in a top half of the array being connected to two other integrated circuits in the top half and one other integrated circuit in the bottom half.

11. In a parallel processor having an array of integrated circuits, each being addressed by a multibit binary address and comprising at least one processor and being interconnected to each of its nearest neighbors in a pattern of a Boolean cube of more than three dimensions, apparatus for interconnecting said integrated circuits on a plurality of boards and backplanes comprising:

means for interconnecting on each circuit board the integrated circuits which are nearest neighbors in a first consecutive number of dimensions;

means for interconnecting on each backplane the integrated circuits which are nearest neighbors in a second consecutive number of dimensions; and

means for interconnecting from one backplane to another the integrated circuits which are nearest neighbors in a third consecutive number of dimensions;

wherein the nearest neighbors of a particular integrated circuit are those integrated circuits whose addresses differ by the Hamming distance one from that of the particular integrated circuit.

12. The apparatus of claim 11 wherein each integrated circuit contains a plurality of processors.

13. The apparatus of claim 11 wherein the means for interconnecting integrated circuits on a backplane comprises means for interconnecting integrated circuits on each board connected to a backplane to integrated circuits on other boards connected to the same backplane.

14. The apparatus of claim 11 wherein at least eight integrated circuits are mounted on a circuit board with each integrated circuit being connected to an least three nearest neighbors on that board, said eight integrated circuits being arranged in an array of two columns and four rows with each integrated circuit in a top half of the array being connected to two other integrated circuits in the top half and one other integrated circuit in the bottom half.

16. The method of claim 14 wherein the nearest neighbors of a particular integrated circuit are those other integrated circuits whose addresses differ by the Hamming distance one from that of the particular integrated circuit.

15. In a parallel processor having an array of integrated circuits, each of said circuits being addressed by a multibit binary address and comprising at least one processor and being interconnected to each of its nearest neighbors in a pattern of a Boolean cube of more than three dimensions, a method of making such interconnections on a plurality of circuit boards and backplanes comprising the steps of:

interconnecting on each circuit board the integrated circuits which are nearest neighbors in dimensions one through L;

interconnecting on each backplane the integrated circuits which are nearest neighbors in dimensions L+1 through M;

interconnecting from one backplane to another the integrated circuits which are nearest neighbors in dimensions M+1 through N; and

adjusting the clock cycle of the processor during the routing of messages between processors in accordance with the dimension of the processors between which the message is being routed.

17. In a parallel processor having an array of integrated circuits, each being addressed by a multibit binary address and comprising at least one processor and being interconnected to each of its nearest neighbors in a pattern of a Boolean cube of more than three dimensions, apparatus for interconnecting said integrated circuits on a plurality of boards and backplanes comprising:

means for interconnecting on each circuit board the integrated circuits which are nearest neighbors in dimensions one through L;

means for interconnecting on each backplane the integrated circuits which are nearest neighbors in dimensions L+1 through M;

means for interconnecting from one backplane to another the integrated circuits which are nearest neighbors in dimensions M+1 through N; and

means for adjusting the clock cycle during the routing of messages between processors in accordance with the dimension of the processors between which the message is being routed.

18. The apparatus of claim 17 wherein the nearest neighbors of a particular integrated circuit are those integrated circuits whose addresses differ by the Hamming distance one from that of the particular integrated circuit.