72
Network-on-Chip
new header flit is received, the address decoder first processes that flit and then
sends the destination address to the port controller; this determines which
output port the packet should be delivered to. In the odd–even mode, there
can be more than one output direction to route packets. In this case, the port
controller will choose the direction in which the corresponding downstream
router has more empty slots in its input FIFO. Once the router has made its
decision on which direction to route, the port controller sends the connection
request to the crossbar arbiter in order to set up a path to the corresponding
output port. Except for the local input controller, each input port controller
also monitors its FIFO occupation ratio. If the ratio reaches the preset congestion threshold (~60%), a value of 1 will be asserted (indicating to the upstream
router that the downstream router is congested) on the corresponding congestion flag wire. Otherwise, a value of 0 will be asserted, indicating to the
upstream router that congestion is not an issue.
The crossbar arbiter maintains the status of the current crossbar connection
and determines whether to grant connection permission to the port controller. When there are multiple input port controllers request for the same available output port, the crossbar arbiter uses the first-come-first-served policy
to decide which input port to grant the access, such that the starvation at a
particular port can be avoided.
The mode controller continuously monitors its neighboring congestion to
determine if the deterministic or the adaptive routing mode needs to be
used. Although more advanced techniques can be used to determine the
optimal routing mode, we use the following simple policy: if any congestion
flag from its neighboring routers is asserted, then the mode controller commands all the input port controllers to work in the adaptive (odd–even) mode;
otherwise, it switches the port controllers to the deterministic (oe-fixed) mode.
It has been observed in simulation that XY routing performs better than
both odd–even and DyAD–OE routing under uniform traffic load. The reason
why XY performs best under uniform traffic is because it embodies global,
long-term information about this traffic pattern. However, the adaptive algorithms select the routing paths based on local, short-term information. This
type of decision benefits only the packets in the immediate future, which
tend to interfere with other packets. Thus, the evenness of uniform traffic is
not necessarily maintained in the long run. However, for most of the applications in the real world, each node will communicate with some nodes more
frequently compared to others. XY routing has serious problems in dealing
with such nonuniform traffic patterns because of its determinism. More precisely, XY routing blindly maintains the unevenness of the nonuniform traffic, just as it maintains the evenness for the uniform traffic. In this scenario,
XY routing is clearly outperformed by odd–even and DyAD–OE under transpose1 traffic. It has been observed in simulation that odd–even and DyAD–OE
have 53.3% and 61.7% improvement over XY, respectively, in terms of sustainable throughput. In fact, for the same traffic pattern and injection rate,
DyAD–OE achieves shorter average packet latency compared to odd–even
Network-on-Chip
new header flit is received, the address decoder first processes that flit and then
sends the destination address to the port controller; this determines which
output port the packet should be delivered to. In the odd–even mode, there
can be more than one output direction to route packets. In this case, the port
controller will choose the direction in which the corresponding downstream
router has more empty slots in its input FIFO. Once the router has made its
decision on which direction to route, the port controller sends the connection
request to the crossbar arbiter in order to set up a path to the corresponding
output port. Except for the local input controller, each input port controller
also monitors its FIFO occupation ratio. If the ratio reaches the preset congestion threshold (~60%), a value of 1 will be asserted (indicating to the upstream
router that the downstream router is congested) on the corresponding congestion flag wire. Otherwise, a value of 0 will be asserted, indicating to the
upstream router that congestion is not an issue.
The crossbar arbiter maintains the status of the current crossbar connection
and determines whether to grant connection permission to the port controller. When there are multiple input port controllers request for the same available output port, the crossbar arbiter uses the first-come-first-served policy
to decide which input port to grant the access, such that the starvation at a
particular port can be avoided.
The mode controller continuously monitors its neighboring congestion to
determine if the deterministic or the adaptive routing mode needs to be
used. Although more advanced techniques can be used to determine the
optimal routing mode, we use the following simple policy: if any congestion
flag from its neighboring routers is asserted, then the mode controller commands all the input port controllers to work in the adaptive (odd–even) mode;
otherwise, it switches the port controllers to the deterministic (oe-fixed) mode.
It has been observed in simulation that XY routing performs better than
both odd–even and DyAD–OE routing under uniform traffic load. The reason
why XY performs best under uniform traffic is because it embodies global,
long-term information about this traffic pattern. However, the adaptive algorithms select the routing paths based on local, short-term information. This
type of decision benefits only the packets in the immediate future, which
tend to interfere with other packets. Thus, the evenness of uniform traffic is
not necessarily maintained in the long run. However, for most of the applications in the real world, each node will communicate with some nodes more
frequently compared to others. XY routing has serious problems in dealing
with such nonuniform traffic patterns because of its determinism. More precisely, XY routing blindly maintains the unevenness of the nonuniform traffic, just as it maintains the evenness for the uniform traffic. In this scenario,
XY routing is clearly outperformed by odd–even and DyAD–OE under transpose1 traffic. It has been observed in simulation that odd–even and DyAD–OE
have 53.3% and 61.7% improvement over XY, respectively, in terms of sustainable throughput. In fact, for the same traffic pattern and injection rate,
DyAD–OE achieves shorter average packet latency compared to odd–even