A Deadlock-Free and Connectivity-Guaranteed Methodology for Achieving Fault-Tolerance in On-Chip Networks
| Autor: | Xiaowei Ren, Michel A. Kinsy, Nanning Zheng, Pengju Ren, Sudhanshu Sane |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Router
020203 distributed computing Computer science business.industry Distributed computing Fault tolerance 02 engineering and technology Adaptive routing Deadlock Network topology 020202 computer hardware & architecture Theoretical Computer Science Network congestion Network on a chip Computational Theory and Mathematics Hardware and Architecture Robustness (computer science) 0202 electrical engineering electronic engineering information engineering System on a chip business Software Computer network |
| Zdroj: | IEEE Transactions on Computers. 65:353-366 |
| ISSN: | 0018-9340 |
| Popis: | To improve the reliability of on-chip network based systems, we design a deadlock-free routing technique that is more resilient to component failures and guarantees a higher degree of node connectivity. The routing methodology consists of three key steps. First, we determine the maximal connected subgraph of the faulty network by checking whether the defective components happen to be the cut vertices and bridges of the network topology. A precise fault diagnosis mechanism is used to identify partial defective routers. Second, we construct an acyclic channel dependency graph that breaks all cycles and preserves connectivity of the maximal connected subgraph . This is done through the cycle-breaking and connectivity guaranteed (CBCG) algorithm. Finally, we introduce a fault-tolerant adaptive routing scheme that can be used with or without virtual channels for network congestion avoidance and high-throughput routing. The simulation results show both the effectiveness and robustness of the proposed approach. For an $8 \times 8$ 2D-Mesh with 40 percent of link damage, full connectivity and deadlock freedom are still archived without disabling any faultless router in 98.18 percent of the simulations. In a 2D-Torus, the simulation percentage is even higher (99.93 percent). The hardware overhead for supporting the introduced features is minimal. An on-line implementation of cbcg using TSMC 65nm library has only 0.966 and 1.139 percent area overhead for the $8\times8$ and $16 \times 16$ 2D-Meshes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|