Dynamic Rescheduling Scheme for Large-Scale Workflows

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


Parallel Computing, Task Scheduling, Grid Computing


Task scheduling is very important for efficient execution of large-scale workflows in distributed computing envi ronments. Static scheduling schemes achieve high perfor mance when executing workflows in stable environments. However, the scheduling costs are very high for large scale workflows and they may perform poorly if the sys tem performance is changed dynamically. Demand-driven scheduling schemes achieve high performance for indepen dent tasks, but they may perform poorly for workflows. Dy namic rescheduling schemes have the advantages of these two types of schemes, because tasks are rescheduled us ing algorithms from static scheduling schemes when the performance is changed. Thus, better performance can be achieved in workflow applications, although the scheduling costs are increased if the system performance is frequently changed. Therefore, a new dynamic scheduling scheme is pro posed to reduce the number of rescheduling tasks. The rescheduling trigger of this scheme is based on task ter minations. Moreover, the scheme reduces the number of rescheduling tasks compared to a scheme using a simple task termination trigger by checking dependencies between tasks. Evaluation using an abstract simulation demon strated that the number of rescheduling tasks was reduced to approximately 1/4 to 1/100 of that without, and with a 5% increase of the execution time.

Important Links:

Go Back