The Non-Uniform Communication Performance of Adaptive Routing for Hierarchical Interconnection Network for 3D VLSI
DOI:
https://doi.org/10.14738/tnc.33.1293Keywords:
TESH network, adaptive routing algorithm, communication performanceAbstract
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 have evaluated the dynamic performance of a TESH network using different non uniform traffic patterns. In this paper, we have evaluated by local communication traffic pattern in addition to the hotspot, perfect shuffle, and complement traffic patterns. It was shown that the dynamic communication performance was improved when inter-BM communication appeared frequently such as perfect shuffle and local communication traffic patterns.
References
. W.J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Trans. on Computers, vol. 39, No.6, pp.775--785, 1990.
. V.K. Jain, T. Ghirmai, and S. Horiguchi, TESH: A new hierarchical interconnection network for massively parallel computing, IEICE Trans. on Inf. & Syst., Vol.E80-D, No.9, pp.837-846, 1997.
. 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, pp. 288-297, 1996.
. V.K. Jain and S. Horiguchi, VLSI Considerations for TESH: A New Hierarchical Interconnection Network for 3-D Integration, IEEE Trans on VLSI Systems, Vol.6, No. 3, pp. 346-353, 1998.
. 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), pp.413-424, 2004.
. G. H. Chapman, V. K. Jain and S. Bhansali, Defect Avoidance in 3-D Heterogeneous sensor, Proceedings of the 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT'04), pp.67-75, 2005.
. Y. Miura and S. Horiguchi, A Deadlock-Free Routing for Hierarchical Interconnection Network: TESH, Proc. of the Fourth International Conference on High Performance Computing in Asia-Pacific Region, pp.128-133, 2000.
. M.M. Hafizur Rahman, Y.Inoguchi, Y.Sato, Y.Miura and S.Horiguchi, On Hot-Spot Traffic Pattern of TESH Network, 11th International Conference on Computer and Information Technology(ICCIT 2008), 2008.12.
. M.M. Hafizur Rahman, Y.Inoguchi, Y.Sato, Y.Miura and S.Horiguchi, Dynamic Communication Performance of a TESH Network under the Nonuniform Traffic Patterns, 11th International Conference on Computer and Information Technology(ICCIT 2008), 2008.12.
. M.M. Hafizur Rahman, Y.Inoguchi, Y.Sato, Y.Miura, S.Horiguchi, Dynamic Communication Performance of the TESH Network under Nonuniform Traffic, Journal of Networks, Vol.4, No.10, pp.941-951, 2009.12.
. W.J. Dally, Virtual-Channel Flow Control, IEEE Trans on Parallel and Destributed Systems, Vol.3, No.2, pp.194-205, 1992.
. C. S. Yang and Y. M. Tsai, Adaptive Routing in k-ary n-cube Multicomputers, Proc. of ICPADS '96, pp.404-411, 1996.
. W.J. Dally and C.L.Seitz, Deadlock-Free Message Routing in Multiprocessor inter-connection Networks, IEEE Trans. on Computers, Vol.C-36, No.5, pp.547-553, 1987.
. W.J. Dally and H. Aoki, Deadlock-Free Adaptive Routing in Multicomputer Networks Using Virtual Channels, IEEE Trans. on Parallel and Distributed Systems, Vol. 4, No. 4, pp.466-475, 1993.
. C.J. Glass and L. M. Ni, Maximally Fully Adaptive Routing in 2D Meshes, ISCA92, pp.278-287, 1992.
. 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.
. 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.
. Y. Miura, M. Kaneko and S. Horiguchi, Examination of Hardware Implementation on Adaptive Routing for Hierarchical Interconnection Network TESH, Proc. of International Workshop on High Performance and
Highly Survivable Routers and Networks (HPSRN 2008), 2008.
. Y.Miura, M.Kaneko, S.Watanabe, Adaptive Routing Algorithms and Implementation for Interconnection Network TESH for Parallel Processing, The 35th IEEE Conference on Local Computer Networks (LCN)，2010.10.
. Y.Miura, M.Kaneko, M.M.Hafizur Rahman and S.Watanabe, Adaptive Routing Algorithms and Implementation for TESH Network, Communications and Network (CN), Vol.5, No.1, pp.34-49, 2013.02.
. Y. Miura, S. Watanabe, and M.M. Hafizur Rahman, The Communication Performance of Adaptive Routing for Hierarchical Interconnection Network for 3D VLSI, Proc. of 2015 International Conference on Information, Computer and Communication Engineering (ICC 2015) (Accepted).
. N.Tsuda, Hierarchical redundancy for array-structure WSIs, Journal of Systems and Computers in Japan, Vol.24, No.7, pp.13--30, 1993.
. L. M. Ni and P. K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, Vol.26, No.2, pp.62-76, 1993.
. M. Grammatikakis, D.F. Hsu, M. Kratzel and J.F. Sibeyn, Packet routing in fixed connection networks: a survey, Journal of Parallel and Distributed Computing, Vol. 54, No. 2, pp.77–132, 1998.
. Andrew A. Chien and Jae H. Kim, Planer-Adaptive Routing:Low-cost Adaptive Networks for Multiprocessors, Journal of the ACM, Vol.42, No.1, pp.91–123, 1995.
. P.R. Miller, Efficient Communications for Fine-Grain Distributed Computers, Ph.D. Dissertation, Southampton University, U.K., 1991.
