1. The cost of a network is proportional to the # of wires between routers.
   • Assume full-duplex channels.
   • p-vertex hypercube Q_k, where k=log p, has k channels per router, whereas torus T(\sqrt{p},\sqrt{p}) has only 4 channels per router.
   • Hence, Q_k network with serial 1-wire channels will cost as T(\sqrt{p},\sqrt{p}) with k/4 wires per channel.
   • The average distance in Q_k is k/2 and the average distance in T(\sqrt{p},\sqrt{p}) is \sqrt{p}/2.
   • Using Equation (7.2), the average base communication latency of a packet will be therefore

     {log p/ 2}td+Mtm
     

     in Q_k, whereas

     {\sqrt{p}/ 2}td+{4/ log p}Mtm
     

     in T(\sqrt{p},\sqrt{p}), since the torus parallel channels have log p/4 times higher bandwidth.
   The conclusion is easy: For larger M, the first terms can be dropped and for p>= 16, the WH torus is faster for conflict-free communication in the average case than equally-sized WH hypercube of the same cost.
2. The cost of a network is proportional to its bisection bandwidth.
   • p-processor hypercube Q_k has bisection width p/2, whereas p-processor torus T(\sqrt{p},\sqrt{p}) has bisection width 2\sqrt{p}.
   • So, by a similar argument, Q_k with serial 1-wire channels has the same bisection bandwidth as T(\sqrt{p},\sqrt{p}) with \sqrt{p}/4 wires per channel.
   • The average base communication latency of a packet will be again

     {log p/ 2}td+Mtm
     

     in Q_k, but

     {\sqrt{p}/ 2}td+{4/ \sqrt{p}}Mtm
     

     in T(\sqrt{p},\sqrt{p}).
   So, the conclusion is basically the same as before.

• A physical WH channel may support several virtual channels multiplexed across the physical channel.
• Each unidirectional virtual channel is realized by an independently managed pair of (flit) buffers.
• Packets can share the physical channel on a flit-by-flit basis.
• The physical channel protocol must be able to distinguish between the virtual channels.

CAPTION: A physical channel divided into two (red and blue) virtual channels
Virtual channels were originally introduced to solve the deadlock avoidance problem, but they can be also used to improve network latency and throughput. Figure illustrates two model situations: Assume P₀ arrived earlier and acquired the channel between the two routers first. In absence of virtual channels, packet P₁ arriving later would be blocked until the transmission of P₀ has been completed. Assume now that physical channels implement two virtual channels. Upon arrival of P₁, the physical channel is multiplexed between them on a flit-by-flit bases and both packets proceed with half speed.

• Assume that P₀ is a full-length packet whereas P₁ is only a small control packet of size of few flits. Then this scheme allows P₁ pass through both routers while P₀ is slowed down for a short time corresponding to the transmission of few packets.
• Assume that P₀ is temporarily blocked downstream from the current router. Then P₁ can proceed at the full speed of the physical channel.

CAPTION: Increased throughput due to virtual channels

Back to the beginning of the page	Back to the CS838 class schedule

Undeliverable packets

Undeliverable packet situations

• buffers in SF and VCT switching,
• channels in circuit and WH switching.

• a node cannot send a packet to itself,
• a packet that reached its destination is always consumed and ejected in finite time by this node,
• routing is distributed and deterministic,
• physical channels are bidirectional full-duplex and can be divided into virtual channels,
• routing and arbitration unit in router can only process one packet header at a time,
• if incoming packets content for this unit, it is allocated in a round robin way,
• if a packet acquired the routing and arbitration unit, but it cannot be routed since the required output channels are busy, it waits in the corresponding input buffer until its next round,
• virtual channels are assigned the physical channel cyclically only if they are ready to route a flit (demand-slotted round robin),
• once a buffer accepts the first flit of a packet, it must accept the remaining flits of the same packet before accepting any flits from another packet,

Livelock:

a packet is denied routing to its destination forever even though it is never blocked permanently. It may be traveling around its destination node, never reaching it because the channels it requires are always occupied by other packets. This can occur if nongreedy adaptive routing is allowed (packets are misrouted, but are not able to get closer to the destination).

Starvation:

a node with a packet is never allowed to inject it into the network (e.g., the traffic within the network is getting higher priority, which makes sometimes sense if the network is heavily loaded). Or a packet, already in the network, is permanently stopped if traffic is intense and the resources requested by it are always granted to other packets also requesting them.

Deadlock:

packets are allowed to hold some resources while requesting others, so that the dependency chain forms a cycle. Then all these packets must wait forever.

CAPTION: A deadlock situation in a wormhole network.
These abnormal situations may be related. For instance, a deadlock can permanently block exactly those resources that misrouted packets need to get out of a livelock. The probability of occurrence of situations preventing packets to be delivered increases with network traffic and decreases with the amount of buffer space. That is why WH is more deadlock-prone than VCT if the routing algorithm is not deadlock-free.

Handling undeliverable packets

Starvation handling:

Starvation can be solved easily if a correct and fair resource allocation scheme is used, such a simple demand-slotted round-robin scheme. If some packets must have higher priority than the others, then some part of the bandwidth must be reserved and guaranteed for lower-priority packets (virtual channels, extra buffers etc). In WH networks, this can be easily implemented.

Livelock handling:

The simplest way is to use greedy routing. In WH networks, it increases throughput since the worms have minimal possible length. If nongreedy routing is used, then the number of misrouting operation must be bounded.

Deadlock handling:

Deadlocks are the most difficult problem to solve among these three. It can be handled in three ways:

deadlock prevention:

resources are granted to packets in such a way that a request can never lead to a deadlock. This is done in circuit switching: the resources are granted before the transmission starts. It is very conservative approach and may lead to very low resource utilization.

deadlock avoidance:

resources are requested as a packet advances through the network so that the resulting global state is deadlock-free. This is less conservative, resources are requested only when they are really needed. A common technique is to establish an ordering between resources and granting them to each packet in descending order, which provides a deadlock-free routing algorithm, if such exists, for given topology. This is the case of dimension-order routing in meshes and binary hypercubes and it is discussed bellow.

deadlock recovery:

Deadlock is allowed, resources are granted to packets without any check, and if a deadlock is detected, some resources are deallocated and granted to other packets. This usually implies aborting some packet transmissions. This can be used only if deadlocks are rare and the results of aborts can be tolerated.

Definition

Consider a network G modeled by a directed graph where the bidirectional channels are implemented by pairs of antiparallel unidirectional channels. Let C be the set of these channels of G and V be the set of nodes (routers) of G. The routing function R in G is a function C× V-> C, which for each current input channel cin C and destination node w returns the output channel R(c,w).

Definition

Given a directed graph G and routing algorithm R, then the channel dependency graph for G and R, CDG(G,R), is a digraph D such that V(D)=E(G) and E(D) is the set of all pairs of adjacent channels used by routing algorithm R. Hence, ( c_i,c_j)in E(D) if and only if routing R can forward a packet from channel c_i to channel c_j for some communication request in G, i.e. if \exists destination node win V(G) such that R(c_i,w)=c_j.

CAPTION: Torus T(5) and its channel dependence graph D
The deadlock avoidance theory stands on the following result.

Theorem

A deterministic routing algorithm R is deadlock-free in G if and only if CDG(G,R) is acyclic.

Corollary

Dimension-order routing is deadlock-free in full-duplex meshes and binary hypercubes.

CAPTION: XY routing in 2-D mesh is deadlock-free
On the other hand, dimension-order routing is not deadlock-free in tori. Figure gives the simplest example. For example, each tuple of z packets P₀,...,P_z-1, where P_i's source node is i and destination node is i+_z2, leads to a deadlock. Every 1-D cycle has a cyclic CDG. Generally,

Lemma

In k-ary n-dimensional tori, for k>= 5, there exists no deadlock-free greedy routing algorithm. However, using two virtual channels per physical one, there exists a deadlock-free nongreedy routing algorithm for tori.

1. Construct D=CDG(G,R).
2. Try to break all cycles in D. Assume that D can be reduced to a directed acyclic graph (DAG) D' so that G remains strongly connected using routing function reduced to remaining channels. Then we have a routing function R' constrained to those channel dependencies that correspond to arcs in D' and since D' is acyclic, R' is deadlock-free.
3. If the reduction cannot be done without making G strongly disconnected, then add arcs to D that correspond to splitting each channel of G into a group of q virtual channels (q>= 2). The additional edges provided by virtual channels make it possible to reduce D to strongly connected DAG while keeping G strongly connected. This reduction is based on lexicographic labeling of channels.

A solution for tori

1. Node u has n output physical channels labeled with (n+1)-letter strings iu, i=0,...,n-1, denoted by c_iu (see Figure ).
   

   CAPTION: Channel labeling in 2-D torus
   

2. Each physical channel c_iu is divided into two virtual channels: upper c_i1u and lower c_i0u.
3. Informally a deadlock free routing function is defined as follows:
   • route in order of descending node addresses:
     • find the nonzero offset in the most significant position (from left to right) by subtracting current address from the destination
     • make a step towards its nullifying by sending the packet along that dimension in descending order so that
       • use the upper virtual channel if the corresponding offset is > 0
       • use the lower virtual channel if the corresponding offset is < 0
4. The formal definition of the new routing function is as follows:
   Consider two routers u and v adjacent in coordinate d, hence v[d]=u[d]\ominus_zd1 (remember the routing always sends packets in descending order in corresponding dimension) and assume that v has received a packet from u with destination address w via channel c_dru, where r in{0,1}. If w=v, then v consumes the packet. Assume that w\not=v. Then v will send the packet further using the output channel

   R'(cdru,w)= 
                    cd1v  if vd < wd
   
                    cd0v  if vd > wd
   
                    ci1v  if for all  k > i; vk=wk and vi < wi
   
                    ci0v  if for all  k > i; vk=wk and vi > wi
   

Lemma

The routing function R correctly routes packets from any node to any other node in T(z₁,...,z_n).

c1v,...,c10,c0(z-1),...,c0(w+1),

c0v,...,c0(w+1),

CAPTION: Deadlock-free routing in T(5) using two virtual channels and the corresponding acyclic CDG
The following example shows a typical permutation of packets which would establish a deadlock if there were no virtual channels. It is cyclic rotation by two positions to the right (it works for any number of positions). Packets form a chain ending with an unblocked buffer, so even if they start at the same time, each of them will eventually make progress.

CAPTION: Routing of a cyclic-2-shift on T(5)

Back to the beginning of the page	Back to the CS838 class schedule