Hardware Reference
In-Depth Information
routing algorithm and the ID of the current router. In this way, request generation,
arbitration and multiplexing should wait first RC to complete before being executed.
This serial dependency can be removed if the head flit carries the output port request
for the current router in parallel to the destination address. Allowing such behavior
requires the head flit to compute the output port request before arriving at the current
router using lookahead routing computation. Lookahead routing computation (LRC)
was first employed in the SGI Spider switch (Galles 1997 ), and extended to adaptive
routing algorithms in Vaidya et al. ( 1999 ).
The implementation of LRC can take many forms. In the traditional case without
any lookahead in RC, shown in Fig. 3.17 , each input port first executes RC and then
continues with the rest operations of the router. In this case, the RC unit of input X
selects to which outputs, A, B, or C, the arriving packets should move. Then, once
the packet arrived to the input of the next router it would repeat RC computation
for moving closer to its destination. Instead of implementing RC after a head flit
has arrived at the input buffer, we can change the order of execution and implement
a
b
RC
X
pre-calculate destination
when traversing the link
destination already
known - no need to wait
need to wait for RC result
before moving forward
X
X
RC
A
RC
C
A
C
A
RC
X
C
RC
C
RC
A
RC
B
B
RC
B
B
c
RC unit for every
possible destination
dst
RC
A
RC
B
RC
C
outPort
X
A B C
next outPort
replace
outPort field
A
C
B
Fig. 3.17 ( a ) Baseline RC placement, ( b ) Lookahead RC in parallel to Link traversal, and ( c )the
implementation of Lookahead RC at each input port that runs in parallel to arbitration and uses
multiple routing computation units one for each possible output port
 
Search WWH ::




Custom Search