Information Technology Reference
In-Depth Information
providing a valid output. These bit enable non-minimal paths to avoid internal failure
inside the 2D mesh.
4
Proposed Method: FADAR-LBDR
Proposed method is motivated by DyAD [5] routing scheme. Similar to the previ-
ous scheme our approach integrates deterministic and adaptive routing schemes to
avoid congestion. Deterministic and Adaptive routing algorithms are implemented with
LBDR resulting in table less network even in presence of faults. Overview of our
proposed method is shown in Figure 2.b.
- Deterministic and adaptive routing algorithms are selected such that they work to-
gether without creating deadlock and livelock situations.
- As the routing implementation is LBDR, routing and connectivity bits of each
router are calculated and set prior to the normal operation. Deroute bits are also
computed for the adaptive routing.
- Initial mode of a router is selected according to its congestion level. If it is low, it
works in deterministic mode. But if congestion is low, and output port supplied by
deterministic routing logic is faulty (connectivity bits corresponding to that output
port is set to 0) then that port is rejected and routing mode shifts from determinis-
tic to adaptive mode. If alternative minimal path generated by adaptive mode also
encounters a failure, it will use deroute bit to avoid failures by routing packets
non-minimally.
- If the congestion level of current router is high then it remains in adaptive mode
and gives the output port which is not faulty and uses deroute bit when required.
4.1
Deadlock and Livelock Avoidance
FADAR algorithm combines two routing algorithms into one. Each routing algorithm
is deadlock-free by itself as the channel dependence graph (CDG) is acyclic, however,
the combination of both may introduce additional dependencies which could create cy-
cles. For this reason, we need to restrict transitions between both algorithms. Proposed
method uses two different sets of virtual channels (VC), one for deterministic routing
and other for adaptive routing as shown in Figure 2.a. One way to use both algorithms
is by relying on an acyclic escape path implemented by OE. In this sense, XY algo-
rithm is used normally and when congestion is detected the message is injected into the
OE virtual channel, following OE routing rules until the message reaches final desti-
nation. Therefore, transitions from OE to XY are not allowed. The overall algorithm is
deadlock-free since the CDG of the OE layer is still acyclic. However, this restriction
may affect performance as the OE layer can be overloaded. One way to relax the OE
layer is to allow transitions to the XY layer. This can be achieved in networks with
virtual-cut-through switching (VCT) and by guaranteeing the OE layer will be always
available. That is, one message located in the OE layer can request both the XY virtual
channel at the next hop and the OE virtual channel at the next hop. If the XY virtual
channel is full, then the OE virtual channel can be selected. In wormhole, as messages
can be blocked along multiple queues, transition to the XY layer should be prevented.
