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

Fig. 4.8 The 2D priority matrix representing the relative priorities of the inputs together with an
example of grant generation for on an arbitrary request vector

the general case not all requests are active. Therefore, first the request from each
input are ANDed with the priority bits that belong to the same row. Then, from
the resulting matrix the inputs that their corresponding column is full of zeroes
are eligible to receive a grant (ready to grant). On the contrary, and respecting the
relative priority of the inputs, the columns with at least 1 bit asserted should be
excluded from the grants.
This operation of the arbiter that relies on a 2D matrix is also shown in Fig. 4.8 .
Beginning from the priority matrix and masking each row with the corresponding
request per input leads to the matrix on the right side of Fig. 4.8 . Observing the
columns of the matrix we see that column 1 has at least 1 bit asserted which means
that another input (input 2 in this case) has a higher priority over input 1. Thus, input
1 cannot receive a grant. On the contrary, inputs 2 and 0 see their corresponding
columns filled with zeroes thus they are allowed to receive a grant. By masking the
ready to grant bits with the requests gives the final grant vector. Input 0 although
had the highest priority and sees a ready to grant bit asserted, it does not receive
a grant due to the lack of an active request in the current arbitration cycle. The
implementation of the arbitration logic of a 3-input arbiter is shown in Fig. 4.9 .
Care should be taken with the priority values since the possibility of a deadlock
exists. For example in the case of a 3-input matrix arbiter with P Œ0; 1 D P Œ1; 2 D
PŒ2;0 D 1 a circular priority dependency is produced, which blocks the arbiter
from producing any grant.

4.3.1 Priority Update Policies

Based on the 2D organization of the priority state, we can derive multiple arbitration
policies. The differentiating factor between the possible arbitration policies is on