Continuous allocation and hybrid migration of processors to improve the performance of online mapping on a 2-D network on chip

Document Type : Original Article

Authors

1 Faculty member of Islamic Azad University of Ramhormoz

2 ّFaculty member of Islamic Azad University of Shahr e Qods

Abstract

The network on chips was introduced as a solution to improve coherence between the network components. As one aspect of the network on chip design is mapping, so, in this paper, we have presented different concepts and parameters in the online mapping for different jobs in the network on chips. Thus, three essential steps are considered in the online mapping for different jobs in the network on chips which are finding the appropriate size of sub-mesh for input job, finding a sub-mesh place in integrating the mesh for online job allocation and finding the main place in sub-mesh. Also, previous efficient models to select the dimensions of the sub-mesh, MD, MPN and MT&MPN, previous processor allocation mechanisms, TRB and TCB, and the traditional processor migration methods based on two-column boundary, two-row boundary, limited left-right compaction, and limited top-down compaction for mesh topology are considered and compared against the proposed hybrid migrations. The mentioned algorithms are used to increase continuity and decrease latency in multiprocessor systems. Since the main goal in the development of the proposed methods is to achieve the maximum performance, so in this process, the impact of different performance parameters will be compared against the previous mechanisms. In this paper, 6 algorithms, which have achieved better performance, have been selected among the 45 ones. We have demonstrated that using hybrid migration strategies enable us to limit the number of processors migrations. Moreover, MT&MPN/TCB/HCM has revealed better results among these algorithms with the average job execution time %38.0248, average job response time %99.5387, and average system utilization %48.0239. Indeed, simulation results show that MPN/TRB/HBM has maximum results of the average power consumption %6.68, and the best results of the average job execution time %38.21.

Keywords

References

  1. A. Gangwar, Z. Xu, NK. Agarwal, R. Sreedharan, and A. Prasad, “Traffic Driven Automated Synthesis of Network-on-Chip from Physically Aware Behavioral Specification”, IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pp. 122–127, 2019.
  2. W. Liao, H. Deng, Y. Luo, S. Xiao, C. Li, Z. Yu, “An Efficient and Low-Overhead Chip-to-Chip Interconnect Protocol Design for NOC”, IEEE International Conference on Integrated Circuits, Technologies and Applications (ICTA), pp. 77–78, 2019.
  3. WT. Shen, CH. Chao, YK. Lien, and AY. Wu, “A New Binomial Mapping and Optimization Algorithm for Reduced-Complexity Mesh-Based On-Chip Network”, in Proceedings of the First International Symposium on Networks-on-Chip (NOC '7), pp. 317-322, 2007.
  4. J. Janidarmian, A. Khademzadeh, and M. Tavnapour, “Onyx: A new heuristic bandwidth-constrained mapping of cores onto tile based Network on Chip”, IEICE Electronics Express, Vol. 6, No. 1, pp. 1-7, 2009.
  5. K. Windisch, V. Lo, and B. Bose, “Contiguous and non-contiguous processor allocation algorithms for k-ary n-cubes”, Technical Report, University of Oregon, Oregon, USA, 1995.
  6. S. Bani-Mohammad, and I. Ababneh, “Improving system performance in non-contiguous processor allocation for mesh interconnection networks”, Simulation Modelling Practice and Theory, Vol. 80, pp. 19-31, 2018.
  7. S. Bani-Mohammad, “Efficient Processor Allocation Strategies for Mesh-Connected Multicomputers”, PhD Thesis, The Faculty of Information and Mathematical Sciences University of Glasgow, Glasgow, U.K, 2008.
  8. S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh, and L. Mackenzie, “Comparative evaluation of contiguous allocation strategies on 3D mesh multicomputers”, Journal of Systems and Software, Vol. 82, No. 2, pp. 307-318, 2009.
  9. KJ. Windisch, W. Liu, and B. Nitzberg, “Non-contiguous processor allocation algorithms for mesh-connected multicomputers”, IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 7, pp. 712-726, 1997.
  10. LK. Goh, and B. Veeravalli, “Design and performance evaluation of combined first-fit task allocation and migration strategies in mesh multicomputer systems”, Journal of Parallel Computing, Vol. 34, No. 9, pp. 508–520, 2008.
  11. A. Reza, and M. Rafie, “Improving Multi Task Running Time in Two Column Boundary Allocation Method in Mesh-based Chip Multiprocessors Using Combined Migration Mechanisms”, International Journal of Computer & Information Technologies (IJOCIT), Vol. 3, No. 3, pp. 743-755, 2015.
  12. A. Reza, and M. Rafie, “Performance improvement in multiprocessors using two row boundary allocation method and online dynamic compaction algorithm”, International journal of computer applications (IJCA), Vol. 123, No. 1, pp. 14-20, 2015.
  13. M. Rafie, A. Khademzadeh, A. Reza, and M. Reshadi, “External Fragmentation Aware Dynamic Multi Task Mapping on Mesh Interconnection”, Journal of Computational and Theoretical Nanoscience, Vol. 13, No. 1, pp. 958-963, 2016.
  14. M. Rafie, A. Khademzadeh, A. Reza, and M. Reshadi, “Performance evaluation of task migration in contiguous allocation for mesh interconnection topology”, Journal of Supercomputing, Vol. 72, No. 4, pp. 1660-1677, 2016.
  15. DD. Sharma, and DK. Pradhan, “A fast and efficient strategy for submesh allocation in mesh-connected parallel computers”, Fifth IEEE Symposium on Parallel and Distributed Processing, pp. 682–689, 1993.
  16. G. Chmaj, D. Zydek, and L. Koszalka, “Allocation Algorithms Problems in Mesh-Connected Systems”, 2004.
  17. S. Khan, S. Anjum, U. A. Gulzari, M. K. Afzal, T. Umer, and F. Ishmanov, “An Efficient Algorithm for Mapping Real Time Embedded Applications on NoC Architecture”, IEEE Access, Vol. 6, pp. 16324–16335, 2018.
  18. F. Ge, C. Cui, F. Zhou, and N. Wu, “A Multi-Phase Based Multi-Application Mapping Approach for Many-Core Networks-on-Chip”, Micromachines, Vol. 12, No. 6, 2021.
  19. R. Khasanov, and J. Castrillon, “Energy-efficient Runtime Resource Management for Adaptable Multi-application Mapping”, In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE), Grenoble, France, 9–13, pp. 909–914, March 2020.
  20. W. Amin, F. Hussain, S. Anjum, S. Khan, N. K. Baloch, Z. Nain, and S. W. Kim, “Performance evaluation of application mapping approaches for network-on-chip designs”, IEEE Access, Vol. 8, pp. 63607–63631, 2020.
  21. L. Zhang, S. Li, L. Qu, Z. Kang, S. Wang, J. Chen, and L. Wang, “MAMAP: Congestion Relieved Memetic Algorithm based Mapping Method for Mapping Large-Scale SNNs onto NoC-based Neuromorphic Hardware”, In Proceedings of the 2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems (HPCC/SmartCity/DSS), pp. 640–647, 2020.
  22. L. Mei, P. Houshmand, V. Jain, S. Giraldo, M. Verhelst, “ZigZag: Enlarging Joint Architecture-Mapping Design Space Exploration for DNN Accelerators”, IEEE Transactions on Computers, Vol. 70, No. 8, pp. 1160–1174, 2021.
  23. J. Fang, H. Zong, H. Zhao, and H. Cai, “Intelligent mapping method for power consumption and delay optimization based on heterogeneous NoC platform”, Electronics, Vol. 8, No. 8, 912, 2019.
  24. S. Bani-Ahmad, “On Improved Processor Allocation in 2D Mesh-based Multicomputers: Controlled Splitting of Parallel Requests”, International Conference on Communication, Computing and Security (ICCCS'11), pp. 204-209, 2011.
  25. R. Zolfaghari, “Efficient and Quick Algorithm for Processor Allocation in Mesh Multi-Computers Network”, International Journal of Engineering and Advanced Technology (IJEAT), Vol. 2, No. 5, pp. 517-523, 2013.
  26. N. Kumar, and DP. Vidyarthi, “A novel energy-efficient scheduling model for multi-core systems”, Cluster Computing, 2020, https://doi. org/10.1007/s10586-020-03143-w.
  27. AB. Kahng, L. Bin, P. Li-Shiuan, and K. Samadi, “ORION 2.0: a fast and accurate NoC power and area model for early-stage design space exploration”, Design, automation & test in Europe conference & exhibition, DATE’09, pp 423–428, 2009, http://hdl.handle.net/1721.1/60547.
 
  1. A. Ghorbani, and H. Khodadadi, “Optimum design of WDM networks by EDFA optical amplifiers with the approach of improving communication distance and data transmission rate”, Journal of Applied Information and Communication Technology Innovations, Vol. 1, No. 1, pp. 67-73, 2021 (in Persian).

 

Volume 4, Issue 2 - Serial Number 2
Summer 2023
March 2021
Pages 71-86

Files

Share

How to cite

Statistics