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

a b

0

1

11

1 0

11

00 1 0

MAX MAX

MAX MAX

L R L R

R

1

L

1

R L

1

1

0

1

MAX

MAX

L R R

1

R

1

AG

AG

Fig. 4.2 Treating requests as 1-bit numbers transforms fixed-priority arbitration to a maximum
selection procedure that identifies the maximum number that lies in the rightmost position. Grant
signals are generated according to the values of the direction flags that identify the index of the
winning position

along with a flag, that denotes the origin, left or right, of the maximum number.
In case of a tie, when equal numbers are compared, the flag always points to the right
according to the FPA policy. Note though that when both numbers under comparison
are equal to 0 (i.e., between the two compared requests, none is active), the direction
flag is actually a don't care value and does not need necessarily to point to the right.
In every case, the path that connects the winning input with the output is defined by
the direction flags of the MAX nodes.
Each MAX node should identify the maximum of two single-bit input requests,
denoted as R L and R R , and declare via the direction flag F if the request with the
greatest value comes from the left (F D 1) or the right (F D 0). The first output of
the MAX node, that is the maximum, can be computed by the logical OR of R L and
R R . The other output of the MAX node, flag F , is asserted when the left request R L
is the maximum. Therefore, F should be equal to 1 when R L D 1 and R R D 0.

4.1.1 Generation of the Grant Signals

The maximum-selection tree shown in Fig. 4.2 a that replaces the traditional FPA,
should be enhanced to facilitate the simultaneous generation of the corresponding
grant signals via the flag bits (F ). The AG signal at the output of the last MAX
is active when at least one grant is generated. Therefore generating grant signals
is equivalent to distributing the value of the AG bit to the appropriate input. If the
direction of the last node points to the left it means that the value of AG should
be propagated to the left subtree and the right subtree should get a zero grant. This
distribution is done by the de-multiplexer next to each comparison node shown in
Fig. 4.2 b. The demultiplexer's input at the root node is the AG bit and its select
line is driven by the associated direction flag. When the AG bit propagates to the