Flexible routing tables for a high-radix router

A multiprocessor computer system interconnect network router comprising routing logic and a plurality of output ports, the router operable to:

• receive a packet, wherein the packet includes a plurality of fields;
• examine the packet to determine if the packet can be routed adaptively;
• if the packet can be routed adaptively, route the packet adaptively, wherein routing adaptively includes:
• selecting a column;
• computing a column mask from mask bits from a plurality of entries in a routing table, the mask bits identifying a subtree of the network in which the destination node resides;
• routing the packet to the selected column;
• and
• selecting an output port as a function of the column mask;
• if the packet is not routed adaptively, route the packet deterministically, wherein routing deterministically includes:
• accessing a routing table to obtain an output port;
• and
• routing the packet to the output port from the routing table.

A multiprocessor computer system comprising a plurality of nodes, each of the plurality of nodes comprising a router, the router comprising routing logic and a plurality of output ports, the router operable to:

• receive a packet, wherein the packet includes a plurality of fields;
• examine the packet to determine if the packet can be routed adaptively;
• if the packet can be routed adaptively, route the packet adaptively, wherein routing adaptively includes:
• selecting a column;
• computing a column mask from mask bits from a plurality of entries in a routing table, the mask bits identifying a subtree of the network in which the destination node resides;
• routing the packet to the selected column;
• and
• selecting an output port as a function of the column mask;
• if the packet is not routed adaptively, route the packet deterministically, wherein routing deterministically includes:
• accessing a routing table to obtain an output port;
• and
• routing the packet to the output port from the routing table.

In a system having a N output ports, wherein N is an integer greater than one, a method of distributing packets across the plurality of output ports, comprising:

• receiving a packet in a processor interconnect network node, wherein the packet includes a plurality of fields;
• examining the packet to determine if the packet can be routed adaptively;
• if the packet can be routed adaptively, routing adaptively, wherein routing adaptively includes:
• selecting a column;
• computing a column mask from mask bits from a plurality of entries in a routing table, the mask bits identifying a subtree of the network in which the destination node resides;
• routing the packet to the selected column;
• and
• selecting an output port as a function of the column mask, wherein selecting is a function of space available in a row buffer for each column;
• if the packet is not routed adaptively can be routed deterministically, routing the packet deterministically, wherein routing deterministically includes:
• accessing a routing table to obtain an output port, wherein accessing includes computing a hash function and selecting output ports based on an output of the hash function;
• and
• routing the packet to the output port obtained from the routing table.

A nontransitory computer readable medium having instructions to cause a computer to implement a method of distributing packets across a plurality of output ports, the method comprising:

• receiving a packet in a processor interconnect network node, wherein the packet includes a plurality of fields;
• examining the packet to determine if the packet can be routed adaptively;
• if the packet can be routed adaptively, routing adaptively, wherein routing adaptively includes:
• selecting a column;
• computing a column mask from mask bits from a plurality of entries in a routing table, the mask bits identifying a subtree of the network in which the destination node resides;
• routing the packet to the selected column;
• and
• selecting an output port as a function of the column mask, wherein selecting is a function of space available in a row buffer for each column;
• if the packet is not routed adaptively can be routed deterministically, routing the packet deterministically, wherein routing deterministically includes:
• accessing a routing table to obtain an output port, wherein accessing includes computing a hash function and selecting output ports based on an output of the hash function;
• and
• routing the packet to the output port obtained from the routing table.