Baseline Switching Modules and Routers - Microarchitecture of Network-on-Chip Routers - page 53

Output
X+

Requests

Dst
1
2

0 1 0 0
0 0 1 0 Y-

Y+

Packet's
Destination

X- 1 0 0 0

X- X+

N

Router

Y-

Fig. 3.15 Routing computation at each router is just a translation of the packet's final destination
to a local output port request

they will reach from there their destination. Misrouting actually does not resolve
contention, but spreads it in space (in the network), while the baseline approach
spreads contention in time by allocating one output to one input in each clock
cycle (Moscibroda and Mutlu 2009 ).
Up to now we assumed that the packets arriving at the input of a router knew
beforehand their selected output port. In the case of a larger network, each packet
will pass through many routers before reaching its final destination. Therefore, a
mechanism is required that will inform the packet which output to follow at each
intermediate router, in order to get closer to its destination. This mechanism is
called routing computation. Routing computation implements the routing algorithm
that is a network wide operation, and manages the paths that the packets should
follow when travelling in the network. Consequently, each router should respect
the properties of the routing algorithm and forward the incoming packets to the
appropriate output following the path decided by the routing algorithm (Duato et al.
1997 ).
For routing computation to work, each packet that travels in the network should
provide to the router some form of addressing information. In the case of source
routing, the packet knows the exact path to its destination beforehand. The head
flit of each incoming packet contains the id of the output port that it is destined to
and the router just performs the connection. On the opposite case, when distributed
routing is employed, the packet carries at its head flit only the address of the
destination node. Selecting the appropriate output is a responsibility of the router
that should translate the packet's destination address to a local output port request,
as shown in Fig. 3.15 . The selection of the appropriate output port is a matter of the
routing algorithm that governs the flow of information in the network as a whole but
it is implemented in a distributed manner by the routers of the network.
Integrating routing computation logic in the routers is simple. In the simplest case
of source routing each packet knows the exact path to its destination and has already
stored the turns (output ports) that should follow at each router of the network. In
this scenario, the head flit of each packet already holds the request vector needed
at each router. Once the head flit reaches the frontmost position of the buffer the
corresponding bits of the header are matched directly with the outPort wires of