Express channels for diminishing latency and increasing throughput in an interconnection network

• US 5,475,857 A
• Filed: 11/18/1994
• Issued: 12/12/1995
• Est. Priority Date: 09/28/1990
• Status: Expired due to Term

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Dally, William J.
• Primary Examiner(s): Harvey, Jack B.
• Assistant Examiner(s): Seto, Jeffrey K.
• Application Number:
  US08/342,447
• Time in Patent Office: 389 Days
• Field of Search: 395/325, 395/800
• US Class Current: 712/11
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

An interconnection network is embellished with express channels that serve as parallel alternative paths to local channels between non-local nodes of the network. The use of the express channels increases throughput and diminishes latency experienced by the network. A single express channel may be used for a given sequence of nodes or alternatively multiple express channels may be utilized. Furthermore, express channels may be oriented in more than one dimension. Interchanges act as routing interfaces between the express channels and the conventional channels. The interchanges may be used as interfaces that adjust the wire density signalling level and speed at the boundaries of modules.

Claims

1. An interconnection network comprising:

a) an array of nodes interconnected by local channels such that any node may communicate with another node through local channels and through nodes of the array interconnected by the local channels;

b) an express channel running in parallel with the local channels to provide an alternative path for messages travelling between a first node and a second node that bypasses nodes interconnected by local channels between the first node and the second node; and

c) interchanges for interfacing the local channels with the express channel so that messages may travel over either the local channels or the express channel.

2. An interconnection network as recited in claim 1 further comprising additional express channels for providing additional alternative paths.

3. An interconnection network as recited in claim 2 further comprising additional interchanges for interfacing the additional express channels with each other and with the local channels.

4. An interconnection network as recited in claim 1 wherein the array is a linear array of nodes.

5. An interconnection network as recited in claim 1 wherein the interchanges are situated periodically throughout the interconnection network.

6. An interconnection network as recited in claim 1 wherein the nodes comprise processing elements.

7. An interconnection network as recited in claim 1 wherein the nodes comprise memory elements.

8. An interconnection network, comprising:

a) a linear array of nodes;

b) local channels interconnecting immediately adjacent nodes to allow messages to pass between nodes such that for a message to travel between two non-adjacent nodes over local channels, the message travels through nodes innerconnected between the non-adjacent nodes;

c) express channels running in parallel to the local channels for providing alternative paths for messages to travel between nodes that bypass intermediate nodes interconnected between said nodes; and

d) interchanges for interfacing the express channels and the local channels so as to allow messages to travel over either the express channels or the local channels.

9. An interconnection network as recited in claim 8 wherein the interchanges comprise a first interchange that interfaces a first of the express channels with the local channels and a second interchange that interface a second of the express channels with the local channels.

10. An interconnection network as recited in claim 8 wherein the interchanges comprise interchanges that interface multiple express channels with each other.

11. An interconnection network as recited in claim 10 wherein said interchanges also interface the express channels with the local channels.

12. An interconnection network as recited in claim 8 wherein the nodes comprise processing elements.

13. An interconnection network as recited in claim 8 wherein the nodes comprise memory elements.

14. In an interconnection network having a plurality of nodes interconnected by local channels, a method of decreasing message latency attributable to nodes, comprising the steps of:

a) providing an express channel that runs in parallel with local channels but that bypasses nodes interconnected by local channels in a locality;

b) providing interchanges positioned in the interconnection network to interface the local channels with the express channel;

c) routing local messages destined to the locality of nodes positioned between interchanges over the local channels; and

d) routing non-local messages destined to nodes positioned outside the locality of nodes over the express channel to decrease message latency attributable to the nodes.

15. A method as recited in claim 14 further comprising the step of providing additional express channels.

16. A method as recited in claim 15 further comprising the step of providing additional interchanges that interface the express channels.

17. A method as recited in claim 16 wherein the interchanges are organized in hierarchical fashion so that a message may consecutively step from level to level of express channels and local channels.

18. A method as recited in claim 16 wherein said additional express channels are oriented in multiple dimensions.

19. A method as recited in claim 18 wherein certain of the interchanges interface express channels oriented in different dimensions.