Concurrent hypercube system with improved message passing

• US 4,814,980 A
• Filed: 04/01/1986
• Issued: 03/21/1989
• Est. Priority Date: 04/01/1986
• Status: Expired due to Fees

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Lieberman, Don, Pniel, Moshe, Tuazon, Jesus O., Peterson, John C.
• Primary Examiner(s): Zache, Raulfe B.
• Assistant Examiner(s): Harrell, Robert B.
• Application Number:
  US06/846,721
• Time in Patent Office: 1,085 Days
• Field of Search: 364/200 MS File, 364/300 MS File, 364/900 MS File, 364/300, 370/59-62, 370/92-95
• US Class Current: 709/216
• CPC Class Codes: G06F 15/17368 non hierarchical topologies

Abstract

A network of microprocessors, or nodes, are interconnected in an n-dimensional cube having bidirectional communication links along the edges of the n-dimensional cube. Each node'"'"'s processor network includes an I/O subprocessor dedicated to controlling communication of message packets along a bidirectional communication link with each end thereof terminating at an I/O controlled transceiver. Transmit data lines are directly connected from a local FIFO through each node'"'"'s communication link transceiver. Status and control signals from the neighboring nodes are delivered over supervisory lines to inform the local node that the neighbor node'"'"'s FIFO is empty and the bidirectional link between the two nodes is idle for data communication. A clocking line between neighbors, clocks a message into an empty FIFO at a neighbor'"'"'s node and vica versa. Either neighbor may acquire control over the bidirectional communication link at any time, and thus each node has circuitry for checking whether or not the communication link is busy or idle, and whether or not the receive FIFO is empty. Likewise, each node can empty its own FIFO and in turn deliver a status signal to a neighboring node indicating that the local FIFO is empty. The system includes features of automatic message rerouting, block message transfer and automatic parity checking and generation.

Claims

1. An asynchronous system of multiprocessor computers ("nodes") connected in a hypercube network configured as a cube, which cube includes nodes at each corner of the cube, bidirectional communication lines for passing data messages along the edge of the cube, and any node in said network being designable as a local node which has its nearest nodes in said network designated as immediate neighboring nodes, said system comprising:

a dedicated I/O processor at every node assigned only for communication tasks throughout said cube-configured network, with each I/O processor operating independently of every other I/O processor in the network to control its own node'"'"'s data message passing to its own immediate neighboring nodes;

a local FIFO at each node connected to a bidirectional communication link which is connected between a local node and each immediate neighboring node;

A FIFO-loading control line leading from a local node to each immediate neighboring node in said cube-configured network; and

means associated with a local node'"'"'s I/O processor and under control of said local I/O processor for loading the neighboring node'"'"'s FIFO via signaling over said bidirectional communication lines and said control line.

2. A system in accordance with claim 1 wherein data messages to be routed through the FIFO'"'"'s of said hypercube-configured network are each preceeded by a destination address, and further comprising:

means at each node associated with the dedicated I/O at that node for reading the destination address from each data message in each node'"'"'s own FIFO; and

means responsive to said destination address read by said reading means for either unloading the local FIFO at the local node or for transferring the data message in the local node'"'"'s FIFO to an empty receive FIFO at one of said immediate neighboring nodes as indicated by said destination address.

3. A system in accordance with claim 1 and further comprising:

transceivers at each node connected between each node'"'"'s FIFO and the bidirectional communication lines connected to said FIFO at each node, with each transceiver being set to a receive or a transmit state;

means at each node associated with the dedicated I/O at that node for controlling the state of that node'"'"'s transceivers and the state of the transceivers at said immediate neighboring nodes, said transceivers, when in a receive state, directly apply data from said bidirectional communication lines to said local node; and

means associated with each of said transceivers, when said transceivers are in a transmit state, for directly applying data from said local FIFO to said bidirectional communication lines.

4. A system in accordance with claim 3 and further comprising:

means for storing at a local node a signal indicative of a full or empty status of each local FIFO.

5. A system in accordance with claim 4 and further comprising:

means at a local node for applying to an immediate neighboring node, a FIFO empty signal indicating that a local FIFO assigned to that neighboring node is empty.

6. A system in accordance with claim 3 and further comprising:

means at a local node responsive to the transmit state at any one of said transceivers for storing said state as a channel busy indication to an immediate neighboring node that the status of the bidirectional communication lines between the local node and said neighbor node is busy.

7. A system in accordance with claim 6 and further comprising:

a microsequencer associated with a dedicated local I/O processor and responsive to an absence of a channel busy signal from a transceiver at said destination address for immediately latching said transceiver to a transmit state when a data message is to be sent over the bidirectional communication lines connected to said transceiver.

8. A system in accordance with claim 7 and further comprising:

means at a local node for storing said channel latch signals associated with each transceiver; and

means at a local node for supplying said channel latch signals from said local node to an immediate neighboring node which is connected to said transceiver.

9. A system in accordance with claim 8 and further comprising:

means at a local node for receiving, from all immediate neighboring nodes, signals indicative of an empty FIFO at said immediate neighboring node(s); and

control means supplying a FIFO-loading clock to said empty FIFO at said immediate neighboring node(s) for loading data supplied from a local node into said FIFO at said immediate neighboring node.

10. A system in accordance with claim 5 wherein:

a dedicated I/O processor at said immediate neighboring node responds to said FIFO empty signal received from said local node for loading the empty FIFO at said local node under control of said dedicated I/O processor at said neighboring node.

11. An asynchronous system of multi-processor computers ("nodes") connected in a hypercube network configured as a cube, which cube includes nodes at each corner of the cubes, bidirectional communication lines for passing data messages along the edges of the cube, and any node in said network being designable as a local node which has its nearest nodes in said network designated as immediate neighboring nodes, said system comprising:

a dedicated I/O processor at every node assigned only for communication tasks throughout said cube configured network, with each I/O processor operating independently of every other I/O processor in the network to control its own node'"'"'s data message passing to its own immediate neighboring nodes;

a local storage means at each node connected to a bidirectional communication link which is connected between a local node and each immediate neighboring node;

a control line leading from a local node to each immediate neighboring node in said cube-configured network; and

means associated with a local node'"'"'s I/O processor and under control of said local I/O processor for loading the neighboring node'"'"'s storage means via said bidirectional communication link and said control line.

12. An asynchronous system of multi-processor computers ("nodes") connected in a hypercube network configured as a cube, which cube includes nodes at each corner of the cube, bidirectional communication lines for passing data messages along the cube, and any node in said network being a local node which has its nearest nodes in said network designated as immediate neighboring nodes, said system comprising:

a dedicated I/O processor at every node assigned only for communication tasks throughout said cube-configured network, with each I/O processor operating independently of every other I/O processor in the network to control its own node'"'"'s data message passing to its own immediate neighboring nodes;

a control line leading from a local node to each immediate neighboring node in said cube-configured network; and

means associated with a local node'"'"'s I/O processor and under control of said local I/O processor for controlling message passing to an immediate neighboring node independently of message passing activity in other `nodes`.

13. A system in accordance with claim 12 wherein data messages to be routed through said hypercube-configured network are each preceeded by a destination address, and further comprising:

means at each node associated with the dedicated I/O at that node for reading the destination address from each data message in each node; and

means responsive to said destination address read by said reading means for either leaving the message at the local node or for transferring the data message to one of said immediate neighboring nodes as indicated by said destination address.

14. A system in accordance with claim 12 and further comprising:

transceivers at each node connected between each node and the bidirectional communication line connected to said immediate nodes, with said transceivers being setable to a receive or a transmit state; and

means at each node associated with the dedicated I/O at that node for controlling the state of that node'"'"'s transceivers and the state of the transceivers at said immediate neighboring nodes as required for said message passing activity.

15. A system in accordance with claim 14 and further comprising:

means at each node associated with each of said transceivers, when said transceivers are in a transmit state, for directly applying data from said local node to said bidirectional communication lines.

16. A system in accordance with claim 15 and further comprising:

a local message storage means at each node; and

means for storing at a local node a signal indicative of a full or empty status of that node'"'"'s local storage means.

17. A system in accordance with claim 16 and further comprising:

means at a local node for applying to an immediate neighboring node, a signal indicating that the status of a local storage means assigned to that neighboring node is available to receive a data message from an inquiring node.

18. A system in accordance with claim 14 and further comprising:

means at a local node responsive to the transmit state at any one of said transceivers for storing said state as a channel busy indication to an immediate neighboring node that the status for the bidirectional communication lines between the local node and said neighbor node is busy.

19. A system in accordance with claim 18 and further comprising:

a microsequencer associated with a dedicated local I/O processor and responsive to an absence of a channel busy signal from a transceiver at said destination address for immediately latching said transceiver to a transmit state when a data message is to be sent over the bidirectional communication lines connected to said transceiver.

20. A system in accordance with claim 19 and further comprising:

means at a local node for storing said channel latch signal associated with each transceiver; and

means at a local node for supplying said channel latch signals from said local node to an immediate neighboring node which is connected to said transceiver.

21. A system in accordance with claim 20 and further comprising:

means at a local node for receiving, from all immediate neighboring nodes, signals indicative of an empty message storage means at said immediate neighboring node(s); and

control means supplying a message-loading clock to said empty storage means at said immediate neighboring node(s) for loading data supplied from a local node into said storage means at said immediate neighboring node.

22. A system in accordance with claim 17 wherein:

a dedicated I/O processor at said immediate neighboring node responds to said local-storage-means-empty signal received from said local node for loading said storage means at said local node under control of said dedicated I/O processor at said neighboring node.