Masaki Matsumoto, Kazuhiko Ohno, Kohei Suzuki, Takahiro Sasaki, and Toshio Kondo
Task Scheduling, Workflow, Parallel Computing, Grid Computing
Task scheduling is very important for efficient execution of large-scale workflows. Static scheduling schemes achieve high performance when executing workflows in stable environments. However, the scheduling costs are very high for large-scale workflows and they may perform poorly if the system performance is changed dynamically. Dynamic rescheduling schemes support the dynamic performance changes because tasks are rescheduled using algorithms from static scheduling schemes when the performance is changed. Thus, better performance can be achieved in workflow applications, although the scheduling costs will increase if the system performance is frequently changed. Therefore, we propose a dynamic recursive adaptive scheduling scheme (DRAS) which can reduces the computational cost. DRAS uses RAS, which is a static scheme with low cost, as rescheduling algorithm. However, if DRAS uses RAS algorithm with no change, the cost increases since RAS is called many times. Thus, we improved the RAS to eliminate the redundant computation. Furthermore, we modified RAS to improve the makespan when used for the rescheduling since DRAS may perform poorly in that case. The evaluation using an abstract simulation shows the makespan of DRAS decreases by 30% compared with a dynamic rescheduling scheme which uses the conventional RAS algorithm. Moreover, DRAS considerably reduces the scheduling time, achieving approximately 6 times speedup for workflows consisting of 1,000 tasks when the dynamic performance is frequently changed.
Important Links:
Go Back
