Torus routing chip

A communication network adaptable for a plurality of concurrently operating computers ("nodes") including at each node an internal message handling circuitry, said network comprising:

• a physical communication channel connecting said plurality of nodes in a k-ary, n-cube configuration and forming a physical cycle in at least one dimension, which cycle includes k nodes;
• at least a pair of virtual channels sharing said physical channel between each pair of nodes in the cycle;
• means in each node for originating messages having a message destination identifier appended to the beginning of a message and indicating a destination for the message to a node other than the originating node;
• a message switching circuit connected at each node between the node and the physical communication channel interconnecting the plurality of node;
• means in each switching circuit for routing messages only in the network and free of storage in any node intermediate the originating and destination nodes;
• and
• means in each node switching circuit responsive to a message's destination identifier when a message reaches a destination node for gating that received message out of the network and into said destination node's internal message handling circuitry.

The improved method of routing messages from an originating node to a destination node in a multicomputer system comprising a plurality of interconnected computer nodes wherein the nodes are connected in a two dimensional array to prevent lockout comprising the steps of:

• (a) connecting pairs of nodes between which messages will travel between the originating node and the destination node with a physical communications channel;
• (b) switchably connecting each of the nodes to the physical communications channel through first and second virtual channels;
• (c) alternately sending messages from one node to a next node over the first and second virtual channels associated with the one node and the next node by time sharing the physical communications channel associated with the one node and the next node;
• (d) using the first virtual channel for the transmission of messages between nodes in the first dimension;
• and,
• (e) using the second virtual channel for the transmission of messages between nodes in the second dimension.

The method of routing messages from an originating node to a destination node in a multicomputer system comprising a plurality of computer nodes interconnected in at least two dimensions comprising the steps of:

• (a) connecting each of the nodes to a first physical communications channel in a first dimension and to a second physical communications channel in a second dimension;
• (b) switchably connecting each of the nodes to the first physical communications channel through first and second virtual channels;
• (c) switchably connecting each of the nodes to the second physical communications channel through third and fourth virtual channels;
• and,
• (d) alternately sending messages from one node to a next node over the first and second virtual channels associated with the one node and the next node by time sharing the physical communications channel associated with the one node and the next node using the first and second virtual channels for the transmission of messages between nodes in he first dimension and using the third and fourth virtual channels for the transmission of messages between nodes in the second dimension;
• (e) checking a message header associated with messages traveling between nodes in the first dimension at each node;
• and,
• (f) switching messages to the second virtual channel at the node where the message header indicates the message has reached its destination in the first dimension.

A message routing system for a plurality of concurrent computer nodes connected together with a unidirectional communication channel connecting said nodes in a cycle, said system comprising:

• a plurality of unidirectional virtual channels sharing said communication channel, each one of the plurality being terminated by a queue at an end;
• means at each node for originating a message packet having a destination node identifier other than the identity of the originating node;
• routing means at each queue for modifying each packet identifier as a function of the virtual channel's queue upon which it arrives and the node to which it is destined;
• and,
• packet switching means associated with said routing means and responsive to said packet identifiers for restricting the packets to those virtual channels leading to the packet's destination node.