Class network routing

• US 20040081155A1
• Filed: 08/22/2003
• Published: 04/29/2004
• Est. Priority Date: 02/24/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Dong, Gara, Alan G., Heidelberger, Philip, Giampapa, Mark E., Blumrich, Matthias A., Coteus, Paul W., Takken, Todd E., Vranas, Pavlos M., Steinmacher-Burow, Burkhard D., Bhanot, Gyan V
• Granted Patent: US 7,587,516 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: F04D 25/166 using fans
• CPC Class Codes: F04D 27/004 by varying driving speed
• CPC Class Codes: F24F 11/77 by controlling the speed of ventilators
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G09G 5/008 Clock recovery
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 7/0338 the correction of the phase error being performed by a feed forward loop
• CPC Class Codes: H05K 7/20836 Thermal management, e.g. server temperature control
• CPC Class Codes: Y02B 30/70 Efficient control or regulation technologies, e.g. for control of refrigerant flow, motor or heating

Abstract

Class network routing is implemented in a network such as a computer network comprising a plurality of parallel compute processors at nodes thereof. Class network routing allows a compute processor to broadcast a message to a range (one or more) of other compute processors in the computer network, such as processors in a column or a row. Normally this type of operation requires a separate message to be sent to each processor. With class network routing pursuant to the invention, a single message is sufficient, which generally reduces the total number of messages in the network as well as the latency to do a broadcast. Class network routing is also applied to dense matrix inversion algorithms on distributed memory parallel supercomputers with hardware class function (multicast) capability. This is achieved by exploiting the fact that the communication patterns of dense matrix inversion can be served by hardware class functions, which results in faster execution times.

Claims

1. A method of class network routing in a network to allow a compute processor in a network of compute processors located at nodes of the network to multicast a message to a plurality of other compute processors in the network comprising:

dividing a message into one or more message packets which pass through the network;

adding a class value to a message packet;

at each switch in the network, using the class value as an index to at least one table whose stored values, or as an input to an algorithm whose generated values, determine actions performed by the switch on the message packet.

2. The method of claim 1, including providing a class value determining a switch action of path-based multidrop message passing for multiphase multicasting of a message packet through the network, to determine if a local node should deposit a copy of the message packet at the local node.

3. The method of claim 2, including:

providing a class-value to implement multidrop message passing;

providing each switch with a table to determine if a copy of the message packet is to be deposited at the local node.

4. The method of claim 1, including providing a class value determining a switch action of multidestination message passing of a message packet to multiple destination nodes in the network.

5. The method of claim 1, wherein a switch duplicates an incoming packet onto multiple outgoing links.

6. The method of claim 5, including providing a class routing table with different values on different incoming links.

7. The method of claim 4, wherein the message packet is multicast to an entire row or surface of the network.

8. The method of claim 1, including:

performing dense matrix inversion algorithms on a network of distributed memory parallel computers with hardware class function multicast capability, wherein the hardware class function multicast capability simultaneously stores into memory a message packet that arrives and immediately sends the message packet to one or more other nodes while that message packet is being stored into memory, such that the communication patterns of the dense matrix inversion algorithms are served by the hardware class function multicast capability to minimize communication delays.

9. The method of claim 1, wherein the network comprises a network of distributed-memory parallel computers;

providing each node of the computer network with one or more processors that operate on local memory;

coordinating the actions of multiple nodes of the computer by using class routing to pass messages between the multiple nodes.

10. The method of claim 9, including:

pairing each node with a switch of the network;

connecting the switches to form a three dimensional torus wherein each switch is linked to six other switches, the links are coupled to a switch in a positive direction and also to a switch in a negative direction in each of the three dimensions;

identifying each;

switch by an x, y, z logical address on the torus, wherein each node has the address of its switch;

including a field value for the logical address in the packet header, to enable the packet to identify a destination node.

11. The method of claim 1, including using a D-phase multicast from an origin node to all nodes of a D-dimensional cube wherein, in a first phase the origin node sends a multidrop message to all other nodes in one of the rows of the sending node, in a second phase each of the recipients of the first phase and the sender of the first phase simultaneously send a multidrop message to all other nodes in a row orthogonal to the row of the first phase, in a third phase each of the recipients of the second phase and the senders of the second phase simultaneously send a multidrop message to all other nodes in a row orthogonal to the rows of the first and second phases, and so on in further phases such that all node of the cube receive the broadcast message after all the phases.

12. The method of claim 1, including providing each switch with a table with associated class values which determine if a copy of a message packet is to be deposited at a destination node.

13. The method of claim 1, for a D-dimensional network, including providing 2{circumflex over ( 

)}D class values for multicast in each of the 2{circumflex over ( 

)}D directions to allow each node in the network to use 2{circumflex over ( 

)}D multicasts to effectively broadcast a packet to all other nodes in the mesh.

14. The method of claim 1, including providing a class value determining a switch action of a unicast of a message packet through the network to a single destination node.

15. The method of claim 1, including providing a class value to enable a node to acquire and store information packets passing through its switch to provide information on the performance of the network.

16. The method of claim 11, including providing class values to determine if a copy of the message packet is to go out on an X link or not, and out on a Y link or not, and out on a Z link or not and so on for the other links of the D dimensions.

17. The method of claim 1, including providing different tables and providing priorities for different tables to enable a switch to decide between conflicting actions indicated by different tables.

18. The method of claim 1, including using a class value as an input to an algorithm for determining a switch action of the switch.

19. The method of claim 1, including using class-based multicasting to create other classes, such that the contents of a table for a particular class value is determined by using another class value.