Method and apparatus for routing data in an inter-nodal communications lattice of a massively parallel computer system by employing bandwidth shells at areas of overutilization

A computer 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, said program product comprising:

• a plurality of computer executable instructions recorded on signal-bearing media, wherein said instructions, when executed by a first node of said computer system, cause the first node to perform the steps of:
• identifying a subset of a plurality of packets for transmission by said network to be routed along a first path between said first node and a second node of said parallel computer system in accordance with a default routing strategy, each packet of said plurality of packets to be transmitted from a respective source to a respective destination node, said first path comprising at least one said link, said subset comprising multiple said packets;
• detecting an overutilization condition of said first path;
• identifying at least one alternative path for use by packets of said subset of packets, each said at least one alternative path being different from said first path and from each other said alternative path;
• responsive to detecting said overutilization condition of said first path, assigning each packet of said subset of packets to a respective path of a plurality of paths, said plurality of paths including said at least one alternative path, wherein at least one respective packet of said subset of packets is assigned to each path of said plurality of paths;
• and
• causing each packet of said subset of packets to be automatically routed along its respective path as assigned by said assigning step.

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 network for inter-nodal communications of application data;
• a respective routing mechanism in each node of said plurality of nodes, each said routing mechanism automatically routing each packet of a respective plurality of packets from a respective source node to a respective destination node along said node-to-node communications links of said network;
• wherein each routing mechanism includes a distribution function which, responsive to detecting an overutilization condition in a first path of said network running between a pair of nodes of said parallel computer system, allocates packets of a subset of packets to be routed between the pair of nodes among a plurality of different paths in said network running between the pair of nodes, each said packet being allocated to a respective one of said plurality of different paths, each said path being allocated at least one said packet;
• and
• wherein each routing mechanism causes each said packet to be automatically routed along the respective path to which it is allocated by said distribution function.