Method and Apparatus for Routing Data in an Inter-Nodal Communications Lattice of a Massively Parallel Computer System by Dynamically Adjusting Local Routing Strategies

• US 20080084889A1
• Filed: 10/06/2006
• Published: 04/10/2008
• Est. Priority Date: 10/06/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Peters, Amanda, Musselman, Roy Glenn, Wallenfelt, Brian Paul, Archer, Charles Jens, Swartz, Brent Allen, Pinnow, Kurt Walter
• Granted Patent: US 7,680,048 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A massively parallel computer system contains an inter-nodal communications network of node-to-node links. Each node implements a respective routing strategy for routing data through the network, the routing strategies not necessarily being the same in every node. The routing strategies implemented in the nodes are dynamically adjusted during application execution to shift network workload as required. Preferably, adjustment of routing policies in selective nodes is performed at synchronization points. The network may be dynamically monitored, and routing strategies adjusted according to detected network conditions.

Claims

1. A computer-implemented method for inter-nodal packet routing in a parallel computer system, said parallel computer system comprising a plurality of nodes arranged in a network of node-to-node communications links for inter-nodal communications, each node comprising at least one processor for executing a respective application sub-process of at least one application and a nodal memory, said method comprising the steps of:

at each of a plurality of said nodes of said parallel computer system, automatically routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy, wherein at least some of said packets must traverse one or more respective intermediate nodes between the respective source node and the respective destination node;

altering said respective local automated routing strategy of at least some nodes of said plurality of nodes during execution of said at least one application;

responsive to said altering step, at each of said at least some nodes for which said respective local automated routing strategy was altered, thereafter routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy as altered by said altering step.

2. The method for inter-nodal packet routing of claim 1, wherein said altering step comprises the steps of:

periodically obtaining network usage data with respect to usage of said network of node-to-node communications links;

analyzing most recently obtained said network usage data to identify a respective optimum local automated routing strategy for each node of said at least some nodes; and

communicating results of said analyzing step to each node of said at least some of nodes for implementation as an altered routing strategy.

3. The method for inter-nodal packet routing of claim 2, wherein said network usage data comprises a respective N-bit value corresponding to each of a plurality of said node-to-node communications links of said network.

4. The method for inter-nodal packet routing of claim 2, wherein said network usage data comprises, with respect to each of a plurality of nodes, data with respect to a plurality of packets originating in the respective node.

5. The method for inter-nodal packet routing of claim 1, wherein each node of said at least some nodes implements the respective local automated routing strategy as altered by said altering step at a common synchronization point.

6. The method for inter-nodal packet routing of claim 1, wherein said steps of altering said respective local automated routing strategy and thereafter routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy as altered by said altering step are performed periodically at respective synchronization points.

7. The method for inter-nodal packet routing of claim 1,

wherein said step of at each of a plurality of said nodes of said parallel computer system, automatically routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy, and said step of responsive to said altering step, at each of said at least some nodes for which said respective local automated routing strategy was altered, thereafter routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy as altered by said altering step, comprise:

(a) selecting a respective routing policy for each of a plurality of packets at a respective source node of each packet using the respective local automated routing strategy, (b) transmitting respective routing policy data with each packet; and

(c) routing each packet in each intermediate node between the respective source node and the respective destination node of the packet according to the respective routing policy by the respective source node.

8. The method for inter-nodal packet routing of claim 1, wherein each said local automated routing strategy is constrained to route packets along a path containing a minimal number of links of said network.

9. The method for inter-nodal packet routing of claim 1, wherein said each said local automated routing strategy determines a respective routing policy for each of a plurality of messages, each message containing one or more said packets, wherein each packet within a message is assigned the respective routing policy identified for the message in which it is contained.

10. The method for inter-nodal packet routing of claim 1,

wherein said plurality of nodes are arranged in a logical N-dimensional lattice, each said communication link of said network coupling a respective first node with a respective second node, the respective first and second nodes having identical coordinates in all except a respective Mth of the N dimensions of said N-dimensional lattice, the respective first and second nodes being logical neighbors in the respective Mth coordinate dimension;

and

wherein each said local automated routing strategy is a member of a set of a plurality of pre-defined local automated routing strategies, each member of said set comprising a fixed preferential order of coordinate dimensions in said logical N-dimensional lattice for all packets originating in the node implementing the respective local automated routing strategy, the preferential order specifying an order of coordinate dimensions in which each packet is to be preferentially transmitted.

11. A parallel computer system, comprising:

a plurality of nodes, each node having at least one processor for executing a respective application sub-process and a memory accessible by the at least one processor;

a plurality of node-to-node communication links forming a process network for inter-nodal communications of application data;

a respective routing mechanism in each node of said plurality of nodes for routing packets along said process network, each said routing mechanism

a respective routing mechanism in each node of said plurality of nodes, each said routing mechanism automatically routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective automated local routing strategy, wherein at least some of said packets must traverse one or more respective intermediate nodes between the respective source node and the respective destination node,

wherein, in at least some said nodes, the respective routing mechanism alters the respective automated local routing strategy of the node during execution of a distributed application in the at least some nodes, and thereafter routes each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy as altered.

12. The parallel computer system of claim 11, wherein each said routing mechanism of said at least some nodes alters its respective automated local routing strategy at a respective synchronization point of an application being executed by said at least some nodes.

13. The parallel computer system of claim 11, further comprising:

a monitoring mechanism for collecting network usage data with respect to said process network, analyzing said network usage data, and determining alterations to a plurality of said automated local routing strategies in respective nodes of said system.

14. The parallel computer system of claim 12, wherein said monitoring mechanism comprises a network separate from said process network for collecting said network usage data from a plurality of nodes of said computer system.

15. The parallel computer system of claim 11, wherein said plurality of nodes are arranged in a logical N-dimensional lattice, each said communication link of said process network coupling a respective first node with a respective second node, the respective first and second nodes having identical coordinates in all except a respective Mth of the N dimensions of said N-dimensional lattice, the respective first and second nodes being logical neighbors in the respective Mth coordinate dimension.

16. The parallel computer system of claim 15, wherein each said local automated routing strategy is a member of a set of a plurality of pre-defined local automated routing strategies, each member of said set comprising a fixed preferential order of coordinate dimensions in said logical N-dimensional lattice for all packets originating in the node implementing the respective local automated routing strategy, the preferential order specifying an order of coordinate dimensions in which each packet is to be preferentially transmitted

17. A program product for inter-nodal packet routing in a parallel computer system, said parallel computer system comprising a plurality of nodes arranged in a network of node-to-node communications links for inter-nodal communications, each node comprising at least one processor for executing a respective application sub-process and a nodal memory, the program product comprising:

a plurality of computer executable instructions recorded on signal-bearing media, wherein said instructions, when executed by at least one node of said computer system, cause the at least one node to perform the steps of;

at each node of said at least one node, automatically routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy, wherein at least some of said packets must traverse one or more respective intermediate nodes between the respective source node and the respective destination node;

at each node of said at least one node, altering said respective local automated routing strategy during execution of said at least one application;

responsive to said altering step, at each node of said at least one node, thereafter routing each of a plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network using a respective local automated routing strategy as altered by said altering step.

18. The program product of claim 17, wherein said altering step is implemented in said at least one node at a synchronization point of said at least one application.

19. The program product of claim 17, wherein said altering step is performed responsive to receiving a command from a source external to the node altering its respective local automated routing strategy.

20. The program product of claim 20, wherein each said local automated routing strategy is constrained to route packets along a path containing a minimal number of links of said network.