Parallel processor that routes messages around blocked or faulty nodes by selecting an output port to a subsequent node from a port vector and transmitting a route ready signal back to a previous node

Claim 2

In a network of interconnected nodes; each node including a processor; each of said processors in said network being assigned a unique processor identification (ID); an apparatus for establishing a communication path through a node of said network comprising: a plurality of input ports; a plurality of output ports; each one of said input ports being paired with a corresponding one of said output ports; control means at one input port of said input ports of a said node for receiving an address packet related to a current message transmitted from an output port of another of said nodes; a router connected to said one input port and to said output ports; registering means for registering said processor identification (ID); comparing means connected to said control means and to said registering means for comparing a target node address in said address packet with said processor ID; said comparing means including means for creating a first condition provided that said ID is equal to said target node address and, alternatively, a second condition provided that said ID is not equal to said target node address; a plurality of receive channels connected to said router; allocation means connected to said comparing means and to said receive channels for allocating to said one input port, one of said plurality of receive channels upon occurrence of said first condition; and, first means connected to said comparing means and to said control means for sending a route ready command over said output port paired with said input port upon occurrence of said first condition.

Claim 3

The combination in accordance with claim 1 further comprising: a port vector; second means connected to said comparing means and to said router for selecting a first unallocated output port from said port vector upon occurrence of said second condition that said node address is not equal to said target node address; and, third means connected to said second means and to said input port for forwarding said address packet to a next node over said first unallocated output port.

Claim 4

The combination in accordance with claim 1 further comprising: means for selecting a first unallocated output port connected to a third unallocated node; and, means for forwarding said address packet to said third node via said first unallocated output port.

Claim 5

The combination in accordance with claim 2 further comprising: means for selecting a first unallocated output port connected to a third node; and, means for forwarding said address packet to said third node via said first unallocated output port.

Claim 6

In a network of interconnected nodes; each node including a plurality of input ports and a plurality of output ports, each one of said input ports being paired with a corresponding one of said output ports; a method of establishing a communication path through a node of said network comprising steps of: A. receiving at an input port of a first of said nodes a first address packet having a target node address therein, said first address packet being related to a current message sent from an output port of a second of said nodes; B. comparing at said first node said target node address in said first address packet with a processor identification ID of said first node; C. allocating a receive channel of said first node to receive a message upon a first condition that said processor ID is the same as said target node address; and, D. sending a route ready command to said second node over said output port paired with said input port at said first node upon said first condition that said processor ID is the same as said target node address.

Claim 7

In a network of interconnected nodes; each node including a plurality of input ports and a plurality of output ports, each one of said input ports being paired with a corresponding one of said output ports; a method of establishing a communication path through a node of said network comprising steps of: A. receiving at an input port of a first of said nodes a first address packet having a target node address therein, said first address packet being related to a current message sent from an output port of a second of said nodes; B. comparing at said first node said target node address in said first address packet with a processor identification ID of said first node; C. allocating a receive channel of said first node to receive a message upon a first condition that said processor ID is the same as said target node address; and, D. sending a route ready command to said second node over said output port paired with said input port at said first node upon said first condition that said processor ID is the same as said target node address.

Claim 8

The method in accordance with claim 5 comprising the further steps of: E. selecting a first output port connected to a third node; and, F. forwarding said address packet to said third node via said selected first output port.

Claim 9

The method in accordance with claim 6 comprising the further steps of: G. receiving a route command; and, H. sending a route reiect command via said output port paired with said input port.

Claim 10

A communication apparatus in which a message can be routed a number of ways in response to an address packet that includes programmable control information that enables the finding and establishing of a route to a destination target node from a source sender node, comprising: a maze router mechanism; said maze router mechanism being an adaptive routing mechanism in which for a message from a particular node to a next node, paths between said particular node and said next node are searched one at a time by a scout packet until a free path is found and established, resulting in an established path from said sender node through said particular node; means at said particular node for sending a path command packet from said particular node back to said sender node, said path command packet being sent out of a particular node output port paired with a particular node input port over which said scout packet was received; a fixed-router mechanism; said fixed-router mechanism being an non-adaptive routing mechanism in which for a message from one node to a next node, one unique predetermined routing path between said one node and said next node is established; and, mode selection means responsive to said address packet for selecting either said maze router mechanism or said fixed-router mechanism.

Claim 11

A communication apparatus in which a message can be routed a number of ways in response to an address packet that includes programmable control information that enables the finding and establishing of a route to a destination target node from a source sender node, comprising: a maze router mechanism; said maze router mechanism being an adaptive routing mechanism in which for a message from a particular node to a next node, paths between said particular node and said next node are searched one at a time by a scout packet until a free path is found and established, resulting in an established path from said sender node through said particular node; means at said particular node for sending a path command packet from said particular node back to said sender node, said path command packet being sent out of a particular node output port paired with a particular node input port over which said scout packet was received; a fixed-router mechanism; said fixed-router mechanism being an non-adaptive routing mechanism in which for a message from one node to a next node, one unique predetermined routing path between said one node and said next node is established; and, mode selection means responsive to said address packet for selecting either said maze router mechanism or said fixed-router mechanism.

Claim 12

A communication apparatus comprising: a memory address bus; a memory data bus; a direct memory access buffers and logic block connected to said memory address bus and to said and memory data bus; a plurality of receive channels; a plurality of send channels; a plurality of routing registers connected to said send channels and to said receive channels; a cut-through arbiter connected to said plurality of receive channels and to said plurality of send channels; a routing arbiter connected to said plurality of send channels and to said routing registers; a processor bus connected from a central processing unit to said receive channels, said send channels and said routing registers and logic; a plurality of input ports; a plurality of input pins; said plurality of input ports being connected to said routing arbiter and to said input pins; a plurality of output ports; and, a plurality of output pins; said plurality output ports being connected to said cut-through arbiter and to said output pins; said plurality of input ports and said plurality of output ports being connected to said cut-through arbiter, said routing arbiter, and to said send and receive channels.

Claim 13

A communication apparatus comprising: a memory address bus; a memory data bus; a direct memory access buffers and logic block connected to said memory address bus and to said and memory data bus; a plurality of receive channels; a plurality of send channels; a plurality of routing registers connected to said send channels and to said receive channels; a cut-through arbiter connected to said plurality of receive channels and to said plurality of send channels; a routing arbiter connected to said plurality of send channels and to said routing registers; a processor bus connected from a central processing unit to said receive channels, said send channels and said routing registers and logic; a plurality of input ports; a plurality of input pins; said plurality of input ports being connected to said routing arbiter and to said input pins; a plurality of output ports; and, a plurality of output pins; said plurality output ports being connected to said cut-through arbiter and to said output pins; said plurality of input ports and said plurality of output ports being connected to said cut-through arbiter, said routing arbiter, and to said send and receive channels.

Claim 14

The communication apparatus in accordance with claim 9 further comprising: mode selection means connected to said cut-through arbiter and to said routing arbiter for selecting either said cut-through arbiter or said routing arbiter; one of said input ports including means for receiving an address packet that includes control information that enables the finding and establishing of a route to a destination node from a source node.

Claim 17

The method in accordance with claim 11 comprising the further steps of: G. pushing route rejected status onto an end-to-end (ETE) queue upon a condition that said step E results in said send port vector being reduced to zero.

Claim 18

The method in accordance with claim 11 wherein said address packet includes a forward bit, said method comprising the further steps of: G. setting a route ready status upon a condition that a mute is established; H. entering a forwarding state upon a condition that said forward bit is set in said address packet; and, I. entering a message transmission state upon a condition that said forward bit is not set in said address packet.

Claim 19

The method in accordance with claim 11 comprising the further steps of: G. inverting said send port vector to provide an alternate send port vector upon a condition that said routing status is route rejected; and, H. using said alternate send port vector to select a first unallocated output port from said alternate send port vector to provide said selected output port.

Claim 22

The method in accordance with claim 15 comprising the further steps of: I. sending a route ready command via an output port paired with said input port upon a condition that said route command indicates that a route is ready.

Claim 23

The method in accordance with claim 15 comprising the further steps of: I. sending a route reject command via an output port paired with said input port upon a condition that said step C of selecting a first unallocated output port specified in said port vector to provide a selected output port results in no port being selected.

Claim 24

The method in accordance with claim 15 comprising the further steps of: I. generating a port vector upon a condition that said result is equal to zero; J. selecting a first ready receive channel using said port vector to provide a port select vector; K. selecting a first unallocated input port specified in said port select vector to provide selected output port; L. allocating said first ready receive channel to receive a message upon a condition that an input port is selected; and M. sending a route ready command via an output port paired with said input port.

Claim 29

The method in accordance with claim 20 comprising further steps of: K. disconnecting said second intermediate node output port from said first intermediate node input port upon receipt of said end -- to -- end acknowledge message.

Claim 30

The communication apparatus of claim 8 wherein a transmission from said sender node to said target node is accomplished over a path established from a send channel at said sender node to a receive channel at said target node, said apparatus further comprising: a plurality of input ports at said sender node; a plurality of output ports at said sender node; each one of said input ports being paired with a corresponding one of said output ports; a plurality of send channels at said sender node; each of said send channels having associated with it a send port vector; said send port vector indicating selected output ports of said sender node through which maze routing is to be attempted; said scout packet being sent out of a first output port of said selected output ports of said sender node, and thereby delivered to an intermediate node, said intermediate node being a next node in a potential path to said target node; means for locking a path from said send channel to said first of said selected output ports of said sender node, so that said output port is reserved for a pending transmission; and, means for unlocking said path from said send channel to said first output port upon a condition that a path rejection packet is subsequently received on a corresponding input port paired with said first output port.

Claim 31

The communication apparatus of claim 22 further comprising: means for selecting a new output port from said send port vector upon said condition that a path rejection packet is received on said corresponding input port paired with said first output port; and, means for sending said scout packet out said new output port.

Claim 32

The communication apparatus of claim 22 further comprising: means for starting a transmission from said sender node to said target node over a path established from said send channel at said sender node to a receive channel at said target node, upon a condition that a path acknowledge packet is received on said corresponding input port paired with said first output port.

Claim 33

The communication apparatus of claim 22 wherein said scout packet includes a node address of said target node, said apparatus further comprising: means for comparing said target node address from said scout packet with said node ID; means for delivering said scout packet to an available receive channel upon a condition that said target node address and said node ID match; means for sending a path acknowledge packet back to said sender node, retracing said scout's path; means for sending a, a path rejection packet is sent back to said source node via said established path if a receive channel is not available; and, means for delivering said scout packet to said next node along a minimum-length path to said target node if a receiving node's node ID does not match said target node address.

Claim 34

In a network of interconnected nodes; each node in said network being assigned a unique identification (ID); a sender node; said sender node originating an address packet having a target node address of a target node; each node in said network including comparing means for comparing said target node address with an ID of said node; said comparing means creating a first condition provided that said ID is not equal to said target node address, indicating that a node is an intermediate node and, alternatively, a second condition provided that said ID is equal to said target node address, indicating that a node is said target node; a plurality of input ports at each of said nodes; a plurality of output ports at each of said nodes; each one of said input ports being paired with a corresponding one of said output ports; control means at one input port of said input ports of a particular node for receiving said address packet transmitted from an output port of a previous node of said interconnected nodes; allocating means, operative upon occurrence of said first condition indicating that said particular node is an intermediate node, for allocating to said one input port, one of said output ports of said particular node, but excluding the output port paired with the input port over which said address packet is received; an improvement characterized by: means at said particular node for establishing a path to a next node upon occurrence of said first condition at said particular node, resulting in an established path from said sender node through said particular node; and, means for sending a path command packet from said particular node back to said sender node, said path command packet being sent out of a particular node output port paired with a particular node input port over which said address packet was received.

Claim 35

In a network of interconnected nodes; each node in said network being assigned a unique identification (ID); a sender node; said sender node originating an address packet having a target node address of a target node; each node in said network including comparing means for comparing said target node address with an ID of said node; said comparing means creating a first condition provided that said ID is not equal to said target node address, indicating that a node is an intermediate node and, alternatively, a second condition provided that said ID is equal to said target node address, indicating that a node is said target node; a plurality of input ports at each of said nodes; a plurality of output ports at each of said nodes; each one of said input ports being paired with a corresponding one of said output ports; control means at one input port of said input ports of a particular node for receiving said address packet transmitted from an output port of a previous node of said interconnected nodes; allocating means, operative upon occurrence of said first condition indicating that said particular node is an intermediate node, for allocating to said one input port, one of said output ports of said particular node, but excluding the output port paired with the input port over which said address packet is received; an improvement characterized by: means at said particular node for establishing a path to a next node upon occurrence of said first condition at said particular node, resulting in an established path from said sender node through said particular node; and, means for sending a path command packet from said particular node back to said sender node, said path command packet being sent out of a particular node output port paired with a particular node input port over which said address packet was received.

Claim 36

The improvement of claim 26 further characterized by: said path command packet being encoded to return path rejection status to a previous node, indicating that a path is not established at said particular node, or path found status to said sender node, indicating that a path is established to said target node through said particular node.

Claim 37

The improvement of claim 26 further characterized by: means, operative upon occurrence of said second condition indicating that said particular node is a target node, for sending a path command packet from said target node back to said sender node; said path command packet being sent out of a target node output port paired with a target node input port over which said address packet was received; said path command packet being encoded to return path found status to said sender node, indicating that a path is established to said target node through said intermediate node; each intermediate node in an established path sender said command message to a previous node out of an output port paired with an input port over which said message packet was received.

Claim 38

The improvement of claim 26 further characterized by: a port vector; said allocating means selecting a first unallocated output port from said port vector upon occurrence of said first condition; and, forwarding means for forwarding said address packet to said next node over said first unallocated output port.

Claim 39

The improvement of claim 29 further characterized by: said means for establishing a path to a next node including means for sequentially selecting unallocated output ports from said port vector upon occurrence of said first condition; and, means for encoding said path command packet to return path rejection status to a previous node over an output port paired with said input port on which said address packet was received, upon a condition that selecting unallocated output ports from said port vector results in no path being established to said next node.

Claim 40

The improvement of claim 29 further characterized by: a fold enable vector indicating which of said plurality of output ports can be folded resulting in a folding partner for a chosen output port, said folding partner being an output port through which a message may be routed; such that if said chosen output port is not available for routing but said folding partner is available, said folding partner is considered as a potential routing candidate.

Claim 41

The improvement of claim 28 further characterized by: sending an end to end acknowledge command packet out of said target node output port paired with said target node input port on which a message packet is received, upon a condition that a message transmission has completed.

Claim 42

The improvement of claim 32 further characterized by: disconnecting an intermediate node output port from an intermediate node input port paired with said intermediate node output port, in response to said end to end acknowledge message.

Claim 43

The improvement of claim 26 further characterized by: a plurality of send channels at said sender node; each of said send channels having associated with it a send port vector; said send port vector indicating selected output ports of said sender node through which routing is to be attempted; a scout packet; said scout packet being sent out of a first output port of said selected output ports of said sender node, and thereby delivered to an intermediate node, said intermediate node being a next node in a potential path to said target node; means for locking a path from said send channel to said first of said selected output ports of said sender node, so that said output port is reserved for a pending transmission; and, means for unlocking said path from said send channel to said first output port upon a condition that a path rejection packet is subsequently received on a corresponding input port paired with said first output port.

Claim 44

The improvement of claim 34 further characterized by: inverting said send port vector to provide an alternate send port vector upon a condition that a routing status is route rejected; and, using said alternate send port vector to select a first unallocated output port from said alternate send port vector to provide said selected output port.

Claim 45

The improvement of claim 34 further characterized by: means for selecting a new output port from said send port vector upon said condition that a path rejection packet is received on said corresponding input port paired with said first output port; and, means for sending said scout packet out said new output port.

Claim 46

The improvement of claim 28 further characterized by: means for starting a transmission from said sender node to said target node over a path established a send channel at said sender node to a receive channel at said target node, upon a condition that a path acknowledge packet is received at said sender node on said corresponding input port paired with said first output port.

Claim 47

In a network of interconnected nodes; each node in said network being assigned a unique identification (ID); a sender node originating an address packet having a target node address of a target node; each node in said network including comparing means for comparing said target node address with a unique identification (ID) of said node; a method comprising steps of: A. creating a first condition provided that said ID is not equal to said target node address, indicating that a node is an intermediate node and, alternatively, a second condition provided that said ID is equal to said target node address, indicating that a node is said target node; B. receiving, at one input port of a particular node, said address packet transmitted from of a previous node of said interconnected nodes; C. allocating, upon occurrence of said first condition indicating that said particular node is an intermediate node, to said one input port, one of said output ports of said particular node, but excluding an output port paired with an input port over which said address packet is received, said particular node establishing a path to a next node upon occurrence of said first condition at said particular node, resulting in an established path from said sender node through said particular node; and, D. sending a path command packet from said particular node back to said sender node out of a particular node output port paired with a particular node input port over which said address packet is received.

Claim 48

In a network of interconnected nodes; each node in said network being assigned a unique identification (ID); a sender node originating an address packet having a target node address of a target node; each node in said network including comparing means for comparing said target node address with a unique identification (ID) of said node; a method comprising steps of: A. creating a first condition provided that said ID is not equal to said target node address, indicating that a node is an intermediate node and, alternatively, a second condition provided that said ID is equal to said target node address, indicating that a node is said target node; B. receiving, at one input port of a particular node, said address packet transmitted from of a previous node of said interconnected nodes; C. allocating, upon occurrence of said first condition indicating that said particular node is an intermediate node, to said one input port, one of said output ports of said particular node, but excluding an output port paired with an input port over which said address packet is received, said particular node establishing a path to a next node upon occurrence of said first condition at said particular node, resulting in an established path from said sender node through said particular node; and, D. sending a path command packet from said particular node back to said sender node out of a particular node output port paired with a particular node input port over which said address packet is received.

Claim 49

The method of claim 38 further comprising steps of: E. encoding said path command packet to return path rejection status to a previous node, indicating that a path is not established at said particular node, or path found status to said sender node, indicating that a path is established to said target node through said particular node.

Claim 50

The method of claim 38 further comprising steps of: E. sending, upon occurrence of said second condition indicating that said particular node is a target node, a path command packet from said target node back to said sender node out of a target node output port paired with a target node input port over which said address packet was received over a target node output port paired with a target node input; F. encoding said path command packet to return path found status to said sender node, indicating that a path is established to said target node through said intermediate node; and, G. sending from each intermediate node in an established path said command message to a previous node out of an output port paired with an input port over which said message packet was received.

Claim 51

The method of claim 38 further comprising steps of: E. providing a port vector; F. selecting a first unallocated output port from said port vector upon occurrence of said first condition; and, G. forwarding means for forwarding said address packet to said next node over said first unallocated output port.

Claim 52

The method of claim 41 further comprising steps of: H. sequentially selecting unallocated output ports from said port vector upon occurrence of said first condition; and, I. sending said path command packet encoded to return path rejection status to a previous node over an output port paired with said input port on which said address packet was received, upon a condition that the step of sequentially selecting unallocated output ports from said port vector results in no path being established to said next node.

Claim 53

The method of claim 41 further comprising steps of: H. providing a fold enable vector indicating which of said plurality of output ports can be folded resulting in a folding partner for a chosen output port, said folding partner being an output port through which a message may be routed; and, I. using said folding partner as potential routing candidate upon a condition that said chosen output port is not available for routing but said folding partner is available.

Claim 54

The method of claim 40 further comprising steps of: H. sending an end to end acknowledge command packet out of said target node output port paired with said target node input port on which a message packet is received, upon a condition that a message transmission has completed.

Claim 55

The method of claim 44 further comprising steps of: I. disconnecting an intermediate node output port from an intermediate node input port paired with said intermediate node output port, in response to said end to end acknowledge message.

Claim 56

The method of claim 38 further comprising steps of: E. providing a plurality of send channels at said sender node; each of said send channels having associated with it a send port vector; said send port vector indicating selected output ports of said sender node through which routing is to be attempted; F. sending a scout packet out of a first output port of said selected output ports of said sender node, and thereby delivered to an intermediate node, said intermediate node being a next node in a potential path to said target node; G. locking a path from said send channel to said first of said selected output ports of said sender node, so that said output port is reserved for a pending transmission; and, H. unlocking said path from said send channel to said first output port upon a condition that a path rejection packet is subsequently received on a corresponding input port paired with said first output port.

Claim 57

The method of claim 46 further comprising steps of: I. inverting said send port vector to provide an alternate send port vector upon a condition that a routing status is route rejected; and, J. using said alternate send port vector to select a first unallocated output port from said alternate send port vector to provide said selected output port.

Claim 58

The method of claim 46 further comprising steps of: I. selecting a new output port from said send port vector upon said condition that a path rejection packet is received on said corresponding input port paired with said first output port; and, J. sending said scout packet out said new output port.

Claim 59

The method of claim 40 further comprising steps of: H. starting a transmission from said sender node to said target node over a path established a send channel at said sender node to a receive channel at said target node, upon a condition that a path acknowledge packet is received at said sender node on said corresponding input port paired with said first output port.