Adaptive Routing Algorithms and Implementation for TESH Network
- 1 Shonan Institute of Technology, Kanagawa, Japan
- 2 ACS Co., Ltd., Tokyo, Japan
- 3 International Islamic University Malaysia (IIUM), Kuala Lumpur, Malaysia
- 4 Shonan Institute of Technology, Kanagawa, Japan
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.
- 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
- 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.
- 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.
- 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
- 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.
- 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.
- 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
- 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
- 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.
- 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
- 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
- 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.