Wormhole communications arrangement for massively parallel processor

• US 5,212,773 A
• Filed: 02/22/1991
• Issued: 05/18/1993
• Est. Priority Date: 05/31/1983
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Hillis, W. Daniel
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US07/660,323
• Time in Patent Office: 816 Days
• Field of Search: 395/DIG. 1, 395/DIG. 2, 395/200, 395/250, 395/275, 395/325, 395/800, 370/77, 370/79, 370/82, 370/83, 370/92, 370/93, 370/54, 370/60, 370/61
• US Class Current: 709/243
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes

Abstract

A parallel processor array is disclosed comprising an array of processor/memories and devices for interconnecting these processor/memories in an n-dimensional pattern having at least 2ⁿ nodes through which data may be routed from any processor/memory in the array to any other processor/memory. Each processor/memory comprises a read/write memory and a processor for producing an output depending at least in part on data read from the read/write memory and on instruction information. The interconnecting device comprises devices for generating an addressed message packet that is routed from one processor/memory to another in accordance with address information in the message packet and a synchronized routing circuit at each node in the n-dimensional pattern for routing message packets in accordance with the address information in the packets. Preferably the address information in the message packet is relative to the node in which the message packet is being sent and each digit of the address represents the relative displacement of the message packet in one dimension from the node to which the message packet is being sent. Advantageously, the n-dimensional pattern is a Boolean cube of 15 dimensions. With presently available technology, more than one million such processor/memories can be operated in parallel while interconnected by these interconnecting devices.

Claims

1. A computer system comprising a plurality of processing elements and a message router in which:

A. each processing element for generating messages, each message comprising an address portion comprising a series of address elements and a data portion comprising at least one data element, each processing element including a message transfer circuit for transmitting messages over said message router and for receiving messages from said router, said message transfer circuit transmitting each message by serially transmitting address elements and a data element thereof and receiving a message by serially receiving at least a data element thereof;

B. said message router being connected to the message transfer circuits of said processing elements for receiving messages transmitted by said message transfer circuits and transferring each such received message to a processing element in accordance with its address portion, said message router comprising a plurality of message router nodes interconnected by a plurality of communications links, at least some of said message router nodes also being connected to said processing elements, said message router nodes each including;

i. a plurality of input circuits each connected to one of said communications links or said processing elements for receiving messages therefrom, each input circuit serially receiving message elements comprising each message received thereby;

ii. a plurality of output circuits each connected to a communications link or to a processing element for transmitting messages thereto, each output circuit serially transmitting message elements comprising each message transmitted thereto; and

iii. a switch connected to said input circuits for, for each message received by said input circuits, decoding one address element of the message to identify therefor an output circuit, said switch establishing a path for said message between the input circuit which received the message and the identified output circuit to facilitate the transfer of message elements of said message therebetween, said switch maintaining the path until the last of the serially-received message elements for the message have been transferred to the identified output circuit.

2. A computer system as defined in claim 1 in which each message router node further includes a message buffer connected to said switch, said switch establishing paths between output circuits and input circuits such that, if a path has already been established between an output circuit and one of said input circuits, and if another input circuit receives a message having an address element which identifies the same output circuit, the switch will establish a path from said other input circuit to said message buffer to enable a transfer of said message to said message buffer for buffering.

3. A computer as defined in claim 2 in which, if multiple input circuits contemporaneously receive messages each having an address element which, when decoded, identifies the same output circuit, the switch selects one of said multiple input circuits for which it establishes a path to the identified output circuit.

4. A computer as defined in claim 3 in which the switch performs the selection of one of said multiple input circuits in accordance with a selected priority.

5. A computer as defined in claim 2 in which said switch further establishes a path from each of the others of said multiple input circuits to said message buffer to buffer messages received thereby.

6. A computer system as defined in claim 1 in which each address element in each said messages constitutes a bit.

7. A computer system as defined in claim 1 in which successive address elements of an address portion of a message enables switches of successive routing nodes in said message router to maintain a path through said successive router nodes for the message.

8. A computer system as defined in claim 1 in which said communications links interconnect said message router nodes in the form of a hypercube.

9. A message router for connection to a plurality of processing elements to form a computer system, each processing element for generating messages each message comprising an address portion comprising a series of address elements and a data portion comprising at least one data element, each processing element including a message transfer circuit for transmitting messages over said message router and for receiving messages from said router, said message transfer circuit transmitting each message by serially transmitting address elements and a data element thereof and receiving a message by serially receiving at least a data element thereof, said message router being connected to the message transfer circuits of said processing elements for receiving messages transmitted by said message transfer circuits and transferring each such received message to a processing element in accordance with its address portion, said message router comprising a plurality of message router nodes interconnected by a plurality of communications links, at least some of said message router nodes also being connected to said processing elements, said message router nodes each including:

A. a plurality of input circuits each connected to one of said communications links or said processing elements for receiving messages therefrom, each input circuit serially receiving message elements comprising each message received thereby;

B. a plurality of output circuits each connected to a communications link or to a processing element for transmitting messages thereto, each output circuit serially transmitting message elements comprising each message transmitted thereto; and

C. a switch connected to said input circuits for, for each message received by said input circuits, decoding one address element of the message to identify therefor an output circuit, said switch establishing a path for said message between the input circuit which received the message and the identified output circuit to facilitate the transfer of message elements of said message therebetween, said switch maintaining the path until the last of the serially-received message elements for the message have been transferred to the identified output circuit.

10. A message router as defined in claim 9 in which each message router node further includes a message buffer connected to said switch, said switch establishing paths between output circuits and input circuits such that, if a path has already been established between an output circuit and one of said input circuits, and if another input circuit receives a message having an address element which identifies the same output circuit, the switch will establish a path from said other input circuit to said message buffer to enable a transfer of said message to said message buffer for buffering.

11. A message router as defined in claim 10 in which said switch further establishes a path from each of the others of said multiple input circuits to said message buffer to buffer messages received thereby.

12. A message router as defined in claim 11 in which the switch performs the selection of one of said multiple input circuits in accordance with a selected priority.

13. A message router as defined in claim 10 in which, if multiple input circuits contemporaneously receive messages each having an address element which, when decoded, identifies the same output circuit, the switch selects one of said multiple input circuits for which it establishes a path to the identified output circuit.

14. A message router as defined in claim 9 in which each of said message elements is a bit.