Performance Improvement in Multiprocessors Using Three Steps of Non Contiguous Migration for Online Mapping

Document Type : Persian Original Article

Authors

1 Department of Computer Engineering, Shahr-e-Qods Branch, Islamic Azad University, Tehran, Iran.

2 Department of Computer Engineering, Ramhormoz Branch, Islamic Azad University, Ramhormoz, Iran.

Abstract

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 which are finding the appropriate size of sub-mesh, finding a sub-mesh place in integrating the mesh for online task allocation and finding the main place in sub-mesh for online task mapping. For this purpose, efficient previous models to select the dimensions of the sub-mesh, the processor migration methods based on the two-row boundary, limited left-right compaction, limited top-down compaction, online dynamic compaction-four corner (ODC-FC) and hybrid migrations for mesh topology are compared with the proposed algorithm to check the comparative performance. Also, the impact of different performance parameters which are average job execution time and average system utilization will be compared against the previous mechanisms to achieve the appropriate configuration of the network on chips. It is worth noting that in this article, 7 algorithms, which have achieved better performance, have been selected among the 29 ones. We have demonstrated that using hybrid migration strategies enable us to limit the number of processors migrations. Consequently, significant improvements have been achieved in the average job execution time (%36 ~ %38.1), and the average system utilization (%38.2~%48.5).

Keywords


 [1] P. K. Sahu and S. Chattopadhyay, “A survey on application mapping strategies for Network-on-Chip design”, Journal of Systems Architecture, Vol. 59, pp. 60–76, 2013.
[2] S. Bani-Mohammad, 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.
[3] R. Zolfaghari, “Efficientand Quick Algorithm for Processor Allocation in Mesh Multi-Computers Network”, International Journal of Engineering and Advanced Technology (IJEAT), Vol. 2, No. 5, 2013.
[4] D. D. Sharma, and D. K. Pradhan, “A fast and efficient strategy for submesh allocation in mesh-connected parallel computers”, in Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, pp. 682–689, 1993.
[5] 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, USA, 2015.
[6] 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.
[7] M. Rafie, A. Khademzadeh, A. Reza, M. Reshadi, “Performance Evaluation of Task Migration in Contiguous Allocation for Mesh Interconnection Topology”, The Journal of Supercomputing, Vol. 72, No. 4, pp. 1660-1677, 2016.
[8] G. Chmaj, D. Zydek, and L. Koszalka, “Allocation Algorithms Problems in Mesh-Connected Systems”, 2nd Student's Science Conference, 2004.
[9] A. Reza, and R. Faghih Mirzaee, “Non-preemptive offline multi-job mapping for a photonic network on a chip”, Nano Communication Networks, Vol. 11, pp. 11-23, 2017.
[10] L. K. 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] 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 Proceedings of the First International Symposium on Networks-on-Chip (NOC '7), pp. 317-322, 2007.
[12] F. Moosavi, M. rafie, and D. Zeinalabedini, “Dynamic and Static Mapping Methods in Two-Dimensional Network on Chips”, International Journal of Computer & Information Technologies (IJOCIT), Vol. 4, No. 2, pp. 23-33, 2016.
[13] S. Bani-Mohammad, “On the Performance of Job Scheduling for Noncontiguous Allocation in 2D Mesh-connected Multicomputers”, in Proceedings of the 16th IEEE Mediterranean Electrotechnical Conference (MELECON), pp. 92-96, 2012.
[14] Y. Zhu, “Efficient processor allocation strategies for mesh-connected parallel computers”, Journal of Parallel and Distributed Computing, Vol. 16, No. 4, pp. 328–337, 1992.
[15] S. Bani-Ahmad, “On Improved Processor Allocation in 2D Mesh-based Multicomputers: Controlled Splitting of Parallel Requests”, in Proceedings of the 2011 International Conference on Communication, Computing and Security (ICCCS'11), pp. 204-209, 2011.
[16] S. B. Ahmad, “Bounded Gradual-Request-Partitioning-Based Allocation Strategies in 2D-Mesh Multicomputers”, International Journal of Digital Content Technology and its Applications, Vol. 5, No. 1, 2011.
[17] 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. 9, No. 912, 2019.