Presenting a Network-on-Chip Mapping Approach Based on Harmony Search Algorithm
Subject Areas : electrical and computer engineering
Zahra Bagheri
1
,
Fatemeh Vardi
2
*
,
Alireza Mahjoub
3
1 - Department of Computer and Information Technology, Parana Branch, Islamic Azad University
2 -
3 - Department of Computer Engineering, Karaj Branch, Islamic Azad University
Keywords: Networks on chip, mapping, harmony search, heuristic,
Abstract :
In network-on-chip implementation, mapping can be considered as an important step in application implementation. The tasks of an application are often represented in the form of a core graph. The cores establish a link between themselves using a communication platform and often the network on the chip. For finding proper mapping for an application, developers have proposed various algorithms. In most cases, due to the complexity, exact search methods are used to find the mapping. However, these methods are suitable for networks with small dimensions. As the size of the network increases, the search time also increases exponentially. This article, from the perspective of a heuristic approach, uses the harmony search method to decide when to connect cores to routers. Our approach uses an improved version of the harmony search algorithm with a focus on reducing power consumption and delay. Algorithm complexity analysis reveals a more appropriate solution compared to similar algorithms with respect to application traffic pattern. Compared to similar methods, the algorithm achieves 39.98% less delay and 61.11% saving in power consumption.
[1] A. Hemani, et al., "Network on chip: an architecture for billion transistor era," in Proc. of the IEEE NorChip Conf., pp. 166-173, Turku, Finland, Nov. 2000.
[2] C. L. Chou and R. Marculescu, "Contention-aware application mapping for network-on-chip communication architectures," in Proc. IEEE Int. Conf. on Computer Design, ICCD'08, pp. 164-169, Lake Tahoe, CA, USA, 12-15 Oct. 2008.
[3] X. S. Yang, "Harmony search as a metaheuristic algorithm search algorithm: theory and applications," Studies in Computational Intelligence, vol 191, pp.1-14, Springer, Berlin, Heidelberg, 2009.
[4] C. Marcon, T. Webber, and A. A. Susin, "Models of computation for NoC mapping: timing and energy saving awareness," Microelectronics J., vol. 60, pp. 129-143, Feb. 2017.
[5] P. Mesidis, Mapping of Real-Time Applications on Network-on-Chip Based MPSOCS, MS Thesis, Department of Computer Science, University of York, Dec. 2011.
[6] P. K. Sahu and S. Chattopadhyay, "A survey on application mapping strategies for network-on-chip design," J. of Systems Architecture, vol. 59, no. 1, pp. 60-76, Jan. 2013.
[7] A. Bender, "MILP based task mapping for heterogeneous multiprocessor systems," in Proc. of International Conf. on Design and Automation, vol. 96, pp. 190-197, Sep. 1996.
[8] K. Srinivasan, K. S. Chatha, and G. Konjevod, "Linear-programming-based techniques for synthesis of network-on-chip architectures," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 14, no. 4, pp. 407-420, Apr. 2006.
[9] P. Ghosh, A. Sen, and A. Hall, "Energy efficient application mapping to NoC processing elements operating at multiple voltage levels," in Proc. 3rd ACM/IEEE Intl Symp. on Networks-on-Chip, pp. 80-85, La Jolla, CA, USA, 10-13 May 2009.
[10] C. Ostler and K. S. Chatha, "An ILP formulation for system-level application mapping on network processor architecture," in Proc. of Design, Automation and Test in Europe, DATE'07, pp. 99-104, Nice, France, 16-20 Apr. 2007.
[11] J. Hu and R. Marculescu, "Communication and task scheduling of application-specific networks-on-chip," IEEE Proc. Computers & Digital Techniques, vol. 152, no. 5, pp. 643-651, Sept. 2005.
[12] S. Tosun, "Clustered-based application mapping method for network-on-chip," J. of Advances in Engineering Software, vol. 42, no. 10, pp. 868-874, Oct. 2011.
[13] R. Marculescu and J. Hu, "Energy-aware mapping for tile-based NoC architectures under performance constraints," in Proc. Asia and South Pacific Design Automation Conf., ASP-DAC'03, pp. 233-239, Kitakyushu, Japan,2 4-24 Jan. 2003.
[14] R. Marculescu and J. Hu, "Energy-and performance-aware mapping for regular NoC architectures," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 4, pp. 180-187, Apr. 2005.
[15] M. Reshadi, A. Khademzadeh, and A. Reza, "Elixir: a new bandwidth-constrained mapping for networks-on-chip," IEICE Electronics Express, vol. 7, no. 2, pp. 73-79, 2010.
[16] R. Pop and S. Kumar, A Survey of Techniques for Mapping and Scheduling Applications to Network on Chip Systems, Technical Report ISSN 1404-0018 04:4, ING Jönköping, 2004.
[17] C. Xu, et al., "Optimization strategy of regular NoC mapping using genetic-based hyper-heuristic algorithm," Symmetry, vol. 14, no. 8, Article ID: 1637, Aug. 2022.
[18] C. Xu, Y. Liu, P. Li, and Y. Yang, "Unified multi-objective mapping for network-on-chip using genetic-based hyper-heuristic algorithms," IET Comput. Digit. Tech, vol. 12, no. 4, pp. 158-166, Jul. 2018.
[19] H. M. Ali, S. Ashrafinia, and J. Liu, "Wireless mesh network planning using quantum inspired evolutionary algorithm [C]," in Proc. IEEE Conf. on Vehicular Technology, 5 pp., San Francisco, CA, USA, 5-8 Sept. 2015.
[20] Y. Xie and Y. Liu, "A research on NoC mapping with quantum ant colony algorithm," in International Conf. on Wireless Communications, Signal Processing and Networking, WiSPNET'17, pp. 874-877, Chennai, v20-24 Mar. 2017.
[21] E. Carvalho, N. Calazans, and F. Moraes, "Dynamic task mapping for MPSoCs," IEEE Design and Test of Computers, vol. 27, no. 5, pp. 26-35, Sept./Oct. 2010.
[22] T. Lei and S. Kumar, "A two-step genetic algorithm for mapping task graphs to a network on chip architecture," in Proc. of the Euromicro Symp. on Digital System Design, DSD'03, pp. 180-187, Belek-Antalya, Turkey, 1-6 Sept. 2003.
[23] A. Hansson, K. Goossens, and A. Radulescu, "A unified approach to constrained mapping and routing on network-on-chip architectures," in Proc. IEEE/ACM Int Conf. on Hardware/Software Codesign and System Synthesis, CODES+ISSS'05, pp. 75-80, Jersey City, NJ, USA,19-21 Sept. 2005.
[24] W. T. Shen, C. H. Chao, Y. K. Lien, and A. Y. Wu, "A new binomial mapping and optimization algorithm for reduced-complexity mesh-based on-chip network," in Proc. of First Int. Symp. on Networks-on-Chip, NOCS'07, pp. 317-322, Princeton, NJ, USA, 7-9 May 2007.
[25] S. Murali and G. De Micheli, "Bandwidth constrained mapping of cores onto NoC architectures," in Proc. of Design, Automation, and Test in Europe Conf. and Exhibition, vol. 2, pp. 896-901, Feb. 2004.
[26] P. K. Sahu, P. Venkatesh, S. Gollapalli, and S. Chattopadhyay, "Application mapping onto mesh structured network-on-chip using particle swarm optimization," in Proc. IEEE Int. Symp. VLSI, ISVLSI'11, pp. 335-336, Chennai, India, 4-6 Jul. 2011.
[27] S. Murali and G. De Micheli, "Bandwidth constrained mapping of cores onto NoC architectures," in Proc. of Design, Automation, and Test in Europe Conf. and Exhibition, DATE'04, vol. 2, pp. 896-901, Paris, France, 16-20 Feb. 2004.
[28] S. Khan, et al., "An optimized hybrid algorithm in term of energy and performance for mapping real time workloads on 2d based on-chip networks," Springer Science + Business Media, LLC, Part of Springer Nature, vol. 48, no. 12, pp. 4792-4804, Dec. 2018.
[29] S. Khan, et al., "An efficient algorithm for mapping real time embedded applications on NoC architecture," IEEE ACCESS, vol. 6, pp. 16324-16335, 2018.
[30] S. Khan, S. Anjum, U. A. Gulzari, T. Umer, and B. S. Kim, "Bandwidth-constrained multi-objective segmented brute-force algorithm for efficient mapping of embedded applications on NoC architecture," IEEE ACCESS, vol. 6, pp. 11242-11254, 2017.
[31] G. Z. Woo, K. J. Hoon, and G. Loganathan, "A new heuristic optimization algorithm: harmony search," Simulation, vol. 76, no. 2, pp. 60-68, Feb. 2001.
[32] Z. W. Geem and Y. H. Cho, "Optimal design of water distribution networks using parameter-setting-free harmony search for two major parameters," J. of Water Resources Planning and Management, vol. 137, no. 4, pp. 377-380, Oct. 2010.
[33] N. Theodossiou and I. Kougias, "Harmony search algorithm," WIT Trans. on State of the Art in Science and Engineering, vol. 56, Ch. 7, 25 pp., Jul. 2012.
[34] P. K. Sahu, K. Manna, T. Shah, and S. Chattopadhyay, "A constructive heuristic for application mapping onto mesh based network-on-chip," J. of Circuits, Systems, and Computers, vol. 24, no. 8, Article ID: 1550126, Aug. 2015.
[35] C. Marcon, et al., "Exploring NoC mapping strategies: an energy and timing aware technique," in Proc. Design, Automation and Test in Europe, pp. 502-507, Munich, Germany, 7-11 Mar. 2005.
[36] M. Mahdavi, M. Fesanghary, and E. Damangir, "An improved harmony search algorithm for solving optimization problems," Appl Math Comput., vol. 188, no. 2, pp. 1567-1579, May 2007.
[37] "Noxim, http://noxim.sourceforge.net [available on dated: 01.08.2014]."
[38] D. Fernandes, M. Neto, L. F. B. Soares, M. M. Freire, and P. R. M. Inácio, "Chapter 10-on the self-similarity of traffic generated by network traffic simulators," Modeling and Simulation of Computer Networks and Systems, pp. 285-311, 2015.