A Survey on Design Approaches to Circumvent Permanent Faults in Networks-on-Chip
---
paper_title: Methods for fault tolerance in networks-on-chip

paper_content:

Networks-on-Chip constitute the interconnection architecture of future, massively parallel multiprocessors that assemble hundreds to thousands of processing cores on a single chip. Their integration is enabled by ongoing miniaturization of chip manufacturing technologies following Moore's Law. It comes with the downside of the circuit elements' increased susceptibility to failure. Research on fault-tolerant Networks-on-Chip tries to mitigate partial failure and its effect on network performance and reliability by exploiting various forms of redundancy at the suitable network layers. The article at hand reviews the failure mechanisms, fault models, diagnosis techniques, and fault-tolerance methods in on-chip networks, and surveys and summarizes the research of the last ten years. It is structured along three communication layers: the data link, the network, and the transport layers. The most important results are summarized and open research problems and challenges are highlighted to guide future research on this topic.
---
paper_title: TILE64 - Processor: A 64-Core SoC with Mesh Interconnect

paper_content:

The TILE64TM processor is a multicore SoC targeting the high-performance demands of a wide range of embedded applications across networking and digital multimedia applications. A figure shows a block diagram with 64 tile processors arranged in an 8x8 array. These tiles connect through a scalable 2D mesh network with high-speed I/Os on the periphery. Each general-purpose processor is identical and capable of running SMP Linux.
---
paper_title: A Distributed Run-Time Environment for the Kalray MPPA®-256 Integrated Manycore Processor☆

paper_content:

Abstract The Kalray MPPA®-256 is a single-chip manycore processor that integrates 256 user cores and 32 system cores in 28 nm CMOS technology. These cores are distributed across 16 compute clusters of 16+1 cores, and 4 quad-core I/O subsystems. Each compute cluster and I/O subsystem owns a private address space, while communication and synchronization between them is ensured by data and control Networks-on-Chip (NoC). This processor targets embedded applications whose program- ming models fall within the following classes: Kahn Process Networks (KPN), as motivated by media processing; single program multiple data (SPMD), traditionally used for numerical kernels; and time-triggered control systems. We describe a run-time environment that supports these classes of programming models and their composition. This environment combines classic POSIX single-process multi-threaded execution inside the compute clusters and I/O subsystems, with a set of specific Inter-Process Communication (IPC) primitives that exploit the NoC architecture. We combine these primitives in order to provide the run-time support for the different target programming models. Interestingly enough, all these NoC-specific IPC primitives can be mapped to a subset of the classic synchronous and asynchronous POSIX file descriptor operations. This design thus extends the canonical ‘pipe-and-filters’ software component model, where POSIX processes are the atomic components, and IPC instances are the connectors.
---
paper_title: Methods for fault tolerance in networks-on-chip

paper_content:

Networks-on-Chip constitute the interconnection architecture of future, massively parallel multiprocessors that assemble hundreds to thousands of processing cores on a single chip. Their integration is enabled by ongoing miniaturization of chip manufacturing technologies following Moore's Law. It comes with the downside of the circuit elements' increased susceptibility to failure. Research on fault-tolerant Networks-on-Chip tries to mitigate partial failure and its effect on network performance and reliability by exploiting various forms of redundancy at the suitable network layers. The article at hand reviews the failure mechanisms, fault models, diagnosis techniques, and fault-tolerance methods in on-chip networks, and surveys and summarizes the research of the last ten years. It is structured along three communication layers: the data link, the network, and the transport layers. The most important results are summarized and open research problems and challenges are highlighted to guide future research on this topic.
---
paper_title: Low-cost fault-tolerant switch allocator for network-on-chip routers

paper_content:

Reliable operation that can be checked on-line is of paramount importance to current and future systems-on-chips that are implemented in very deep submicron technologies. In such systems, the communication among architectural modules is handled by a modular network-on-chip infrastructure that should be sufficiently protected from transient faults that may affect its correct operation. The error protection mechanism should cover all fault scenarios and incur the minimum area/energy/delay overhead. In this paper, we propose such an on-line checking mechanism for the switch allocator of the router that detects every possible single transient or permanent fault in the arbiters and handles it appropriately, thus preserving the reliable operation of the switch.
---
paper_title: Exploiting Network-on-Chip structural redundancy for a cooperative and scalable built-in self-test architecture

paper_content:

This paper proposes a built-in self-test/self-diagnosis procedure at start-up of an on-chip network (NoC). Concurrent BIST operations are carried out after reset at each switch, thus resulting in scalable test application time with network size. The key principle consists of exploiting the inherent structural redundancy of the NoC architecture in a cooperative way, thus detecting faults in test pattern generators too. At-speed testing of stuck-at faults can be performed in less than 1200 cycles regardless of their size, with an hardware overhead of less than 11%.
---
paper_title: Formally enhanced runtime verification to ensure NoC functional correctness

paper_content:

As silicon technology scales, modern processors and embedded systems are rapidly shifting towards complex chip multi-processor (CMP) and system-on-chip (SoC) designs, comprising several processor cores and IP components communicating via a network-on-chip (NoC). As a side-effect of this trend, ensuring their correctness has become increasingly problematic. In particular, the network-on-chip often includes complex features and components to support the required communication bandwidth among the nodes in the system. In this landscape, it is no wonder that design errors in the NoC may go undetected and escape into the final silicon, with potential detrimental impact on the overall system. In this work, we propose ForEVeR, a solution that complements the use of formal methods and runtime verification to ensure functional correctness in NoCs. Formal verification, due to its scalability limitations, is used to verify the smaller modules, such as individual router components. We complete the protection against escaped design errors with a runtime technique, a network-level error detection and recovery solution, which monitors the traffic in the NoC and protects it against escaped functional bugs that affect the communication paths in the network. To this end, ForEVeR augments the baseline NoC with a lightweight checker network that alerts destination nodes of incoming packets ahead of time. If a bug is detected, flagged by missed packet arrivals, a recovery mechanism delivers the in-flight data safely to the intended destination via the checker network. ForEVeR's experimental evaluation shows that it can recover from NoC design errors at only 4.8% area cost for an 8x8 mesh interconnect, with a recovery performance cost of less than 30K cycles per functional bug manifestation. Additionally, it incurs no performance overhead in the absence of errors.
---
paper_title: The Turn Model for Adaptive Routing

paper_content:

We present a model for designing wormhole routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive. A unique feature of this model is that it is not based on adding physical or virtual channels to network topologies (though it can be applied to networks with extra channels). Instead, the model is based on analyzing the directions in which packets can turn in a network and the cycles that the turns can form. Prohibiting just enough turns to break all of the cycles produces routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive for the network. In this paper, we focus on the two most common network topologies for wormhole routing, n-dimensional meshes and k-ary n-cubes, without extra channels. In an n-dimensional mesh, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns permit partial adaptiveness in routing. Partially adaptive routing algorithms are described for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations of partially adaptive and nonadaptive routing algorithms for 2D meshes and hypercubes show that which algorithm has the lowest latencies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, partially adaptive routing algorithms perform better than nonadaptive ones.
---
paper_title: A highly resilient routing algorithm for fault-tolerant NoCs

paper_content:

Current trends in technology scaling foreshadow worsening transistor reliability as well as greater numbers of transistors in each system. The combination of these factors will soon make long-term product reliability extremely difficult in complex modern systems such as systems on a chip (SoC) and chip multiprocessor (CMP) designs, where even a single device failure can cause fatal system errors. Resiliency to device failure will be a necessary condition at future technology nodes. In this work, we present a network-on-chip (NoC) routing algorithm to boost the robustness in interconnect networks, by reconfiguring them to avoid faulty components while maintaining connectivity and correct operation. This distributed algorithm can be implemented in hardware with less than 300 gates per network router. Experimental results over a broad range of 2D-mesh and 2D-torus networks demonstrate 99.99% reliability on average when 10% of the interconnect links have failed.
---
paper_title: A Lightweight Fault-Tolerant Mechanism for Network-on-Chip

paper_content:

Survival capability is becoming a crucial factor in designing multicore processors built with on-chip packet networks, or networks on chip (NoCs). In this paper, we propose a lightweight fault-tolerant mechanism for NoCs based on default backup paths (DBPs) designed to maintain, in the presence of failures, network connectivity of both non-faulty routers as well as healthy processor cores which may be connected to faulty routers. The mechanism provides default paths as backup between certain router ports which serve as alternative datapaths to circumvent failed components within a faulty router. Along with a minimal subset of normal network channels, the set of default backup paths internal to faulty routers form - in the worst case - a unidirectional ring topology that provides network-wide connectivity to all processor cores. Routing using the DBP mechanism is proved to be deadlock-free with only two virtual channels even for fault scenarios in which regular networks degrade to irregular (arbitrary) topologies. Evaluation results show that, for a 2-D mesh wormhole NoC, only 12.6% additional hardware resources are needed to implement the proposed DBP mechanism in order to provide graceful performance degradation without chip-wide failure as the number of faults increases to the maximum needed to form ring.
---
paper_title: A Fault-Tolerant and Deadlock-Free Routing Protocol in 2-D Meshes Based on Odd-Even Turn Model

paper_content:

We propose a deterministic fault-tolerant and deadlock-free routing protocol in two-dimensional (2D) meshes based on dimension-order routing and the odd-even turn model. The proposed protocol, called extended X-Y routing, does not use any virtual channels by prohibiting certain locations of faults and destinations. Faults are contained in a set of disjointed rectangular regions called faulty blocks. The number of faults to be tolerated is unbounded as long as nodes outside faulty blocks are connected in the 2D mesh network. The extended X-Y routing can also be used under a special convex fault region called an orthogonal faulty block, which can be derived from a given faulty block by activating some nonfaulty nodes in the block. Extensions to partially adaptive routing, traffic and adaptivity-balancing using virtual networks, and routing without constraints using virtual channels and virtual networks are also discussed.
---
paper_title: Fault-tolerant wormhole routing algorithms in meshes in the presence of concave faults

paper_content:

A fault ring is a connection of only nonfaulty adjacent nodes and links such that the interior of the ring contains only faulty components. This paper proposes two wormhole routing algorithms that deal with more relaxed shapes of fault rings than previously known algorithms in the mesh networks. As a result, the number of components to be made disabled would be reduced considerably in some cases. First algorithm, called F4, uses four virtual channels and allows all four sides of fault rings to contain concave shapes. Second algorithm, F3, permits up to three sides to contain concave shapes using only three virtual channels. Both F3 and F4 are free of deadlock and livelock and guarantee the delivery of messages between any pair of nonfaulty and connected nodes in the network.
---
paper_title: Vicis: A reliable network for unreliable silicon

paper_content:

Process scaling has given designers billions of transistors to work with. As feature sizes near the atomic scale, extensive variation and wearout inevitably make margining uneconomical or impossible. The ElastIC project seeks to address this by creating a large-scale chip-multiprocessor that can self-diagnose, adapt, and heal. Creating large, flexible designs in this environment naturally lends itself to the repetitive nature of network-on-chip (NoC), but the loss of a single link or router will result in complete network failure. In this work we present Vicis, an ElastIC-style NoC that can tolerate the loss of many network components due to wearout induced hard faults. Vicis uses the inherent redundancy in the network and its routers in order to maintain correct operation while incurring a much lower area overhead than previously proposed N-modular redundancy (NMR) based solutions. Each router has a built-in-self-test (BIST) that diagnoses the locations of hard fault and runs a number of algorithms to best use ECC, port swapping, and a crossbar bypass bus to mitigate them. The routers work together to run distributed algorithms to solve network-wide problems as well, protecting the networking against critical failures in individual routers. In this work we show that with stuck-at fault rates as high as 1 in 2000 gates, Vicis will continue to operate with approximately half of its routers still functional and communicating.
---
paper_title: Tackling Permanent Faults in the Network-on-Chip Router Pipeline

paper_content:

The proliferation of multi-core and many-core chips for performance scaling is making the Network-on-Chip (NoC) occupy a growing amount of silicon area spanning several metal layers. The NoC is neither immune to hard faults and transient faults nor unaffected by the adverse increase in hard faults caused by technology scaling. The ramifications for the NoC are immense: a single fault in the NoC may paralyze the working of the entire chip. To this end, we propose a Permanent Fault Tolerant Router (PFTR) that is capable of tolerating multiple permanent faults in the pipeline. PFTR is designed by making architectural modifications to individual pipeline stages of the baseline NoC router. These architectural modifications involve adding minimum extra circuitry and exploiting temporal parallelism to accomplish fault tolerance. Tolerance of multiple faults is achieved by striking a balance between three important design factors namely, area overhead, power overhead and reliability. We use Silicon Protection Factor (SPF) as the reliability metric to assess the reliability improvement of the proposed architecture. SPF takes into account the number of faults required to cause failure and the area overhead of the additional circuitry to evaluate reliability. SPF calculation reveals that the proposed PFTR is 11 times more reliable than the baseline NoC router. Synthesis results using Cadence Encounter RTL Compiler at 45nm technology show that the additional circuitry adds an area overhead of 31% and power overhead of 30% with respect to the baseline NoC router. PFTR provides much better reliability with much less overhead as compared to other fault tolerant routers such as BulletProof, Vicis and RoCo [15].
---
paper_title: Network-on-Chip (NoC) Topologies and Performance: A Review

paper_content:

With the development of integration technology, System-on-Chip (SoC), composed of heterogeneous cores on a single chip, has entered the billion-transistor era. As the microprocessor industry moves from single-core to multi-core, and eventually to many-core architectures, containing tens to hundreds of similar cores arranged on a single multiprocessor chip requires efficient communication among processors. A highperformance, flexible, scalable, and design-friendly interconnection architecture is highly desired for modern SoC and microprocessor designs. How to provide efficient communication poses a challenge to both academia and industry. Before the advent of Network-on-Chip (NoC), interconnection architectures were usually based on dedicated wires or shared buses. However, they cannot meet the ever-increasing demand from the onchip systems due to the lack of scalability. NoC has been proposed as a highly structured and scalable solution to address the communication problems in on-chip systems. NoC has several advantages over dedicated wiring and buses, e.g., highbandwidth, low-latency, low-power consumption and scalability. Messages are transported back and forth via the interconnection networks. Thus, the interconnections among multiple cores on a chip have a significant impact on communication and performance of the chip design in terms of end-to-end delay, throughput, and packets loss ratio. Therefore, it is worthwhile studying the different characteristics of different topologies. In this paper, we review the most popular topologies and also some recent topologies for interconnection networks. We study their performance and summarize their strengths and limitations.
---
paper_title: A recursively construction scheme for super fault-tolerant hamiltonian graphs

paper_content:

Abstract For the interconnection network topology, it is usually represented by a graph. When a network is used, processors and/or links faults may happen. Thus, it is meaningful to consider faulty networks. We consider k -regular graphs in this paper. We define a k -regular hamiltonian and hamiltonian connected graph G is super fault-tolerant hamiltonian if G remains hamiltonian after removing at most k − 2 vertices and/or edges and remains hamiltonian connected after removing at most k − 3 vertices and/or edges. A super fault-tolerant hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity . The aim of this paper is to investigate a construction scheme to construct various super fault-tolerant hamiltonian graphs. Along the way, the recursive circulant graph is a special case of our construction scheme, and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained.
---
paper_title: Scalable and fault-tolerant network-on-chip design usingthe quartered recursive diagonal torus topology

paper_content:

Network-on-a-chip (NoC) is an effective approach to connect and manage the communication between the variety of design elements and intellectual property blocks required in large and complex system-on-chips. In this paper, we propose a new NoC architecture, referred as the Quartered Recursive Diagonal Torus (QRDT), which is constructed by overlaying diagonal torus. Due to its small diameter and rich routing recourses, QRDT is determined to be well suitable to construct highly scalable NoCs. In QRDT, data packets can be routed through a proposed minimal routing algorithm based on the Johnson codes that have traditionally been used in finite state machine designs. It has been shown that this proposed routing algorithm with minor modifications is capable of handling the single link/node failure. The hardware cost of the proposed QRDT architecture and its associated routing algorithm is revealed by designing two QRDT routers which have been synthesized using TSMC 0.18¼m CMOS technology.
---
paper_title: A torus assignment for an interconnection network recursive diagonal torus

paper_content:

Recursive Diagonal Torus (RDT) is a class of interconnection network consisting of recursively overlaid two-dimensional square diagonal tori for massively parallel computers, with up to 216 nodes. Connection structures of the RDT vary according to the assignment of upper rank diagonal tori into a node. Although traditional simple assignment called RDT(2,4,1)//spl alpha/ shows enough performance under the uniform traffic, the congestion of low rank tori degrades the performance when local communication is dominant. RDT(2,4,1)//spl beta/ torus assignment is proposed, focusing on improving the performance for local communication. With a simplified simulation algorithm, the result shows that RDT(2,4,1)//spl beta/ improves the average distance compared with RDT(2,4,1)//spl alpha/ assignment when considering local area.
---
paper_title: Fault-tolerant routing in A PRDT(2,1)-based NoC

paper_content:

Fault tolerance is one of the most dominant issues for NoC systems. This paper presents a new fault tolerant routing algorithm for a network topology PRDT(2,1). The proposed algorithm converts a fault region into a rectangular in shape without disabling a large number of non-faulty nodes. It provides strong self-adaptability while utilizing as few virtual channels as possible. As a result, the connection keeps unchanged only if the network does not break by fault regions. In addition, it has been shown that the proposed algorithm can guarantee the connection and the deadlock-free of the network. The result of simulation shows that the proposed routing algorithm is of feasibility of gracefully degraded operation
---
paper_title: A RDT-based interconnection network for scalable network-on-chip designs

paper_content:

The interconnection network plays an important role in the performance and energy consumption of a network-on-chip (NoC) system. In this paper, we propose a RDT(2,2,1)//spl alpha/-based interconnection network for NoC designs. RDT(2,2,1)//spl alpha/ is constructed by recursively overlaying 2D diagonal meshes (torus). The number of layers needed for routing the links in RDT(2,2,1)//spl alpha/ is shown to be bounded at 6, which is feasible to be implemented with current and future VLSI technologies. With the innovative diagonal structure and its simple rank assignment, RDT(2,2,1)//spl alpha/ possesses the following features: recursive structure, smaller diameter and average distance, embedded mesh/torus topology, a constant node degree of 8, and robust routing schemes. These features make RDT(2,2,1)//spl alpha/ a promising solution for the interconnection network of NoC designs satisfying the requirements for scalability, energy-efficiency, customizability, and fault-tolerance.
---
paper_title: Firefly: illuminating future network-on-chip with nanophotonics

paper_content:

Future many-core processors will require high-performance yet energy-efficient on-chip networks to provide a communication substrate for the increasing number of cores. Recent advances in silicon nanophotonics create new opportunities for on-chip networks. To efficiently exploit the benefits of nanophotonics, we propose Firefly - a hybrid, hierarchical network architecture. Firefly consists of clusters of nodes that are connected using conventional, electrical signaling while the inter-cluster communication is done using nanophotonics - exploiting the benefits of electrical signaling for short, local communication while nanophotonics is used only for global communication to realize an efficient on-chip network. Crossbar architecture is used for inter-cluster communication. However, to avoid global arbitration, the crossbar is partitioned into multiple, logical crossbars and their arbitration is localized. Our evaluations show that Firefly improves the performance by up to 57% compared to an all-electrical concentrated mesh (CMESH) topology on adversarial traffic patterns and up to 54% compared to an all-optical crossbar (OP XBAR) on traffic patterns with locality. If the energy-delay-product is compared, Firefly improves the efficiency of the on-chip network by up to 51% and 38% compared to CMESH and OP XBAR, respectively.
---
paper_title: Recursive diagonal torus: an interconnection network for massively parallel computers

paper_content:

Recursive Diagonal Torus (RDT), a class of interconnection network is proposed for massively parallel computers with up to 2/sup 16/ nodes. By making the best use of a recursively structured diagonal mesh (torus) connection, the RDT has a smaller diameter (e.g., it is 11 for 2/sup 10/ nodes) with a smaller number of links per node (i.e., 8 links per node) than those of the hypercube. A simple routing algorithm, called vector routing, which is near-optimal and easy to implement is also proposed. Although the congestion on upper rank tori sometimes degrades the performance under the random traffic, the RDT provides much better performance than that of a 2D/3D torus in most cases and, under hot spot traffic, the RDT provides much better performance than that of a 2D/3D/4D torus. The RDT router chip which provides a message multicast for maintaining cache consistency is available. Using the 0.5 /spl mu/m BICMOS SOG technology, versatile functions, including hierarchical multicasting, combining acknowledge packets, shooting down/restart mechanism, and time-out/setup mechanisms, work at a 60 MHz clock rate.
---
paper_title: Topology and Binary Routing Schemes of A PRDT-Based NoC

paper_content:

In this paper, we present a novel network topology to build an on chip interconnection network. This so called PRDT(2, 1) structure offers a few distinct architectural features, including (i) high scalability, (ii) small diameter and average distance, (iii) reconfigurability with its embedded mesh/torus topology, and (iv) high degree of fault tolerance. Routing in a PRDT(2, 1)-based network can be performed using an efficient and deadlock-free binary routing scheme without using virtual channels. As an extension to this binary routing scheme, we further propose a fully adaptive routing algorithm which is also deadlock-free by using a few virtual channels. Comparisons between the proposed routing algorithms and a vector routing algorithm have been conducted though computer simulations, and the results show that the proposed routing algorithms can achieve better performance than the vector routing algorithm but require significantly less buffers
---
paper_title: Message transfer algorithms on the recursive diagonal torus

paper_content:

Recursive diagonal torus (RDT) is a class of interconnection network for massively parallel computers with 2/sup 16/ nodes. In this paper, message transfer algorithms on the RDT are proposed and discussed. First, a simple one-to-one message routing algorithm called the vector routing is introduced and the result of its practical extension called the floating vector routing is reported. Next, broadcasting on the RDT are shown. Finally, deadlock-free message routing algorithms which are an extension of the e-cube routing are proposed. >
---
paper_title: The Hamiltonian property of generalized de Bruijn digraphs

paper_content:

Abstract It has been shown that the generalized de Bruijn digraphs G B ( n , d ) and the Imase-Itoh digraphs G I ( n , d ) have Hamiltonian circuits of gcd ( n , d ) > 1. For gcd ( n , d ) = 1 the problem remains open except for d = 1 and 2. In this paper we give a unified proof for all d ≥ 3 that both G B ( n , d ) and G I ( n , d ) have Hamiltonian circuits.
---
paper_title: de Bruijn graph as a low latency scalable architecture for energy efficient massive NoCs

paper_content:

In this paper, we use the generalized binary de Bruijn (GBDB) graph as a scalable and efficient network topology for an on-chip communication network. Using just two-layer wiring, we propose an optimum tile-based implementation for a GBDB-based Network-on-Chip (NoC). Our experimental results show that the latency and energy consumption of generalized de Bruijn graph are much less with compared to Mesh and Torus, the two common NoC architectures in the literature.
---
paper_title: The de Bruijn multiprocessor network: a versatile parallel processing and sorting network for VLSI

paper_content:

It is shown that the binary de Bruijn multiprocessor network (BDM) can solve a wide variety of classes of problems. The BDM admits an N-node linear array, an N-node ring, (N-1)-node complete binary trees, ((3N/4)-2)-node tree machines, and an N-node one-step shuffle-exchange network, where N (=2/sup k/, k an integer) is the total number of nodes. The de Bruijn multiprocessor networks are proved to be fault-tolerant as well as extensible. A tight lower bound of the VLSI layout area of the BDM is derived; a procedure for an area-optimal VLSI layout is also described. It is demonstrated that the BDM is more versatile than the shuffle-exchange and the cube-connected cycles. Recent work has classified sorting architectures into (1) sequential input/sequential output, (2) parallel input/sequential output, (3) parallel input/parallel output, (4) sequential input/parallel output, and (5) hybrid input/hybrid output. It is demonstrated that the de Bruijn multiprocessor networks can sort data items in all of the abovementioned categories. No other network which can sort data items in all the categories is known. >
---
paper_title: A novel deadlock-free routing technique for a class of de Bruijn graph based networks

paper_content:

This paper introduces a new deadlock-free routing algorithm with fewer virtual channels than the known algorithm for a generalized de Bruijn digraph of m virtual channels, where m is the maximum message path length and r is a radix. Our new algorithm requires maximum m-[/sup m-1///sub r/] virtual channels per physical channel. Extension to this algorithm for a generalized de Bruijn graph and a dBCube graph is introduced, and virtual channel requirements have also been identified. In most of dBCube graphs, maximum m-[/sup m-1///sub r/] virtual channels are required for the outcluster channels, and maximum m+1-[/sup m///sub r/] virtual channels for the incluster channels, where m is the maximum length of the cluster-to-cluster path. >
---
paper_title: Low Latency and Energy Efficient Scalable Architecture for Massive NoCs Using Generalized de Bruijn Graph

paper_content:

Employing thousands of cores in a single chip is the natural trend to handle the ever increasing performance requirements of complex applications such as those used in graphics and multimedia processing. System-on-chips (SoCs) platforms based on network-on-chips (NoCs) could be a viable option for the deployment of large multicore designs with thousands of cores. This paper proposes the generalized binary de Bruijn (GBDB) graph as a reliable and efficient network topology for a large NoC. We propose a reliable routing algorithm to detour a faulty channel between two adjacent switches. In addition, using integer linear programming, we propose an optimal tile-based implementation for a GBDB-based NoC in which the number of channels is less than that of Torus which has the same number of links. Our experimental results show that the latency and energy consumption of the generalized de Bruijn graph are much less than those of Mesh and Torus. The low energy consumption of a de Bruijn graph-based NoC makes it suitable for portable devices which have to operate on limited batteries. Also, the gate level implementation of the proposed reliable routing shows small area, power, and timing overheads due to the proposed reliable routing algorithm.
---
paper_title: Reliable network-on-chip based on generalized de Bruijn graph

paper_content:

In this paper, we propose the generalized de Bruijn graph as a reliable and efficient network topology for a Network-on-Chip (NoC) design. We also propose a reliable routing algorithm to detour a problematic (i.e., faulty or congested) link. Our experimental results show that the latency and energy consumption of generalized de Bruijn graph are much less with compared to Mesh and Torus, the two common NoC architectures in the literature. The low energy consumption of de Bruijn graph-based NoC makes it suitable for portable devices which have to operate on limited batteries. Also, the gate level implementation of the proposed reliable routing shows a small area, power, and timing overheads due to the proposed reliable routing algorithm.
---
paper_title: De Bruijn graphs and their applications to fault tolerant networks

paper_content:

The goal of this expository paper is to introduce De Bruijn graphs and discuss their applications to fault tolerant networks. We will begin by examining N.G. de Bruijn’s original paper and the proof of his claim that there are exactly 2 n−1−n De Bruijn cycles in the binary De Bruijn graph B(2, n). In order to study fault tolerance we explore the properties of Hamiltonian and Eulerian cycles that occur on De Bruijn graphs and the type of redundancy that occurs as a result. Lastly, in this paper we seek to provide some guidance into further research on De Bruijn graphs and their potential applications to other areas.
---
paper_title: Wormhole routing in de Bruijn networks and hyper-de Bruijn networks

paper_content:

The order-(m, n) hyper-de Bruijn graph HD(m, n) is the direct product of an order-m hypercube and an order-n de Bruijn graph. The hyper-de Bruijn graph offers flexibility in terms of connections per node and the level of fault-tolerance. These networks as well possess logarithmic diameter, simple routing algorithms and support many computationally important subgraphs and admit efficient implementation. In this paper, we present results on wormhole routing in binary de Bruijn and hyper-de Bruijn networks. For an N-node binary de Bruijn network, four deadlock-free routing algorithms are presented. These algorithms use log N, /spl lceil/2/3 log N/spl rceil/, /spl lceil/1/2 log N/spl rceil/ and 4 virtual channels per physical channel. The number of hops needed to route a message using the above algorithms are /spl les/log N, /spl les/log N, /spl les/log N and /spl les/2 log N, respectively. We present a generalized approach to design deadlock-free wormhole routing algorithms for the hyper-de Bruijn networks, based on the above algorithms.
---
paper_title: De Bruijn graph based 3D Network on Chip architecture design

paper_content:

Network on Chip (NoC) is an on-chip communication methodology proposed to resolve the increased interconnection problem in System in Chip (SoC). Since the three dimensional (3D) integrated circuit (IC) can offer shorter interconnection wire for Network on Chip, 3D NoC becomes an emerging research area in recent years. The architecture of 3D NoC is one of the most important and fundamental issues in 3D NoC research area, since it plays an important roll in network latency, throughput, power consumption, application mapping, and chip complexity. In this paper, we propose a new architecture based on De Bruijn graph for 3D NoC, since De Bruijn graph is a topology with small diameter, simple routing and high reliability. We evaluate this architecture with two Mesh based architectures. The simulation result shows that the De Bruijn graph based architecture can achieve smaller network latency than Mesh based architectures.
---
paper_title: A recursively construction scheme for super fault-tolerant hamiltonian graphs

paper_content:

Abstract For the interconnection network topology, it is usually represented by a graph. When a network is used, processors and/or links faults may happen. Thus, it is meaningful to consider faulty networks. We consider k -regular graphs in this paper. We define a k -regular hamiltonian and hamiltonian connected graph G is super fault-tolerant hamiltonian if G remains hamiltonian after removing at most k − 2 vertices and/or edges and remains hamiltonian connected after removing at most k − 3 vertices and/or edges. A super fault-tolerant hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity . The aim of this paper is to investigate a construction scheme to construct various super fault-tolerant hamiltonian graphs. Along the way, the recursive circulant graph is a special case of our construction scheme, and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained.
---
paper_title: Complex network inspired fault-tolerant NoC architectures with wireless links

paper_content:

The Network-on-Chip (NoC) paradigm has emerged as a scalable interconnection infrastructure for modern multi-core chips. However, with growing levels of integration, the traditional NoCs suffer from high latency and energy dissipation in on-chip data transfer due to conventional metal/dielectric based interconnects. Three-dimensional integration, on-chip photonic, RF and wireless links have been proposed as radical low-power and low-latency alternatives to the conventional planar wire-based designs. Wireless NoCs with Carbon Nanotube (CNT) antennas are shown to outperform traditional wire based NoCs by several orders of magnitude in power dissipation and latency. However such transformative technologies will be prone to high levels of faults and failures due to various issues related to manufacturing and integration. On the other hand, several naturally occurring complex networks such as colonies of microbes and the internet are known to be inherently fault-tolerant against high rates of failures and harsh environments. This paper proposes to adopt such complex network based architectures to minimize the effect of wireless link failures on the performance of the NoC. Through cycle accurate simulations it is shown that the wireless NoC architectures inspired by natural complex networks perform better than their conventional wired counterparts even in the presence of a high degree of faults.
---
paper_title: Networks on Chips: Technology and Tools

paper_content:

The design of today's semiconductor chips for various applications, such as telecommunications, poses various challenges due to the complexity of these systems. These highly complex systems-on-chips demand new approaches to connect and manage the communication between on-chip processing and storage components and networks on chips (NoCs) provide a powerful solution. This book is the first to provide a unified overview of NoC technology. It includes in-depth analysis of all the on-chip communication challenges, from physical wiring implementation up to software architecture, and a complete classification of their various Network-on-Chip approaches and solutions.
---
paper_title: Performance Evaluation of Adaptive Routing Algorithms for achieving Fault Tolerance in NoC Fabrics

paper_content:

Commercial designs are integrating from 10 to 100 embedded functional and storage blocks in a single system on chip (SoC) currently, and the number is likely to increase significantly in the near future. The communication requirements of these large Multi Processor SoCs (MP-SoCs) are convened by the emerging network-on-a-chip (NoC) paradigm. In the deep sub-micron (DSM) VLSI processes, it is difficult to guarantee correct fabrication with an acceptable yield without employing design techniques that take into account the intrinsic existence of manufacturing faults. To become a viable alternative IC design methodology the NoC paradigm must address the system-level reliability issues, which is going to be the dominant concern in the DSM and beyond silicon era. By incorporating adaptiveness in the data communication mechanism we are able to tolerate permanent manufacturing faults in the NoC interconnect architectures. The corresponding performance and cost figures must be carefully analyzed and weighted against the specific application requirements. In this paper we explore the performance tradeoffs associated with adaptive routing schemes in NoC fabrics.
---
paper_title: ZoneDefense: A Fault-Tolerant Routing for 2-D Meshes Without Virtual Channels

paper_content:

Fault-tolerant routing is usually used to provide reliable on-chip communication for many-core processors. This paper focuses on a special class of algorithms that do not use virtual channels. One of the major challenges is to keep the network deadlock free in the presence of faults, especially those locating on network edges. State-of-the-art solutions address this problem by either disabling all nodes of the faulty network edges or including all faults into one faulty block. Therefore, a large number of fault-free nodes will be sacrificed. To address this problem, the proposed ZoneDefense routing not only includes faults into convex faulty blocks but also spreads the faulty blocks' position information in corresponding columns. The nodes, which know the position of faulty blocks, form the defense zones. Therefore, packets can find the faulty blocks and route around them in advance. Exploiting the defense zones, the proposed ZoneDefense routing could tolerate many more faults with significantly reduced sacrificed fault-free nodes compared with the state-of-the-art algorithms. Furthermore, the ZoneDefense routing does not degrade the network performance in the absence of faults, and could get similar performance as its counterparts in the presence of faults.
---
paper_title: A highly resilient routing algorithm for fault-tolerant NoCs

paper_content:

Current trends in technology scaling foreshadow worsening transistor reliability as well as greater numbers of transistors in each system. The combination of these factors will soon make long-term product reliability extremely difficult in complex modern systems such as systems on a chip (SoC) and chip multiprocessor (CMP) designs, where even a single device failure can cause fatal system errors. Resiliency to device failure will be a necessary condition at future technology nodes. In this work, we present a network-on-chip (NoC) routing algorithm to boost the robustness in interconnect networks, by reconfiguring them to avoid faulty components while maintaining connectivity and correct operation. This distributed algorithm can be implemented in hardware with less than 300 gates per network router. Experimental results over a broad range of 2D-mesh and 2D-torus networks demonstrate 99.99% reliability on average when 10% of the interconnect links have failed.
---
paper_title: A Fault tolerant mechanism for handling Permanent and Transient Failures in a Network on Chip

paper_content:

Network on chips (NoC) have emerged as a feasible solution to handle growing number of communicating components on a single chip. The scalability of chips however increases the probability of errors, hence making reliability a major issue in scaling chips. We hereby propose a comprehensive fault tolerant mechanism for packet based NoCs to deal with packet losses or corruption due to transient faults as well as a dynamic routing mechanism to deal with permanent link and/or router failure on-chip
---
paper_title: Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs

paper_content:

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an application specific routing algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8times8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.
---
paper_title: Segment-based routing: an efficient fault-tolerant routing algorithm for meshes and tori

paper_content:

Computers get faster every year, but the demand for computing resources seems to grow at an even faster rate. Depending on the problem domain, this demand for more power can be satisfied by either, massively parallel computers, or clusters of computers. Common for both approaches is the dependence on high performance interconnect networks such as Myrinet, Infiniband, or 10 Gigabit Ethernet. While high throughput and low latency are key features of interconnection networks, the issue of fault-tolerance is now becoming increasingly important. As the number of network components grows so does the probability for failure, thus it becomes important to also consider the fault-tolerance mechanism of interconnection networks. The main challenge then lies in combining performance and fault-tolerance, while still keeping cost and complexity low. This paper proposes a new deterministic routing methodology for tori and meshes, which achieves high performance without the use of virtual channels. Furthermore, it is topology agnostic in nature, meaning it can handle any topology derived from any combination of faults when combined with static reconfiguration. The algorithm, referred to as segment-based routing (SR), works by partitioning a topology into subnets, and subnets into segments. This allows us to place bidirectional turn restrictions locally within a segment. As segments are independent, we gain the freedom to place turn restrictions within a segment independently from other segments. This results in a larger degree of freedom when placing turn restrictions compared to other routing strategies. In this paper a way to compute segment-based routing tables is presented and applied to meshes and tori. Evaluation results show that SR increases performance by a factor of 1.8 over FX and up*/down* routing.
---
paper_title: Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks

paper_content:

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2D meshes based on Wu's fault-tolerant odd-even turn model (2000) and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It does not use any virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and is a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and they include much fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2D meshes using extended MCCs.
---
paper_title: Brisk and limited-impact NoC routing reconfiguration

paper_content:

The expected low reliability of the silicon substrate at upcoming technology nodes presents a key challenge for digital system designers. Networks-on-chip (NoCs) are especially concerning because they are often the only communication infrastructure for the chips in which they are deployed. Recently, routing reconfiguration solutions have been proposed to address this problem. However, they come at a high silicon cost, and often require suspending the normal network activity while executing a centralized, resource-hungry reconfiguration algorithm. This paper proposes a novel, fast and minimalistic routing reconfiguration algorithm, called BLINC. BLINC utilizes pre-computed routing metadata to quickly evaluate localized detours upon each fault manifestation. We showcase the efficacy of our algorithm by deploying it in a novel NoC fault detection and reconfiguration solution, where BLINC enables uninterrupted NoC operation during aggressive online testing. If a fault seems likely to occur, we circumvent it in advance with the aid of our BLINC reconfiguration algorithm. Experimental results show an 80% reduction in the average number of routers affected by a reconfiguration event, compared to state-of-the-art techniques. BLINC enables negligible performance degradation in our detection and reconfiguration solution, while solutions based on current techniques suffer a 17-fold latency increase.
---
paper_title: A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in meshes

paper_content:

We propose a new fault block model, minimal-connected-component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal "Manhattan" routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.
---
paper_title: A deterministic fault-tolerant and deadlock-free routing protocol in 2-D meshes based on odd-even turn model

paper_content:

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on dimension-order routing and the recently proposed odd-even turn model. The proposed protocol, called extended X-Y routing, does not use any virtual channels by prohibiting certain locations of faults and destinations. Faults are contained in a set of disjointed rectangular regions called faulty blocks. The number of faults to be tolerated is unbounded as long as nodes outside faulty blocks are connected in the mesh network. The extended X-Y routing can also be used under a special convex fault region called orthogonal faulty block, which can be derived from a given faulty block by activating some nonfaulty nodes in the block. Extensions to partial adaptive routing, traffic- and adaptivity-balanced using virtual networks, and routing without constraints using virtual channels and virtual networks are also discussed.
---
paper_title: Fault-tolerant routing for on-chip network without using virtual channels

paper_content:

Thanks to its less design complexity, less power consumption and service time, to avoid using virtual channel has became a very attractive approach to building future reliable and massively parallel many-core systems. Furthermore, less area of the light-weight router decrease the probability of failure. To this end, by constructing an acyclic channel dependency graph that breaks all cycles and preserves connectivity of the network, we propose a new deadlock-free fault-tolerant adaptive routing without virtual channel. Extensive experiments of 8x8 2D-mesh network demonstrate 99.73% and 97.56% reliability under uniform random traffic when 10% and 20% of the links are failed.
---
paper_title: ZoneDefense: A Fault-Tolerant Routing for 2-D Meshes Without Virtual Channels

paper_content:

Fault-tolerant routing is usually used to provide reliable on-chip communication for many-core processors. This paper focuses on a special class of algorithms that do not use virtual channels. One of the major challenges is to keep the network deadlock free in the presence of faults, especially those locating on network edges. State-of-the-art solutions address this problem by either disabling all nodes of the faulty network edges or including all faults into one faulty block. Therefore, a large number of fault-free nodes will be sacrificed. To address this problem, the proposed ZoneDefense routing not only includes faults into convex faulty blocks but also spreads the faulty blocks' position information in corresponding columns. The nodes, which know the position of faulty blocks, form the defense zones. Therefore, packets can find the faulty blocks and route around them in advance. Exploiting the defense zones, the proposed ZoneDefense routing could tolerate many more faults with significantly reduced sacrificed fault-free nodes compared with the state-of-the-art algorithms. Furthermore, the ZoneDefense routing does not degrade the network performance in the absence of faults, and could get similar performance as its counterparts in the presence of faults.
---
paper_title: Congestion aware, fault tolerant, and thermally efficient inter-layer communication scheme for hybrid NoC-bus 3D architectures

paper_content:

Three-dimensional IC technology offers greater device integration and shorter interlayer interconnects. In order to take advantage of these attributes, 3D stacked mesh architecture was proposed which is a hybrid between packet-switched network and a bus. Stacked mesh is a feasible architecture which provides both performance and area benefits, while suffering from inefficient intermediate buffers. In this paper, an efficient architecture to optimize system performance, power consumption, and reliability of stacked mesh 3D NoC is proposed. The mechanism benefits from a congestion-aware and bus failure tolerant routing algorithm called Adaptive-Z for vertical communication. In addition, we hybridize the proposed adaptive routing with available algorithms to mitigate the thermal issues by herding most of the switching activities closer to the heat sink. Our extensive simulations with synthetic and real benchmarks, including the one with an integrated video-conference application, demonstrate significant power, performance, and peak temperature improvements compared to a typical stacked mesh 3D NoC.
---
paper_title: Logic-Based Distributed Routing for NoCs

paper_content:

The design of scalable and reliable interconnection networks for multicore chips (NoCs) introduces new design constraints like power consumption, area, and ultra low latencies. Although 2D meshes are usually proposed for NoCs, heterogeneous cores, manufacturing defects, hard failures, and chip virtualization may lead to irregular topologies. In this context, efficient routing becomes a challenge. Although switches can be easily configured to support most routing algorithms and topologies by using routing tables, this solution does not scale in terms of latency and area. We propose a new circuit that removes the need for using routing tables. The new mechanism, referred to as logic-based distributed routing (LBDR), enables the implementation in NoCs of many routing algorithms for most of the practical topologies we might find in the near future in a multicore chip. From an initial topology and routing algorithm, a set of three bits per switch output port is computed. By using a small logic block, LHDR mimics (demonstrated by evaluation) the behavior of routing algorithms implemented with routing tables. This result is achieved both in regular and irregular topologies. Therefore, LBDR removes the need for using routing tables for distributed routing, thus enabling flexible, fast and power-efficient routing in NoCs.
---
paper_title: A fault-tolerant and congestion-aware routing algorithm for Networks-on-Chip

paper_content:

This paper presents a fault-tolerant routing algorithm for mesh-based Networks-on-Chip (NoC) with faulty links. It is a distributed, adaptive and congestion-aware routing algorithm where only two virtual channels are used for both adaptiveness and fault-tolerance. The proposed routing method has a multilevel fault-tolerance capability and therefore it is capable to tolerate more faulty links in more complicated faulty situations with additional hardware costs. The network performance, fault-tolerance capability and hardware overhead are evaluated through appropriate simulations. The experimental results show that the overall reliability of a Network-on-Chip is significantly enhanced against multiple link failures or partially faulty routers with only a small hardware overhead.
---
paper_title: ARIADNE: Agnostic Reconfiguration in a Disconnected Network Environment

paper_content:

Extreme transistor technology scaling is causing increasing concerns in device reliability: the expected lifetime of individual transistors in complex chips is quickly decreasing, and the problem is expected to worsen at future technology nodes. With complex designs increasingly relying on Networks-on-Chip (NoCs) for on-chip data transfers, a NoC must continue to operate even in the face of many transistor failures. Specifically, it must be able to reconfigure and reroute packets around faults to enable continued operation, i.e., generate new routing paths to replace the old ones upon a failure. In addition to these reliability requirements, NoCs must maintain low latency and high throughput at very low area budget. In this work, we propose a distributed reconfiguration solution named Ariadne, targeting large, aggressively scaled, unreliable NoCs. Ariadne utilizes up*/down* for fast routing at high bandwidth, and upon any number of concurrent network failures in any location, it reconfigures to discover new resilient paths to connect the surviving nodes. Experimental results show that Ariadne provides a 40%-140% latency improvement (when subject to 50 faults in a 64-node NoC) over other on-chip state-of-the-art fault tolerant solutions, while meeting the low area budget of on-chip routers with an overhead of just 1.97%.
---
paper_title: Dynamic fault-tolerant routing algorithm for networks-on-chip based on localised detouring paths

paper_content:

Downscaled complementary metal-oxide semiconductor (CMOS) technology feature sizes have enabled massive transistor integration densities. Multi-core chips with billions of transistors are now a reality. However, this rapid increase in on-chip resources has come at the expense of higher susceptibility to defects and wear-out. The inter-router communication links of networks-on-chips (NoCs) are composed of metal wires that are especially vulnerable to catastrophic physical effects such as those of electro-migration, which can even cause link disconnects. To address this hazard, fault-tolerant (FT) routing algorithms sustain on-chip communication by re-routing messages around faulty links, or regions. This work presents a new FT routing scheme that employs a localised re-routing approach. Packets are de-toured around faulty links/regions based on purely local and distributed decisions, and without any global link state knowledge. The algorithm, which is proven to be deadlock- and livelock-free, also handles dynamically occurring faults. Detailed evaluation with synthetic traffic patterns and real applications within a full-system simulation environment demonstrate the efficacy of the new scheme with up to 12% of NoC links being faulty. Synthesis results also prove the feasibility of the proposed protocol at modest hardware and power consumption overheads of only over 5 and 2.5%, respectively.
---
paper_title: A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks

paper_content:

An important open problem in wormhole routing has been to find a necessary and sufficient condition for deadlock-free adaptive routing. Recently, Duato has solved this problem for a restricted class of adaptive routing algorithms. In this paper, a necessary and sufficient condition is proposed that can be used for any adaptive or nonadaptive routing algorithm for wormhole routing, as long as only local information is required for routing. The underlying proof technique introduces a new type of dependency graph, thechannel waiting graph, which omits most channel dependencies that cannot be used to create a deadlock configuration. The necessary and sufficient condition can be applied in a straightforward manner to most routing algorithms. This is illustrated by proving deadlock freedom for a partially adaptive nonminimal mesh routing algorithm that does not require virtual channels and a fully adaptive minimal hypercube routing algorithm with two virtual channels per physical channel. Both routing algorithms are more adaptive than any previously proposed routing algorithm with similar virtual channel requirements.
---
paper_title: Fault-Tolerant Deadlock-Free Adaptive Routing for Any Set of Link and Node Failures in Multi-cores Systems

paper_content:

Future applications will require processors with many cores communicating through a regular interconnection network. Meanwhile, as the Deep submicron technology fore- shadows highly defective chips era, fault-tolerant designs become compulsory. In particular, the fault tolerance of a core interconnect is critical, and inevitably increases its complexity. In this paper, we present a novel adaptive routing algorithm that is able to route messages in the presence of any set of multiple nodes and links failures, as long as a path exists. Compared to the existing solutions, the proposed algorithm provides fault tolerance without using any routing table. It is scalable and can be applied to multicore chips with a 2D mesh core interconnect of any size. The algorithm is deadlock-free and avoids infinite looping in fault-free and faulty 2D meshes, based on Virtual Networks and Virtual Channels. We simulated the proposed algorithm using the worst case scenario, regarding the traffic patterns and the failure rate up to 40%. Experimentation results confirmed that the algorithm tolerates multiple failures even in the most extreme failure patterns. Additionally, we monitored the trade off between the fault tolerance and the average latency for faulty cases, as measurement of the performance degradation. The algorithm detects the interconnects partitioning and enables "preferred paths" for streaming applications.
---
paper_title: Fault-tolerant adaptive routing under an unconstrained set of node and link failures for many-core systems-on-chip

paper_content:

An online fault tolerant routing algorithm for 2D mesh Networks-on-Chip is presented in this work. It combines an adaptive routing algorithm with neighbor fault-awareness and a new traffic-balancing metric. To be able to cope with runtime permanent and temporary failures that may result in message corruption, message loss or deadlocks, the routing algorithm is enhanced with packet retransmission and a new message recovery scheme. Simulation results, for various network sizes, different traffic patterns, under an unconstrained number of node and link faults, temporary and/or permanent, demonstrate the scalability and efficiency of the proposed algorithm to tolerate multiple failures likely encountered in deep submicron technologies. As the experiments have shown, the proposed algorithm maintains high reliability of more than 97.68% for a 2D mesh network of 16x16 and in the presence of 384 simultaneous link faults. For the same network and in the extreme scenario of 103 routers being simultaneously faulty, the obtained reliability is more than 93.40%.
---
paper_title: Characterization and Implementation of Fault-Tolerant Vertical Links for 3-D Networks-on-Chip

paper_content:

Through silicon vias (TSVs) provide an efficient way to support vertical communication among different layers of a vertically stacked chip, enabling scalable 3-D networks-on-chip (NoC) architectures. Unfortunately, low TSV yields significantly impact the feasibility of high-bandwidth vertical connectivity. In this paper, we present a semi-automated design flow for 3-D NoCs including a defect-tolerance scheme to increase the global yield of 3-D stacked chips. Starting from an accurate physical and geometrical model of TSVs: 1) we extract a circuit-level model for vertical interconnections; 2) we use it to evaluate the design implications of extending switch architectures with ports in the vertical direction; moreover, 3) we present a defect-tolerance technique for TSV-based multi-bit links through an effective use of redundancy; and finally, 4) we present a design flow allowing for post-layout simulation of NoCs with links in all three physical dimensions. Experimental results show that a 3-D NoC implementation yields around 10% frequency improvement over a 2-D one, thanks to the propagation delay advantage of TSVs and the shorter links. In addition, the adopted fault tolerance scheme demonstrates a significant yield improvement, ranging from 66% to 98%, with a low area cost (20.9% on a vertical link in a NoC switch, which leads a modest 2.1% increase in the total switch area) in 130 nm technology, with minimal impact on very large-scale integrated design and test flows.
---
paper_title: A Fault-Tolerant and Deadlock-Free Routing Protocol in 2-D Meshes Based on Odd-Even Turn Model

paper_content:

We propose a deterministic fault-tolerant and deadlock-free routing protocol in two-dimensional (2D) meshes based on dimension-order routing and the odd-even turn model. The proposed protocol, called extended X-Y routing, does not use any virtual channels by prohibiting certain locations of faults and destinations. Faults are contained in a set of disjointed rectangular regions called faulty blocks. The number of faults to be tolerated is unbounded as long as nodes outside faulty blocks are connected in the 2D mesh network. The extended X-Y routing can also be used under a special convex fault region called an orthogonal faulty block, which can be derived from a given faulty block by activating some nonfaulty nodes in the block. Extensions to partially adaptive routing, traffic and adaptivity-balancing using virtual networks, and routing without constraints using virtual channels and virtual networks are also discussed.
---
paper_title: Fully Adaptive Fault-Tolerant Routing Algorithm for Network-on-Chip Architectures

paper_content:

In this paper, we present a novel fully adaptive and fault-tolerant routing algorithm for Network-on-Chips (NoCs) called Force-Directed Wormhole Routing (FDWR). The proposed routing algorithm is implemented in the switches of a TLM (Transaction Level Model) packet switching NoC using SystemC. Based on these switches, mesh, torus, and hypercube topologies for NoCs can be automatically generated. We show how the proposed algorithm distributes the traffic uniformly across the entire network to avoid overloaded links. Simulation results depict that the proposed routing algorithm is able to route packets even in the case of faulty links or switches in the NoC. Furthermore, it is shown that in the case of faulty switches the area around that switches is not overloaded and that the traffic is uniformly distributed across the entire network.
---
paper_title: High Performance Fault-Tolerant Routing Algorithm for NoC-Based Many-Core Systems

paper_content:

Networks-on-Chip (NoCs) has become a promising approach for the on-chip communication infrastructure of many-core Systems-on-Chip (SoCs). Faults may occur in the NoC both at the router and link level. There are many fault-tolerant approaches presented both in the off-chip and on-chip networks. Some approaches disable some healthy components in order to form a specific shape and others not. Regardless of all varieties, there has always been a common assumption among them. Most of all traditional fault-tolerant methods are based on rerouting packets around a faulty node or region. These approaches affect the performance significantly not only by taking longer paths but also by creating hotspot around a fault. The focus of this paper is to maintain the performance of NoC in the presence of faults. The presented method takes advantage of a fully adaptive routing algorithm using one and two virtual channels along the X and Y dimensions. This method is able to tolerate all cases of one-faulty node without losing the performance of NoC. According to the experimental results, this presented fault-tolerant routing algorithm is able to support up to six faulty nodes in the 8×8 mesh network by up to 98% reliability.
---
paper_title: Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs

paper_content:

An efficient routing algorithm is important for large on-chip networks [network-on-chip (NoC)] to provide the required communication performance to applications. Implementing NoC using table-based switches provide many advantages, including possibility of changing routing algorithms and fault tolerance, due to the option of table reconfigurations. However, table-based switches have been considered unsuitable for NoCs due to their perceived high area and power consumption. In this paper, we describe the region-based routing (RBR) mechanism which groups destinations into network regions allowing an efficient implementation with logic blocks. RBR can also be viewed as a mechanism to reduce the number of entries in routing tables. RBR is general and can be used in conjunction with any adaptive routing algorithm. In particular, we have evaluated the proposed scheme in conjunction with a general routing algorithm, namely segment-based routing (SR) and an application specific routing algorithm (APSRA) using regular and irregular mesh topologies. Our study shows that the number of entries in the table is significantly reduced, especially for large networks. Evaluation results show that RBR requires only four regions to support several routing algorithms in a 2-D mesh with no performance degradation. Considering link failures, our results indicate that RBR combined with SR is able to tolerate up to 7 link failures in an 8times8 mesh. RBR also reduces area and power dissipation of an equivalent table-based implementation by factors of 8 and 10, respectively. Moreover, the degradation in performance of the network is insignificant when using APSRA combined with RBR.
---
paper_title: A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks

paper_content:

The theoretical background for the design of deadlock-free adaptive routing algorithms for wormhole networks is developed. The author proposes some basic definitions and two theorems. These create the conditions to verify that an adaptive algorithm is deadlock-free, even when there are cycles in the channel dependency graph. Two design methodologies are also proposed. The first supplies algorithms with a high degree of freedom, without increasing the number of physical channels. The second methodology is intended for the design of fault-tolerant algorithms. Some examples are given to show the application of the methodologies. Simulations show the performance improvement that can be achieved by designing the routing algorithms with the new theory. >
---
paper_title: Fault-Tolerant Routing Algorithm for Network on Chip without Virtual Channels

paper_content:

Constructing 2D mesh topology network on chips (NoCs) without using virtual channels becomes attractive approach to building future massive multi-core computer systems because of its large amount of bandwidths, less design complexity, and less space consumption of routers. Dead lock problem on NoC is critical because it makes data transmission between nodes unreachable, and inevitable failures in hardware make mesh topology irregular. Although several fault-tolerant techniques are available, deadlock-free routing control algorithm for irregular mesh topology is promising approach to utilize large amount of bandwidths of NoC. The main drawback of available routing control algorithms is that many healthy nodes are deactivated to guarantee deadlock-freeness, and a number of deactivated nodes lead to traffic congestion. In this paper, we propose new fault-tolerant routing algorithm on 2D mesh topology NoC constructed without using virtual channels. The proposed algorithm is fully analyzed its dead lock-freeness, and the experimental result shows that the proposed algorithm can achieve both less number of deactivated nodes and higher throughput.
---
paper_title: Addressing Manufacturing Challenges with Cost-Efficient Fault Tolerant Routing

paper_content:

The high-performance computing domain is enriching with the inclusion of Networks-on-chip (NoCs) as a key component of many-core (CMPs or MPSoCs) architectures. NoCs face the communication scalability challenge while meeting tight power, area and latency constraints. Designers must address new challenges that were not present before. Defective components, the enhancement of application-level parallelism or power-aware techniques may break topology regularity, thus, efficient routing becomes a challenge.In this paper, uLBDR (Universal Logic-Based Distributed Routing) is proposed as an efficient logic-based mechanism that adapts to any irregular topology derived from 2D meshes, being an alternative to the use of routing tables (either at routers or at end-nodes). uLBDR requires a small set of configuration bits, thus being more practical than large routing tables implemented in memories. Several implementations of uLBDR are presented highlighting the trade-off between routing cost and coverage. The alternatives span from the previously proposed LBDR approach (with 30\% of coverage) to the uLBDR mechanism achieving full coverage. This comes with a small performance cost, thus exhibiting the trade-off between fault tolerance and performance.
---
paper_title: d2-LBDR: Distance-driven routing to handle permanent failures in 2D mesh NoCs

paper_content:

With the advent of deep sub-micron technology, fault-tolerant solutions are needed to keep many-core chips operative. In NoCs, Logic Based Distributed Routing (LBDR) proved to be a flexible routing framework for 2D meshes with link and router faults. However, to provide full coverage, LBDR requires a module named FORKS which replicates some messages. This imposes the use of virtual cut-through switching and a complex router arbiter, increasing excessively the router cost, mainly in buffer area. Also, some failure combinations require the use of a non-trivial dynamic reconfiguration strategy to avoid deadlocks. We propose d2-LBDR which adds, on every router, a distance register to the closest failure. This enables the support of more failure combinations without an excessive implementation cost. Indeed, we restore the use of wormhole switching, keeping router architecture simple, while achieving the same fault coverage as the best LBDR version, without requiring complex switching strategies nor any dynamic reconfiguration strategy. Results show that a small area overhead (3%) is enough for the implementation of a fully flexible routing method without any limiting support case when compared with LBDR. d2-LBDR reduces area overhead over the best LBDR approach (300% overhead against 3%) while preserving fault coverage. Results show d2-LBDR performance equal to LBDR.
---
paper_title: AFRA: a low cost high performance reliable routing for 3D mesh NoCs

paper_content:

Three-dimensional network-on-chips are suitable communication fabrics for high-density 3D many-core ICs. Such networks have shorter communication hop count, compared to 2D NoCs, and enjoy fast and power efficient TSV wires in vertical links. Unfortunately, the fabrication process of TSV connections has not matured yet, which results in poor vertical links yield. In this work, we address this challenge and introduce AFRA, a deadlock-free routing algorithm for 3D mesh-based NoCs that tolerates faults on vertical links. AFRA is designed to be simple, high performance, and robust. The simplicity is achieved by applying ZXY and XZXY routings in the absence and presence of fault, respectively. Furthermore, AFRA, as will be proved, is deadlock-free when all vertical faulty links have the same direction. This enables the routing to save virtual channels for performance rather than scarifying them for deadlock avoidance. Finally, AFRA provides robustness, which means supporting connection for all possible pairs of communicating nodes in high fault rates. AFRA is evaluated, though cycle accurate network simulation, and is compared with planar adaptive routing. Results reveal that AFRA significantly outperforms planar adaptive routing in both synthetic and real traffic patterns. In addition, the robustness of AFRA is calculated analytically.
---
paper_title: A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip

paper_content:

In this paper we present a reconfigurable routing algorithm for a 2D-mesh network-on-chip (NoC) dedicated to fault- tolerant, massively parallel multi-processors systems on chip (MP2-SoC). The routing algorithm can be dynamically reconfigured, to adapt to the modification of the micro-network topology caused by a faulty router. This algorithm has been implemented in a reconfigurable version of the DSPIN micro-network, and evaluated from the point of view of performance (penalty on the network saturation threshold), and cost (extra silicon area occupied by the reconfigurable version of the router).
---
paper_title: uDIREC: unified diagnosis and reconfiguration for frugal bypass of NoC faults

paper_content:

As silicon continues to scale, transistor reliability is becoming a major concern. At the same time, increasing transistor counts are causing a rapid shift towards large chip multi-processors (CMP) and system-on-chip (SoC) designs, comprising several cores and IPs communicating via a network-on-chip (NoC). As the sole medium of on-chip communication, a NoC should gracefully tolerate many permanent faults. We propose uDIREC, a unified framework for permanent fault diagnosis and subsequent reconfiguration in NoCs that provides graceful performance degradation with increasing number of faults. Upon in-field transistor failures, uDIREC leverages a fine-resolution diagnosis mechanism to disable faulty components very sparingly. At its core, uDIREC employs a novel routing algorithm to find reliable and deadlock-free routes that utilize the still-functional links in the NoC. uDIREC places no restriction on topology, router architecture and number and location of faults. Experimental results show that uDIREC, implemented in a 64-node NoC, drops 3x fewer nodes and provides 25% higher throughput (beyond 15 faults) when compared to other state-of-the-art fault-tolerance solutions. uDIREC's improvement over prior-art grows with more faults, making it a suitable NoC reliability solution for a wide range of fault rates.
---
paper_title: OSR-Lite: Fast and deadlock-free NoC reconfiguration framework

paper_content:

Current and future on-chip networks will feature an enhanced degree of reconfigurability. Power management and virtualization strategies as well as the need to survive to the progressive onset of wear-out faults are root causes for that. In all these cases, a non-intrusive and efficient reconfiguration method is needed to allow the network to function uninterruptedly over the course of the reconfiguration process while remaining deadlock-free. This paper is inspired by the overlapped static reconfiguration (OSR) protocol developed for off-chip networks. However, in its native form its implementation in NoCs is out-of-reach. Therefore, we provide a careful engineering of the NoC switch architecture and of the system-level infrastructure to support a cost-effective, complete and transparent reconfiguration process. Performance during the reconfiguration process is not affected and implementation costs (critical path and area overhead) are proved to be fully affordable for a constrained system. Less than 250 cycles are needed for the reconfiguration process of an 8×8 2D mesh with marginal impact on system performance.
---
paper_title: Synergistic use of multiple on-chip networks for ultra-low latency and scalable distributed routing reconfiguration

paper_content:

Extending the principle of partially good die allowance to manycore processors, and testing them over time to detect the onset of permanent faults, are only feasible through proper support in the on-chip interconnection network. In fact, this implies the ability to reconfigure the routing algorithm at runtime to reflect changes in network topologies. Current literature cannot avoid a large hardware and/or software overhead when tackling this challenge. This paper exploits the existence of multiple physical networks in industry-relevant manycore processors in a synergistic way, for the sake of fast and scalable distributed reconfiguration of the routing function at runtime.
---
paper_title: Brisk and limited-impact NoC routing reconfiguration

paper_content:

The expected low reliability of the silicon substrate at upcoming technology nodes presents a key challenge for digital system designers. Networks-on-chip (NoCs) are especially concerning because they are often the only communication infrastructure for the chips in which they are deployed. Recently, routing reconfiguration solutions have been proposed to address this problem. However, they come at a high silicon cost, and often require suspending the normal network activity while executing a centralized, resource-hungry reconfiguration algorithm. This paper proposes a novel, fast and minimalistic routing reconfiguration algorithm, called BLINC. BLINC utilizes pre-computed routing metadata to quickly evaluate localized detours upon each fault manifestation. We showcase the efficacy of our algorithm by deploying it in a novel NoC fault detection and reconfiguration solution, where BLINC enables uninterrupted NoC operation during aggressive online testing. If a fault seems likely to occur, we circumvent it in advance with the aid of our BLINC reconfiguration algorithm. Experimental results show an 80% reduction in the average number of routers affected by a reconfiguration event, compared to state-of-the-art techniques. BLINC enables negligible performance degradation in our detection and reconfiguration solution, while solutions based on current techniques suffer a 17-fold latency increase.
---
paper_title: A complete self-testing and self-configuring NoC infrastructure for cost-effective MPSoCs

paper_content:

Networks-on-chip need to survive to manufacturing faults in order to sustain yield. An effective testing and configuration strategy however implies two opposite requirements. One one hand, a fast and scalable built-in self-testing and self-diagnosis procedure has to be carried out concurrently at NoC switches. On the other hand, programming the NoC routing mechanism to go around faulty links and switches can be optimally performed by a centralized controller with global network visibility. To the best of our knowledge, this article proposes for the first time a global network testing and configuration strategy that meets the opposite requirements by means of a fault-tolerant dual network architecture and a fast configuration algorithm for the most common failure patterns. Experimental results report an area overhead as low as 12.5p with respect to the baseline switch architecture while achieving a high degree of fault tolerance. In fact, even when multiple stuck-at faults are considered, the capability of fault masking by the dual network is always over 80p, and the support for multiple link failures is more than 90p in presence of two unusable links in the main network with minimum set-up times.
---
paper_title: An array-based test circuit for fully automated gate dielectric breakdown characterization

paper_content:

We propose an array-based test circuit for efficiently characterizing gate dielectric breakdown. Such a design is highly beneficial when studying this statistical process, where up to thousands of samples are needed to create an accurate time to breakdown Weibull distribution. The proposed circuit also facilitates investigations of any spatial correlation of dielectric failures, and can monitor a progressive decrease in gate resistance. Measurement results are presented from a 32 × 32 test array implemented in a 130-nm bulk CMOS process. Results show that this system is capable of taking accurate measurements across a range of voltages and temperatures, which is critical for extrapolating accelerated stress experiment results to expected device lifetimes under realistic operating conditions.
---
paper_title: BulletProof: a defect-tolerant CMP switch architecture

paper_content:

As silicon technologies move into the nanometer regime, transistor reliability is expected to wane as devices become subject to extreme process variation, particle-induced transient errors, and transistor wear-out. Unless these challenges are addressed, computer vendors can expect low yields and short mean-times-to-failure. In this paper, we examine the challenges of designing complex computing systems in the presence of transient and permanent faults. We select one small aspect of a typical chip multiprocessor (CMP) system to study in detail, a single CMP router switch. To start, we develop a unified model of faults, based on the time-tested bathtub curve. Using this convenient abstraction, we analyze the reliability versus area tradeoff across a wide spectrum of CMP switch designs, ranging from unprotected designs to fully protected designs with online repair and recovery capabilities. Protection is considered at multiple levels from the entire system down through arbitrary partitions of the design. To better understand the impact of these faults, we evaluate our CMP switch designs using circuit-level timing on detailed physical layouts. Our experimental results are quite illuminating. We find that designs are attainable that can tolerate a larger number of defects with less overhead than naive triple-modular redundancy, using domain-specific techniques such as end-to-end error detection, resource sparing, automatic circuit decomposition, and iterative diagnosis and reconfiguration.
---
paper_title: A Lightweight Fault-Tolerant Mechanism for Network-on-Chip

paper_content:

Survival capability is becoming a crucial factor in designing multicore processors built with on-chip packet networks, or networks on chip (NoCs). In this paper, we propose a lightweight fault-tolerant mechanism for NoCs based on default backup paths (DBPs) designed to maintain, in the presence of failures, network connectivity of both non-faulty routers as well as healthy processor cores which may be connected to faulty routers. The mechanism provides default paths as backup between certain router ports which serve as alternative datapaths to circumvent failed components within a faulty router. Along with a minimal subset of normal network channels, the set of default backup paths internal to faulty routers form - in the worst case - a unidirectional ring topology that provides network-wide connectivity to all processor cores. Routing using the DBP mechanism is proved to be deadlock-free with only two virtual channels even for fault scenarios in which regular networks degrade to irregular (arbitrary) topologies. Evaluation results show that, for a 2-D mesh wormhole NoC, only 12.6% additional hardware resources are needed to implement the proposed DBP mechanism in order to provide graceful performance degradation without chip-wide failure as the number of faults increases to the maximum needed to form ring.
---
paper_title: Bringing NoCs to 65 nm

paper_content:

Very deep submicron process technologies are ideal application fields for NoCs, which offer a promising solution to the scalability problem. This article sheds light on the benefits and challenges of Noc-Based interconnect design in nanometer CMOS. The author present experimental results from fully working 65-NM Noc Designs and a detailed scalability analysis.
---
paper_title: A low latency router supporting adaptivity for on-chip interconnects

paper_content:

The increased deployment of system-on-chip designs has drawn attention to the limitations of on-chip interconnects. As a potential solution to these limitations, networks-on-chip (NoC) have been proposed. The NoC routing algorithm significantly influences the performance and energy consumption of the chip. We propose a router architecture which utilizes adaptive routing while maintaining low latency. The two-stage pipelined architecture uses look ahead routing, speculative allocation, and optimal output path selection concurrently. The routing algorithm benefits from congestion-aware flow control, making better routing decisions. We simulate and evaluate the proposed architecture in terms of network latency and energy consumption. Our results indicate that the architecture is effective in balancing the performance and energy of NoC designs.
---
paper_title: A Gracefully Degrading and Energy-Efficient Modular Router Architecture for On-Chip Networks

paper_content:

Packet-based on-chip networks are increasingly being adopted in complex system-on-chip (SoC) designs supporting numerous homogeneous and heterogeneous functional blocks. These network-on-chip (NoC) architectures are required to not only provide ultra-low latency, but also occupy a small footprint and consume as little energy as possible. Further, reliability is rapidly becoming a major challenge in deep sub-micron technologies due to the increased prominence of permanent faults resulting from accelerated aging effects and manufacturing/testing challenges. Towards the goal of designing low-latency, energy-efficient and reliable on-chip communication networks, we propose a novel fine-grained modular router architecture. The proposed architecture employs decoupled parallel arbiters and uses smaller crossbars for row and column connections to reduce output port contention probabilities as compared to existing designs. Furthermore, the router employs a new switch allocation technique known as "mirroring effect" to reduce arbitration depth and increase concurrency. In addition, the modular design permits graceful degradation of the network in the event of permanent faults and also helps to reduce the dynamic power consumption. Our simulation results indicate that in an 8 times 8 mesh network, the proposed architecture reduces packet latency by 4-40% and power consumption by 6-20% as compared to two existing router architectures. Evaluation using a combined performance, energy and fault-tolerance metric indicates that the proposed architecture provides 35-50% overall improvement compared to the two earlier routers
---
paper_title: A Reliable Routing Architecture and Algorithm for NoCs

paper_content:

Aggressive transistor scaling continues to drive increasingly complex digital designs. The large number of transistors available today enables the development of chip multiprocessors that include many cores on one die communicating through an on-chip interconnect. As the number of cores increases, scalable communication platforms, such as networks-on-chip (NoCs), have become more popular. However, as the sole communication medium, these interconnects are a single point of failure so that any permanent fault in the NoC can cause the entire system to fail. Compounding the problem, transistors have become increasingly susceptible to wear-out related failures as their critical dimensions shrink. As a result, the on-chip network has become a critically exposed unit that must be protected. To this end, we present Vicis, a fault-tolerant architecture and companion routing protocol that is robust to a large number of permanent failures, allowing communication to continue in the face of permanent transistor failures. Vicis makes use of a two-level approach. First, it attempts to work around errors within a router by leveraging reconfigurable architectural components. Second, when faults within a router disable a link's connectivity, or even an entire router, Vicis reroutes around the faulty node or link with a novel, distributed routing algorithm for meshes and tori. Tolerating permanent faults in both the router components and the reliability hardware itself, Vicis enables graceful performance degradation of networks-on-chip.
---
paper_title: NISHA: A fault-tolerant NoC router enabling deadlock-free Interconnection of Subnets in Hierarchical Architectures

paper_content:

Decrease in the Integrated Circuit (IC) feature sizes leads to the increase in the susceptibility to transient and permanent errors. The growing rate of such errors in ICs intensifies the need for a wide range of solutions addressing reliability at various levels of abstractions. Network on Chip (NoC) architecture has been introduced to address the increasing demand for communication bandwidth among processing cores. The structural redundancy inherited in NoC-based system can be leveraged to improve reliability and compensate for the effects of failures. In this paper, we propose a fault-tolerant NoC router NISHA, which stands for No-deadlock Interconnection of Subnets in Hierarchical Architectures. Armed with a new flow control mechanism, as well as an enhanced Virtual Channel (VC) regulator, the proposed router can mitigate the effects of both transient and permanent errors. A Dynamic/Static virtual channel allocation with respect to the local and global traffic is supported in NISHA; thereby, it maintains a deadlock-free state in the presence of routers or link failures in hierarchical topologies. Experimental results show an enhanced operation of NoC applications as well as the decrease in the average latency and energy consumption.
---
paper_title: Reliability aware NoC router architecture using input channel buffer sharing

paper_content:

To address the increasing demand for reliability in on-chip networks, we proposed a novel Reliability Aware Virtual channel (RAVC) NoC router micro-architecture that enables both dynamic virtual channel allocations and the rational sharing among the buffers of different input channels. In particular, in the case of failure in routers, the virtual channels of routers surrounding the faulty routers can be totally recaptured and reassigned to other input ports. Moreover, our proposed RAVC router isolates the faulty router from occupying network bandwidth. Experimental result shows that proposed micro-architecture provides 7.1% and 3.1 % average latency decrease under uniform and transpose traffic pattern. Considering the existence of failures in routers of on-chip network, RAVC provides 28% and 16% decrease in the average packet latency under the uniform and transpose traffic pattern respectively.
---
paper_title: QORE: A fault tolerant network-on-chip architecture with power-efficient quad-function channel (QFC) buffers

paper_content:

Network-on-Chips (NoCs) are quickly becoming the standard communication paradigm for the growing number of cores on the chip. While NoCs can deliver sufficient bandwidth and enhance scalability, NoCs suffer from high power consumption due to the router microarchitecture and communication channels that facilitate inter-core communication. As technology keeps scaling down in the nanometer regime, unpredictable device behavior due to aging, infant mortality, design defects, soft errors, aggressive design, and process-voltage-temperature variations, will increase and will result in a significant increase in faults (both permanent and transient) and hardware failures. In this paper, we propose QORE - a fault tolerant NoC architecture with Quad-Function Channel (QFC) buffers. The use of QFC buffers and their associated control (link and fault controllers) enhance fault-tolerance by allowing the NoC to dynamically adapt to faults at the link level and reverse propagation direction to avoid faulty links. Additionally, QFC buffers reduce router power and improve performance by eliminating in-router buffering. Our simulation results using real benchmarks and synthetic traffic mixes show that QORE improves speedup by 1.3× and throughput by 2.3× when compared to state-of-the art fault tolerant NoCs designs such as Ariadne and Vicis. Moreover, using Synopsys Design Compiler, we also show that network power in QORE is reduced by 21% with minimal control overhead.
---
paper_title: A Reliable Routing Architecture and Algorithm for NoCs

paper_content:

Aggressive transistor scaling continues to drive increasingly complex digital designs. The large number of transistors available today enables the development of chip multiprocessors that include many cores on one die communicating through an on-chip interconnect. As the number of cores increases, scalable communication platforms, such as networks-on-chip (NoCs), have become more popular. However, as the sole communication medium, these interconnects are a single point of failure so that any permanent fault in the NoC can cause the entire system to fail. Compounding the problem, transistors have become increasingly susceptible to wear-out related failures as their critical dimensions shrink. As a result, the on-chip network has become a critically exposed unit that must be protected. To this end, we present Vicis, a fault-tolerant architecture and companion routing protocol that is robust to a large number of permanent failures, allowing communication to continue in the face of permanent transistor failures. Vicis makes use of a two-level approach. First, it attempts to work around errors within a router by leveraging reconfigurable architectural components. Second, when faults within a router disable a link's connectivity, or even an entire router, Vicis reroutes around the faulty node or link with a novel, distributed routing algorithm for meshes and tori. Tolerating permanent faults in both the router components and the reliability hardware itself, Vicis enables graceful performance degradation of networks-on-chip.
---
paper_title: Tackling Permanent Faults in the Network-on-Chip Router Pipeline

paper_content:

The proliferation of multi-core and many-core chips for performance scaling is making the Network-on-Chip (NoC) occupy a growing amount of silicon area spanning several metal layers. The NoC is neither immune to hard faults and transient faults nor unaffected by the adverse increase in hard faults caused by technology scaling. The ramifications for the NoC are immense: a single fault in the NoC may paralyze the working of the entire chip. To this end, we propose a Permanent Fault Tolerant Router (PFTR) that is capable of tolerating multiple permanent faults in the pipeline. PFTR is designed by making architectural modifications to individual pipeline stages of the baseline NoC router. These architectural modifications involve adding minimum extra circuitry and exploiting temporal parallelism to accomplish fault tolerance. Tolerance of multiple faults is achieved by striking a balance between three important design factors namely, area overhead, power overhead and reliability. We use Silicon Protection Factor (SPF) as the reliability metric to assess the reliability improvement of the proposed architecture. SPF takes into account the number of faults required to cause failure and the area overhead of the additional circuitry to evaluate reliability. SPF calculation reveals that the proposed PFTR is 11 times more reliable than the baseline NoC router. Synthesis results using Cadence Encounter RTL Compiler at 45nm technology show that the additional circuitry adds an area overhead of 31% and power overhead of 30% with respect to the baseline NoC router. PFTR provides much better reliability with much less overhead as compared to other fault tolerant routers such as BulletProof, Vicis and RoCo [15].
---
paper_title: Minimal-path fault-tolerant approach using connection-retaining structure in Networks-on-Chip

paper_content:

There are many fault-tolerant approaches presented both in off-chip and on-chip networks. Regardless of all varieties, there has always been a common assumption between them. Most of all known fault-tolerant methods are based on rerouting packets around faults. Rerouting might take place through nonminimal paths which affect the performance significantly not only by taking longer paths but also by creating hotspot around a fault. In this paper, we present a fault-tolerant approach based on using the shortest paths. This method maintains the performance of Networks-on-Chip in the presence of faults. To avoid using non-minimal paths, the router architecture is slightly modified. In the new form of architecture, there is an ability to connect the horizontal and orthogonal links of a faulty router such that healthy routers are kept connected to each other. Based on this architecture, a fault-tolerant routing algorithm is presented which is obviously much simpler than traditional fault-tolerant routing algorithms. According to this algorithm, only the shortest paths are used by packets in the presence of fault. This results retains the performance of NoCs in faulty situations. This algorithm is highly reliable, for an instance, the reliability is more than 99.5% when there are six faulty routers in an 8×8 mesh network.
---
paper_title: Implications of Rent's Rule for NoC Design and Its Fault-Tolerance

paper_content:

Rent's rule is a powerful tool for exploring VLSI design and technology scaling issues. This paper applies the principles of Rent's rule to the analysis of networks-on-chip (NoC). In particular, a bandwidth-version of Rent's rule is derived, and its implications for future NoC scaling examined. Hop-length distributions for Rent's and other traffic models are then applied to analyse NoC router activity. For fault-tolerant design, a new type of router is proposed based on this analysis, and it is evaluated for mutability and its impact on congestion by further use of the hop-length distributions. It is shown that the choice of traffic model has a significant impact on scaling behaviour, design and fault-tolerant analysis
---
paper_title: A fine-grained link-level fault-tolerant mechanism for networks-on-chip

paper_content:

Silicon technology scaling is continuously enabling denser integration capabilities. However, this comes at the expense of higher variability and susceptibility to wear-out. With an escalating number of on-chip components expected to be defective in near-future chips, modern parallel systems, such as Chip Multi-Processors (CMP), become especially vulnerable to these faults. Just a single link failure in the underlying Network on-Chip (NoC) may cause inter-tile communication to halt and even deadlock, rendering the chip useless. While fault-tolerant routing schemes do exist, they can only handle a finite number of link faults. In this paper, we address permanent wire failures which can occur in on-chip parallel links at manufacture-time or while in operation. Instead of marking the entire link as faulty, we present a methodology where the Partially Faulty Link (PFL) can still be used to transfer data between NoC routers, thus maintaining network connectivity, extending the yield and lifetime of the chip, and allowing for graceful performance degradation. To achieve this, we devise architectural augmentations both to the router and link micro-architectures, along with link fault detection, diagnosis, and re-configuration at the level of wire granularity. Statistical link-level fault models present the usability of PFLs, while relevant load-balancing routing algorithms and low-cost re-transmission mechanisms are also presented and coupled to the proposed architecture. Hardware synthesis demonstrates the feasibility of the proposed extensions to the base NoC architecture. Results obtained from full-system simulations show that high-performance NoCs are realizable in the presence of PFLs.
---
paper_title: A Dual-Layer Method for Transient and Permanent Error Co-Management in NoC Links

paper_content:

We propose an error control method to comanage transient and permanent errors in the data link and physical layers of a network-on-chip (NoC). To reduce energy overhead, a configurable error control coding (ECC) unit adapts the number of redundant wires to the noise conditions, achieving a required error detection capability. Infrequently used redundant wires are utilized as spare wires to replace permanently unusable links. Furthermore, we propose a packet reorganization algorithm that cooperates with a shortened ECC method to support low-latency split transmission. Simulations show that the proposed method reduces packet latency and energy per useful packet by up to 50% and 70%, respectively, compared with previous methods.
---
paper_title: Fine-grained splitting methods to address permanent errors in Network-on-Chip links

paper_content:

We propose a series of fine-grained splitting transmission methods to address permanent errors in Network-on-Chip (NoC) links, maintaining high throughput and ensuring reliability. While prior permanent error management approaches discard the entire or half link, our proposed methods greatly improve wire utilization in the presence of permanent errors. A case study shows that our methods achieve throughput improvement of 234% and 56%, respectively, compared to fault-tolerant routing and half-splitting methods in the presence of high number of permanent errors.
---
paper_title: A low-overhead fault tolerance scheme for TSV-based 3D network on chip links

paper_content:

Three-dimensional die stacking integration provides the ability to stack multiple layers of processed silicon with a large number of vertical interconnects. Through Silicon Vias (TSVs) provide a promising area- and power-efficient way to support communication between different stack layers. Unfortunately, low TSV yield significantly impacts design of three-dimensional die stacks with a large number of TSVs. This paper presents a defecttolerance technique for TSVs-based multi-bit links through an efficient and effective use of redundancy. This technique is ideally suited for three-dimensional network-on-chip (NoC) links. Simulation results demonstrate significant yield improvement, from 66% to 98%, with a low area cost (17% on a vertical link in a NoC switch, which leads a modest 2.1% increase the total switch area) in 130nm technology, with minimal impact of VLSI design and test flows.
---
paper_title: Spare sharing network enhancement for scalable systems

paper_content:

Future systems based on nano-scale devices will provide great potentials for scaling up in system complexity, yet at the same time be highly susceptible to operational faults. While spare units can be used to enhance reliability through the repair-based approaches, redundancy is most effectively utilized if any spare unit can be used to replace any faulty unit. However, such a scheme demands a fully connected network of spare sharing, and will be dreadfully expensive when system size and complexity scale up. In this paper, we focus on scalable systems with spare units shared under interconnect constraints in a limited way. Particularly, we propose an approach to add a small number of connections in the “spare sharing network” to boost system reliability. The proposed methodology identifies and connects the vulnerable units to the exploitable spares, thus strengthening the entire system at low cost. Simulation results confirm that the proposed methodology boosts reliability at the small cost of a few additional interconnections.
---
paper_title: Defect tolerance in homogeneous manycore processors using core-level redundancy with unified topology

paper_content:

Homogeneous manycore processors are emerging for tera-scale computation. Effective defect tolerance techniques are essential to improve the yield of such complex integrated circuits. In this paper, we propose to achieve fault tolerance by employing redundancy at the core-level instead of at the microarchitecture-level. When faulty cores existing on-chip in this architecture, how to reconfigure the processor with the most effective topology is a relevant research problem. We present novel solutions for this problem, which not only maximize the performance of the manycore processor, but also provide a unified topology to operating system and application software running on the processor. Experimental results show the effectiveness of the proposed techniques.
---
paper_title: A fault tolerant NoC architecture using quad-spare mesh topology and dynamic reconfiguration

paper_content:

Network-on-Chip (NoC) is widely used as a communication scheme in modern many-core systems. To guarantee the reliability of communication, effective fault tolerant techniques are critical for an NoC. In this paper, a novel fault tolerant architecture employing redundant routers is proposed to maintain the functionality of a network in the presence of failures. This architecture consists of a mesh of 2x2 router blocks with a spare router placed in the center of each block. This spare router provides a viable alternative when a router fails in a block. The proposed fault-tolerant architecture is therefore referred to as a quad-spare mesh. The quad-spare mesh can be dynamically reconfigured by changing control signals without altering the underlying topology. This dynamic reconfiguration and its corresponding routing algorithm are demonstrated in detail. Since the topology after reconfiguration is consistent with the original error-free 2D mesh, the proposed design is transparent to operating systems and application software. Experimental results show that the proposed design achieves significant improvements on reliability compared with those reported in the literature. Comparing the error-free system with a single router failure case, the throughput only decreases by 5.19% and latency increases by 2.40%, with about 45.9% hardware redundancy.
---
paper_title: Reliability in Application Specific Mesh-Based NoC Architectures

paper_content:

Networks on chips (NoCs) provide a mechanism for handling complex communications in the next generation of integrated circuits. At the same time, lower yield in nano-technology, makes self repair communication channels a necessity in design of digital systems. This paper proposes a reliable NoC architecture based on specific application mapped onto an NoC. This architecture is capable of recovering from permanent switch failures via replacing them by neighboring switches. This method has hardware and power consumption overhead, but significantly improves reliability and has a very little effect on the performance of the system. We suggest a reliability analysis method based on the combinatorial reliability models and use it to evaluate our proposed fault-tolerant NoC architecture.
---
paper_title: QuT: A low-power optical Network-on-Chip

paper_content:

To enable the adoption of optical Networks-on-Chip (NoCs) and allow them to scale to large systems, they must be designed to consume less power and energy. Therefore, optical NoCs must use a small number of wavelengths, avoid excessive insertion loss and reduce the number of microring resonators. We propose the Quartern Topology (QuT), a novel low-power all-optical NoC. We also propose a deterministic wavelength routing algorithm based on Wavelength Division Multiplexing that allows us to reduce the number of wavelengths and microring resonators in optical routers. The key advantages of QuT network are simplicity and lower power consumption. We compare QuT against three alternative all-optical NoCs: optical Spidergon, λ-router and Corona under different synthetic traffic patterns. QuT demonstrates good scalability with significantly lower power and competitive latency. Our optical topology reduces power by 23%, 86.3% and 52.7% compared with 128-node optical Spidergon, λ-router and Corona, respectively.
---
paper_title: Reliability of wireless on-chip interconnects based on carbon nanotube antennas

paper_content:

Design technologies for integrated systems beyond the current CMOS era will present unprecedented advantages such as very high device densities and challenges such as soaring power dissipation issues. Most of the research effort in the emerging area of nanoelectronics has revolved around creating novel devices to replace the traditional CMOS transistor. The development of higher-level communication architectures necessary for integrating such devices into high performance systems has not received the same level of attention so far. With the current trend of CMOS scaling, traditional planar metal-based on-chip interconnect schemes are projected to be the principal bottleneck in meeting the performance needs and specifications of Systems on Chip (SoCs). Three-dimensional integration and on-chip optical and RF communication links have been envisioned as promising alternatives. In this paper we explore the possibility of having an on-chip wireless communication infrastructure using carbon nanotube antennas operating in optical frequencies, and the effect of variations in nanotube properties on the communication behavior.
---

Title: A Survey on Design Approaches to Circumvent Permanent Faults in Networks-on-Chip
Section 1: INTRODUCTION
Description 1: This section provides an overview of technological advancements in semiconductor technologies, the emergence of Networks-on-Chip (NoCs), and the impact of permanent faults due to scaling of transistor sizes.

Section 2: Scope
Description 2: Description of the scope of the survey, focusing on architectural measures to contain permanent faults and excluding other fault classes like transient and intermittent errors, as well as fault models and detection mechanisms.

Section 3: RESEARCH ON FAULT-TOLERANT TOPOLOGIES
Description 3: This section reviews topologies that are both scalable and robust against permanent faults, discussing topology characteristics, common topologies, new topologies, and an analysis of each.

Section 4: RESEARCH ON FAULT-TOLERANT ROUTING ALGORITHMS
Description 4: Discussion of various on-chip routing algorithms and their applications for fault tolerance in NoCs. Includes static and adaptive routing, packet replication, and the impact of using routing tables.

Section 5: RESEARCH ON FAULT-TOLERANT ROUTER MICROARCHITECTURE
Description 5: Introduction to the architecture of a NoC router, the impacts of permanent faults on components, and various robust design solutions including hardware redundancy, modular design, port management, holistic approaches, and containment of link errors.

Section 6: RESEARCH ON SYSTEM-LEVEL REDUNDANCY AND RECONFIGURATION
Description 6: Exploration of higher-level redundancy and reconfiguration techniques, including the use of spare cores, spare routers, and links, and strategies for efficient integration and topology reconfiguration.

Section 7: CONCLUSION
Description 7: Summarizes the findings of the survey, highlights the significance of fault-tolerant design in NoCs, and points to areas requiring further research, including scalable, fault-tolerant design solutions and robust NoC designs using emerging technologies.