Hardware Reference
In-Depth Information
matched input-output pairs is augmented with new matchings. Pipelining between
iterations is a viable alternative (Gupta and McKeown
1999
), however a more
scalable solution is desirable.
Instead of letting a different input VC to connect to an output in each cycle,
other allocation strategies try to prolong the duration of an input and output
match by letting whole flows of packets to pass before changing the connec-
tion (Michelogiannakis et al.
2011
;Maetal.
2012
). This approach allows for full
output utilization for many cycles but may create starvation phenomena. The main
implementation strategy for this exhaustive-like scheduling approach, involves some
form of weighted arbitration that is biased in favor of certain input-output pairs that
correspond to heavily backlogged flows (Ramabhadran and Pasquale
2003
;Abts
and Weisser
2007
).
Switch Allocation in the Case of Adaptive Routing
The presented organization of the SA unit assumed that each input VC will never
ask for more than one output port. In the case of adaptive routing this may not
be the case and the adaptive routing algorithm may allow each input VC to select
more than one possible output ports. In this case, SA1 and SA2 do not suffice for
completing the switch allocation process and an additional selection step is needed.
The additional selection steps can be done either at the beginning of SA letting each
input VC to select one candidate output port or at the end. The selection unit (not
shown in Fig.
7.11
) either picks randomly a destination or decides after sensing the
state of the network (Ascia et al.
2008
) and taking into account other network-level
criteria such as load balancing the traffic throughout the network or offering quality
of service guarantees.
7.3
VA and SA Built with Centralized Allocators
Besides separable allocation strategies that implement the allocation process sepa-
rately per input (or per input VC) and per output (or per output VC), VA and SA can
be built in a centralized manner that solves allocation at once by actually merging
input and output arbitration phases in one merged step.
A centralized allocator of N requesters and N resources receives the corre-
sponding requests in a matrix form. Each row of the matrix corresponds to the
requests of one requester that can ask for multiple resources. Equivalently, each
column of the request matrix corresponds to one resource that can accept multiple
requests. A valid schedule should contain at most a single 1 per row and per column
guaranteeing in this way a unique requester-resource connection. A centralized
allocator does not examine the requests independently per row and per column
as done by the separable allocators but solves the problem concurrently for many
requester-resource pairs. The request-resource pairs that can be matched at once
Search WWH ::
Custom Search