An Advanced Cost-Aware Mapping Algorithm Based on Frog Leaping and Tabu Search for Two-Dimensional Network-On-Chip
الموضوعات : International Journal of Smart Electrical EngineeringAzin Hatefi 1 , Elham Yaghoubi 2
1 - Department of Computer Engineering, Na.C., Islamic Azad University, Najafabad, Iran
2 -
الکلمات المفتاحية: network on two, dimensional chip, application graph, Tabu search algorithm, frog leaping algorithm,
ملخص المقالة :
One of the main challenges in two-dimensional Network on Chip (NoC) architectures is mapping application graphs onto tile-based architectures. Without appropriate mapping algorithms, the system's performance can be significantly degraded. Various mapping algorithms have been proposed for NoC. However, most of these methods have not been able to address the main challenges in mapping algorithms, particularly the communication cost. To this end, a mapping algorithm named FTMA (Frog leaping and Tabu Search Mapping Algorithm) for two-dimensional mesh topology-on-chip base is proposed which utilizes the combination of frog leaping mapping algorithm and Tabu search for mapping operation. Using these two algorithms in the proposed method provides several advantages for the mapping algorithm. These advantages include finding the best mapping in the shortest time, utilizing smart memory to reduce extra costs, and being suitable for most application graphs. The algorithm is also appropriate for graphs with a large number of nodes and provides a final solution. Simulation results show that the proposed mapping algorithm reduces communication costs. The reduction percentages are 7.45, 15.34, 11.60, 15.18, 17.68, and 15.64 compared to the ISFLA, IAM, ELIXIR, PSMAP, ACO, NMAP, LMAP, and BMA methods, respectively.
[1] A. Cakin, S. Dilek, S. Tosun, "Energy-aware application mapping methods for mesh-based hybrid wireless network-on-chips", The Journal of Supercomputing, vol. 80, pp. 15582–15612, July 2024, doi: 10.1007/s11227-024-06062-4.
[2] M. Wang, K.C.M. Lee, B.M.F. Chung, S.V. Bogaraju, H.C. Ng, J.S.J. Wong, "Low-latency in situ image analytics with FPGA-based quantized convolutional neural network", IEEE Trans. on Neural Networks and Learning Systems, vol. 33, no. 7, pp. 2853-2866, July 2022, doi: 10.1109/TNN-LS.2020.3046452.
[3] S. Shafaghi, R. Sabbaghi-Nadooshan, "Opti-m¬a¬l path diagnosis by genetic algorithm for NoCs", International Journal of Smart Electrical Engineering, vol. 1, no. 2, pp. 131-136, June 2012, dor: 20.1001.1.22519246.2-012¬.01.02.8.6.
[4] C. Xu, Y. Liu. P. Li, Y. Yang, "Unified multi-objective mapping for network-on-chip using genetic-based hyper-heuristic algorithms", IET Computers and Digital Techniques, vol. 12, no. 4, pp. 158-166, March 2018, doi: 10.1049/iet-cdt.2017.0156.
[5] C. Marcon, E. Moreno, N. Calazons, F. Moraes, "Comparison of network-on-chip mapping algorithms targeting low energy consumption", IET Computers & Digital Techniques, vol. 2, no. 6, pp. 471-482, Nov. 2008, doi: 10.1049/iet-cdt:20070111.
[6] P. Sharma, S. Biswas, P. Mitra, "Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip", Microprocessors and Microsystems, vol. 64, no. 9, pp. 88-100, Feb. 2019, doi: 10.1016/j.micpro.2018.10.008.
[7] M.Z. Dageleh, M.A. Jamali, "V-CastNet3D: A novel clustering-based mapping in 3-D Network on chip", Nano Communication Networks, vol. 18, no. 5, pp. 51-61, Dec. 2018, doi: 10.1016/j.nanc¬om.2017.11.002.
[8] N. Ghorbani, E. Babaei, S. Laali, P. Farhadi, "Per unit coding for combined economic emission load dispatch using smart algorithms", International Journal of Smart Electrical Engineering, vol. 5, no. 1, pp. 11-21, March 2016, dor: 20.1001.1.22519246.2¬016.¬05.01.3.7.
[9] A. Liu, X. Zhang, Z. Liu, Y. Li, X. Peng, X. Li, Y. Qin, C. Hu, Y. Qiu, H. Jiang, Y. Wang, Y. Li, J. Tang, J. Liu, H. Guo, T. Deng, S. Peng, H. Tian, T.L. Ren, "The roadmap of 2D materials and devices toward chips. nano-micro let", vol. 16, Article Number: 119, Feb. 2024, doi: 10.1007/s40820-023-01273-5.
[10] N. Taherkhani, R. Akbar, F. Safaei, M. Moudi, "A congestion-aware routing algorithm for mesh-based platform networks-on-chip", Microelectronics Journal, vol. 114, Article Number: 105145, Aug. 2021, doi: 10.1016/j.mejo.2021.105145.
[11] P. Kumar, “A Survey on application mapping strategies for network on chip design”, Journal of System Architecture, Vol. 54, Issue. 2, pp. 60-76, 2013.
[12] M. El-Azazy, A.I. Osman, M. Nasr, Y. Ibrahim, N. Al-Hashimi, K. Al-Saad, M.A. Al-Ghouti, M.F. Shibl, A.H. Al-Muhtaseb, D.W. Rooney, A.S. El-Shafie, "The interface of machine learning and carbon quantum dots: From coordinated innovative synthesis to practical application in water control and electrochemistry", Coordination Chemistry Reviews, vol. 517, Article Number: 215976, April 2024, doi: 10.1016/j.ccr.2024.215976.
[13] W. Amin, F. Hussain, S. Anjum, S. Saleem, N.K. Baloch, Y.B. Zikria, H. Yu, "Efficient application mapping approach based on grey wolf optimization for network on chip", Journal of Network and Computer Applications, vol. 219, Article Number: 103729, Oct. 2023, doi: 10.1016/j.jnca.2023.103729.
[14] J. Hu, R. Marculescu, “Energy and Performance Aware Mapping for Regular NOC Architectures,” IEEE Transaction on computer Aided Design ofIntegrated Circuit and Systems, vol. 24, no. 4, pp. 551-562, 2005.
[15] Z. Tang, Y. Wu, J. Wang, T. Ma, "IoT service composition based on improved shuffled frog leaping algorithm", Heliyon, vol. 10, no. 7, Article Number: e28087, April 2024, doi: 10.1016/j.heliyon.2024.e28087.
[16] H.P. Hsu, C.N. Wang, "A hybrid approach combining improved shuffled frog-leaping algorithm with dynamic programming for disassembly process planning", IEEE Access, vol. 9, pp. 57743-57756, 2021, doi: 10.1109/ACCESS.2021.3072831.
[17] X. Guo, C. Fan, M. Zhou, S. Liu, J. Wang, S. Qin, "Human–robot collaborative disassembly line balancing problem with stochastic operation time and a solution via multi-objective shuffled frog leaping algorithm", IEEE Trans. on Automation Science and Engineering, vol. 21, no. 3, pp. 4448-4459, July 2024, doi: 10.1109/TASE.2023.3296733.
[18] R. Phosung, K. Areerak, K. Areerak, "Design and optimization of control system for more electric aircraft power systems using adaptive tabu search algorithm based on state-variables-averaging model", IEEE Access, vol. 12, pp. 76579-76588, May 2024, doi: 10.1109/ACCESS.2024.3406855.
[19] H. Lotfi, "A new hybrid algorithm for multi-objective distribution feeder reconfiguration considering reliability", International Journal of Smart Electrical Engineering, vol. 8, no. 3, pp. 83-92, Sept. 2019, https://dorl.net/dor/20.1001.1.22519246.2019.08.03.1.0.
[20] J.P. Matos-Carvalho, F. Moutinho, A.B. Salvado, T. Carrasqueira, R. Campos-Rebelo, D. Pedro, L.M. Campos, J.M. Fonseca, A. Mora, "Static and dynamic algorithms for terrain classification in UAV aerial imagery", Remote Sensing, vol. 11, no. 21, Article Number: 2501, Oct. 2019, doi: 10.3390/rs11212501.
[21] S. Murali, G. De Micheli, “Bandwidth-constrained mapping of cores onto NoC architectures”, In proc. Proceedings Design, Automation and Test in Europe Conference and Exhibition, Paris, France, France, pp. 896-901, 2004.
[22] C. Marcon, E. Moreno, N. Calazons, F. Moraes, “Comparison of network-on-chip mapping algorithms targeting low energy consumption”, IET Computers & Digital Techniques, Vol. 2, Issue. 6, pp. 471-482, 2008.
[23] B. Yang, L. Guang, T.C. Xu, T. Santti, J. Plosila, "Multi-application mapping algorit-hm for Network- on-Chip platforms”, IEEE 26th Convention of Electrical and Electronics Engineers (IEEE), Eliat, Israel, pp. 542– 544, 2010.
[24] M. Rashedi, A. Khademzadeh, A. Reza, “Elixir: Anew bandwidthconstrained mapping for Networks-on-chip”, Electronics Express, Vol.7, No.2, pp. 73-79, 2010.
[25] Y. Xie. Y. Liu, “A research on NOC mapping with Quantum Ant Colony Algorithm”, in proc. 2017 International Conference on Wireless Communications, Signal Processing and Networking (WiSPNET), Chennai, India, pp. 874-877, 2017.
[26] P. Kaur, SH. Mehta, "Resource provisioning and work flow scheduling in clouds using augmented shuffled frog leaping algorithm", Journal of Parallel and Distributed Computing, vol. 101, no. 4, pp. 41-50, March 2017, doi: 10.1016/j.jpdc.2016.11.003.
[27] P. Sahu, P. Venkatesh, S. Gollapalli, S.Chattopadhyay, “Application Mapping onto Mesh Structured Network-on-Chip Using Particle Swarm Optimization”, IEEE Computer Society Annual Symposium on VLSI, Chennai, India, pp. 335-336, 2011.
[28] M. Keley, A. Khademzadeh, M. Hosseinzadeh, “Efficient Mapping Algorithm on Mesh-based NoCs in Terms of Cellular Learning Automata”, International Arab Journal of Information Technology, Vol. 16, No. 2, PP. 312-322, 2019.
[29] B. Broumand, E. Yaghoubi, B. Barekatain,"An enhanced cost-aware mapping algorithm based on improved shuffled frog leaping in network on chip", The Journal of Supercomputing, vol. 77, pp. 498-522, Jan. 2021, doi: 10.1007/s11227-020-03271-5.
[30] P. Mazaheri Kalahroudi, E. Yaghoubi, B. Barekatain, "IAM: an improved mapping on a 2-Dnetwork on chip to reduce communicationcost and energy consumption", Photonic Network Communications, doi: 10.1007/s11107-020-00911-x, 2020.
[31] T. Maqsood, K. Bilal, S. Madani, "Congestion-aware core mapping for Network-on-Chip based systems using betweenness centrality", Future Generation Computer Systems, vol. 82, no. 5, pp. 459-471, May 2018, doi: 10.1016/j.future.2016.12.031.
