Patent Description:
Ring-based network topologies, such as multi-dimensional torus and twisted torus networks, are typically used in on-chip and off-chip networks. These network topologies may suffer from deadlock. Deadlock occurs when a chain of packets is waiting on each other to make progress through the network and the chain forms a cycle that prevents any of the packets from progressing. Typical approaches to ensure a deadlock-free network topology include using a dateline or a red-rover algorithm, both of which rely on virtual channels. However, the use of virtual channels may result in reduced performance of the network topology due to imbalanced distributions of the data packets throughout the network. Moreover, the use of a dateline may create long virtual channel dependency chains, which can lead to compounding unfairness and loss of throughput as the number of nodes per dimension increases.

<CIT> discloses an apparatus including a network interface and a processor. The network interface is configured to communicate with a network that includes a plurality of switches interconnected in a Cartesian topology having multiple dimensions. The processor is configured to predefine an order among the dimensions of the Cartesian topology, to search for a preferred route via the network from a source switch to a destination switch.

This technology is directed to routing data packets through a ring-based network without deadlock. The invention is directed to a method of routing data packets within a ring network per claim <NUM> and corresponding ring network claim <NUM>.

Dependent claims describe preferred embodiments of the invention.

A more complete appreciation of the disclosure and many of the attendant advantages thereof will be readily obtained by reference to the following detailed description when considered in connection with the accompanying drawings, wherein:.

The technology described herein is directed to improving the performance of ring-based network topologies while ensuring deadlock-free operation by shortening dependency chains and efficiently load balancing the virtual channel (VC) resources of the network. In this regard, the dependency chains may be shortened by adding an additional dateline such that the two datelines are separated by half the diameter of the ring. Increasing the efficiency of the load balancing between the VC resources may include switching a data packet to a second VC at any time, so long as that data packet will not cross one of the datelines.

In a ring-based network topology, nodes that form the network may be connected via physical links, such as wires, cables, traces, etc. Each physical link may carry data packets on any number of VCs. In this regard, each physical link between a pair of nodes can communicate data packets via one or more VCs. For example, and as illustrated in the ring network <NUM> of <FIG>, each node pair is connected via a physical link. For instance, node0 <NUM> is connected to node1 <NUM> via physical link <NUM>, node1 <NUM> is connected to node2 <NUM> via physical link <NUM>, node2 <NUM> is connected to node3 <NUM> via physical link <NUM>, node3 <NUM> is connected to node4 <NUM> via physical link <NUM>, node4 <NUM> is connected to node5 <NUM> via physical link <NUM>, and node5 <NUM> is connected to node0 <NUM> via physical link <NUM>. Each physical link <NUM>-<NUM> in ring network <NUM> includes two virtual channels VC0 and VC1, as illustrated by callouts <NUM> and <NUM>, which illustrate VC0 (as a solid line) and VC1 (as a dashed line) for connections <NUM> and <NUM>, respectively. For clarity, <FIG> illustrates the VCs only for connections <NUM> and <NUM>, but it should be understood that the other connections, including connections <NUM>, <NUM>, <NUM>, and <NUM> also include virtual channels VC0 and VC1. Although ring network <NUM> includes only six nodes (<NUM>-<NUM>) and two virtual channels (VC0 and VC1) a ring network may include any number of nodes and any number of virtual channels.

Nodes may include any type of computing resource capable of communicating with other computing resources. For instance, nodes may include computers, servers, mobile devices, processors, cores, routers, memory, cards (e.g., accelerator cards), FIFOs, or other such queues, etc. In some instances, nodes may include a collection of computing resources, such as processors with routers, etc..

Selection of the VC on which to transmit a data packet may be static. In static routing, the routes may be predetermined and fixed. Mechanically, the static routes can be stored in tables, such as within RAM memory within the node. The destination of a packet may be used to index a table and lookup the route to the destination.

In ring-based network topologies, dateline routing is used to designate one physical link in each direction of a ring as a dateline. In this regard, the physical links may be bidirectional links, such that both directions in a ring can be treated separately. Queueing structures are typically programmed to transmit each data packet on a first channel. In the event the data packets cross the dateline, the data packets are moved to the second virtual channel until the data packets reach their respective destination nodes.

For example, and as illustrated in ring network <NUM> of <FIG>, which may be compared to ring network <NUM>, a dateline <NUM> is positioned between nodes <NUM> and <NUM>. The ring network <NUM> includes six nodes <NUM>-<NUM>, and physical links between each adjacent node, including physical links <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Each physical link includes two virtual channels VC0 (illustrated as a solid line) and VC1 (illustrated as a dashed line), with the exception of physical link <NUM>, which may be considered a transition link that transfers the data packets between VC0 and VC1. To illustrate the transition from VC0 to VC1, <FIG> illustrates physical link <NUM>, between node5 <NUM> and node0 <NUM>, as a single line, with the line being solid on the left side of dateline <NUM> and dashed on the right side of dateline <NUM>.

As data packets traverse the network <NUM>, a routing algorithm may initially route the data packets on VC0. However, in the event a data packet crosses the dateline <NUM>, the routing algorithm may switch the data packet to VC1 and subsequently route the data packet on VC1 to its destination node. As most data packets reach their respective destination nodes prior to passing the dateline <NUM>, a spiral-like chain of acyclic VC dependencies is created. This chain of acyclic dependencies is sufficient to ensure that ring network <NUM> is deadlock-free. However, the dateline routing creates a chain of VC dependencies longer than the ring network itself.

While no individual packet will travel along the entirety of the chain, created by VC0 and VC1, a sequence of dependent packets can be blocked along the chain. To advance blocked data packets, queuing structures of network <NUM> may implement an arbitration algorithm, such as a locally fair or globally fair arbitration algorithm.

To reduce the length of the dependency chain, a second dateline may be introduced. The two datelines, referred to herein as "dual-datelines," may be separated by half the diameter of the ring network. For example, and as illustrated in ring network <NUM> of <FIG>, which may be compared to ring networks <NUM> and <NUM>, a first dateline <NUM> is positioned after the third node (<NUM>) and the second dateline <NUM> is positioned after node5 <NUM> of the six-node ring network <NUM>. In this regard, the first dateline <NUM> is positioned between node2 <NUM> and node3 <NUM>, and the second dateline <NUM> is positioned between node5 <NUM> and node0 <NUM>. Thus, there are three nodes positioned on each side of the datelines, with nodes <NUM>, <NUM>, and <NUM> being positioned between the second dateline <NUM> and the first dateline <NUM> and nodes <NUM>, <NUM>, and <NUM> being positioned between the first dateline <NUM> and the second dateline <NUM>.

Like ring network <NUM>, ring network <NUM> includes six nodes <NUM>-<NUM>, and physical links between each adjacent node, including physical links <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Each physical link includes two virtual channels VC0 (illustrated as a solid line) and VC1 (illustrated as a dashed line), with the exceptions of transition links <NUM> and <NUM>.

As data packets traverse network <NUM>, the routing algorithm may initially route the data packets on VC0. However, in the event a data packet crosses the first dateline <NUM> or the second dateline <NUM>, the routing algorithm may switch the routing of the data packet to VC1. The routing algorithm may then route the data packet on VC1 to its destination node. A data packet may traverse, at most, two physical links on VC0 before being transitioned to VC1. For example, a data packet may be transmitted from node0 <NUM> to node5 <NUM>. In this example, the data packet may traverse physical links <NUM> and <NUM> on VC0, but then be transitioned to VC1 when crossing the first dateline <NUM> at physical link <NUM>. The data packet may then traverse physical links <NUM> and <NUM> on VC1 before reaching destination node5 <NUM>. In contrast, and referring to <FIG>, a data packet may traverse five physical links before transitioning from VC0 to VC1. In this regard, a data packet may be transmitted on VC0 over the physical links from node0 <NUM> to node5 <NUM>, including physical links <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Although <FIG> illustrates only two datelines in ring network <NUM>-the first dateline <NUM> and the second dateline <NUM>-ring networks may include any number of datelines,.

Better balancing of data packet traffic on the virtual channels may be achieved by routing data packets that will not cross a dateline to the second virtual channel VC1. In this regard, data packets that will not cross a virtual channel may be transitioned from VC0 to VC1 when the data packet is N hops from its destination node. The value of N may be based on the size of the ring network (e.g., the number of nodes in the ring network) and the expected packet traffic patterns.

Balanced VC usage may be determined based on an assumed traffic pattern. In this regard, different types of traffic patterns may use each VC differently. For example, a network with an all-to-all traffic pattern may have different balancing needs than a network with all-to-one or other such traffic patterns. In the examples used herein, global all-to-all traffic patterns are discussed. In a network implementing a global all-to-all traffic pattern, each network node can receive data packets from every other network node and transmit data packets to every other network node.

Queuing structures, including turn and dimension queues, may route data packets through the network. In this regard, networks may use these queuing structures to direct data packets as the data packets traverse the network. The turn queue may be used to direct data packets as they turn from one dimension of the torus network to the next. For instance, the turn queue may be used to direct a data packet received by a node on a first dimension onto another dimension. Dimension queues may direct data packets continuing along a single dimension of the network and on a virtual channel. For instance, the dimension queue may direct a data packet from one node to another along the same dimension and on a common virtual channel, such as VC0 or VC1. The queuing structures may be part of the node or a component connected to the node. For instance, the queueing structures may be part of a router or other network interface integrated into a node.

<FIG> illustrates queuing structures within nodes <NUM>, <NUM>, <NUM>, and <NUM> of a network <NUM>. As shown, each node includes queuing structures. In this regard, node <NUM> includes turn queues <NUM>, <NUM> and dimension queue <NUM>, node <NUM> includes turn queues <NUM>, <NUM> and dimension queue <NUM>, node <NUM> includes turn queues <NUM>, <NUM> and dimension queue <NUM>, and node <NUM> includes turn queues <NUM>, <NUM> and dimension queue <NUM>. Turn queues <NUM>, <NUM>, <NUM>, <NUM> and <NUM>, <NUM>, <NUM>, <NUM> may direct data onto and off of dimensions of the torus network.

As further illustrated in <FIG>, an example data packet is shown as entering, progressing through, and exiting the network <NUM> by arrows <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. In this regard, arrow <NUM> illustrates the data packet entering node <NUM> via turn queue <NUM>. The data packet is transmitted from node <NUM> to dimension queue <NUM> in node <NUM>, as illustrated by arrow <NUM>. From node <NUM>, the data packet is transmitted to dimension queue <NUM> of node <NUM>, as illustrated by line <NUM>. The data packet is then transmitted to turn queue <NUM> in node <NUM>, where it is subsequently transmitted out, as indicated by arrow <NUM>.

The data packet in the example shown in <FIG> makes three "hops. " A hop is a transmission from one node to another node. In <FIG>, the three hops are the transmission from node <NUM> to node <NUM>, from node <NUM> to node <NUM>, and from node <NUM> to node <NUM>. In instances where a data packet is limited to <NUM> or <NUM> hops along a network, the data packet would be limited to using turn queues. In this regard, the data packet would not use any dimension queues, as the data packet would be egressing or ingressing dimensions of the torus ring network using turn queues.

Referring to network <NUM> in <FIG>, the dimension queues in each node <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> may be assigned a virtual channel for routing along a dimension of the ring network. In this regard, dimensions queues <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> of nodes <NUM>-<NUM>, respectively, are assigned VC1. Dimension queues <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> of nodes <NUM>-<NUM>, respectively, are assigned VC0. Data packets traveling between nodes on the same virtual channel, e.g., VC0 or VC1, would pass between dimension queues having the same assigned virtual channel. For instance, a data packet passing between node <NUM> and <NUM> on virtual VC0 would pass from dimension queue <NUM> to dimension queue <NUM>. Similarly, a data packet passing between node <NUM> and <NUM> on virtual channel VC1 would pass from dimension queue <NUM> to dimension queue <NUM>.

For data packets traveling h ≥ <NUM> hops, the data packets use h-<NUM> dimension queue(s) along their routes. As all-to-all traffic is symmetric, the total usage of the dimension queues may be determined by summing over the routes that are at least two hops:<MAT> where h is the number of hops and t(h) is the fraction of traffic that travels h hops along the dimension queues. The units of this sum are the average number of data packets that enter the dimension queues on a node when a single packet is injected at each node in the ring network.

For all-to-all traffic in a torus ring network, with an even number of nodes k along its dimensions: <MAT>.

To balance load between the two VCs dedicated to the dimension queues VC0 and VC1, the routing algorithm may have a threshold T defined. Any data packet with T or fewer hops remaining in its route, and not going to pass a dateline, may be placed into VC1. Otherwise, the data packet may use VC0.

<FIG> shows a <NUM>-hop route of data packet <NUM>, illustrated by arrows labeled DP1 over network <NUM>. In this regard, data packet <NUM> enters node <NUM> into the turn queue <NUM>. Data packet <NUM> is then transmitted to node <NUM> by the turn queue <NUM> to dimension queue <NUM> and onto VC0. From the dimension queue <NUM>, data packet <NUM> is transmitted to dimension queue <NUM> of node <NUM> and onto VC1. From dimension queue <NUM>, data packet <NUM> is transmitted to turn queue <NUM> of Node <NUM>, where it is subsequently taken off of the network <NUM>.

<FIG> further shows a <NUM>-hop route of data packet <NUM>, illustrated by arrows labeled DP2, over network <NUM>. In this regard, data packet enters network <NUM> via node <NUM> into turn queue <NUM>. From turn queue <NUM> data packet <NUM> is transmitted to dimension queue <NUM> of node <NUM> and onto VC1. From dimension queue <NUM> the data packet is transmitted to turn queue <NUM> of node <NUM>, where it is subsequently taken off of the network <NUM>.

The routing of data packet <NUM> and data packet <NUM> is based on the routing algorithm of network <NUM> having a threshold of T = <NUM>. Thus, data packet <NUM> is initially routed onto VC0 in node <NUM>, as data packet <NUM> has <NUM>-hops remaining. It is not until data packet <NUM> reached node <NUM>, when data packet <NUM> has <NUM>-hop remaining, equaling the threshold value of <NUM>, that it gets routed onto VC1. If the threshold value were <NUM>-hops, data packet <NUM> would have been routed onto VC1 at node <NUM>.

With reference to the <NUM>-hop route of data packet <NUM>, the data packet is immediately routed onto VC1, since data packet <NUM> has a <NUM>-hop remaining, equaling the threshold value of <NUM> when it reaches node <NUM>.

As network <NUM> is not shown to include a dateline, no consideration of a dateline is made in the routing of the data packets over network <NUM>. However, if a date line were present, data packets <NUM> and <NUM> would only switch to VC1 at the threshold value if the data packets were not to later cross a dateline. The number of datelines a packet may cross may be determined by performing a table lookup. In this regard, the number of datelines along a route to a destination node may be stored in the RAM memory table routes. Accordingly, the number of datelines to be traversed by a data packet to a destination node may be determined by using the destination of the data packet to index a table and lookup the number of datelines along the route to the destination, as stored in the table.

To compute a threshold value that balances load between the dimensions VC0 and VC1, the total load on the dimension queues may be divided into the load contributed by data packets with h hops remaining, which is defined as: <MAT>.

Every packet that travels two or more hops, for example, will eventually have one hop remaining. Thus, the sum of the fraction of the traffic for each of these hops (i.e., r(<NUM>) = t(<NUM>) + t(<NUM>) +. ) may be determined to find the utilization of the dimension queues contributed by packets with one hop remaining. Since every packet has some number of hops remaining, summing over r(h) recovers the total load as computed above: <MAT>.

A T may then be selected to minimize the imbalance between the two VCs: <MAT>.

Example values of threshold T have been computed using the above equations for different sized rings in table <NUM>, below:.

Empirically, there is a linear relationship between ring size and the calculated threshold value (T). Thus, selecting a threshold value, where (T) = round(<NUM> · k - <NUM>) may yield a result for rings where k is a multiple of <NUM> and where the network includes up to <NUM> nodes.

The concepts from the previous section can be extended to twisted tori with appropriate definitions for the t(h) function. Example values of threshold T for twisted tori networks have been computed using the equation for different size rings in table <NUM>, below:.

As with torus ring networks, there is a linear relationship between ring size and the calculated threshold value (T) for twisted tori networks. In this regard, a threshold value (T), for values of k ≤ <NUM>, may be determined using one of the following equations: <MAT> <MAT>.

In some instances, datelines may be removed from a ring network routing algorithm. By removing datelines, improved throughput through the network may be achieved, in particular when direct memory access (DMA) size increases. Certain conditions may be met before datelines are removed. These conditions may include (<NUM>) the network includes eight or fewer nodes in the ring (this corresponds to k ≤ <NUM> for twisted tori network); (<NUM>) VC usage is balanced using the balancing techniques described herein; and (<NUM>) when there are eight nodes in the ring (also applies to k = <NUM> twisted tori), the nodes alternate between positive direction and negative direction tiebreaking for the routes that go exactly halfway around the ring.

In networks having more than <NUM> nodes, networks where VC balancing is disabled, or networks where tiebreaking does not alternate, the acyclic dependencies of the VC are lost and VC0 to VC0 dependencies appear between all nodes, necessitating a dateline (or other approach) to break the VC0 cycle.

In some embodiments, nodes may include queuing structures with input and output queues. In this regard, and unlike input or output queued architectures, such as described in <FIG> and <FIG>, a data packet at each hop travels through an input and an output queue. These pairs of queues may be split into their associated dimension. For instance, and as illustrated in <FIG>, within the combined input-output queuing architecture of network <NUM>, the nodes may include a turn from a previous dimension, such as turns <NUM>, <NUM>, <NUM> of nodes <NUM>, <NUM>, and <NUM>, turns to next dimensions, such as turns <NUM>, <NUM>, and <NUM> of nodes <NUM>, <NUM>, and <NUM>. Additionally, the nodes may include dimension queuing structures associated with the virtual channels, such as queuing structures <NUM>, <NUM>, and <NUM> associated with VC0 in nodes <NUM>, <NUM>, and <NUM>, respectively. Additionally, nodes <NUM>, <NUM>, and <NUM> include queuing structures <NUM>,<NUM>, and <NUM> associated with VC1, respectively.

As further shown in <FIG>, each queueing structure may be split into input queues, identified by "(i)" and output queues, identified by "(o)". For instance, dimension queueing structure <NUM> includes VC1 (i), the input queue, and VC1 (o), the output queue. During the transmission of a data packet, the data packet passes through both an input queue and an output queue. For instance, data packet <NUM>, labeled DP1 in <FIG>, passes through the turn <NUM> queueing structure, including through the input queue, labeled as T(i) and the output queue, labeled as T(o).

As also shown in <FIG>, a transition between VCs occurs when a packet goes from an input queue to an output queue. In this regard, DP1 may pass from VC0 (i) (an input queue) to VC1(o) (an output queue) in node <NUM>. VC1 (o) may subsequently pass DP1 to input queue VC1 (i) of node <NUM>. Within node <NUM>, the data packet may be passed to T(o).

<FIG> illustrates a flow diagram <NUM> for routing data packets in a network. In block <NUM>, a data packet is received at a first queueing structure within a first node of the ring network. The data packet is to be transmitted to a destination node on the network. In block <NUM>, the first node determines a number of hops the data packet will traverse as it is transmitted from the first node to the destination node of the ring network. In block <NUM>, the first node compares the number of hops to a threshold hop value to determine whether the number of hops is equal to or less than the threshold hop value. In block <NUM>, the first node transmits the data packet to (i) a dimension queues structure for a first virtual channel within a second node of the ring network if the number of hops is greater than the threshold hop value; or (ii) a dimension queues structure for a second virtual channel or a turn queuing structure within the second node if the number of hops is equal to or less than the threshold hop value.

Although the foregoing examples illustrate ring networks, such as ring networks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> the technology described herein may be applicable to other ring-based network topologies such as multiple ring-based topologies (e.g., "torus" and "twisted torus") topologies.

Claim 1:
A method of routing data packets within a ring network (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>), the method comprising:
receiving, at a first queueing structure within a first node (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>; ) of the ring network (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>), a data packet to be transmitted to a destination node;
determining, by the first node(<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>), a number of hops the data packet will traverse as it is transmitted from the first node (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>) to the destination node of the ring network (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>); the method being characterized in comprising :
comparing, by the first node (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>), the number of hops to a threshold hop value to determine whether the number of hops is equal to or less than the threshold hop value; and
transmitting, by the first node (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>), the data packet to:
(i) a dimension queuing structure for a first virtual channel (VCO) within a second node of the ring network (<NUM>; <NUM>; <NUM>; <NUM>; <NUM>; <NUM>) if the number of hops is greater than the threshold hop value; or
(ii) a dimension queuing structure for a second virtual channel (VC1) or a turn queuing structure within the second node if the number of hops is equal to or less than the threshold hop value.