An Adaptive Scheduling Scheme for Large-Scale Workflows on Heterogeneous Environments

K. Ohno, M. Matsumoto, T. Sasaki, T. Kondo, and H. Nakashima (Japan)


Parallel Computing, Task Scheduling, Grid Computing


We are developing a task parallel script language MegaScript for executing large-scale workflows on widely distributed heterogeneous environments. For efficient execution of this language, we have proposed a multi-layered task scheduling scheme: the upper layer making rough global scheduling, and the lower layer making precise local scheduling. However, the cost for local scheduling is still a serious issue. Therefore, we propose an adaptive scheduling scheme appropriate to this kind of workflow. The scheme adaptively switches DAG scheduling and independent task scheduling, reducing the scheduling cost for independent task sets in the workflow. The results of our evaluation show our scheme achieved a 540 times speedup of total scheduling time when each host executes 100 tasks on average without serious extension of the makespan less than 7%.

Important Links:

Go Back