Systems and methods for routing packets in multiprocessor computer systems

1. In a multiprocessor computer system having a plurality of processing nodes and physical communication links interconnecting the processing nodes in a predefined topology, wherein each processing node includes a processor, a router and a local memory, wherein the physical communication links connect a router in one processing node to a router in another processing node, and wherein each router consults a routing table resident within its associated processing node when deciding where to route a message from one processing node to an adjacent processing node, a method of building a routing table, comprising:

a) determining all single hops for each processing node;

b) querying each adjacent node for its single hop routes;

c) determining if all nodes can be reached;

d) if all nodes cannot be reached, setting x=2;

e) querying each adjacent node for its “x” hop routes;

f) eliminating all routes to a particular node that are longer than existing routes from the node where the routing table will reside to that particular node;

g) eliminating all routes that introduce a cyclic dependency;

h) choosing a preferred route to the particular node among the routes that have not been eliminated by either f or g;

i) determining if all nodes can now be reached;

j) if all nodes cannot be reached, setting x=x+1 and repeating e through j; and

k) if all nodes can be reached, building the routing table.

2. The method of claim 1 , wherein querying each adjacent node for its “x” hop routes includes obtaining dependency information for each route.

3. The method of claim 2 , wherein the dependency information is stored as a bit vector.

4. The method of claim 1 , wherein choosing a preferred route to the particular node includes comparing routes to the particular node to a route obtained by applying a routing algorithm and selecting the route that is closest to the route obtained by applying the routing algorithm.

5. The method of claim 1 , wherein querying each adjacent node includes reading hop routes from the local memory of the adjacent node.

6. A multiprocessor computer system comprising:

a plurality of processing element nodes, each processing element node having a processor, a router and a local memory; and

physical communication links interconnecting the processing element nodes in a predefined topology, wherein the physical communication links connect a router in one processing element node to a router in another processing element node;

wherein each router includes:

a plurality of ports, wherein the ports receive and send messages;

a routing table associated with each port, wherein the routing table includes entries having directions for routing a message along a given route; and

a route processor, wherein the route processor determines the directions for routing by:

a) determining all single hops for each processing node;

b) querying each adjacent node for its single hop routes;

c) determining if all nodes can be reached;

d) if all nodes cannot be reached, setting x=2;

e) querying each adjacent node for its “x” hop routes;

f) eliminating all routes to a particular node that are longer than existing routes from the node where the routing table will reside to that particular node;

g) eliminating all routes that introduce a cyclic dependency;

h) choosing a preferred route to the particular node among the routes that have not been eliminated by either f or g;

i) determining if all nodes can now be reached;

j) if all nodes cannot be reached, setting x=x+1 and repeating e through j; and

k) if all nodes can be reached, building the routing table.

7. The system of claim 6 , wherein querying each adjacent node for its “x” hop routes includes obtaining dependency information for each route.

8. The system of claim 7 , wherein the dependency information is stored as a bit vector.

9. The system of claim 6 , wherein choosing a preferred route to the particular node includes comparing routes to the particular node to a route obtained by applying a routing algorithm and selecting the route that is closest to the route obtained by applying the routing algorithm.

10. The system of claim 6 , wherein each router is capable of accessing the local memory on adjacent nodes.

11. A device, comprising:

a plurality of ports including a first port and a second port, wherein the ports receive and send messages;

a routing table associated with each port, wherein the routing table includes entries having directions for routing a message along a given route; and

a route processor, wherein the route processor determines the directions for routing by:

a) determining all single hops for each of a plurality of processing nodes including a first node and a second node;

b) querying each adjacent node for its single hop routes;

c) determining if all nodes can be reached;

d) if all nodes cannot be reached, setting x=2;

e) querying each adjacent node for its “x” hop routes;

f) eliminating all routes to a particular node that are longer than existing routes from the node where the first routing table will reside to that particular node;

g) eliminating all routes that introduce a cyclic dependency;

h) choosing a preferred route to the particular node among the routes that have not been eliminated by either f or g;

i) determining if all nodes can now be reached;

j) if all nodes cannot be reached, setting x=x+1 and repeating e through j; and

k) if all nodes can be reached, building the first routing table.

12. The device of claim 11 , wherein querying each adjacent node for its “x” hop routes includes obtaining dependency information for each route.

13. The device of claim 12 , wherein the dependency information is stored as a bit vector.

14. The device of claim 11 , wherein choosing a preferred route to the particular node includes comparing routes to the particular node to a route obtained by applying a routing algorithm and selecting the route that is closest to the route obtained by applying the routing algorithm.

15. The device of claim 11 , wherein the routing table includes a different port routing table for each of the plurality of ports.

16. In a computer having a plurality of ports and a routing table associated with each port, wherein the routing table includes entries having directions for routing a message along a given route, a computer-readable medium including instructions that, when executed by a computer, cause the computer to determine the directions for routing by:

a) determining all single hops from the computer to its adjacent processing nodes;

b) querying each adjacent processing node for its single hop routes;

c) determining if all nodes can be reached;

d) if all nodes cannot be reached, setting x=2;

e) querying each adjacent processing node for its “x” hop routes;

f) eliminating all routes to a particular node that are longer than existing routes from the node where the first routing table will reside to that particular node;

g) eliminating all routes that introduce a cyclic dependency;

h) choosing a preferred route to the particular node among the routes that have not been eliminated by either f or g;

i) determining if all nodes can now be reached;

j) if all nodes cannot be reached, setting x=x+1 and repeating e through j; and

k) if all nodes can be reached, building the routing table.

17. The medium of claim 16 , wherein querying each adjacent node for its “x” hop routes includes obtaining dependency information for each route.

18. The medium of claim 17 , wherein the dependency information is stored as a bit vector.

19. The medium of claim 16 , wherein choosing a preferred route to the particular node includes comparing routes to the particular node to a route obtained by applying a routing algorithm and selecting the route that is closest to the route obtained by applying the routing algorithm.

20. The medium of claim 16 , wherein the routing table includes a different port routing table for each of the plurality of ports.