Adaptive routing in a parallel computing system
First Claim
1. A method for routing a message in a regular topology network between a source node and a destination node, said source node building a data transaction comprising a message and header, said header including bit groups that define nodal network paths, at least one node in one of said paths performing the steps of:
- (a) employing one of said bit groups of said header to establish multiple connections from an input link receiver to output link transmitters within said one node, each of said output link transmitters linked with a succeeding node, said input link receiver linked to a preceding node;
(b) copying the header from said input link receiver to each of said connected output link transmitters;
(c) modifying each copied header so that said copied header defines network paths to said destination node from succeeding nodes linked to one of said connected output link transmitters into which said header was copied; and
(d) transmitting said modified headers and said message to said succeeding nodes.
1 Assignment
0 Petitions
Accused Products
Abstract
A multi-dimensional, multi-nodal routing mechanism is described for relaying information from node to node using a header consisting of route descriptor bits. Each node'"'"'s receiver/transmitter pair changes states as the information is guided to the destination node. The message is propagated over several nodes simultaneously to traverse the nodes and reach the destination node quickly. When the final node is reached, all alternate communication routes are freed.
-
Citations
15 Claims
-
1. A method for routing a message in a regular topology network between a source node and a destination node, said source node building a data transaction comprising a message and header, said header including bit groups that define nodal network paths, at least one node in one of said paths performing the steps of:
-
(a) employing one of said bit groups of said header to establish multiple connections from an input link receiver to output link transmitters within said one node, each of said output link transmitters linked with a succeeding node, said input link receiver linked to a preceding node; (b) copying the header from said input link receiver to each of said connected output link transmitters; (c) modifying each copied header so that said copied header defines network paths to said destination node from succeeding nodes linked to one of said connected output link transmitters into which said header was copied; and (d) transmitting said modified headers and said message to said succeeding nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 12, 13)
-
-
8. An apparatus for routing a message in a regular topology nodal network, between a source node and a destination node, said source node building a data transaction comprising a message and header, said header including bit groups that define paths through said nodal network, at least one node in one of said paths comprising:
-
switch means; a plurality of output link transmitters, each of said output link transmitters linked with a succeeding node; a plurality of input link receivers, each input link receiver coupled to a preceding node and responsive to a received bit group of a said header, to establish multiple concurrent connections through the switch means, to output link transmitters within said one node and for copying said header to each of said connected output link transmitters; and means for modifying each said copied header to define nodal network paths to said destination node from succeeding nodes linked to one of said output link transmitter into which said header was copied, whereby each of said output link transmitters transmits its modified header and said message to the succeeding node to which said one of said output link transmitters is linked. - View Dependent Claims (9, 10, 11, 14, 15)
-
Specification