Inter-computer message routing system with each computer having separate routinng automata for each dimension of the network

• US 5,105,424 A
• Filed: 06/02/1988
• Issued: 04/14/1992
• Est. Priority Date: 06/02/1988
• Status: Expired due to Term

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Flaig, Charles M., Seitz, Charles L.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Coleman, Eric
• Application Number:
  US07/201,682
• Time in Patent Office: 1,412 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 370/94.1, 370/94.3
• US Class Current: 709/243
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/34 Source routing

Abstract

In a multicomputer, concurrent computing system having a plurality of computing nodes, this is a method and apparatus for routing message packets between the nodes. The method comprises providing a routing circuit at each node and interconnecting the routing circuits to define communications paths interconnecting the nodes along which message packets can be routed; at each routing circuit, forming routes to other nodes as a sequence of direction changing and relative address indicators for each node between the starting node and each destination node; receiving a message packet to be transmitted to another node and an associated destination node designator therefor; retrieving the route to the destination node from a memory map; adding the route to the destination node to the beginning of the message packet as part of a header; transmitting the message packet to the routing circuit of the next adjacent node on the route to the destination node; and at each intermediate node, receiving the message packet; reading the header; directing the message packet to one of two outputs thereof as a function of routing directions in the header, updating the header to reflect passage through the routing circuit; and at the destination node, stripping remaining portions of the header from the message packet; storing the message packet; and, informing the node that the message packet has arrived.

Claims

1. An inter-computer message routing system wherein message packets are routed among a plurality of computers along communication paths between said computers in an n-dimensional network of said communication paths, different groups of said communication paths comprising different ones of the n dimensions of said network, said message packets each comprising a header containing successive routing directions relative to successive computers along a selected route in said network, said system comprising:

a plurality of routers, each router being associated with a corresponding one of said computers, each of said routers comprising n routing automata corresponding to said n dimensions, each of said n routing automata having plural message packet inputs and plural message packet outputs, at least some of said inputs and outputs being connected to respective communication paths of the corresponding one of said n dimensions, said n routing automata being connected together in cascade from a message packet output of one to a message packet input of the next one of said routing automata corresponding to a sequence of dimensions of the routing automata;

routing logic means disposed within each one of said routing automata, said routing logic means comprising means for reading the header of a message packet received from one of the inputs of said one routing automata, means for directing said message packet to one of said outputs of said one routing automata in accordance with the contents of said header, and means for modifying said header to reflect the passage of said message packet through said one routing automata, whereby each of said routing automata performs all message routing for the message packets traveling in a corresponding one of said dimensions.

2. The system of claim 1 wherein said means for directing said message packet to one of said outputs comprises plural decision element means each having one decision input and plural decision outputs for directing a message packet received at said decision input to one of said decision outputs in accordance with the contents of said header, and plural merge element means having plural merge inputs and a single merge output for directing message packets received at the plural merge inputs thereof to said merge output without interference between said message packets.

3. The system of claim 2 wherein within a single one of each routing automata at least some of said decision inputs are connected to respective message packet inputs, at least some of said merge inputs are connected to respective decision outputs and at least some of said merge outputs are connected to respective message packet outputs.

4. The system of claim 1 wherein said header comprises a sequence of symbols and said means for modifying said header comprises:

means for decrementing a leading symbol in said header whereby said header specifies a direction for said message packet relative to a next one of the computers along said selected path.

5. The system of claim 4 wherein said means for modifying said header further comprises means for stripping no longer needed portions of said header.

6. The system of claim 4 wherein said sequence of symbols include symbols each comprising a count decrementable by said means for modifying said header, said count specifying a duration of travel in a constant dimension.

7. The system of claim 6 wherein said system permits bi-directional travel in each one of said dimensions, said sequence of symbols further including binary directional symbols specifying one of two directions.

8. The system of claim 6 wherein said means for modifying said header comprises means for decrementing a leading non-zero one of said counts and wherein said header specifies a change to the next one of said sequence of dimensions upon two consecutive leading counts thereof preceding one of said binary directional symbols being decremented to zero.

9. The system of claim 8 wherein said means for directing said message packet comprises means responsive to said header specifying a change o the next one of said sequence of dimensions for directing said message packet to a message packet output connected in cascade to a message packet input of a next routing automata of said next dimension.

10. The system of claim 3 wherein:

travel by said message packets along said paths is mono-directional and said system is one of a group of networks comprising 2-dimensional mesh networks and 3 dimensional torus networks;

there are two message packet inputs in each routing autotmata comprising one message packet input which receives message packets traveling in the corresponding dimension and another message packet input connectable to a message packet output of a preceding routing automata connected in cascade therewith; and

there are two message packet outputs in each routing automata comprising one message packet output which transmits message packets for travel in said corresponding dimension and another message packet output connectable to a message packet input of a succeeding routing automata in cascade therewith.

11. The system of claim 10 wherein:

there are two decision element means and two merge element means in each of said routing automata;

each of said decision element means has two decision outputs and each merge element means has two merge inputs.

12. The system of claim 3 wherein:

travel by said message packets along said paths is bi-directional;

there are three message packet inputs in each routing autotmata comprising first and second message packet inputs which receive message packets traveling in first and second directions in the corresponding dimension respectively, and a third message packet input connectable to a message packet output of a preceding routing automata connected in cascade therewith; and

there are three message packet outputs in each routing automata comprising first and second message packet outputs which transmit message packets for travel in first and second directions in said corresponding dimension respectively, and a third message packet output connectable to the third message packet input of a succeeding routing automata in cascade therewith.

13. The system of claim 12 wherein:

there are at least three decision element means and three merge element means in each of said routing automata;

at least one of said decision element means has three decision inputs including first and second decision inputs corresponding to said first and second directions and a third input corresponding to said preceding dimension;

at least one of said merge element means has three merge inputs of which at least one is connected to one of the three decision outputs of said one decision element means having three decision outputs.

14. The system of claim 1 wherein each of said computers comprise an integrated circuit including the corresponding router, a processor, a memory, a packet interface connected to said router and a bus connecting said packet interface, said memory and said processor, wherein:

said processor comprises means for retrieving information data from said memory to be routed in said network in a message packet and for computing an initial header based upon destination instructions stored in said memory; and

said packet interface comprises means for forming a data stream comprising said information data and said initial header and transmitting said data stream to said router connected thereto as a message packet.

15. The system of claim 4 wherein:

said metwork is one-dimensional and comprises an asynchronous pipeline of succesive ones of said computers in which said routers are connected in a cascaded succession of routers each comprising one routing automata; and

said means for decrementing comprises means for providing an asynchronous request signal to a successive one of said routing automata.

16. The system of claim 2 wherein said plural decision element means are a first set of substantially identical building block elements, said plural merge element means are a second set of substantially identical building block elements and wherein each of said routing automata are of substantially identical structure.

17. An inter-computer message routing system wherein message packets are routed among a plurality of computers along communication paths between said computers in an n-dimensional network of said communication paths, different groups of said communication paths comprising different ones of the n dimensions of said network, said message packets each comprising a header containing successive routing directions relative to successive computers along a selected route in said network, said system comprising:

a plurality of routers, each router being associated with a corresponding one of said computers, each of said routers comprising n routing automata corresponding to said n dimensions, each of said n routing automata having plural message packet inputs and plural message packet outputs, at least some of said inputs and outputs being connected to respective communication paths of the corresponding one of said n dimensions, said n routing automata being connected together in cascade from a message packet output of one to a message packet input of the next one of said routing automata corresponding to a sequence of dimensions of the routing automata;

routing logic means disposed within each one of said routing automata for directing a message packet received from one of the inputs of said one routing automata to one of said outputs of said one routing automata in accordance with the contents of said header, whereby said routing automata performs all message routing for the message packets traveling in a corresponding one of said dimensions.

18. The system of claim 17 wherein said means for directing said message packet to one of said outputs comprises plural decision element means each having one decision input and plural decision outputs for directing a message packet received at said decision input to one of said decision outputs in accordance with the contents of said header, and plural merge element means having plural merge inputs and a single merge output for directing message packets received at the plural merge inputs thereof to said merge output without interference between said message packets.

19. The system of claim 18 wherein within a single one of each routing automata at least some of said decision inputs are connected to respective message packet inputs, at least some of said merge inputs are connected to respective decision outputs and at least some of said merge outputs are connected to respective message packet outputs.

20. The system of claim 19 wherein:

travel by said message packets along said paths is mono-directional and said system is one of a group of networks comprising 2-dimensional mesh networks and 3 dimensional torus networks;

there are two message packet inputs in each routing autotmata comprising one message packet input which receives message packets traveling in the corresponding dimension and another message packet input connectable to a message packet output of a preceding routing automata connected in cascade therewith; and

there are two message packet outputs in each routing automata comprising one message packet output which transmits message packets for travel in said corresponding dimension and another message packet output connectable to a message packet input of a succeeding routing automata in cascade therewith.

21. The system of claim 17 wherein:

travel by said message packets along said paths is bi-directional;

there are three message packet inputs in each routing autotmata comprising first and second message packet inputs which receive message packets traveling in first and second directions in the corresponding dimension respectively, and a third message packet input connectable to a message packet output of a preceding routing automata connected in cascade therewith; and

there are three message packet outputs in each routing automata comprising first and second message packet outputs which transmit message packets for travel in first and second directions in said corresponding dimension respectively, and a third message packet output connectable to the third message packet input of a succeeding routing automata in cascade therewith.

22. The system of claim 17 wherein each of said computers comprise an integrated circuit including the corresponding router, a processor, a memory, a packet interface connected to said router and a bus connecting said packet interface, said memory and said processor, wherein:

said processor comprises means for retrieving information data from said memory to be routed in said network in a message packet and for computing an initial header based upon destination instructions stored in said memory; and

said packet interface comprises means for forming a data stream comprising said information data and said initial header and transmitting said data stream to said router connected thereto as a message packet.

23. The system of claim 18 wherein:

said metwork is one-dimensional and comprises an asynchronous pipeline of succesive ones of said computers in which said routers are connected in a cascaded succession of routers each comprising one routing automata; and

said routing logic means comprises means for providing an asynchronous request signal to a successive one of said routing automata.

24. The system of claim 18 wherein said plural decision element means are a first set of substantially identical building block elements, said plural merge element means are a second set of substantially identical building block elements and wherein each of said routing automata are of substantially identical structure.

25. A computer node chip for use in an inter-computer message routing system wherein message packets are routed among a plurality of such computer node chips along communication paths between said computer node chips in an n-dimensional network of said communication paths, different groups of said communication paths comprising different ones of the n dimensions of said network, said message packets each comprising a header containing successive routing directions relative to successive computer node chips along a selected route in said network, said computer node chip comprising:

a router comprising n routing automata corresponding to said n dimensions, each of said n routing automata having plural message packet inputs and plural message packet outputs, at least some of said inputs and outputs being connected to respective communication paths of the corresponding one of said n dimensions, said n routing automata being connected together in cascade from a message packet output of one to a message packet input of the next one of said routing automata corresponding to a sequence of dimensions of the routing automata;

routing logic means disposed within each one of said routing automata, said routing logic means comprising means for reading the header of a message packet received from one of the inputs of said one routing automata, means for directing said message packet to one of said outputs of said one routing automata in accordance with the contents of said header, and means for modifying said header to reflect the passage of said message packet through said one routing automata, whereby each of said routing automata performs all message routing for the message packets traveling in a corresponding one of said dimensions;

a processor;

a memory; and

a packet interface connected to said router and a bus connecting said packet interface, said memory and said processor, wherein said processor comprises means for retrieving information data from said memory to be routed in said network in a message packet and for computing an initial header based upon destination instructions stored in said memory, and said packet interface comprises means for forming a data stream comprising said information data and said initial header and transmitting said data stream to said router connected thereto as a message packet.

26. The chip of claim 25 wherein:

said means for directing said message packet to one of said outputs comprises plural decision element means each having one decision input and plural decision outputs for directing a message packet received at said decision input to one of said decision outputs in accordance with the contents of said header, and plural merge element means having plural merge inputs and a single merge output for directing message packets received at the plural merge inputs thereof to said merge output without interference between said message packets; and

within a single one of each routing automata at least some of said decision inputs are connected to respective message packet inputs, at least some of said merge inputs are connected to respective decision outputs and at least some of said merge outputs are connected to respective message packet outputs.