High-Speed Allocators for VC-Based Routers - Microarchitecture of Network-on-Chip Routers - page 138

has enough credits (similar to combined allocation); else a grant from the SA will
be useless. At the same time, during speculative SA, they compete with other input
VCs that do not have allocated an output VC, after checking that there is at least
one available output VC and with credits. Although they don't know which specific
output VC to check for availability and readiness (they will know only when VA1
that runs in parallel, finishes), checking the existence of at least one output VC
that satisfies both criteria is enough, since the same two-criteria qualify also the
candidates of VA1.

8.4.1 Handling the Speculative and the Non-speculative

Grants

Once the availability and readiness of the selected output VCs is checked for all flits
both switch allocators run in parallel. A grant from the speculative SA is considered
valid only when there is no other grant from the non-speculative SA referring to the
same input and output port. All invalid speculative grants are masked away and the
rest are kept and included in the final input-output SA match. Figure 8.5 a depicts
the switch allocator and its two subcomponents used in the case of speculative
VC-based router including also the masking logic of the speculative grants.
Masking of the invalid speculative grants is done in two steps. In the first step,
we need to identify the input-output pairs that have been matched by the non-
speculative switch allocator that produces always valid matches. Two bit vectors,
named grantInput and grantOutput are computed in parallel; grantInput .i / D
1 when the i th input has received a grant from the non speculative SA, and
grantOutput .j / D 1 when the j th output has been granted from the non-speculative
SA. Then, using the grantInput and the grantOutput bit vectors a 2D matrix of bits
is computed called the free matrix; free .i; j / D 1 when input i and output j have
not received a grant from the non-speculative SA. Therefore, the input-output pair
i; j is a candidate for accepting a grant from the speculative switch allocator. Using
the free matrix we can derive the final valid grants of the speculative SA as follows:
validSpecGrants .i; j / D

initialSpecGrants .i; j /.
Becker and Dally in ( 2009 ) observed that instead of waiting the non-speculative
SA to produce grants and mask afterwards the invalid grants of the non-speculative
SA, we can achieve the same result, if pessimistically, mask the speculative grants
with the corresponding non-speculative requests. The organization of the SA with
a pessimistic masking of the speculative grants is shown in Fig. 8.5 b. Using this
approach, we are allowed to compute the row- and column-wise reduction trees
for computing the free bits, in parallel with allocation, removing them from the
critical path. This pessimism makes sense at low network traffic, where a non-
speculative request is likely to be granted due to the low contention in the network.
As the network traffic increases more and more speculative grants are unnecessarily
masked by non-speculative requests that fail to produce a grant.
The grants returning from the VC allocator, the speculative and the non-
speculative switch allocator should be treated accordingly so that no output with

free .i; j / ^