Chaochao Feng
ABSTRACT
We propose a reconfigurable fault-tolerant deflection routing algorithm (FTDR) based on reinforcement learning for NoC. The algorithm reconfigures the routing table through a kind of reinforcement learning---Q-learning using 2-hop fault information. It is topology-agnostic and insensitive to the shape of the fault region. In order to reduce the routing table size, we also propose a hierarchical Q-learning based deflection routing algorithm (FTDR-H) with area reduction up to 27% for a switch in an 8 x 8 mesh compared to the original FTDR. Experimental results show that in the presence of faults, FTDR and FTDR-H are better than other fault-tolerant deflection routing algorithms and a turn model based fault-tolerant routing algorithm.
- C. Constantinescu, "Trends and challenges in VLSI circuit reliability," IEEE Micro, 23(4): 14--19, July-August 2003. Google Scholar
Digital Library
- Z. Lu, M. Zhong and A. Jantsch, "Evaluation of on-chip networks using deflection routing," In Proceedings of ACM Great Lakes Symposium on VLSI, pages 296--301, May 2006. Google ScholarDigital Library
- T. Moscibroda and O. Mutlu, "A case for bufferless routing in on-chip networks," In Proceedings of International Symposium on Computer Architecture, pages 196--207, June 2009. Google ScholarDigital Library
- M. Hayenga, N. E. Jerger and M. Lipasti, "SCARAB: a single cycle adaptive routing and bufferless network," In Proceedings of International Symposium on Microarchitecture, pages 244--254, June 2009. Google ScholarDigital Library
- A. Kohler and M. Radetzki, "Fault-tolerant architecture and deflection routing for degradable NoC switches," In Proceedings of IEEE International Symposium on Networks-on-Chip, pages 22--31, May 2009. Google ScholarDigital Library
- C. Feng, Z. Lu, A. Jantsch, J. Li and M. Zhang, "FoN: Fault-on-Neighbor aware routing algorithm for Networks-on-Chip," In Proceedings of the 23rd IEEE International SoC Conference, pages 441--446, September 2010.Google Scholar
- D. Fick, A. Deorio, G. Chen, V. Bertacco, D. Sylvester and D. Blaauw, "A highly resilient routing algorithm for fault-tolerant NoCs," In Proceedings of Design, Automation and Test in Europe Conference and Exhibition, pages 21--26, April 2009. Google ScholarDigital Library
- J. Wu, "Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels," IEEE Transactions on Parallel and Distributed Systems, 11(2):149--159, February 2000. Google ScholarDigital Library
- Y. J. Suh, B. V. Dao, J. Duato and S. Yalamanchili, "Software-based rerouting for fault-tolerant pipelined communication," IEEE Transactions on Parallel and Distributed Systems, 11(3):193--211, March 2000. Google ScholarDigital Library
- Z. Zhang, A. Greiner and S. Taktak, "A reconfigurable routing algorithm for a fault-tolerant 2D-mesh Network-on-Chip," In Proceedings of ACM/IEEE Design Automation Conference, pages 441--446, June 2008. Google ScholarDigital Library
- R. Holsmark, M. Palesi and S. Kumar, "Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions," Journal of Systems Architecture, 54(3):427--440, March 2007. Google ScholarDigital Library
- V. Puente, J. A. Gregorio, F. Vallejo and R. Beivide, "Immunet: dependable routing for interconnection networks with arbitrary topology," IEEE Transactions on Computers, 57(12):1676--1689, December 2009. Google ScholarDigital Library
- A. Mejia, M. Palesi, J. Flieh, S. Kumar, P. Lopez, R. Holsmark and J. Duato, "Region-based routing: a mechanism to support efficient routing algorithms in NoCs," IEEE Transactions on VLSI Systems, 17(3):356--369, May 2009. Google ScholarDigital Library
- M. Majer, C. Bobda, A. Ahmadinia and J. Teich, "Packet routing in dynamically changing networks on chip," In Proceedings of IEEE International Parallel and Distributed Processing Symposium, pages 154b, April 2005. Google ScholarDigital Library
- E. Nilsson, M. Millberg, J. Oberg and A. Jantsch, "Load distribution with the proximity congestion awareness in a network on chip," In Proceedings of Design, Automation and Test in Europe Conference and Exhibition, pages 1126--1127, March 2003. Google ScholarDigital Library
- X. Chen, Z. Lu, A. Jantsch and S. Chen, "Supporting distributed shared memory on multi-core network-on-chips using a dual microcoded controller," In Proceedings of Design, Automation and Test in Europe Conference and Exhibition, pages 39--44, March 2010. Google ScholarDigital Library
- J. A. Boyan and M. L. Littman, "Packet routing in dynamically changing networks: a reinforcement learning approach," Advances in Neural Information Processing Systems, Vol. 6, pages 671--678, 1994.Google Scholar
Index Terms
- A reconfigurable fault-tolerant deflection routing algorithm based on reinforcement learning for network-on-chip
Recommendations
Fault-tolerant Network-on-Chip based on Fault-aware Flits and Deflection Routing
NOCS '15: Proceedings of the 9th International Symposium on Networks-on-ChipDeflection routing is a promising approach for energy and hardware efficient NoCs. Future VLSI designs will have an increasing susceptibility to failures and breakdowns. The inherent redundancy of NoCs can be used to tolerate such failures. We extended ...
A reconfigurable routing algorithm for a fault-tolerant 2D-Mesh Network-on-Chip
DAC '08: Proceedings of the 45th annual Design Automation ConferenceIn 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 ...
KARL: A Cost-effective Routing Algorithm in Fault Tolerant 3D Network-on-Chip via K-means Assisted Reinforcement Learning
ICBDC '22: Proceedings of the 7th International Conference on Big Data and ComputingIn order to guarantee the communication quality of large-scale multicore processors, 3D Network-on-Chip has become the dominate component for interconnecting various IPs via using 3D stacking technology. A cost-effective routing algorithm KARL is ...
Comments