Baseline Virtual-Channel Based Switching Modules and Routers - Microarchitecture of Network-on-Chip Routers - page 115

per input

granted
input VC

l o cal MUX
select

V:1
arb

V input VC
requests

N

per outp u t crossbar

select

N

N:1
arb

N

port request of
granted Input VC

N:1
arb

V:1
arb
total N
V:1 arbiters

total N
N:1 arbiters

Fig. 7.7 The switch allocator for a many-to-one connection requires two stages of arbitration. One
per input that selects one input VC from each input port, and, one per output that finally grants on
the competing inputs

In the routers that do not support VCs and presented in Chaps. 3 and 5 , an arbiter
updates its priority whenever it delivers at least one grant. However, SA1 arbiters
should update their priority only if a grant is also received by SA2, following the
iSlip rules (McKeown 1999 ). The reason why this is crucial can be perceived by
the following example, in which the arbiters of SA1 and SA2 update their priorities
independent of the result of each other.
Assume that input VC#3, that belongs to input port 1, has already allocated an
output VC and performs switch allocation using the round-robin arbiters of SA1
and SA2, respectively. Input VC#2, that belongs to input port 0, also owns an
output VC of the output port and participate in SA as well. Both input VCs win
in SA1 (they belong to different inputs) and advance to SA2, in order to fight for
accessing the output port. SA2 arbiter's priority favors input port 0, thus, input VC#2
is granted and priority is updated to point to input port 1. However, the SA1 of
input 1 has updated its priority to point to VC#4. As a result, in the next cycle,
input VC#4, which is also allocated to an output VC, wins in SA1 and possibly in
SA2 thus letting VC#3 loose for two consecutive cycles. Depending on the router's
configuration and the traffic pattern, the above situation of VC#3 wining in SA1
but losing in SA2, may be repeated indefinitely. This situation can be avoided by
guaranteeing that if an input VC wins in SA1, it will remain the winner input VC
until it is granted in SA2 as well. Under this rule, an input VC may need to wait at
most N 1 cycles to be granted in SA2.