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

HP segment LP segment

Position 7 6 5 4 3 2 1 0

Requests
Priority
Arithmetic
Symbol

1 1 0 1 0 1 1 0

1 1 1 1 1 0 0 0

3 3 1 3 1 2 2 0

Search order

Fig. 4.5 The priority vector of the round-robin arbiter separates the requests to a high-priority and
a low-priority segment. Treating the requests and the priority bits at each position as independent
arithmetic symbols transforms the dynamic cyclic search of round-robin arbitration to an acyclic
process that selects the maximum number

which are placed in positions with P i D 0, belong to the low-priority (LP) segment.
The operation of the arbiter is to give a grant to the first (rightmost) active request of
the HP segment and, if not finding any, to give a grant to the first (rightmost) active
request of the LP segment. According to the already known solutions, this operation
involves, either implicitly or explicitly, a cyclic search of the requests, starting from
the HP segment and continuing to the LP segment.
Either at the HP or the LP segment, the pairs of bits .R i ;P i / can assume any
value. We are interested in giving an arithmetic meaning to these pairs. Therefore,
we treat the bits R i P i as a 2-bit unsigned quantity with a value equal to 2R i C P i .
For example, in the case of an 8-input arbiter, the arithmetic symbols we get for
a randomly selected request and priority vector are also shown in Fig. 4.5 .From
the 4 possible arithmetic symbols, i.e., 3, 2, 1, 0, the symbols that represent an
active request are either 3 (from the HP segment) or 2 (from the LP segment). On
the contrary, the symbols 1 and 0 denote an inactive request that belongs to the
HP and the LP segment, respectively. According to the described arbitration policy
and the example priority vector of Fig. 4.5 , the arbiter should start looking for an
active request from position 3 moving upwards to positions 4, 5, 6, 7 and then to
0, 1, 2 until it finds the first active request. The request that should be granted lies
in position 4, which is the first (rightmost) request of the HP segment. Since this
request belongs to the HP segment, its corresponding arithmetic symbol is equal to
3. Therefore, granting the first (rightmost) request of the HP segment is equivalent to
giving a grant to the first maximum symbol that we find when searching from right
to left. This general principle also holds for the case that the HP segment does not
contain any active request. Then, all arithmetic symbols of the HP segment would
be equal to 1 and any active request of the LP segment would be mapped to a larger
number (arithmetic symbol 2).
Therefore, by treating the request and the priority bits as arithmetic symbols, we
can transform the round-robin cyclic search to the equivalent operation of selecting
the maximum arithmetic symbol that lies in the rightmost position. Searching for the
maximum symbol and reporting at the output only its first (rightmost) appearance,