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

Chapter 8
High-Speed Allocators for VC-Based Routers
The packets arriving to a VC-based router should allocate two kinds of resources
before being able to move to their destined output port. Each packet should allocate
an output VC and each flit should guarantee exclusive access to a router's output
port, on a cycle-by-cycle basis. The output VCs are allocated to the packets of the
input VCs during VC Allocation (VA), while Switch Allocation (SA) decides which
input VC will move to which output in each clock cycle. Both allocation operations
evolve in two steps.
For example, VA is split in two parts called VA1 and VA2. VA1 decides locally
the output VC that each input VC will ask for. In case that there are several candidate
output VCs, VA1 performs a local arbitration step and selects only one of them. Thus
after VA1 each input VC holds only one output VC request (the output port that the
output VC belongs to is known beforehand by routing computation). In a baseline
router organization, VA1 selects among output VC requests that are checked to be
available; an input VC will never ask for an output VC that is not currently available.
In a loosely coupled VA1 implementation, this availability check of output VCs is
not always necessary. In any case, after VA1, the second stage of VC allocation,
called VA2, is executed per output VC; each output VC receives at most one request
from each input VC and grants only them. After VA2, a match between input VCs
and output VCs has been derived that contains no conflicts. The matched output
VCs become un-available and the matching input VCs are set to a lock state using
the outVCLock state variables.
Equivalently, SA also evolves in two steps. In the first step, called SA1, one
input VC from each input is selected to try to reach the selected output port of the
router. Then, each output independent from the rest, in SA2, decides which input to
select. After SA1 and SA2 the winning flits move to their destined output port. The
movement is done via the per-input and per-output multiplexers that get configured
by the grants produced by SA1 and SA2, respectively. Before SA begins, it is
assumed that the input VCs have already allocated an output VC. This conservative
assumption can be removed with care and let packets that have not yet allocated an