Back to results
US 6,272,141 B1Granted
Multiple level minimum logic network
AssigneeThe United States of America as represented by the National Security Agency
InventorCoke S. Reed
Life of this patent
Estimating the term…
Abstract
A network or interconnect structure utilizes a data flow technique that is based on timing and positioning of messages communicating through the interconnect structure. Switching control is distributed throughout multiple nodes in the structure so that a supervisory controller providing a global control function and complex logic structures are avoided. The interconnect structure operates as a “deflection” or “hot potato” system in which processing and storage overhead at each node is minimized. Elimination of a global controller and buffering at the nodes greatly reduces the amount of control and logic structures in the interconnect structure, simplifying overall control components and network interconnect components and improving speed performance of message communication.
Claims73
An interconnect structure comprising:
- a plurality of nodes arranged in a topology of three dimensions;
- means for transmitting a message from a node N to a target destination including:
- means for determining whether a node en route to the target destination in the second and third dimensions and advancing one level toward the destination level of the first dimension is blocked by another message;
- means for advancing the message one level toward the destination level of the first dimension when the en route node is not blocked;
- means for moving the message in the second and third dimensions along a constant level in the first dimension otherwise;
- means for specifying the first dimension to describe a plurality of levels, the second dimension to describe a plurality of nodes spanning a cross-section of a level, and the third dimension to describe a plurality of nodes in the cross-section of a level;
- means for sending a control signal from a node on the level of the en route node to the node N in the first dimension, the control signal specifying whether the node en route is blocked;
- means for timing transmission of a message using a global clock specifying timing intervals to keep integral time modulus the number of nodes in a cross-section of a level;
- means for setting a first time interval α for moving the message in the second and third dimensions;
- means for setting a second time interval α−β for advancing the message one level toward the destination level, the global clock specifying a global time interval equal to the second time interval, the first time interval being smaller than the global time interval;
- and
- means for setting a third time interval for sending the control signal from the node on the level of the en route node to the node N, the third time interval being equal to β.
9 more elements
A communication interconnect structure for transmitting messages, comprising:
- a plurality of nodes arranged in a structure including:
- a hierarchy of levels from a source level to a destination level;
- a plurality of nodes spanning a cross-section of a level;
- and
- a plurality of nodes in a cross-section span, the level of a node being determined entirely by the position of the node in the structure;
- a plurality of interconnect lines coupling the nodes in the structure including for a node N on a level L:
- a message input interconnect line coupled to a node on a previous level L+1;
- a message input interconnect line coupled to a node on the level L;
- a message output interconnect line coupled to a node on the level L;
- a message output interconnect line coupled to a node on a subsequent level L−1;
- a control input interconnect line coupled to the message output interconnect line of a node on the level L−1;
- and
- a switch coupled to receive a message on the control input interconnect line and, in accordance with the message, to selectively transmit a message without buffering on the message output interconnect line coupled to the subsequent level L−1 node or on the message output interconnect line coupled to the level L.
10 more elements
A method of communicating messages in an interconnect structure comprising:
- arranging a plurality of nodes in a structure including a plurality of hierarchical levels from a source level to a destination level, the level of a node being determined entirely by the position of the node in the structure, a plurality of nodes sparming a cross-section of a level and a plurality of nodes in a cross-section span, the nodes having an input connection on the same level, an input connection on a previous level, an output connection on the same level and an output connection on a subsequent level;
- specifying a destination node in the destination level for receiving a message;
- originating the message at a node in the source level;
- communicating a message from node to node including:
- determining at a node whether a node on a subsequent level is directed toward the destination node;
- determining at a node whether the node on the subsequent level is blocked by another message;
- advancing the message to the node on the subsequent level when the node is directed toward the destination node and a node is unblocked;
- and
- otherwise traversing the message to a node on the same level.
6 more elements
A communication interconnect structure comprising:
- a plurality of nodes;
- and
- a plurality of interconnect lines coupling the nodes, a node X of the plurality of nodes having:
- a message input interconnect line coupled to a node A distinct from the node X;
- and
- a message input interconnect line coupled to a node B distinct from the node A and the node X, the node X accepting a message input from the node A and a message input from the node B with a control signal communicating between the node A and the node B for determining a priority relationship between conflicting messages, the control signal enforcing the priority relationship between the sending of a message from the node A to the node X and the sending of a message from the node B to the node X.
3 more elements
An interconnect apparatus, comprising:
- a plurality of nodes;
- and
- a plurality of interconnect lines in an interconnect structure selectively coupling the nodes in a hierarchical multiple level structure arranged to include:
- a plurality of J+1 levels in an hierarchy of levels arranged from a lowest destination level L0 to a highest level LJ which is farthest from the lowest destination level L0, the level of a node being determined entirely by the position of the node in the structure, the interconnect structure transmitting a message M in a plurality of discrete time steps, the message M moving in a time step and the interconnect structure having interconnections to move the message M in one of three ways in the time step including:
- the message M enters a node in the interconnect structure from a device external to the interconnect structure;
- the message M exits the interconnect structure to a designated output buffer;
- and
- the message M either moves from a node U on a level Lk to a different node V on the same level Lk or moves from the node U to a node W on a level Li where k is greater than i so that the level Li is closer to the destination level L0 than the level Lk.
5 more elements
An interconnect apparatus, comprising:
- a plurality of nodes;
- and
- a plurality of interconnect lines selectively coupling the nodes in a hierarchical multiple level structure with the level of a node being determined entirely by the position of the node in the structure in which data moves only unilaterally from a source level to a destination level or laterally along a level of the multiple level structure, a data message being transmitted through the multiple level structure from a source node to a designated destination node, a level of the multiple levels including:
- one or more groups of nodes, the data message being transmitted to a group of the one or more groups of nodes that is en route to the destination node, a group of the one or more groups including:
- a plurality of nodes, the data message being transmitted to a node N of the plurality of nodes of a group unilaterally toward the destination level if the node is not blocked and otherwise the data message being transmitted laterally if the node is blocked.
2 more elements
A network communicating messages in a sequence of discrete time steps, the network comprising:
- a plurality of nodes, the nodes including communication devices that receive messages and send messages;
- and
- a plurality of interconnect lines L interconnecting communication devices at the plurality of nodes, a node N of the plurality of nodes including:
- a connection to an interconnect line LUN for transmitting a message from a device U to the node N;
- a connection to an interconnect line LVN for transmitting a message from a device V to the node N;
- the network having a precedence relationship PN(U,V) relating to the node N and the devices U and V such that the device U has precedence over the device V in sending a message to the node N so that for a message MU at the device U that is directed to the node N via the interconnect line LUN at a time step t and a message MV at the device V that is directed to the node N via the interconnect line LVN also at a time step t, the message MU is successfully sent to the node N and the node V uses a control signal to decide where to send the message MV.
3 more elements
A network comprising:
- a plurality of nodes N;
- and
- a plurality of interconnect lines L connecting the plurality of nodes N in a predetermined pattern, the interconnect lines carrying messages M and control signals C, the messages M and control signals C being received by a node of the plurality of nodes at a discrete time step t and the messages M being moved to subsequent nodes of the plurality of nodes in an immediately subsequent discrete time step t+1, the plurality of interconnect lines L connecting the plurality of nodes N to include:
- a node NA having a message input interconnection for receiving a message MA, a control input interconnection for receiving a control signal CA, a direct message output interconnection to a node ND, a direct message output interconnection to a node NE, a direct control output interconnection to a device G, and a control logic for determining whether the message MA is sent to the node ND or the node NE based on:
- (1) the control signal CA;
- (2) a location of the node NA within the plurality of interconnect lines L;
- and
- (3) a routing information contained in the message MA.
5 more elements
An interconnect apparatus comprising:
- a plurality of nodes N;
- and
- a plurality of interconnect lines L connecting the plurality of nodes N in a predetermined pattern, the plurality of interconnect lines L connecting the plurality of nodes N to include:
- a node NA having a direct message input interconnection for receiving a message MA and having a plurality of direct message output interconnections for transmitting the message MA to a plurality of nodes including a preferred node NP being most preferred for receiving the message MA, the preferred node NP being determined only by routing information in a header of the message MA and the position of the node NA within the plurality of interconnect lines L;
- the preferred node NP having a plurality of direct message input interconnections for receiving a message MP from a plurality of nodes including a priority node NB which has priority for sending a message to the preferred node NP, the priority node NB being determined by position of the node NB within the plurality of interconnect lines L so that:
- if the node NA is the same as the node NB, then the message MA is the message MP and is sent from the node NA to the node NP;
- and
- if the node NA is not the same as the node NB and the node NB directs a message MB to the node NP, then the message MB is sent from the node NB to the node NP.
5 more elements
A network capable of carrying a plurality of messages M concurrently comprising:
- a plurality of output ports P;
- a plurality of nodes N, the individual nodes N including a plurality of direct message input interconnections and a plurality of direct message output interconnections, the individual nodes N for passing messages M to predetermined output ports of the plurality of output ports P, the predetermined output ports P being designated by the messages M;
- and
- a plurality of interconnect lines in an interconnect structure selectively coupling the nodes in a hierarchical multiple level structure arranged to include a plurality of J+1 levels in an hierarchy of levels arranged from a lowest destination level L0 to a highest level LJ which is farthest from the lowest destination level L0, the output ports P being connected to nodes at the lowest destination level L0, the level of a node being determined entirely by the position of the node in the structure,
- the network including a node NA of the plurality of nodes N, a control signal operating to limit the number of messages that are allowed to be sent to the node NA to eliminate contention for the predetermined output ports of the node NA so that the messages M are sent through the direct message output connections of the node NA to nodes NH that are a level L no higher than the level of the node NA, the nodes NH being on a path to the designated predetermined output ports P of the messages M.
2 more elements
An interconnect apparatus, comprising:
- a plurality of nodes;
- and
- a plurality of interconnect lines in an interconnect structure selectively coupling the nodes in a hierarchical multiple level structure arranged to include:
- a plurality of J+1 levels with J an integer greater than 0 in an hierarchy of levels arranged from a lowest destination level L0 to a highest level LJ with the level of a node being determined entirely by the position of the node in the structure, the interconnect structure transmitting a plurality of multiple-bit messages entering the interconnect structure unsorted through a plurality of input ports, an individual message M of the plurality of messages being self-routing, the individual message M moving in a plurality of ways including three ways which are sufficient for the message M to exit the interconnect structure through an output port designated by the message M, the three ways being:
- (1) the message M enters a node in the interconnect structure from a device external to the interconnect structure, the message M designating one or more designated output ports;
- (2) the message M moves through a node in the interconnect structure without buffering to a designated output port;
- and
- (3) the message M moves either through a node U on a level Lk of the interconnect structure without buffering to a different node V on the same level Lk or moves through the node U on a level Lk of the interconnect structure without buffering to a node W on a level Li nearer in the hierarchy to the destination level L0 than the level Lk.
5 more elements
An interconnect structure comprising:
- a plurality of nodes;
- and
- a plurality of interconnect lines in an interconnect structure selectively coupling the nodes in a structure, the interconnect structure transmitting a plurality of multiple-bit messages entering the interconnect structure unsorted through a plurality of input ports, an individual message M of the plurality of messages being self-routing, the interconnect structure including:
- a node NE having a first data input interconnection from a node NA and a second data input interconnection from a node NF distinct from the node NA;
- and
- a control interconnection between the node NA and node NF for carrying a control signal to resolve contention for sending messages to the node NE, the control signal being supplied from the node NA or the node NF each distinct from the node NE with which messages are communicated.
3 more elements
A method of moving messages through an interconnect structure comprising:
- interconnecting a plurality of devices in a structure, the devices having a plurality of message input terminals and a plurality of message output terminals, a plurality of interconnect lines interconnecting the device with connections from a message output terminal of a sending device to a message input terminal of a receiving device;
- assigning a priority among a plurality of sending devices having output message terminals coupled to the input message terminal of a single receiving device;
- entering a message into the interconnect structure for transfer to one or more designated output ports;
- sending a message, without buffering, from a sending device to a receiving device en route to the one or more output ports using self-routing, with the sending device neither requesting of the receiving device nor receiving from the receiving device, permission to send the message to the receiving device;
- communicating among a plurality of sending devices that send messages to a single receiving device, a sending device with priority for sending messages to the single receiving device having a control signal output terminal connected by an interconnect line to a control signal input terminal of a sending device without priority, the sending device with priority sending a control signal to the sending device without priority;
- deflecting a message intended to be sent from a sending device without priority to an intended receiving device, the deflected message being deflected to an alternative receiving device, the alternative receiving device also being en route to the one or more output ports.
3 more elements
A method of sending data comprising:
- providing an interconnect apparatus including a plurality of nodes N and a plurality of interconnect lines L connecting the plurality of nodes N in a predetermined pattern;
- connecting the plurality of nodes N using the plurality of interconnect lines L to include:
- a node NA having a direct message input interconnection for receiving a message MA and having a plurality of direct message output interconnections for transmitting the message MA to a plurality of nodes including a preferred node NP being most preferred for receiving the message MA, the preferred node NP being only determined by routing information in a header of the message MA and the position of the node NA within the plurality of interconnect lines L;
- the preferred node NP having a plurality of direct message input interconnections for receiving a message MP from a plurality of nodes including a priority node NB which has priority for sending a message to the preferred node NP, the priority node NB being determined by position of the node NB within the plurality of interconnect lines L;
- if the node NA is the same as the node NB, sending the message MA as the message MP from the node NA to the node NP;
- and
- if the node NA is not the same as the node NB and the node NB directs a message MB to the node NP, then sending the message MB from the node NB to the node NP.
4 more elements
A method of sending messages comprising:
- providing a network for canying a plurality of messages M concurrently including:
- a plurality of output ports P;
- and
- a plurality of nodes N, the individual nodes N including a plurality of direct message input interconnections and a plurality of direct message output interconnections, the individual nodes N for passing messages M to predetermined output ports of the plurality of output ports P, the predetermined output ports P being designated by the messages M;
- and
- a plurality of interconnect lines in an interconnect structure;
- selectively coupling the nodes in a hierarchical multiple level structure to include a plurality of J+1 levels with J an integer greater than 0 in an hierarchy of levels arranged from a lowest destination level L0 to a highest level LJ which is farthest in the hierarchy from the lowest destination level L0, the level of a node being determined entirely by the position of the node in the structure, the output ports P being connected to nodes at the lowest destination level L0,
- including in the network a node NA of the plurality of nodes N;
- limiting the number of messages M that are allowed to enter the plurality of direct message input interconnections of node NA to eliminate contention for the predetermined output ports of the node NA so that the messages M are sent through the direct message output connections of the node NA to nodes NH that are a level L no higher than the level of the node NA, the nodes NH being on a path to the designated predetermined output ports P of the messages M.
6 more elements
A method of transmitting a message through an hierarchical interconnect structure including a plurality of nodes and a plurality of interconnect lines, the method comprising:
- selectively coupling the nodes in an hierarchical multiple level structure arranged to include a plurality of J+1 levels with J an integer greater than 0 in an hierarchy of levels arranged from a lowest destination level L0 to a highest level LJ, the level of a node being determined entirely by the position of the node in the structure;
- entering a plurality of messages into the interconnect structure unsorted through a plurality of input ports;
- moving, using self-routing, an individual message M of the plurality of messages through nodes, the message M moving in a plurality of ways including three ways which are sufficient for the message M to exit the interconnect structure through an output port designated by the message M, the three ways including:
- (1) entering the message M to a node in the interconnect structure from a device external to the interconnect structure, the message M designating one or more designated output ports;
- (2) moving the message M through a node in the interconnect structure without buffering to a designated output port;
- and
- (3) moving the message M either through a node U on a level Lk of the interconnect structure without buffering to a different node V on the same level Lk, the different node V also having a pathway to a designated output port;
- or moving the message M through the node U on the level Lk of the interconnect structure without buffering to a node W on a level Li nearer in the hierarchy to the destination level L0 than the level Lk.
5 more elements
Dependencies are inferred from the claim text.