Arbitration Logic - Microarchitecture of Network-on-Chip Routers - page 66

Fig. 4.7 The structure of
the merged arbiter and
multiplexer implementing
the round robin policy

D 7 3 D 6 3 D 5 0 D 4 3 D 3 0 D 2 2 D 1 2 D 0 0

MAX MAX MAX MAX

MUX MUX MUX MUX

3 3 2 2

R R R L

D 4 D 2 D 1

D 6

MAX MAX

MUX MUX 2

3

R R

D 1

D 4

MAX

MUX

L

3

D 4

switch the data words that are associated with the input numbers (i.e., the requests),
we can route at the output the data word that is associated with the winning request.
This combined operation can be implemented by adding a 2-to-1 multiplexer next
to each MAX node and connecting the direction flag to the select line of the
multiplexer. The organization of this merged round robin arbiter and multiplexer
is shown in Fig. 4.7 .

4.3 Arbiters with 2D Priority State

Other arbitration policies require the addition of extra priority state bits that treat
arbitration and the relative priority of inputs in a different way (Dally and Towles
2004 ; Satpathy et al. 2012 ; Boucard and Montperrus 2009 ). Let's assume that
priority is kept in a 2D matrix, where in each position i; j (i th row, j th column) a
priority bit is stored that records the relative priority between inputs i and j .When
PŒi;j D 1, the request from input i has higher priority than the request from input
j . To reflect the priority of i over j, the symmetric matrix element PŒj;i should be
set equal to 0. Also, the elements of the diagonal PŒi;i have no physical meaning
and can be assumed equal to 0. An example priority matrix is shown in Fig. 4.8 .In
this case, input 0 has a higher priority than input 1 and 2, while input 2 has a higher
priority than input 1. By summing the number of ones per row, the total priority
order among all inputs is revealed. The input with the largest sum has the highest
priority and the rest inputs follow in a decreasing order of sums (priority).
The arbiter receives the current request and the priority matrix and decides which
input to grant. Assume at first the case that all requests are active at each arbitration
cycle. Then, if at least one 1 exists on column j of the priority matrix then the
request of input j cannot be granted, since there is at least one input with higher
priority than j . This condition for column j can be identified by ORing all bits of
the same column and nullifying the corresponding grant (j th output). However, in