Makespan Minimization for Efficient Placement of Distributed Computations on Virtual Dynamic Environment

Authors

  • Albert Djakene Wandala University of Ngaoundere, , Cameroon
  • Omer Yenke Blaise University of Ngaoundere, , Cameroon

Keywords:

Placement, Makespan, Distributed System, Distributed computations, Virtualization

Abstract

Nowadays, virtualization, containerization technology and computer development make it possible to build distributed systems with virtual nodes, offering considerable performance for the execution of distributed computations. However, building such infrastructure faces various challenges of distributed systems, including load balancing, fault tolerance and wise placement of distributed computations on compute nodes. In this paper, we focus on the efficient placement of distributed computations in a virtual distributed system with the aim of minimizing the makespan. Several approaches have been proposed to reduce the placement makespan , but the need of improvement  still remains. Consequently, in this work, we propose a new approach that minimizes the makespan of distributed computations on compute nodes by performing fine-grained intelligent placement. The results obtained during tests have shown a better placement of distributed computations on core nodes than existing approaches, regardless of the characteristics of the processes, cores, distributed computations and compute nodes.

References

[ 1 ] Nadiminti, K.; De, A.M.D.; Buyya, R. Distributed systems and recent innovations: Challenges and benefits. InfoNet Magazine 2006, 16, 1–5.

[ 2 ] Yenke, B.O.; Abba Ari, A.A.; Dibamou Mbeuyo, C.; Voundi, D.A. “Virtual Machine Performance upon Intensive Computations”. GSTF Journal on Computing (JoC) 2015, 4. https://doi.org/10.5176/2251-3043_4.3.336.

[ 3 ] Stuart, T.A. Introduction to Distributed Systems, 1st ed.; Prentice Hall, 1994.

[ 4 ] Chanaka, F. “ The Evolution of Distributed Systems”. https://dzone.com/articles/the-evolution-of-distributed-systems, 2018, [Accessed 12 October 2019].

[ 5 ] Binason, A. “ IDJ : Une Breve Histoire de l’Ordinateur”. https://babilown.com/2010/02/01/idj-une-brve-histoire-de-lordinateur/, February 2010, [Accessed 15 November 2019].

[ 6 ] Rodrigue, C.N. “Environnement d’exécution pour des services de calcul à la demande sur des grappes mutualisées”. Theses, Université de Grenoble, June 2012.

[ 7 ] Hyungro, L. “Virtualization basics: Understanding techniques and fundamentals”. School of Informatics and Computing Indiana University 2014, 815.

[ 8 ] Phelep, J. “La Conteneurisation”. https://phelepjeremy.wordpress.com/2017/06/21/la-conteneurisation/ , June 2017,[Accessed 10 January 2021].

[ 9 ] Meriem, M. “ Placement Dynamique de Tâches dans une Grille de Calcul”. Theses, Université d’Oran, June 2012.

[ 10 ] Braun, T.D.; Siegel, H.J.; Beck, N.; Bölöni, L.L.; Maheswaran, M.; Reuther, A.I.; Robertson, J.P.; Theys, M.D.; Yao, B.; Hensgen, D.; et al. “ A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems”. Journal of Parallel and Distributed Computing 2001, 61, 810–837. https://doi.org/https://doi.org/10.1006/jpdc.2000.

[ 11 ] Boyer, W.F.; Hura, G.S. “Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments”. Journal of Parallel and Distributed Computing 2005, 65, 1035–1046. https://doi.org/https://doi.org/10.1016/j.jpdc.2005.04.017

[ 12 ] Sinnen, O. Task scheduling for parallel system; Wiley Series on Parallel and Distributed Computing, Wiley-Interscience, 2007.

[ 13 ] Gamboa dos Santos, C. “Problématique du placement de tâches dans MeDLey”. Research Report RR-3256, INRIA, 1997

[ 14 ] Ali, S.; Siegel, H.; Maheswaran, M.; Hensgen, D.; Ali, S. “Modeling task execution time behavior in heterogeneous computing systems”, Tamkang J. Science and Engineering 2000, 3, 195–207.

[ 15 ] Singh, L.; Agarwal, N.” An Improved Min-Min Task Scheduling Algorithm with Grid Utilization and Minimized Makespan”. International journal of computers amp;amp; Technology 2015,14, 5960–5966. https://doi.org/10.24297/ijct.v14i8.1860

[ 16 ] Maheswaran, M.; Ali, S.; Siegel, H.J.; Hensgen, D.; Freund, R.F. “Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems”. Journal of Parallel and Distributed Computing 1999, 59, 107–131. https://doi.org/https://doi.org/10.1006/jpdc.1999.1581.

[ 17 ] Konjaang, J.; Fahrul, H.; Muhammed, A. “An optimized max-min scheduling algorithm in cloud computing”. Journal of Theoretical and Applied Information Technology 2017, 95, 1916–1926.

[ 18 ] Sallar, Salam, M.; Badel, R.; Nashat, Salih abdulkarim, A.; Rafi Faraj, A.; Reham, A.A.; Abdullah, M.; Mohd, D. “optimized MIN-MIN Task scheduling algorithm for scientific workflows in a cloud environment”. Journal of Theoretical and Applied Information Technology 2023, 100, 480–506.

Downloads

Published

2025-01-26

How to Cite

Albert Djakene Wandala, & Omer Yenke Blaise. (2025). Makespan Minimization for Efficient Placement of Distributed Computations on Virtual Dynamic Environment. International Journal of Computer (IJC), 53(1), 80–96. Retrieved from https://ijcjournal.org/index.php/InternationalJournalOfComputer/article/view/2333

Issue

Section

Articles