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

independently from the rest. Thus, the probability that all N inputs are not sending

to output j , thus rendering output j idle, is Q P ij D .1 1=N / N . Therefore, output
j is accepting a new flit with probability 1 .1 1=N / N . This value starts from 0.75
for 2 2 switch, moves to 0.703 for a 3 3 switch and converges to 0.63 for large
values of N . As proven in Karol et al. ( 1987 ), if we take into account that current
scheduling decisions are not independent from the previous ones then the maximum
throughput per output is lower and saturates around 58 % for large values of N .

3.6 Routers in the Network: Routing Computation

The need to connect many sources to many destinations in a regular manner and
without using many wires has led to the design of network topologies. A router is
placed at the crossroads of such network topologies as shown in Fig. 3.14 and should
forward to the correct output all traffic that arrives at its inputs. Each input/output
port of the router that is connected to the network's links should be independently
flow controlled providing lossless operation and high communication throughput.
The router should support in parallel all input-output permutations. When only
one input requests a specific output, the router should connect the corresponding
input with the designated output. When two or more inputs compete for gaining
access to the same output in the same cycle the router is responsible for resolving
the contention. This means that only one input will gain access to the output port.
The flits of the input that lost stay it the input buffer of the current router and
retry in the next cycle. Alternatively, the flits of the lost input can be misrouted
to the first available output and move to another node of the network, hoping that

a

ACC NI

NI RAM

ACC NI

NI CPU

CPU NI

NI DSP

b

Arbitrary IO
permutations

Resolve Contention

Fig. 3.14 Routers are
responsible for keeping the
network connected and
resolving contention for the
same resource while allowing
multiple packets to flow in
the network concurrently