Adaptive message routing for multi-dimensional networks

Abstract

An adaptive routing means and method useful for transferring messages on a number of multi-dimensional network topologies that connect distributed multi-processing systems. A plurality of processing nodes comprising processing means for processing information and router means for routing messages are connected in a multi-dimensional network (A) with an identical or redundant message passing multi-dimensional network (B) of routers being connected to network A. Each router comprises four types of channels for message passing: 1) a channel to transfer information between a router and a processor coupled to the router, 2) a channel to transfer information in an X direction, 3) a channel for the Y direction, and 4) a channel for the Z direction. This connectivity allows messages to pass between nodes within network A, between routers within network B, or between network A and network B by passing through a router. Messages are routed in networks A and B by routing first in the X dimension and then in the Y dimension. The present invention transitions between A and B networks when contention is encountered in the X or Y direction, if the appropriate Z channel is available. If an X or Y channel is not immediately granted, a request is made for the Z channel. Both the request for an X or Y channel and the request for the Z channel are maintained until one request is granted. The message is then routed on the granted channel and the other request is withdrawn. The router does not commit to routing on a particular channel until one channel is available.

What is claimed is: 
     
       1. A network for routing messages comprising: a first network having a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network;   a second network having a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension; and   message routing means operably disposed within each said router of both said first network and said second network, said message routing means routing messages from a source node to a destination node via said first network channels and said second network channels, said message routing means routing messages between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.   
     
     
       2. The network claimed in claim 1 wherein said routers use routing information contained in each message for routing said message to its said destination node. 
     
     
       3. The network claimed in claim 1 wherein said first network and said second network are arranged in a two-dimensional dual mesh connection of nodes, said routers of said first network and said second network having X channels for routing messages in an X direction and Y channels for routing messages in a Y direction. 
     
     
       4. The network claimed in claim 1 wherein said message routing means routing messages between said first network and said second network on said Z channels in either direction. 
     
     
       5. The network claimed in claim 1 wherein said message routing means routing messages between said first network and said second network on said Z channels if the previous channel traversed was not a Z channel. 
     
     
       6. The network claimed in claim 1 wherein said message routing means further including: means for requesting the use of a primary channel in order to route a message thereon;   means for determining if a requested channel is available for use;   means for requesting the use of a secondary channel in order to route said message thereon if said primary channel is unavailable; and   means for granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.   
     
     
       7. The network claimed in claim 6 further including means for withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted. 
     
     
       8. The network claimed in claim 7 wherein said secondary channel is one of said Z channels. 
     
     
       9. The network claimed in claim 7 wherein said message routing means further including: means for repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.   
     
     
       10. The network claimed in claim 1 wherein said messages are routed using relative message addressing. 
     
     
       11. The network claimed in claim 1 wherein said messages are routed using absolute message addressing. 
     
     
       12. In a network having a first network including a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network and a second network including a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension, a process for routing messages comprising the step of: routing messages from a source node to a destination node via said first network channels and said second network channels, said messages being routed between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.   
     
     
       13. The process claimed in claim 12 wherein said message routing step further including: requesting the use of a primary channel in order to route a message thereon;   determining if a requested channel is available for use;   requesting the use of a secondary channel in order to route said message thereon if said primary channel is unavailable; and   granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.   
     
     
       14. The process claimed in claim 12 further including a step of: decoding routing information contained in each message for routing said message to its said destination node.   
     
     
       15. The process claimed in claim 12 further including a step of: routing messages in either an X direction or a Y direction in said first network depending upon information contained in each message.   
     
     
       16. The process claimed in claim 12 wherein messages may be routed on said Z channels from said first network to said second network or from said second network to said first network. 
     
     
       17. The process claimed in claim 13 further including a step of: withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted.   
     
     
       18. The process claimed in claim 13 further including a step of: repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.   
     
     
       19. A network routing apparatus comprising: a primary channel and a secondary channel, said primary channel and said secondary channel being used to route messages in a first network;   a Z channel, said Z channel being used to route messages to a second network; and   routing logic coupled to said primary channel, said secondary channel, and said Z channel, said routing logic comprising: means for requesting the use of said primary channel in order to route a message thereon;   means for determining if a requested channel is available for use;   means for requesting the use of said secondary channel in order to route said message thereon if said primary channel is unavailable; and   means for granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.     
     
     
       20. The network routing apparatus claimed in claim 19 further including: means for decoding routing information contained in each message for routing said message to a destination node.   
     
     
       21. The network routing apparatus claimed in claim 19 further including: means for routing messages in either an X direction or a Y direction in said first network depending upon information contained in each message.   
     
     
       22. The network routing apparatus claimed in claim 19 wherein messages may be routed on said Z channel from said first network to said second network or from said second network to said first network. 
     
     
       23. The network routing apparatus claimed in claim 19 wherein said routing logic further comprises means for withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted. 
     
     
       24. The network routing apparatus claimed in claim 19 wherein said routing logic further comprises means for repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.