Optimal network architectures for minimizing average distance in k-ary n-dimensional mesh networks

ABSTRACT

A general expression for the average distance for meshes of any dimension and radix, including unequal radices in different dimensions, valid for any traffic pattern under zero-load condition is formulated rigorously to allow its calculation without network-level simulations. The average distance expression is solved analytically for uniform random traffic and for a set of local random traffic patterns. Hot spot traffic patterns are also considered and the formula is empirically validated by cycle true simulations for uniform random, local, and hot spot traffic. Moreover, a methodology to attain closed-form solutions for other traffic patterns is detailed. Furthermore, the model is applied to guide design decisions. Specifically, we show that the model can predict the optimal 3-D topology for uniform and local traffic patterns. It can also predict the optimal placement of hot spots in the network. The fidelity of the approach in suggesting the correct design choices even for loaded and congested networks is surprising. For those cases we studied empirically it is 100%.

References

1. A. Agarwal. Limits on interconnection network performance. IEEE Trans. on Parallel and Distributed Systems, 2(4):398--412, 1991.
2. G. E. P. Box and K. B. Wilson. On the experimental attainment of optimum conditions. Journal of the Royal Statistical Society. Series B (Methodological), 13(1):1--45, 1951.
3. W. Dally and B. Towles. Principles and practices of interconnection networks. Morgan Kaufmann, 2004.
4. W. J. Dally. Performance analysis of k-ary n-cube interconnection networks. IEEE Trans. on Computers, 39(6):775--785, June 1990.
5. S. Foroutan, Y. Thonnart, R. Hersemeule, and A. Jerraya. An analytical method for evaluating network-on-chip performance. In Proc. Design, Automation Test in Europe Conference, pages 1629--1632, March 2010.
6. Z. Guz, I. Walter, E. Bolotin, I. Cidon, R. Ginosar, and A. Kolodny. Network delays and link capacities in application-specific wormhole NoCs. VLSI Design, 2007.
7. R. Holsmark. Deadlock free routing in mesh networks on chip with regions. Licentiate thesis, Department of Computer and Information Science, Linköpings Universitet, 2009.
8. F. Jafari, Z. Lu, A. Jantsch, and M. Yaghmaee. Buffer optimization in network-on-chip through flow regulation. IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, 29(12):1973--1986, December 2010.
9. A. Khonsari, M. Ould-Khaoua, and J. Ferguson. A general analytical model of adaptive wormhole routing in k-ary n-cube interconnection networks. SIMULATION SERIES, 35:547--554, 2003.
10. A. Kiasari, D. Rahmati, H. Sarbazi-Azad, and S. Hessabi. A Markovian performance model for networks-on-chip. In Proc. Euromicro Conf. on Parallel, Distributed and Network-Based Processing, pages 157--164, February 2008.
11. S. Koohi, M. Mirza-Aghatabar, S. Hessabi, and M. Pedrani. High-level modeling approach for analyzing the effects of traffic models on power and throughput in mesh-based NoCs. In IEEE/ACM Int. Conf. on VLSI Design, pages 415--420, January 2008.
12. H. Liu, W. Lin, and Y. Song. An efficient processor partitioning and thread mapping strategy for mesh-connected multiprocessor systems. In Proc. ACM symposium on Applied computing, page 412. ACM, 1997.
13. Z. Lu, M. Millberg, A. Jantsch, A. Bruce, P. Van der Wolf, and T. Henriksson. Flow regulation for on-chip communication. In Proc. of Design Automation and Test Europe Conf., April 2009.
14. U. Ogras, P. Bogdan, and R. Marculescu. An analytical approach for network-on-chip performance analysis. IEEE Trans. on Comp.-Aided Design of Integrated Circuits and Systems,, 29(12):2001--2013, December 2010.
15. Y. Qian, Z. Lu, and W. Dou. Worst-case flit and packet delay bounds in wormhole networks on chip. IEICE Transactions, 92--A(12):3211--3220, 2009.
16. Y. Qian, Z. Lu, and W. Dou. Analysis of worst-case delay bounds for on-chip packet-switching networks. IEEE Trans. on Comp.-Aided Design of Integrated Circuits and Systems,, 29(5):802--815, May 2010.
17. A. Weldezion, M. Grange, D. Pamunuwa, Z. Lu, A. Jantsch, R. Weerasekera, and H. Tenhunen. Scalability of network-on-chip communication architecture for 3-D meshes. In Proceedings of the 2009 3rd ACM/IEEE International Symposium on Networks-on-Chip, pages 114--123. IEEE Computer Society, 2009.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• General and reference

  • Cross-computing tools and techniques

    • Design

    • Performance

• Networks

  • Network types

    • Packet-switching networks