Fault-Tolerant Adaptive Routing Algorithm for 2D Torus Network
DOI:
https://doi.org/10.14738/tnc.71.6032Keywords:
Network on Chip, Interconnection Network, Adaptive Routing, Turn Model, Fault ToleranceAbstract
A 2D torus network is one of the most popular networks for parallel processing. We have researched the North-South First (NSF) routing which is applicable to a 2D torus and combines the north-first (NF) and south-first (SF) methods. We focused on the proposal of a routing algorithm aimed at avoiding congestion of the crowded network. It was superior in congestion tolerance but not in fault tolerance. We have therefore been researching algorithms considering fault tolerance of the NSF method. In this paper we propose an NSF-FT method which is a new routing algorithm with improved fault tolerance. We evaluated the congestion resistance and fault tolerance of the proposed method by dynamic communication performance evaluation by simulation. The software simulation showed that the proposed algorithm has higher performance.References
(1) J. Y. Ngai and C. L. Seitz, A framework for adaptive routing in multicomputer networks, ACM SIGARCH Computer Architecture News, vol. 19, no. 1, pp. 6–14, 1991.
(2) T. Schonwald, J. Zimmermann, O. Bringmann, and W. Rosenstiel, Fully Adaptive Fault-Tolerant Routing Algorithm for Network-on-Chip Architectures, Digital System Design Architectures, Methods and Tools, pp. 527–534, 2007.
(3) M. M. Hafizur Rahman, Yukinori Sato, Yasuyuki Miura, and Yasushi Inoguchi, Dynamic Communication Performance of a Hierarchical 3D-Torus Network, IASTED, In 10th International Conference Parallel and Distributed Computing and Networks (PDCN 2011), 2011.
(4) Y. Miura and S. Horiguchi, An Adaptive Routing for Hierarchical Interconnection Network TESH, Proc. of the Third International Conference on Parallel And Distributed Computing, Applications and Technologies, pp. 335–342, 2002.
(5) Y. Miura, Masahiro Kaneko, M. M. Hafizur Rahman, and Shigeyoshi Watanabe, Adaptive Routing Algorithms and Implementation for TESH Network, Communications and Network (CN), vol. 5, no. 1, pp. 34–49, 2013.
(6) W. J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Trans. on Computers, vol. 39, no. 6, pp. 775–785, 1990.
(7) W.J. Dally and Hiromichi Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Trans. on Parallel and Distributed Systems, vol. 4, pp. 466–475, 1993.
(8) M. P. Merlin and J. P. Schweitzer, Deadlock Avoidance in Store-and-Forward Networks-1: Store and Forward Deadlock, IEEE Trans. On Communications, vol. COM-28, no. 3, pp. 345–354, 1980.
(9) W. J. Dally and C. L. Seitz. Deadlock-Free Message Routing in Multiprocessor Interconnection Networks. IEEE Trans. on Computers, vol. C-36, no. 5, pp. 547–553, 1987.
(10) C. S. Yang, Y. M. Tsai, and Y. L. Tsai, Adaptive Routing in k-ary n-cube Multicomputers, Proc. of 1996 International Conference on Parallel and Distributed Systems(ICPADS'96), pp. 404–411, 1996.
(11) J. Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Trans. on Parallel and Distributed Systems, vol. 4, no. 12, pp. 1320–1331, 1993.
(12) D. H. Linder and J. C. Harden, An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Trans. on Computers, vol. C-40, no.1, pp. 2–12, 1991.
(13) R. S. Ramanujam and Bill Lin, Destination-based adaptive routing on 2D mesh networks, 2010 ACM/IEEE Symposium onArchitectures for Networking and Communications Systems (ANCS), pp. 1–12, 2010.
(14) C. J. Glass and L. M. Ni, Maximally Fully Adaptive Routing in 2D Meshes, Proc. of The 19th International Symposium on Computer Architecture, pp. 278–287, 1992.
(15) C. J. Glass and L. M. Ni, The Turn Model for Adaptive Routing, Proc. of The 25th Annual International Symposium on Computer Architecture, pp. 441–450, 1998.
(16) Jie Wu, A Fault-tolerant and Deadlock-free Routing Protocol in 2D Meshes Based on Odd-even Turn Model, IEEE Trans. on Computers, vol. 52, no. 9, pp. 1154–1169, 2003.
(17) A. Jouraku, M. Koibuchi, and H. Amano, An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks, IEEE Trans. on Parallel and Distributed Systems, vol. 18, no. 3, pp. 320–333, 2007.
(18) W. J. Dally, Virtual-Channel Flow Control, IEEE Trans. on Parallel and Destributed Systems, vol. 3, no. 2, pp. 194–205, 1992.
(19) K. Matoyama, Y. Miura, and S. Watanabe, Adaptive routing of the 2-
D torus network, Proc. of FIT2009, RC-005, 2009 (in Japanese).
(20) Y. Miura, K. Shimozono, K. Matoyama, and S. Watanabe, An Adaptive Routing of the 2-D Torus Network Based on Turn Model, Proc. of 4th International Workshop on Advances in Networking and Computing, pp. 587-591,December 2013.
(21) Yasuyuki Miura, Kentaro Shimozono, Kazuya Matoyama, and Shigeyoshi Watanabe, The Static and Dynamic Performance of an Adaptive Routing Algorithm of 2-D Torus Network Based on Turn Model, Proc. of the 2014 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA’ 14), pp. 114–120, July 2014.
(22) Yasuyuki Miura, Kentaro Shimozono, Naohisa Fukase, Shigeyoshi Watanabe, and Kazuya Matoyama, An Adaptive Routing Algorithm of 2-D Torus Network Based on Turn Model: The Communication Performance, International Journal of Networking and Computing (IJNC), pp. 223–238,January 2015.
(23) Tsukasa-Pierre Nakao and Yasuyuki Miura, The Study on Adaptive Routing Algorithm of 2-D Torus Network with Fault Tolerance, IEICE Technical Report (FIIS64),October 2017.
(24) J. Duato A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing Wormhole Networks, Proc. of the International Conference on Parallel Processing, vol. 1, pp. 142-149, 1994.
(25) E. Fleury and P. Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routing Networks, IEEE Trans. on Parallel and Distributed Systems, vol. 9, no. 7, pp. 626–638, 1998.
(26) Naohisa Fukase, Yasuyuki Miura, Shigeyoshi Watanabe, and M. M. Hafizur Rahman, The Performance Evaluation of a 3D Torus Network Using Partial Link-Sharing Method in NoC Router Buffer, IEICE Trans. on Information and Systems, vol. E100–D, no. 10, October 2017.
(27) Naohisa Fukase, Yasuyuki Miura, and Shigeyoshi Watanabe, Link-Sharing Method of Buffer in Router Circuit of Direct-Connection Network, IEEJ Trans EIS, vol. 132, no. 10, pp. 1675–1688, 2012.
(28) N. Aosaka, Y. Fukushima, M. Fukushi, and M. Kameyama, Fault-Tolerant Cogestion-Avoidance Routing for 2D-Mesh Network-on-Chip,Technical report of IEICE. FIIS10, no. 271, March 2010.
