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

excluding those output VCs that even if they are free do not have available credits
to host a new incoming flit.
The relative placement of VA1 with respect to switch allocation (SA) for the
implementation of combined allocation is discussed in the following paragraphs.

8.3.1 Combined Allocation with VA1 in Series to SA

The organization of the combined allocator that performs VA1 for each input VC in
series to the SA stage is shown in Fig. 8.3 a. Each input VC is searching in VA1 for an
output VC that is available and has at least one credit available. The input VCs that
managed to find an output VC that fulfills both criteria are eligible to participate
in SA1. SA1 accepts also the requests of those input VCs that have allocated an
output VC in the past and secured the existence of at least one available credit. The
winning input VC as in traditional SA passes its input request via a multiplexer to
the output stage of switch allocation (SA2). The grants of the per-output arbiters are
gathered per input and the existence of at least one grant for each input is computed
via an OR gate. Then, each input taking into account the grants of SA1 knows which
input VC (if any) has won in switch allocation. The grants per input VC have a dual
meaning: First it allows the flit to move to the output, and, at the same time, if it is a
head flit that has not allocated an output VC, to receive the output VC that has been
selected during VA1.

8.3.2 Combined Allocation with VA1 in Parallel to SA

In the previous paragraph before letting SA to begin, each input VC should select an
output VC to request, selecting one from the pool of available ones that had at least
one credit as well. The output VC that each input VC has selected after arbitration
(VA1) is not used before the end of SA2. Therefore, there is no reason for SA1
and SA2 to wait for VA1 to finish but can execute in parallel to it, as illustrated
in Fig. 8.3 b. The only information that each input VC needs in order to participate
in SA1 is that there is at least one output VC at the selected output port that is
available and with credits. There is no need the input VC to know which output
VC exactly fulfills the two criteria of availability and readiness. This will be found
during VA1 that executes in parallel to SA1 and SA2. Then, once SA2 decided
which VC won per input, if this winning input VC has not allocated yet an output
VC, it gets allocated in the same cycle to the output VC that was selected by VA1 in
parallel. This is needed only for the head flits that acquire an output VC at the same
time they win in SA. The rest flits keep the output VC that has been allocated to them
in previous cycle and actually participate only in the SA part of combined allocation.
In Kumar et al. ( 2007 ), a similar approach has been followed that does not include