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

multiple requests
can be active per cycle

Requests

Arbitration
Logic

Grants

Priority
Updated

Priority
State a singe grant

is give per cycle

Fig. 4.1 Dynamic priority arbiter allows the priority of each position to change in a programmable
way. The selected arbitration policy is implemented in a synergistic way by the arbitration logic
and the priority-update logic

In any FPA, the request of position 0 (rightmost) has the highest priority and the
request of position N 1 the lowest. For example, when an 8-port FPA receives
the request vector R 7 :::R 0 D 01100100, it would grant input 2 because it has the
rightmost active request. When at least one request is granted, an additional flag
AG (Any Grant (AG)) is asserted. The FPA can be implemented in many ways.
We are interested only in high-speed implementations, where all grant signals are
computed in parallel for each bit position (Weste and Harris 2010 ). In this case,
the gr ant sign al G i is computed via the well-known priority encoding rel ati on G i D
R i R i 1 ::: R 1 R 0 ,where represents the boolean-AND operation and R i denotes

the complement of R i .
An alternative fast implementation can be derived by employing fast adder
circuits in the place of priority encoders. At fi rst, we need to derive an intermediate
sum by adding 1 to the inverted requests R. Then, the grant signals are derived
via the bitwise AND of the intermediate sum and the original request vector.
Fo r example, the complement of the 8-bit request vector R D 01100100 is
R D 10011011. Incrementing by one this vector leads to an intermediate sum of
10011100. The bit-wise AND of the sum and the original request vector leads to
correct grant vector 00000100 that grants the request of input 2.
Alternatively, fixed priority arbitration can be achieved if we treat the request
signals of the FPA as numbers with values 0 and 1, and the fixed priority arbitration
as a sorting operation on these numbers (Dimitrakopoulos et al. 2013 ). Practically,
the selection of the rightmost 1, as dictated by the FPA, can be equivalently
described as the selection of the maximum number that lies in the rightmost position.
Selecting the maximum of a set of numbers can be performed either by a tree or a
linear comparison structure. Such structures compare recursively the elements of
the set in pairs and the maximum of each pair is propagated closer to the output.
Similarly, the sorting-based FPA can be implemented as a binary tree with N 1
comparison nodes. Such a tree, for a 4-port FPA, is shown in Fig. 4.2 a. Each node
receives two single-bit numbers as input and computes the maximum of the two,