Information Technology Reference
In-Depth Information
is affected by several design choices like topology, switching mechanism, and routing
algorithms. In NoC, 2D mesh is the most common topology for constructing massively
parallel multi-processors.
The routing algorithm [3] determines the path (sequence of channels) a packet should
take to reach destination node. It can be deterministic where a fixed path is always cho-
sen without considering the current network status or adaptive, where multiple paths
can be generated and final path is selected based on current network status. Adaptive-
ness of a routing algorithm can used to handle the network congestion by avoiding the
congested path. Most prominent characteristic of a routing algorithm is that it should be
deadlock and livelock free. Recently, to handle faults present in on chip network, fault
tolerance in routing algorithm is also considered as main issue to deal with [4]. Fault
tolerance is the ability of the routing algorithm to work around the presence of failed
components.
The primary focus of this paper is to address the fault tolerance in NoC using a
fault tolerant routing algorithm. We propose a novel Fault Aware Dynamic Adaptive
Routing using LBDR (FADAR-LBDR), an extension of Dynamic ADaptive (DyAD)
routing algorithm [5]. Experimental results show the effectiveness of FADAR-LBDR
algorithm even in presence of multiple link failures.
Rest of the paper is organised as follows: Section 2 discusses the related work in
fault tolerance. Section 3 discusses DyAD approach. Section 4 shows Logic based Dis-
tributed Routing (LBDR), a routing implementation in NoC. Section 5 presents our
proposed method. Experimental setup is presented in Section 6. Result analysis and
future remarks are given in Section 7.
2
Related Work
In [6], Duato
et al
have shown how faults in the network affect the two main characteris-
tic of the routing algorithm i.e freedom from deadlock and livelock. They also presented
various definitions related to fault tolerant routing algorithm and defined common fault
models use to design fault tolerant routing algorithm. Fault tolerant routing in SAF,
VCT and Wormhole- switched networks is also presented in detail.
Glass and Ni [7] presented a method of designing dynamic fault-tolerant wormhole
routing algorithms using turn model [8] without using virtual channels. They modified
turn based negative first routing algorithm to use non-minimal paths and made it tol-
erate (
n
1) faults in n-dimensional meshes. Ali
et al
[9] presented two most popular
dynamic routing algorithms, Distance vector routing and Link state Routing from off-
chip interconnects. Based on above routing algorithms author proposed one dynamic
fault tolerant algorithm which is a modified version of link state routing.
Based on local information of faults Boppana and Chalasani [10] presented the issue
of fault-tolerance into fully-adaptive and deterministic wormhole routing algorithms.
They used block fault model where faults consist of rectangular region and fault rings
and fault-chains are incorporated to route the messages around faulty-regions.
−
