Lambda network having 2.sup.m-1 nodes in each of m stages with each node coupled to four other nodes for bidirectional routing of data packets between nodes
OwnerLeonard M. Napolitano, Jr.inventor
Life of this patent
Estimating the term…
Abstract
The Lambda network is a single stage, packet-switched interprocessor communication network for a distributed memory, parallel processor computer. Its design arises from the desired network characteristics of minimizing mean and maximum packet transfer time, local routing, expandability, deadlock avoidance, and fault tolerance. The network is based on fixed degree nodes and has mean and maximum packet transfer distances where n is the number of processors. The routing method is detailed, as are methods for expandability, deadlock avoidance, and fault tolerance.
Claims14
A multiprocessor communication network for transfer of data packets in a distributed memory parallel processor computing system, comprising:
- (a) a plurality of nodes arranged in m stages with 2.sup.m-1 nodes in each of said stages, each of said nodes being connected by links to four other nodes;
- (b) a plurality of processing elements equal to the number of nodes, one of each of said processing elements located at and connected to one node by a link;
- (c) means at each node for localized control of packet routing between nodes;
- and
- (d) means at each node for bidirectionally routing packets between nodes, whereby the number of nodes in said network is m2.sup.m-1 nodes, where m is an integer having a value greater than two.
A method for local control of routing data packets between nodes along bidirectional loops in a distributed memory parallel processor computer system comprising a plurality of nodes arranged in m stages with 2.sup.m-1 nodes in each of said stages, each of said nodes being connected by links to four other nodes, a plurality of processing elements equal to the number of nodes, one of each of said processing elements located at and connected to one node by a link, means at each node for localized control of packet routing between nodes, and means at each node for bidirectionally routing packets between nodes, whereby the number of nodes in said network is m2.sup.-1 nodes, where m is an integer having a value greater than two, the method comprising the steps of:
- (a) constructing a current loop address of the packet given a current node address;
- (b) constructing a destination loop address of the packet given a destination node address;
- (c) transforming the current loop address to the destination loop address to produce a loop resultant;
- (d) normalizing a destination stage address and the loop resultant;
- (f) switching loops according to the value of a predetermined bit of the normalized loop resultant;
- and
- (g) changing direction according to the value of a predetermined bit of the normalized destination stage address, the value of a predetermined bit of the normalized loop resultant, and stage size of the system.
A method for deadlock avoidance in a distributed memory parallel processor computer system comprising a plurality of nodes arranged in In stages with 2.sup.m-1 nodes in each of said stages, each of said nodes being connected by links to four other nodes, a plurality of processing elements equal to the number of nodes, one of each of said processing elements located at and connected to one node by a link, means at each node for localized control of packet routing between nodes, and means at each node for bidirectionally routing packets between nodes, whereby the number of nodes in said network is m2.sup.m-1 nodes, where m is an integer having a value greater than two, and having at least one input FIFO queue connected to each node input communication port at each link for the transfer of packets between a specific node and each of the four other nodes connected to said specific node and connected to a processing element input communication port for the transfer of packets between a specific node and its processing element, said method comprising the steps of:
- (a) determining the number of nodes that a data packet must traverse to reach its destination node;
- (b) transmitting the packet to the next node only when a number of packet storage spaces in a fullest input queue of the next node is equal to the number of nodes that a packet must traverse to reach its destination;
- (c) recirculating packets in any queue when packets have not been transmitted from a queue after a predetermined time.
A multiprocessor communication network for the transfer of data packets in a distributed memory parallel processor computing system, comprising:
- (a) a plurality of nodes arranged in m stages, each of said stages having 2.sup.m-1 nodes, each of said nodes being connected by links to four other nodes, each node including a switch point for routing packets from one link to another, a node input communication port and a node output communication port at each link for the transfer of packets between a specific node and each of the four other nodes connected to said specific node, a processing element input communication port and a processing element output communication port for the transfer of packets between said specific node and its processing element, at least one input FIFO queue connected to each of said communication ports for storing packets to be routed to each of the four connected nodes, and one of said FIFO queues storing packets to be routed to said processing element associated with said specific node, an output multiplexer connected to each output communication port, and routing determination circuitry;
- (b) a plurality of processing elements equal to the number of nodes, one of each of said processing elements located at and connected to one node by a link;
- (c) means at each node for localized control of packet routing between nodes, said means for localized control includes means for constructing a current loop address of the packet given a current node address including a current stage address, means for constructing a destination loop address of the packet given a destination node address having a destination stage address, means for transforming the current loop address to the destination loop address to produce a loop resultant, means for normalizing the stage addresses and the loop resultant, means for switching loops according to the value of a predetermined bit of the normalized loop resultant, means for selecting four possible paths to a destination node, means for arranging the possible paths in order of shortest length so that the output path corresponding to the input port through which the packet arrived is placed in fourth position, and means for routing the packet out a first intact path link;
- (d) means at each node for bidirectionally routing packets between nodes by changing direction according to the value of a predetermined bit of the normalized destination stage address, the value of a predetermined bit of the normalized loop resultant, and stage size of the system;
- and
- (e) means for avoiding deadlock which includes means for determining the number of nodes a packet must traverse to reach its destination node, means for transmitting the packet to the next node only when the number of packet storage spaces in a fullest input queue of the next node is equal to the number of nodes that a packet must traverse to reach its destination, and means for recirculating packets in any queue when packets have not been transmitted from a queue after a predetermined time,
- whereby the number of nodes in said network is m2.sup.m-1 nodes, where m is an integer having a value greater than two and wherein a packet arriving at one of said nodes is placed in one of said input FIFO queues, and said routing determination circuitry selects one of said communication output ports for routing said packet, and said output multiplexer outputs said packet.
Dependencies are inferred from the claim text.