Adaptive Routing Algorithms and Implementation for TESH Network

Yasuyuki Miura, Masahiro Kaneko, M. M. Hafizur Rahman, Shigeyoshi Watanabe

ACS Co., Ltd., Tokyo, Japan.
International Islamic University Malaysia (IIUM), Kuala Lumpur, Malaysia.
Shonan Institute of Technology, Kanagawa, Japan.

DOI: 10.4236/cn.2013.51004                

Abstract

The Tori-connected mESH (TESH) Network is a k-ary n-cube networks of multiple basic modules, in which the basic modules are 2D-mesh networks that are hierarchically interconnected for higher level k-ary n-cube networks. Many adaptive routing algorithms for k-ary n-cube networks have already been proposed. Thus, those algorithms can also be applied to TESH network. We have proposed three adaptive routing algorithms—channel-selection, link-selection, and dynamic dimension reversal—for the efficient use of network resources of a TESH network to improve dynamic communication performance. In this paper, we implement these routers using VHDL and evaluate the hardware cost and delay for the proposed routing algorithms and compare it with the dimension order routing. The delay and hardware cost of the proposed adaptive routing algorithms are almost equal to that and slightly higher than that of dimension order routing, respectively. Also we evaluate the communication performance with hardware implementation. It is found that the communication performance of a TESH network using these adaptive algorithms is better than when the dimension-order routing algorithm is used.

Keywords

TESH Network; Adaptive Routing Algorithm; Hardware Cost; Router Delay; Communication Performance

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. J. Dally, “Performance Analysis of k-Ary n-Cube Interconnection Networks,” IEEE Transactions on Computers, Vol. 39, No. 6, 1990, pp. 775-785. doi:10.1109/12.53599
[2]	V. K. Jain, T. Ghirmai and S. Horiguchi, “TESH: A New Hierarchical Interconnection Network for Massively Parallel Computing,” IEICE Transactions on Information and Systems, Vol. E80-D, No. 9, 1997, pp. 837-846.
[3]	V. K. Jain, T. Ghirmai and S. Horiguchi, “Reconfiguration and Yield for TESH: A New Hierarchical Interconnection Network for 3-D Integration,” IEEE Proceedings of International Conference Wafer Scale Integration, Austin, 9-11 October 1996, pp. 288-297.
[4]	V. K. Jain and S. Horiguchi, “VLSI Considerations for TESH: A New Hierarchical Interconnection Network for 3-D Integration,” IEEE Transactions on VLSI Systems, Vol. 6, No. 3, 1998, pp. 346-353. doi:10.1109/92.711306
[5]	S. Bhansali, et al., “3D Heterogeneous Sensor System on a Chip for Defense and Security Applications,” Proceedings of the SPIE Defense and Security Symposium (DSS), Vol. 5417, 2004, pp. 413-424.
[6]	G. H. Chapman, V. K. Jain and S. Bhansali, “Defect Avoidance in 3-D Heterogeneous Sensor,” Proceedings of the 1992 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT’04), Cannes, 10-13 October 2005, pp. 67-75.
[7]	Y. Miura and S. Horiguchi, “A Deadlock-Free Routing for Hierarchical Interconnection Network: TESH,” Proceedings of the 4th International Conference on High Performance Computing in Asia-Pacific Region, Beijing, 14-17 May 2000, pp. 128-133. doi:10.1109/HPC.2000.846532
[8]	W. J. Dally, “Virtual-Channel Flow Control,” IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 2, 1992, pp. 194-205. doi:10.1109/71.127260
[9]	C. S. Yang and Y. M. Tsai, “Adaptive Routing in k-Ary n-Cube Multicomputers,” Proceedings of ICPADS’96, Tokyo, 3-6 June 1996, pp. 404-411.
[10]	W. J. Dally and C. L. Seitz, “Deadlock-Free Message Routing in Multiprocessor inter-connection Networks,” IEEE Transactions on Computers, Vol. C-36, No. 5, 1987, pp. 547-553. doi:10.1109/TC.1987.1676939
[11]	W. J. Dally and H. Aoki, “Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 4, 1993, pp. 466-475. doi:10.1109/71.219761
[12]	C. J. Glass and L. M. Ni, “Maximally Fully Adaptive Routing in 2D Meshes,” Proceedings of the 1992 International Conference on Parallel Processing, An Arbor, 17-21 August 1992, pp. 101-104.
[13]	J. Duato, “A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 12, 1993, pp. 1320-1331. doi:10.1109/71.250114
[14]	Y. Miura and S. Horiguchi, “An Adaptive Routing for Hierarchical Interconnection Network TESH,” Proceedings of the 3rd International Conference on Parallel And Distributed Computing, Applications and Technologies, Kanazawa, 3-6 September 2002, pp. 335-342.
[15]	Y. Miura, M. Kaneko and S. Horiguchi, “Examination of Hardware Implementation on Adaptive Routing for Hierarchical Interconnection Network TESH,” Proceedings of International Workshop on High Performance and Highly Survivable Routers and Networks (HPSRN 2008), Sendai, 13-14 March 2008, pp. 17-30.
[16]	L. M. Ni and P. K. McKinley, “A Survey of Wormhole Routing Techniques in Direct Networks,” Proceedings of the IEEE, Vol. 81, No. 2, pp. 62-76, 1993.
[17]	A. Kumary, P. Kunduz, A. P. Singhx, L.-S. Pehy and N. K. Jhay, “A 4.6T bits/s 3.6 GHz Single-Cycle NoC Router with a Novel Switch Allocator in 65 nm CMOS,” 25th International Conference on Computer Design (ICCD 2007), Lake Tahoe, 7-10 October 2007, pp. 63-70. doi:10.1109/ICCD.2007.4601881
[18]	M. Koibuchi, K. Anjo, Y. Yamada, A. Jouraku and H. Amano, “A Simple Data Transfer Technique Using Local Address for Networks-on-Chips,” IEEE Transactions on Parallel and Distributed Systems, Vol. 17, No. 12, 2006, pp. 1425-1437. doi:10.1109/TPDS.2006.166
[19]	G. F. Pfister and V. A. Norton, “Hot Spot Contention and Combining in Multistage Interconnection Networks,” IEEE Transactions on Computers, Vol. 34, No. 10, 1985, pp. 943-948. doi:10.1109/TC.1985.6312198