Table of Content

Open Access iconOpen Access

ARTICLE

crossmark

A Load Balanced Task Scheduling Heuristic for Large-Scale Computing Systems

Sardar Khaliq uz Zaman1, Tahir Maqsood1, Mazhar Ali1, Kashif Bilal1, Sajjad A. Madani1, Atta ur Rehman Khan2,*

1 Department of Computer Science, COMSATS University, Pakistan
2 Faculty of Computing and Information Technology, Sohar University, Oman

* Corresponding Author: email

Computer Systems Science and Engineering 2019, 34(2), 79-90. https://doi.org/10.32604/csse.2019.34.079

Abstract

Optimal task allocation in Large-Scale Computing Systems (LSCSs) that endeavors to balance the load across limited computing resources is considered an NP-hard problem. MinMin algorithm is one of the most widely used heuristic for scheduling tasks on limited computing resources. The MinMin minimizes makespan compared to other algorithms, such as Heterogeneous Earliest Finish Time (HEFT), duplication based algorithms, and clustering algorithms. However, MinMin results in unbalanced utilization of resources especially when majority of tasks have lower computational requirements. In this work we consider a computational model where each machine has certain bounded capacity to execute a predefined number of tasks simultaneously. Based on aforementioned model, a task scheduling heuristic Extended High to Low Load (ExH2LL) is proposed that attempts to balance the workload across the available computing resources while improving the resource utilization and reducing the makespan. ExH2LL dynamically identifies task-to-machine assignment considering the existing load on all machines. We compare ExH2LL with MinMin, H2LL, Improved MinMin Task Scheduling (IMMTS), Load Balanced MaxMin (LBM), and M-Level Suffrage-Based Scheduling Algorithm (MSSA). Simulation results show that ExH2LL outperforms the compared heuristics with respect to makespan and resource utilization. Moreover, we formally model and verify the working of ExH2LL using High Level Petri Nets, Satisfiability Modulo Theories Library, and Z3 Solver.

Keywords


Cite This Article

S. Khaliq uz Zaman, T. Maqsood, M. Ali, K. Bilal, S. A. Madani et al., "A load balanced task scheduling heuristic for large-scale computing systems," Computer Systems Science and Engineering, vol. 34, no.2, pp. 79–90, 2019.

Citations




cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1841

    View

  • 1304

    Download

  • 1

    Like

Share Link