Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters |
| |
Authors: | Jorge G Barbosa Belmiro Moreira |
| |
Affiliation: | a Universidade do Porto, Faculdade de Engenharia, Departamento de Engenharia Informática, Lab. de Int. Artificial e Ciência dos Computadores, Rua Dr. Roberto Frias, 4200-465 Porto, Portugal b Universidade do Porto, Faculdade de Engenharia, Rua Dr. Roberto Frias, 4200-465 Porto, Portugal |
| |
Abstract: | This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach. |
| |
Keywords: | Parallel task scheduling List scheduling Image data Multiple DAG Non-deterministic job arrival |
本文献已被 ScienceDirect 等数据库收录! |
|