A Hybrid Scheduling Scheme for Large-Scale Heterogeneous Environments

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


Parallel Computing, Grid Computing, Scheduling


We are developing a task parallel script language MegaScript for parallel processing on large-scale widely distributed environments. To achieve high performance, MegaScript requires a scheme that efficiently schedules de pendent tasks to be executed on a heterogeneous environ ment. However, the scheduling overhead of existing static schemes are too large while dependency among tasks re duces efficiency of simple dynamic scheduling schemes. Therefore, we propose a combination of multiple schemes to have an efficient hybrid scheduling scheme. To reduce the overhead of static scheduling, we use multi-layered schedulers: the upper layer makes rough global schedul ing, and the lower layer makes precise local scheduling. We also incorporate a dynamic scheduler into our scheduler to cope with dynamic change of the system performance. The evaluation using abstract simulation exhibited 6.9–9.8 times speed-up and good scalability, compared to a single level static scheduler.

Important Links:

Go Back