Collective network routing

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation of co-pending application Ser. No. 11/100,207, filed Apr. 6, 2005, for “Collective Network Routing”, the disclosure of which is herein incorporated by reference in its entirety, which claims the benefit of Provisional Application No. 60/625,026, for “Collective Network Routing,” filed Nov. 4, 2004.

GOVERNMENT CONTRACT

0002This invention was made with Government support under Subcontract B517552 under prime contract W-7405-ENG-48 awarded by The Department of Energy. The Government has certain rights in this invention.

BACKGROUND OF THE INVENTION

00031. Field of the Invention

0004This invention generally relates to the field of high-speed digital data processing systems; and more specifically, the invention relates to methods and systems for routing messages in computer systems.

00052. Background Art

0006Massively parallel computer systems comprise a large number of data processing elements, which are typically connected using a network. Each node connected to the said network typically is comprised of a network interface and the local data processing elements. The network interface receives data from the network, which is addressed to this particular node, and the network interface also injects the local results into the network. Data is typically routed through the network in packets; and the packets are routed by a plurality of routers, typically one router per node. The network, specifically the plurality of the network routers, ensures the movement of the injected packets between the connected nodes towards the desired packet destinations.

0007Typically, the node, which produces a data packet, specifies the desire destination of that packet by specifically providing a unique address of the said packet destination. Upon injection of such an attributed packet, the plurality of network routers make local routing decisions to incrementally reduce the distance of the packet to its destination by forwarding the packet to a connected node closer to the specified destination. This universal point-to-point style of communication is state of the art and used by most of today's implemented computer networks. The drawback of using addresses as part of the packet attributes is the limitation of the network scalability to the maximal number of addresses presentable with the bits dedicated to the packet address.

0008Furthermore, additional auxiliary networks have been used to implement special support for collective communication such as global broadcasts to all connected nodes (CM-5). These networks have typically the topology of a tree or a fat tree, since the tree topology provides the minimal distance between any two connected nodes and, thus, minimal communication latency.

0009There are several constraints imposed to particular nodes by the tree topology. For example, the dedicated root node splits the network into two domains, left and right. Traffic from one domain targeted to the other domain must go through the root node under any circumstances. A broken root-node, router and/or links, will render the entire network useless since no packets can be routed from the left to the right partition. In addition, leaf nodes in a tree network have only one connection to the network. If this link is broken, the entire network is also not functional anymore.

SUMMARY OF THE INVENTION

0010An object of this invention is to provide an improved method and system for routing data packets through multi-node computer networks.

0011Another object of the invention is to avoid using addresses to route data packets through computer networks by classifying the packets into a limited set of classes for which the packet behavior can be specified in detail on a per-node basis.

0012A further object of the present invention is to allow the nodes of a multi-node computer network to utilize an arbitrary number of links between nodes while still assuring deterministic packet routes through the network and thus allow for well-defined, well-behaving collective operations.

0013Another object of this invention is to route data packets through a multi-node computer network by employing a general address-less static routing method applicable to arbitrary network topologies, which allows to embed a plurality of virtual logical networks in one physical network.

0014A further object of the invention is to enable a multi-node computer system to define and process collective packet operations such as global packet reductions (global maximum or similar) on networks of arbitrary size and shape.

0015These and other objectives are attained with a method of and a system for routing data packets in a computer network having a multitude of nodes and a multitude of links connecting the nodes together, and wherein each data packet includes a class identifier. The method comprises the steps of, each node, for each of a defined set of data packets, checking or looking at the data packet to identify the class of the data packet, and routing the data packet from the node based on the identified class of the data packet.

0016The preferred embodiment of the invention, described in detail below, provides a method and apparatus for identifying collectives of packets among a plurality of packets on a network in a system of connected data processing elements which are connected using an arbitrary network topology. The preferred method yields local routing decisions as well as decisions whether collective packet reduction operations or other operations should be applied to the identified packet collective. The local result of the said collective packet operation is routed to the collective of connected nodes and/or locally received. The preferred embodiment of the invention allows the specification of packet data reductions among an arbitrary set of nodes, connected using an arbitrary interconnection topology. In addition to packet reductions, the invention also can be utilized to multi-/broadcast packets among one or more configurable sets of nodes in a network.

0017The preferred embodiment of the invention provides a number of important advantages. For instance, the invention avoids using addresses—and thus avoids their associated limitations—by classifying packets into a limited set of classes for which the packet behavior can be specified in detail on a per-node basis using, for example, local class descriptor tables. Each class may have a virtually unlimited set of nodes participating.

0018In addition, this preferred embodiment allows nodes to utilize an arbitrary number of links between nodes while still assuring deterministic packet routes through the network and, thus, allows for well-defined, well-behaving collective operations. Since the effective topology is defined per packet class, the topology may be modified dynamically, for example to compensate for broken links or to extend or shrink the affected network partition. Changes of the logical network topology may also be transparent to the application.

0019Further, the preferred embodiment of the invention disclosed herein solves several problems of auxiliary networks by employing a general address-less static routing method applicable to arbitrary network topologies, which allows to embed a plurality of virtual logical networks in one physical network; for example tree networks with redundant links or irregular networks. The absence of source or target addresses allows the application of this invention to networks of any size and shape.

0020In addition, the invention, in its preferred embodiment, allows to define and process collective packet operations such as global packet reductions (global sum or global maximum or similar) on networks of arbitrary size and shape.

0021Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description, given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0022<figref idref="DRAWINGS">FIG. 1</figref> shows the general architecture of a network comprising a plurality of nodes connected by an interconnection network of the degree n.

0023<figref idref="DRAWINGS">FIG. 2</figref> describes the general structure of a single node of the network of <figref idref="DRAWINGS">FIG. 1</figref>.

0024<figref idref="DRAWINGS">FIG. 3</figref> depicts a sparsely connected network topology, suitable for the invention described herein.

0025<figref idref="DRAWINGS">FIG. 4</figref> shows a route descriptor table comprising n route descriptors describing the packet behavior for a node with four network links plus one local client.

0026<figref idref="DRAWINGS">FIG. 5</figref> shows one exemplary route descriptor configuration for class <b>0</b> of the two nodes A and B of the network shown in <figref idref="DRAWINGS">FIG. 3</figref>.

0027<figref idref="DRAWINGS">FIG. 6</figref> illustrates a data packet that may be used in the practice of this invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

0028The herein described invention solves the problem to describe packet routes of single packets and to define packet collectives for collective packet operations among a plurality of nodes connected by a network with arbitrary topology of degree n as shown at <b>10</b> in <figref idref="DRAWINGS">FIG. 1</figref>. Each node <b>12</b> itself comprises the network interface and the local client, which contains the processing elements for data processing of the received data and for injecting results of the local computation into the network.

0029The general structure of the network interface with four links, for a network of degree four, is also shown in <figref idref="DRAWINGS">FIG. 2</figref>. Each network link comprises a network receiver <b>14</b>, which receives packets from the network link and presents the packets to the arbiter <b>16</b>, which routes the packets, via sender <b>20</b>, towards the targets specified using the collective class routing method herein described. The network interface also includes a local client CPU and memory, represented at <b>22</b>.

0030In particular, the arbiter <b>16</b> first evaluates the packet header information, shown at <b>24</b> in <figref idref="DRAWINGS">FIG. 6</figref>, such as the class <b>26</b> of the packet and the specified packet opcode <b>30</b>. Using the class information, the arbiter <b>16</b> retrieves the appropriate route descriptor from the route descriptor table, shown at <b>32</b> in <figref idref="DRAWINGS">FIG. 4</figref>. The route descriptor table can be read and written and contains the specific description <b>34</b> of the packet behavior for all available packet classes for this particular node. The route descriptor table may be different for each node in the network, depending on the position of the node in the logical network structure and on the availability of physical connections to neighboring nodes.

0031The route descriptor table <b>32</b> may be initialized immediately after booting the local client. During runtime, packet classes may be allocated and initialized to implement a specific communication pattern such as packet broadcast or a packet reduction. From that time on, packets, injected with the appropriate class-tag, follow the configured packet routes according to the route descriptors deposited in the nodes along the packet path through the network. For collective packet operations such as reductions, the route descriptor <b>34</b> also indicates which packets are members of the collective. The router <b>36</b> will wait until the packet collective is complete and it will then forward the packet collective while applying the specified packet operation.

0032The collective is considered to be complete if all channels which are identified as source-channels have collective packets available. Whether a packet is considered a collective packet or not is specified on a per-packet basis using the packet opcode field <b>30</b> of the packet header <b>22</b>, shown in <figref idref="DRAWINGS">FIG. 6</figref>.

0033For the configuration shown in <figref idref="DRAWINGS">FIG. 5</figref>, for example, Node A considers a packet collective as complete if the receivers of channel <b>2</b>, channel <b>1</b>, and the local client signal the availability of a packet, which is marked with an opcode such as ADD or MAX, which in turn indicates a collective operation. In that case, the router applies the specified operation to the packet collective and routes the result of that operation to the sender of channel <b>0</b>.

0034Packets, not marked as operands of collective packet operations, are simply routed to the target channels without waiting for the other sources. In general the rule for forwarding packets is: if the packet enters the node from a channel which is marked as a source channel for the given packet class, then the packet or the packet collective is routed to the specified target channels of that class. If the channel is not an explicit source channel, then the packet is routed to all the source channels and no collective operation is applied even though the packet opcode may request a collective operation.

0035The apparatus enabling the method of collective class routing, the route descriptor table <b>32</b>, is an array of registers, which can be read and written, comprising at least two bits per potential packet route (channel). One bit indicates whether the particular channel is a dedicated source channel for that packet class. The other bit is set for all channels which are dedicated targets for packets of the given class. Thus the descriptor describes the packet routes and the packet collective for collective operations.

0036With reference to <figref idref="DRAWINGS">FIG. 6</figref>, each packet header comprises the packet class <b>26</b> and the packet opcode <b>30</b>. The class is used to identify the appropriate packet routes, and the opcode is used to decide whether collective operations should be applied. <figref idref="DRAWINGS">FIG. 5</figref> shows an example of a particular configuration for class <b>0</b> of the two nodes A and B of the network shown in <figref idref="DRAWINGS">FIG. 3</figref>. It should be noted that a number of configurations may coexist in parallel, each using a different class with different sources and targets specified.

0037While it is apparent that the invention herein disclosed is well calculated to fulfill the objects stated above, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art, and it is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention.