A Recursive Adaptive Scheduling Scheme for Large-Scale Workflows

Masaki Matsumoto, Kazuhiko Ohno, Takahiro Sasaki, and Toshio Kondo


Task Scheduling, Workflow, Parallel Computing, Grid Computing


Task scheduling is very important for efficient execution of large-scale workflows. However, scheduling large-scale workflows using most existing scheduling schemes is not practical because of the huge computational costs. To solve this problem, we have proposed an adaptive scheduling scheme (AS) with low computational cost. However, many practical workflows are collections of sub-workflows and AS may not schedule them efficiently. Therefore, we propose a recursive adaptive scheduling scheme (RAS) that improves AS to achieve high performance for such workflows. In RAS, sub-workflows are replaced to pseudo tasks. Then RAS makes stepwise scheduling; it recursively applies AS to each sub-workflow when the corresponding pseudo task is scheduled. The evaluation using an abstract simulation shows the scheduling time of RAS is approximately 1/100 compared to AS for workflows consisting of 10,000 tasks.

Important Links:

Go Back