Multi-path message routing without deadlocks

Claim 1

A method of routing a message through an array of data processing nodes which are intercoupled with channels in rows and columns; said message including a header with a S x field which selects a +X or -X direction for said message to travel on said rows of channels, a ΔX field which specifies the number of nodes through which said message must pass in the direction selected by said S x field, a S y field which selects a +Y or -Y direction for said message to travel on said columns of channels, and a ΔY field which specifies the number of nodes through which said message must pass in the direction selected by said S y field; said method being performed by a node which receives said header and including the steps of: examining said header for a first state wherein ΔX≠0 and ΔY≠0 and S x S y select a first predetermined pair of directions; sending said message through said node, if said first state exists, on just a single channel in the one direction of said first pair such that it followed by the other direction of said first pair form a clockwise turn; examining said header for a second state wherein ΔX≠0 and ΔY≠0 and S x S y select a second predetermined pair of directions; sending said message through said node, if said second state exists, on just a single channel in the one direction of said second pair such that it followed by the other direction of said second pair form a counterclockwise turn; examining said header for a third state wherein ΔX≠0 and ΔY≠0 and S x S y select neither said first or second predetermined pairs of directions; and, sending said message through said node, if said third state exists, on just a single channel in either one of the directions selected by S x S y based on channel availability and without regard to whether said message will make a clockwise turn or counterclockwise turn.

Claim 2

A method of routing a message through an array of data processing nodes which are intercoupled with channels in rows and columns; said message including a header with a S x field which selects a +X or -X direction for said message to travel on said rows of channels, a ΔX field which specifies the number of nodes through which said message must pass in the direction selected by said S x field, a S y field which selects a +Y or -Y direction for said message to travel on said columns of channels, and a ΔY field which specifies the number of nodes through which said message must pass in the direction selected by said S y field; said method being performed by a node which receives said header and including the steps of: examining said header for a first state wherein ΔX≠0 and ΔY≠0 and S x S y select a first predetermined pair of directions; sending said message through said node, if said first state exists, on just a single channel in the one direction of said first pair such that it followed by the other direction of said first pair form a clockwise turn; examining said header for a second state wherein ΔX≠0 and ΔY≠0 and S x S y select a second predetermined pair of directions; sending said message through said node, if said second state exists, on just a single channel in the one direction of said second pair such that it followed by the other direction of said second pair form a counterclockwise turn; examining said header for a third state wherein ΔX≠0 and ΔY≠0 and S x S y select neither said first or second predetermined pairs of directions; and, sending said message through said node, if said third state exists, on just a single channel in either one of the directions selected by S x S y based on channel availability and without regard to whether said message will make a clockwise turn or counterclockwise turn.