Congestion estimation of router input ports in Network-on-Chip for efficient virtual allocation

Subject Areas : Computer Networks and Distributed Systems

Midia Reshadi ¹ , Ali Ramezanzad ² , Akram Reza ³

1 - Science and research branch of Islamic Azad University
2 - Department of Computer Engineering Science and Research Branch, Islamic Azad University Tehran, Iran
3 - Computer engineeringdepartman,share qods branch,azad eslamic university

Received: 2018-04-16 Accepted : 2018-06-21 Published : 2018-05-01

Keywords: Modified-Neighbor-on-Path (MNoP), Neighbor-on-Path (NoP), selection strategy, Adaptive routing, Network-on-chip (NoC),

Abstract :

Effective and congestion-aware routing is vital to the performance of network-on-chip. The efficient routing algorithm undoubtedly relies on the considered selection strategy. If the routing function returns a number of more than one permissible output ports, a selection function is exploited to choose the best output port to reduce packets latency. In this paper, we introduce a new selection strategy that can be used in any adaptive routing algorithm. The intended selection function is named Modified-Neighbor-on-Path, the purpose of that is handling the condition of hesitation happening when the routing function provides a set of acceptable output ports. In fact, number of inquiries that each router has sent to its neighbors in determined past cycles is a new parameter that can be combined with number of free slots of adjacent nodes in the latest selection function named Neighbor-on-Path. Performance analysis is performed by using exact simulation tools under different traffic scenarios. Outcomes show how the proposed selection function applied to West-first and North-last routing algorithms outperforms in average delay up to 20 percent on maximum and an acceptable improvement in total energy consumption.

References:

[1] W.J. Dally and B. Towles, “Route Packets, Not Wires: On-Chip Interconnection Networks,” Proc. ACM/IEEE Design Automation Conf., pp. 684-689, 2001.
[2] J.C. Martı´nez, F. Silla, P. Lo´pez, and J. Duato, “On the Influence of the Selection Function on the Performance of Networks of Workstations,” Proc. Int’l Symp. High Performance Computing, pp. 292-299, 2000.
[3] L. M. Ni and P. K. McKinley. A survey of wormhole routing techniques in direct networks. Computer, 26(2):62–76, 1993.
[4] J.Duato,S.Yalamanchili,andL.Ni,Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2002.
[5] G.-M. Chiu, “The Odd-Even Turn Model for Adaptive Routing,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 7, pp. 729- 738, July 2000.
[6] J. Duato, et al., Interconnection networks : an engineering approach. San Francisco, CA: Morgan Kaufmann, 2003, pp. 87.
[7] C. Chen-Ling and R. Marculescu, "Contention-aware application mapping for Network-on-Chip communication architectures," in Computer Design, 2008. ICCD 2008. IEEE International Conference on, 2008, pp. 164-169.
[8] G. Ascia, et al., "Implementation and Analysis of a New Selection Strategy for Adaptive Routing in Networks-on-Chip," Computers, IEEE Transactions on, vol. 57, pp. 809-820, 2008.
[9] B. Niazmand, M. Reshadi, and A. Reza,“ PathAware: A Contention-aware Selection Function for Application-specific Network-On-Chips,” in NORCHIP, 2012, pp. 1–6.
[10] D. Salemi, et al., "Power-aware selection policy for networks on chip," in Design & Technology of Integrated Systems in Nanoscale Era (DTIS), 2011 6th International Conference on, 2011, pp. 1-4.
[11] M. Palesi, et al., "Bandwidth-aware routing algorithms for networks-on-chip platforms," Computers & Digital Techniques, IET, vol. 3, pp. 413-429, 2009.
[12] A. Dana, N. Salehi, “Congestion aware routing algorithm for mesh network-on-chip platform,” in Indian Journal of Science and Technology, Vol. 5, No. 6, pp. 2822-2830, June 2012.
[13] Wu, Dong, Al-Hashimi, Bashir M. and Schmitz, Marcus T. (2006) Improving Routing Efficiency for Network-on-Chip through Contention-Aware Input Selection. In, 11th Asia and South Pacific Design Automation Conference (ASP-DAC 2006).
[14] W. Trumler, S. Schlingmann, T. Ungerer, J. Bahn, and N. Bagherzadeh. Self-optimized Routing in a Network on-a-Chip. In M. Hinchey, A. Pagnoni, F. Ram- mig, and H. Schmeck, editors, Biologically-Inspired Collaborative Computing, volume 268 of IFIP International Federation for Information Processing, pages 199–212. Springer Boston, 2008.
[15] P. Gratz, et al., "Regional congestion awareness for load balance in networks-on-chip," in High Performance Computer Architecture, 2008. HPCA 2008. IEEE 14th International Symposium on, 2008, pp. 203-214.
[16] S. Azampanah, et al., "LATEX: New Selection Policy for Adaptive Routing in Application-Specific NoC," in Parallel, Distributed and Network-Based Processing (PDP), 2012 20th Euromicro International Conference on, 2012, pp. 515-519.
[17] S. Ma, et al., "DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip," SIGARCH Comput. Archit. News, vol. 39, pp. 413-424, 2011.
[18] L. Shu-Yen, et al., "Traffic-and thermal-aware routing for throttled three-dimensional Network-on-Chip systems," in VLSI Design, Automation and Test (VLSI-DAT), 2011 International Symposium on, 2011, pp. 1-4.
[19] H. Hsien-Kai, et al., "Regional ACO-based routing for load-balancing in NoC systems," in Nature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on, 2010, pp. 370-376.
[20] F. Fazzino, M. Palesi, and D. Patti, “Noxim: Network-on-Chip simulator,” http://noxim.sourceforge.net.