US 5,212,773 AGranted

Wormhole communications arrangement for massively parallel processor

AssigneeThinking Machines Corporation

InventorW. Daniel Hillis

Life of this patent

Estimating the term…

Loading patent…

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

Claims14

Dependent claims

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.

3 more elements

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.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 07/660,323Filed 22 Feb 1991 · division
Priority: 31 May 1983
Granted: 18 May 1993
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 15/17381
Non hierarchical topologies: two dimensional, e.g. mesh, torus
G06F 15/8023
Single instruction multiple data [SIMD] multiprocessors: two dimensional arrays, e.g. mesh, torus
G06F 15/803
Single instruction multiple data [SIMD] multiprocessors: three-dimensional arrays or hypercubes
G06F
Computing and data processing

Family

Serial499,474Parent of this continuation · filed 31 May 1983
Serial184,739Parent of this division · filed 27 Jun 1988
US 4,814,973 AParent of this continuation · filed 21 May 1989
Serial478,082Parent of this division · filed 9 Feb 1990
Serial489,179Parent of this division · filed 5 Mar 1990
US 5,123,109 AParent of this division
US 5,152,000 AParent of this division
US 5,008,815 AParent of this division
US 5,212,773 AThis patent

From the US filing history. Foreign family members aren’t listed.