Method and apparatus for routing message packets

• US 4,598,400 A
• Filed: 11/15/1984
• Issued: 07/01/1986
• 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): Olms, Douglas W.
• Application Number:
  US06/671,835
• Time in Patent Office: 593 Days
• Field of Search: 370/60, 370/94, 370/54, 340/825.53, 340/825.52
• 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 parallel processor array is disclosed comprising an array of processor/memories and means 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 means comprises means 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 means.

Claims

1. Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising:

means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed,

means associated with each dimension for examining a digit of the address of said message packet received at a node to determine if the displacement in that dimension is zero,

means associated with each dimension for routing said message packet to another node in the same dimension if an examined digit indicates that the message packet has not reached its destination and if a connection to such node is available,

means for passing the message packet from one examining means to another when the message packet is not routed to another node in the same dimension, and

storing and processing means for routing message packets that have reached their destination to a message sink, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to said examining means for further routing.

8. The apparatus of claim 1 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

46. The apparatus of claim 1 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

47. The apparatus of claim 1 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

48. The apparatus of claim 47 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

49. The apparatus of claim 1 further comprising means for acknowledging to a source of said message packet successful transmission of said message packet.

2. Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising:

means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed,

at least first and second means for examining the first and second digits, respectively, of the address of said message packet received at a node to determine if the displacement in that dimension is zero,

at least first and second means for routing said message packet to another node in the first and second dimensions, respectively, if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available,

first means for providing the message packet to said second means for examining the second digit of the address information when said first connection is not available or said first digit indicates that the message packet has reached its destination in that dimension,

second means for providing the message packet to additional examining means or to storing and processing means when a connection is not available or said second digit indicates that the message packet has reached its destination in that dimension, and

storing and processing means for routing messages that have reached their destination to a message sink, for temporarily storing messages that have not been routed on to their destination and for recycling stored messages to said first examining means for further routing.

3. The apparatus of claim 2 further comprising means for updating the relative displacement at each node through which the message packet is routed.

4. The apparatus of claim 2 wherein two copies of the relative displacement are generated at the originating node and the displacement in one copy is up-dated at each node through which the message packet is routed while individual bits in the other copy of the relative displacement are examined by the routing means to control the routing of the message packet.

5. The apparatus of claim 2 wherein said first examining means, first routing means and first providing means at each node operate in synchronism with the first examining means, first routing means and first providing means at the other nodes of said network and said second examining means, second routing means and second providing means at each node operate in synchronism with the second examining means, second routing means and second providing means at the other nodes of said network.

9. The apparatus of claim 2 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

6. Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising:

means for generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed,

for each dimension of the address, a plurality of means for examining the digit associated with that dimension in the address of said message packet received at a node to determine if the displacement in that dimension is zero, for routing said message packet to another node in that dimension if the examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and for providing the message packet to another means at the same node for performing the same steps with respect to another dimension when the examined digit indicates that the message packet has reached its destination in that dimension or when the connection to another node in that dimension is not available, and

means connected to the examining, routing and providing means of the last dimension for routing to a data sink message packets that have reached their destination, for temporarily storing message packets that have not been routed on to their destination and for recycling stored message packets to the examining, routing and providing means of the first dimension.

10. The apparatus of claim 6 wherein the routing means associated with each dimension further comprises means for routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

7. A method for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising the steps of

(a) generating a message packet that is routed from one node to another in said pattern in accordance with relative address information included in said message packet, said relative address comprising as many digits as there are dimensions, each digit representing the relative displacement of the message packet from the node to which it is addressed,

(b) examining a digit of the address of said message packet received at a node to determine if the displacement in that dimension is zero,

(c) routing said message packet to another node if the examined digit indicates that the message packet has not reached its destination and if a connection to such node is available,

(d) providing the message packet to means for examining another digit of the address when said first connection is not available or said first digit examined indicates that the message packet has reached its destination in that dimension,

(e) repeating steps (b), (c) and (d) until all digits of the relative address have been examined,

(f) if the message packet reaches the node to which it is addressed by the time all the digits of the relative address have been examined, providing the message packet to a data sink at said node and if the message packet has not reached the node to which it is addressed repeating steps (b) through (f).

11. The method of claim 7 further comprising the step of routing a message packet to another node in the same dimension even if the displacement in that dimension is zero when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity.

12. A method for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising the steps of:

generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension,

examining a digit of the address of said message packet received at a node to determine if the message packet has reached its destination in the dimension associated with that digit,

routing said message packet to another node in the same dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and

if said message packet is not routed, examining another digit of the address of said message packet to determine if the message packet has reached its destination in the dimension associated with that digit.

13. The method of claim 12 further comprising the step of routing to a message sink message packets that have reached their destination.

14. The method of claim 12 wherein the address information is relative address information in which each digit represents the relative displacement of the message packet from the node to which it is addressed, said method further comprising the step of updating the relative displacement at each node through which the message packet is routed.

15. The method of claim 12 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

16. The method of claim 12 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

17. The method of claim 12 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

18. The method of claim 12 wherein the step of examining another digit of the address of the message packet is repeated until either the message packet is routed to another node or it is determined that the message packet has reached the node to which it is addressed.

19. The method of claim 12 wherein the steps of examining a digit of the address and routing the message packet are repeated until the message packet has reached the node to which it is addressed.

20. The method of claim 12 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

21. The method of claim 20 wherein the order in which the dimensions are traversed by each of said message packets depends on the presence of other messages packets being routed through the network.

22. The method of claim 20 wherein the steps of examining a digit of the address and routing the plurality of message packets are repeated until all the message packets have reached the nodes to which they are addressed.

23. A method for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising the steps of:

generating a plurality of message packets each of which is routed from a different node in said pattern to another node in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension,

examining at each node a digit of the address of said message packet received at said node to determine if the message packet has reached its destination in the dimension associated with that digit,

routing said message packet to another node in the same dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and

if said message packet is not routed, examining another digit of the address of said message packet to determine if the message packet has reached its destination in the dimension associated with that digit.

24. The method of claim 23 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

25. The method of claim 23 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

26. The method of claim 23 wherein the plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes in the same dimension.

27. The method of claim 23 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

28. The method of claim 23 wherein the steps of examining a digit of the address and routing the plurality of message packets are repeated until all the message packets have reached the nodes to which they are addressed.

29. A method for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising the steps of:

generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension,

during a first period of a routing cycle examining a first digit of the address of said message packet at a first node where said digit is then located to determine if the message packet has reached its destination in a first dimension associated with that digit,

routing said message packet to another node in the first dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available,

during a second period of the same routing cycle, examining a second digit of the address of said message packet at a node where said digit is then located to determine if the message packet has reached its destination in a second dimension associated with that digit,

routing said message packet to another node in the second dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and

during additional periods of the same routing cycle, routing the message packet until each digit of address information is examined at a node where said digit is then located, whereby during one routing cycle, the message packet can be routed serially through as many nodes as there are dimensions.

30. The method of claim 29 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

31. The method of claim 29 further comprising the step of routing a message packet to another node in the same dimension, even if the displacement in that dimension is zero, when no other message packet is being routed to said node in that dimension and the routing means is filled to capacity with other message packets, whereby a path traversed by a message packet from one node to another in said network varies depending on the presence of other message packets being routed through the same nodes in the network.

32. The method of claim 29 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

33. The method of claim 29 wherein the routing cycle is repeated until the message packet has reached the node to which it is addressed.

34. The method of claim 29 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

35. The method of claim 34 wherein the routing cycle is repeated until all the message packets have reached the node to which they are addressed.

36. A method for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising the steps of:

generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension,

during successive periods of a routing cycle examining successive digits of the address of said message packet at a node where the digit being examined is then located to determine if the message packet has reached its destination in a dimension associated with that digit,

routing said message packet to another node in that dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and

repeating the routing cycle until the message packet has reached the node to which it is addressed.

37. The method of claim 36 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

38. The method of claim 36 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

39. The method of claim 38 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

40. The method of claim 36 further comprising the step of acknowledging to a source of a message packet successful transmission of said message packet.

41. Apparatus for routing message packets through a network of nodes that are interconnected in a pattern of two or more dimensions comprising:

means for generating a message packet that is routed from one node to another in said pattern in accordance with address information included in said message packet, said address information comprising as many digits as there are dimensions, each digit providing addressing information for one dimension,

means operative during successive periods of a routing cycle for examining successive digits of the address of said message packet at a node where the digit being examined is then located to determine if the message packet has reached its destination in a dimension associated with that digit, and for routing said message packet to another node in that dimension if an examined digit indicates that the message packet has not reached its destination in that dimension and if a connection to such node is available, and

means for repeating the routing cycle until the message packet has reached the node to which it is addressed.

42. The apparatus of claim 41 wherein the order in which the dimensions are traversed by said message packet depends on the presence of other message packets being routed through the network.

43. The apparatus of claim 41 wherein a plurality of message packets are generated simultaneously at different nodes, the same digit of the address of each message packet is examined simultaneously at different nodes and message packets are routed simultaneously from different nodes to nodes of the same dimension.

44. The apparatus of claim 43 wherein the routing cycle is repeated until all message packets have reached the node to which they are addressed.

45. The apparatus of claim 41 further comprising means for acknowledging to a source of said message packet successful transmission of said message packet.