Baseline Switching Modules and Routers - Microarchitecture of Network-on-Chip Routers - page 51

updates in the forward direction spend one more cycle before reaching an output
buffer. Without any further change, by just increasing the buffer size at the output,
full throughput communication is guaranteed.

3.5 Head-of-Line Blocking

Assume for example the case of a 3-input and 3-output switch shown in Fig. 3.13 .If
two inputs request the same output, then contention arises and the arbiter will grant
only one of the two competing inputs. The one that won arbitration will pass to the
requested output and leave the router in the next clock cycle, provided that a buffer
is available downstream. The packet that lost arbitration will be blocked in the input
buffer until the tail of the winning packet leaves the router too. In our example,
input 2 participated in the arbitration for output 2 and lost. However, besides the
two flits heading to output 2, input 2 holds also flits that want to leave from output
1 that is currently idle. Unfortunately, those flits are behind the frontmost position
of the buffer at input 2 and are needlessly blocked, as depicted in Fig. 3.13 .This
phenomenon is called head-of-line blocking and is a major performance limiter for
switches. It can be alleviated only by allowing more flexibility at the input buffers
that should allow multiple flits to compete in parallel during arbitration even if they
don't hold the frontmost position.
A good way to understand HOL blocking is use the example presented in Medhi
and Ramasamy ( 2007 ): Think of yourself in a car traveling on a single-lane road.
You arrive at an intersection where you need to turn right. However, there is a car
ahead of you that is not turning and is waiting for the traffic signal to turn green.
Even though you are allowed to turn right at the light, you are blocked behind the
first car since you cannot pass on a single lane.
The throughput expected per output can be easily estimated if the traffic
distribution is known beforehand. Without loss of generality, assume that each input
wants to transmit a new flit per cycle, and that each flit is destined to each output
with equal probability P D 1=N . When more than one inputs are heading for the
same output only one will get through and the rest will be blocked. An output j
will be idle only when none of the inputs have a flit for this output. The probability
that input i chooses output j is P ij D 1=N . Thus, the probability of not selecting
the corresponding output is P ij D 1 1=N . An input sends or not to output j

in#0 out#0

2 2

in#1 out#1

0 0 0

in#2 out#2

Fig. 3.13 Demonstration of a
Head-of-Line Blocking
scenario

1 1 2 2

blocked