Flexible routing tables for a high-radix router

1. A multiprocessor computer system interconnect network node 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.

2. The multiprocessor computer system interconnect network node of claim 1 , wherein the router comprises a high-radix router.

3. The multiprocessor computer system interconnect network node of claim 1 , wherein the routing table is adapted to avoid faults in the subtree.

4. The multiprocessor computer system interconnect network node of claim 1 , wherein the multiprocessor computer system interconnect network comprises a folded close network or a fat tree network.

5. The multiprocessor computer system interconnect network node of claim 1 , wherein the router further comprises an array of router tiles.

6. The multiprocessor computer system interconnect network node of claim 5 , wherein each router tile in the array of router tiles comprises one input and one output port, and is coupled to other output tiles that are in the same row or column.

7. 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.

8. The multiprocessor computer system interconnect router of claim 7 , wherein the router comprises a high-radix router.

9. The multiprocessor computer system interconnect network router of claim 7 , wherein the multiprocessor computer system interconnect network comprises a folded close network or a fat tree network.

10. The multiprocessor computer system interconnect network router of claim 7 , wherein the router further comprises an array of router tiles.

11. The multiprocessor computer system interconnect network router of claim 10 , wherein each router tile in the array of router tiles comprises one input and one output port, and is coupled to other output tiles that are in the same row or column.

12. 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.

13. The multiprocessor computer system of claim 12 , wherein the router further comprises an array of router tiles.

14. The multiprocessor computer system of claim 12 , wherein the router comprises a high-radix router.

15. The multiprocessor computer system of claim 12 , wherein each node further comprises one or more processors.

16. The multiprocessor computer system of claim 12 , wherein the multiprocessor computer system interconnect network comprises a folded close network or a fat tree network.

17. The multiprocessor computer system of claim 13 , wherein each router tile in the array of router tiles comprises one input and one output port, and is coupled to other output tiles that are in the same row or column.

18. 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.

19. The method of claim 18 , wherein the hash function is an XOR of input port and destination processor.

20. The method of claim 18 , wherein the hash function changes as a function of network level.

21. The method of claim 18 , wherein packet destination is associatively checked against routing table entries.

22. 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.