International Journal of Distributed and Cloud Computing

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Processor Allocation Two-Dimensional MeshBased Multi-Computer Systems: Protecting against Over-Partitioning and Maintaining Certain System Utilization Level


Affiliations
1 Professor of Data Science, Department of Intelligent Systems, Faculty of Artificial Intelligence Al-Balqa Applied University, Jordan
     

   Subscribe/Renew Journal


Gradual Request-Partitioning-Based (GRPB) processor allocation strategies try to remedy the problem internal fragmentation by having requests get be allocated non-contiguously in the form of gradually produced blocks in case contiguous allocation is not possible. In this article, we experimentally show that GRPB techniques suffer from the problem of over-partitioning, and thus, negatively affects key performance indicators of multi-computer systems. This paper also proposes a framework for using fuzzy logic to control specific key performance levels in two-dimensional mesh-based multi-computer systems. We demonstrated that it is possible to implement a fuzzy-based feedback control system to control a number of performance indicators in the parallel system. The proposed allocation scheme prevents over-splitting of parallel jobs by forcefully limit to the maximum number of blocks that can be assigned to any parallel job. This maximum number is referred to as the partitioning-bound. Preventing parallel processes from getting over-partitioned is vitally important as this (i) reduces the distance of inter-processor source-to-destination communication and (ii) helps in avoiding the “inter-process interference”; the main cause of communication contention. Fuzzy-based allocation provides a mechanism to dynamically control the partitioning-bound. Instead of pre-setting and having a fixed partitioning-bound level, we provide a way to set this value at run time taking into consideration the current status to multi-computer system.

Keywords

Fuzzy-control, Gradual request-partitioning, Internal fragmentation, Multi-computer systems, Non-contiguous processor allocation.
Subscription Login to verify subscription
User
Notifications
Font Size


  • S. Bani-Mohammad, I. Ababneh, and M. Yassen, “A new compacting non-contiguous processor allocation algorithm for 2D mesh multicomputers,” JITR, vol. 8, no. 4, pp. 57-75, 2015.

  • 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, ISSN: 1569-190X, 2018.

  • G. M. Chiu, and S. K. Chen, “An efficient submesh allocation scheme for two-dimensional meshes with little overhead,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 5, pp. 471-486, May 1999.

  • Ababneh, “An efficient free-list submesh allocation scheme for two-dimensional mesh-connected multicomputers,” Journal of Systems and Software, vol. 79, no. 8, pp. 1168-1179, Aug. 2006.

  • Ababneh, and J. Davis, “Program-based static allocation policies for highly parallel computers,” Proc. IPCCC 95, IEEE Computer Society Press, Scottsdale, AZ, USA, 28-31 Mar. 1995, pp. 61-68.

  • S. Bani-Ahmad, “Processor allocation with reduced internal and external fragmentation in 2D mesh-based multi-computers,” Journal of Applied Sciences, vol. 11, no. 6, pp. 943-952, 2011, doi: 10.3923/jas.2011.943.952.

  • S. Bani-Mohammad, M. Ould-Khaoua, I. Ababneh, and L. Machenzie, “A fast and efficient processor allocation strategy which combines a contiguous and noncontiguous processor allocation algorithms,” Technical Report: TR-2007-229, DCS Technical Report Series, Department of Computing Science, University of Glasgow, Jan. 2007.

  • B. S. Yoo, and C. R. Das, “A fast and efficient processor allocation scheme for mesh-connected multi-computers,” IEEE Transactions on Parallel and Distributed Systems, vol. 51, no. 1, pp. 46-60, Jan. 2002.

  • K. Li, and K. H. Cheng, “A two-dimensional buddy system for dynamic resource allocation in a partition ble mesh connected system,” Journal of Parallel and Distributed Computing, vol. 12, no. 1, pp. 79-83, May 1991.

  • P. J. Chuang, and N. F. Tzeng, “Allocating precise submesh in mesh-connected systems,” IEEE Transactions Parallel and Distributed Systems, pp. 211217, Feb. 1994.

  • 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.

  • D. Rupanetti, and H. Salamy, “Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures,” Journal of Systems Architecture, ISSN: 1383-7621, vol. 98, pp. 17-26, 2019.

  • L. E. Rubio-Anguiano, A. C. Trabanco, J. L. B. Velasco, and A. Ramírez-Treviño, “Maximizing utilization and minimizing migration in thermal-aware energyefficient real-time multiprocessor scheduling,” IEEE Access, vol. 9, pp. 83309-83328, 2021, doi: 10.1109/ ACCESS.2021.3086698.

  • C. Y. Chang, and P. Mohapatra, “Performance improvement of allocation schemes for mesh-connected computers,” Journal of Parallel and Distributed Computing, vol. 52, no. 1, pp. 40-68, Jul. 1998.

  • J. Ding, and L. N. Bhuyan, “An adaptive submesh allocation strategy for two-dimensional mesh connected systems,” Proc. Int. Conf. Parallel Process. II, Aug.1993, pp. 193-200.

  • S. Bani-Mohammad, I. M. Ababneh, and M. Yassen,“A new compacting non-contiguous processor allocation algorithm for 2D mesh multi-computers,” Journal of Information Technology Research (JITR), vol. 8, no. 4, 2015.

  • P. Krueger, T. Lai, and V. A. Radiya, “Job scheduling is more important than processor allocation for hypercube computers,” IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, pp. 488-497, May 1994.

  • V. Lo, K. Windisch, W. Liu, and B. Nitzberg, “Noncontiguous processor allocation algorithms for meshconnected multi-computers,” IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 7, pp. 712- 726, Jul. 1997.

  • T. Liu, K. W. Huang, F. Lombardi, and L. N. Bhuyan, “A submesh allocation scheme for mesh-connected multiprocessor systems,” Proc. Int. Conf. Parallel Process. II, Aug. 1995, pp. 159-163.

  • S. Bani-Ahmad, “Submesh allocation in 2D-mesh multicomputers: Partitioning at the longest dimension of requests,” The International Arab Journal of Information Technology (IAJIT), vol. 10, no. 3, May 2013.

  • S. Bani-Mohammad, “An efficient all shapes busy list processor allocation algorithm for 3D mesh multi computers,” IJCAC, vol. 7, no. 2, pp. 10-26, 2017.

  • S. Bani-Ahmad, “Intra-job communication contention and request-partitioning-based allocation strategies in 2D-mesh multi-computers,” Third International Symposium on Parallel Architectures, Algorithms and Programming (PAAP’10), Dalian, LiaoNing, P. R. China, 18-20 Dec. 2010.

  • R. Stobart, “Tutorial on fuzzy control,” IEE Colloquium on Two Decades of Fuzzy Control - Part 1, London, 1993, pp. 1/1-1/6.

  • H. J. Zimmermann, Fuzzy Set Theory and its Applications. Kluwer Academic, Dordrecht, 1991.

  • K. Windisch, J. V. Miller, and V. Lo, “ProcSimity: An experimental tool for processor allocation and scheduling in highly parallel systems,” Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers’95), Washington, USA, 6-9 Feb. 1995, pp. 414-421.

  • ProcSimity V4.3 User’s Manual, University of Oregon, 1997.

  • J. Jantzen, Design of Fuzzy Controllers. Tech. Report No. 98-E 864 (design), Technical University of Denmark, Department of Automation, 30 Sep. 1999.

  • J. Jantzen, Tutorial on Fuzzy Logic. Tech. Report No. 98-E 868, Technical University of Denmark, Department of Automation, 19 Aug. 1998.


Abstract Views: 317

PDF Views: 0




  • Processor Allocation Two-Dimensional MeshBased Multi-Computer Systems: Protecting against Over-Partitioning and Maintaining Certain System Utilization Level

Abstract Views: 317  |  PDF Views: 0

Authors

Sulieman A. Bani-Ahmad
Professor of Data Science, Department of Intelligent Systems, Faculty of Artificial Intelligence Al-Balqa Applied University, Jordan

Abstract


Gradual Request-Partitioning-Based (GRPB) processor allocation strategies try to remedy the problem internal fragmentation by having requests get be allocated non-contiguously in the form of gradually produced blocks in case contiguous allocation is not possible. In this article, we experimentally show that GRPB techniques suffer from the problem of over-partitioning, and thus, negatively affects key performance indicators of multi-computer systems. This paper also proposes a framework for using fuzzy logic to control specific key performance levels in two-dimensional mesh-based multi-computer systems. We demonstrated that it is possible to implement a fuzzy-based feedback control system to control a number of performance indicators in the parallel system. The proposed allocation scheme prevents over-splitting of parallel jobs by forcefully limit to the maximum number of blocks that can be assigned to any parallel job. This maximum number is referred to as the partitioning-bound. Preventing parallel processes from getting over-partitioned is vitally important as this (i) reduces the distance of inter-processor source-to-destination communication and (ii) helps in avoiding the “inter-process interference”; the main cause of communication contention. Fuzzy-based allocation provides a mechanism to dynamically control the partitioning-bound. Instead of pre-setting and having a fixed partitioning-bound level, we provide a way to set this value at run time taking into consideration the current status to multi-computer system.

Keywords


Fuzzy-control, Gradual request-partitioning, Internal fragmentation, Multi-computer systems, Non-contiguous processor allocation.

References