Patent ID: 7706275

Claim:
A method for inter-nodal packet routing in a parallel computer system, said parallel computer system comprising a plurality of nodes arranged in a regular lattice 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 method comprising the steps of: generating a plurality of packets for transmission by said network, each said packet to be transmitted from a respective source to a respective destination node, 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 of a plurality of said nodes of said parallel computer system automatically routing each packet of said plurality of packets from its respective source node to its respective destination node along said node-to-node communications links of said network using an automated routing strategy based on the arrangement of said regular lattice network; identifying a subset of said plurality of packets to be routed along a first path from a first node to a second node of said parallel computer system, 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 from said first node to said second node 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 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 automatically routing each packet of said subset of packets along its respective path as assigned by said assigning step, each of any intermediate nodes in each respective path using said automated routing strategy to automatically route each respective packet to a respective next node along its respective path.