204
Network-on-Chip
affect the noise margins and compromises the signal integrity of the design.
Therefore, special attention should be taken to resolve the IR drop effects
during post-layout phase.
7.3 Permanent Fault Controlling Techniques
Permanent faults, at one level, are modeled as stuck-at faults, or as fail-stop
faults. In the stuck-at fault, a node is stuck at either logic 0 or logic 1. In the failstop model, a complete module (router or link) malfunctions and informs its
neighbors about its out-of-order status (Dally and Towles 2004). Triple modular redundancy (TMR) is a well-known technique to handle stuck-at faults at
links in which the faulty link, its two duplicate copies, and a voter are used
to ensure protection against such errors.
In NoC, FIFOs are designed as either register based or SRAM based.
For SRAM-based FIFOs, if any cell or row is permanently faulty, it can be
repaired by a built-in self-repair (BISR) mechanism using redundant rows
and columns (Wang et al. 2006). The detailed architecture of a BISR-based
SRAM is beyond the scope of this book. Although physical faults are not as
common and frequent as transient faults on-chip, in case a component fails,
it is not always possible to repair or replace it on chip. In such a case, it is
important to reroute the packets on alternate paths so that the communication infrastructure remains intact. Hence, to overcome the permanent faults,
NoC must have to support adaptive (or dynamic) routing to avoid the faulty
regions of the network and choose alternative paths dynamically. The main
idea is to keep the chip in functioning state with graceful degradation of
performance in the presence of faults.
Valinataj et al. (2009) proposed a deterministic, low-cost, deadlock-free,
faulty-link-tolerant routing algorithm through dynamic reconfiguration to
use new unique paths instead of the broken paths. For router permanent
faults, Linder and Harden (1991) used a virtual channel (VC)-based faulttolerant routing in two-dimensional (2D) mesh. Since the use of VC leads
to more area and power consumption, several literatures have addressed
fault-tolerant routing algorithms without using VCs. The packets are routed
through alternate paths either by using a turn model (Chen and Chiu 1998;
Fukushima et al. 2009; Glass and Ni 1996; Wu 2003) or by updating the
routing table (Ali et al. 2007a; Fick et al. 2009), so that the communication
infrastructure remains intact. Patooghy and Miremadi (2009) proposed a
deadlock-free XYX routing for handling permanent faults in NoC. It makes a
redundant copy of each packet at the source node and exploits two different
routing algorithms, XY and YX, to route the original and redundant packets,
respectively. Since two copies of each packet are received by the destination
router, the erroneous packet is detected and replaced with the correct one.
Network-on-Chip
affect the noise margins and compromises the signal integrity of the design.
Therefore, special attention should be taken to resolve the IR drop effects
during post-layout phase.
7.3 Permanent Fault Controlling Techniques
Permanent faults, at one level, are modeled as stuck-at faults, or as fail-stop
faults. In the stuck-at fault, a node is stuck at either logic 0 or logic 1. In the failstop model, a complete module (router or link) malfunctions and informs its
neighbors about its out-of-order status (Dally and Towles 2004). Triple modular redundancy (TMR) is a well-known technique to handle stuck-at faults at
links in which the faulty link, its two duplicate copies, and a voter are used
to ensure protection against such errors.
In NoC, FIFOs are designed as either register based or SRAM based.
For SRAM-based FIFOs, if any cell or row is permanently faulty, it can be
repaired by a built-in self-repair (BISR) mechanism using redundant rows
and columns (Wang et al. 2006). The detailed architecture of a BISR-based
SRAM is beyond the scope of this book. Although physical faults are not as
common and frequent as transient faults on-chip, in case a component fails,
it is not always possible to repair or replace it on chip. In such a case, it is
important to reroute the packets on alternate paths so that the communication infrastructure remains intact. Hence, to overcome the permanent faults,
NoC must have to support adaptive (or dynamic) routing to avoid the faulty
regions of the network and choose alternative paths dynamically. The main
idea is to keep the chip in functioning state with graceful degradation of
performance in the presence of faults.
Valinataj et al. (2009) proposed a deterministic, low-cost, deadlock-free,
faulty-link-tolerant routing algorithm through dynamic reconfiguration to
use new unique paths instead of the broken paths. For router permanent
faults, Linder and Harden (1991) used a virtual channel (VC)-based faulttolerant routing in two-dimensional (2D) mesh. Since the use of VC leads
to more area and power consumption, several literatures have addressed
fault-tolerant routing algorithms without using VCs. The packets are routed
through alternate paths either by using a turn model (Chen and Chiu 1998;
Fukushima et al. 2009; Glass and Ni 1996; Wu 2003) or by updating the
routing table (Ali et al. 2007a; Fick et al. 2009), so that the communication
infrastructure remains intact. Patooghy and Miremadi (2009) proposed a
deadlock-free XYX routing for handling permanent faults in NoC. It makes a
redundant copy of each packet at the source node and exploits two different
routing algorithms, XY and YX, to route the original and redundant packets,
respectively. Since two copies of each packet are received by the destination
router, the erroneous packet is detected and replaced with the correct one.