US 5,513,322 AGranted

Multi-path message routing without deadlocks

AssigneeUnisys Corporation

InventorChiYeh Hou

Life of this patent

Estimating the term…

Abstract

Messages are routed through an array of data processing nodes which are intercoupled with channels in rows and columns. Under certain conditions, a message can exit a node in either one of two directions; and this enables the message to reach its destination by multiple routes. Under other conditions, the message must exit the node in only predetermined direction, and that direction is selected to avoid message routing deadlocks.

Claims16

Dependent claims

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.sub.x field which selects a +X or -X direction for said message to travel on said rows of channels, a .DELTA.X field which specifies the number of nodes through which said message must pass in the direction selected by said S.sub.x field, a S.sub.y field which selects a +Y or -Y direction for said message to travel on said columns of channels, and a .DELTA.Y field which specifies the number of nodes through which said message must pass in the direction selected by said S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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.sub.x S.sub.y based on channel availability and without regard to whether said message will make a clockwise turn or counterclockwise turn.

6 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

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.sub.x field which selects a +X or -X direction for said message to travel on said rows of channels, a .DELTA.X field which specifies the number of nodes through which said message must pass in the direction selected by said S.sub.x field, a S.sub.y field which selects a +Y or -Y direction for said message to travel on said columns of channels, and a .DELTA.Y field which specifies the number of nodes through which said message must pass in the direction selected by said S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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 .DELTA.X.noteq.0 and .DELTA.Y.noteq.0 and S.sub.x S.sub.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.sub.x S.sub.y based on channel availability and without regard to whether said message will make a clockwise turn or counterclockwise turn.

6 more elements