Method and apparatus for routing message packets

• US 5,117,420 A
• Filed: 01/07/1991
• Issued: 05/26/1992
• Est. Priority Date: 04/27/1987
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Robertson, George G., Kahle, Brewster, Hillis, W. Daniel, Steele, Guy L. Jr.
• Primary Examiner(s): Paschall, Mark H.
• Application Number:
  US07/638,474
• Time in Patent Office: 505 Days
• Field of Search: 370/60, 370/94.1, 370/58, 370/54, 340/825.52, 340/825.53
• US Class Current: 370/400
• 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

Abstract

A message packet router is describes that performs the functions of determining if a message packet is addressed to circuitry associated with the router, of routing message packets to their destination if possible and of storing message packets that cannot be routed on because of circuit conflicts. The router also provides additional functions of merging message packets addressed to the same destination, of saving the state of the router at each significant point in the message routing cycle, and of running the entire routing cycle backwards. This later feature makes it possible to broadcast message packets selectively to certain processors in the array.

Claims

1. A parallel processing array comprising a plurality of nodes interconnected by communications links, each node comprising:

A. at least one processor for processing data and for generating messages for transfer to other processors in response to commands, each processor in said array being identified by an address and each message including an address portion which contains the address of the processor to receive the address; and

B. a communications node including;

i. a message injector for receiving messages from the processor for transfer to other processors;

ii. a message switch connected to said message injector and said communications links for selectively coupling messages from said message injector onto communications links connected thereto in accordance with the address to facilitate the transfer of messages with said processors in accordance with the address in the address portion of said respective messages, said message switch also receiving messages from communications links connected thereto;

iii. a message combining circuit connected to said message switch, said message combining circuit comparing addresses in address portions of messages contemporaneously received by said switch and selectively performing a combining operation in response to a positive comparison; and

iv. a message ejector for receiving messages from the switch and determining whether the address in the address portion of each message identifies the processor and coupling the message to the processor in response to a positive determination.

2. A parallel processing array as defined in claim 1 in which said message switch includes:

A. a local message receiving circuit for receiving messages from said message injector;

B. a local message coupling circuit for coupling messages to said message ejector;

C. a remote message receiving circuit for receiving messages from selected ones of said communications links;

D. a remote message coupling circuit for coupling messages over selected ones of said communications links; and

E. a switch circuit for selectively switching messages from said local message receiving circuit and said remote message receiving circuit to said local message coupling circuit and said remote message coupling circuit in accordance with the address in the respective address portion of each message.

3. A parallel processing array as defined in claim 1 in which said message switch couples messages to said message combining circuit over a predetermined number of lines, said message combining circuit comprising:

A. a message address comparison portion connected to said lines for comparing addresses in address portions of messages coupled over pairs of such lines;

B. a message combining portion connected to said lines and to said address comparison portion for performing a combining operation in response to a positive comparison by said message address comparison portion.

4. A parallel processing array as defined in claim 3 in which:

A. said message combining portion comprising a plurality of message combining cells, each having a first input terminal connected to one of said lines and having a second input terminal and an output terminal, each message combining cell in response to an enabling signal performing a selected combining operation in connection with signals received at said first and second input terminals to generate a combined message signal coupled to said output terminal; and

B. said message address comparison portion includes a plurality of address comparison cells each connected to a pair of said lines, each address comparison cell performing an address comparison operation in connection with addresses in address portions of messages coupled over the respective pair of lines and, in response to a positive comparison, coupling the message to the second input terminal of a message combining cell.

5. A parallel processing array comprising a plurality of nodes interconnected by communications links, each node comprising:

A. at least one processor for processing data and for generating messages for transfer to other processors in response to commands, each processor in said array being identified by an address and each message including an address portion which contains the address of the processor to receive the address; and

B. a communications node including;

i. a message switch for selectively transmitting and receiving messages over said communications links in accordance with the respective address in the address portion of said respective messages to facilitate the transfer of messages among said processors; and

ii. a message combining circuit connected to said message switch, said message combining circuit comparing addresses in address portions of messages contemporaneously received by said message switch and selectively performing a combining operation in response to a positive comparison.