US4814980A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Concurrent hypercube system with improved message passing
Assignee: California Institute of Technology
•
Filing: 1986-04-01
•
Granted: 1989-03-21
•
Expires: 2006-04-01
Abstract
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.
Inventors
- 👤 John C. Peterson
- 👤 Jesus O. Tuazon
- 👤 Don Lieberman
- 👤 Moshe Pniel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:29
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
187 words
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.
Claim 2
Dependent Claim
187 words
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.
Claim 3
Dependent Claim
107 words
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.
Claim 4
Dependent Claim
122 words
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.
Claim 5
Dependent Claim
30 words
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.
Claim 6
Dependent Claim
38 words
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.
Claim 7
Dependent Claim
58 words
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.
Claim 8
Dependent Claim
62 words
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.
Claim 9
Dependent Claim
52 words
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.
Claim 10
Dependent Claim
65 words
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.
Claim 11
Dependent Claim
48 words
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.
Claim 12
Dependent Claim
187 words
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.
Claim 13
Dependent Claim
187 words
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.
Claim 14
Dependent Claim
157 words
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`.
Claim 15
Dependent Claim
157 words
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`.
Claim 16
Dependent Claim
91 words
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.
Claim 17
Dependent Claim
79 words
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.
Claim 18
Dependent Claim
41 words
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.
Claim 19
Dependent Claim
41 words
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.
Claim 20
Dependent Claim
49 words
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.
Claim 21
Dependent Claim
58 words
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.
Claim 22
Dependent Claim
62 words
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.
Claim 23
Dependent Claim
52 words
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.
Claim 24
Dependent Claim
69 words
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.
Claim 25
Dependent Claim
47 words
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.
References Cited (Backward Citations)
US3979728A
Cited
US3970993A
Cited
US4270170A
Cited
US4247892A
Cited
US4229790A
Cited
US4380046A
Cited
US4514807A
Cited
US4412285A
Cited
US4523273A
Cited
US4569041A
Cited
US4598400A
Cited
US4621339A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-03-20 | 1992-09-19 | 1993-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-03-20 | 1996-09-19 | 1997-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-03-20 | 2000-09-19 | 2001-03-21 | $7700.00 | Window Closed / Lapsed |