Hybrid task scheduling: integrating static and dynamic heuristics

• C. Boeres UFF
• A. Lima UFF
• V. E. F. Rebello UFF

Resumo

Researchers are constantly looking for ways to improve the execution time of parallel applications on distributed systems. Although compile-time static scheduling heuristics employ complex mechanisms, the quality of their schedules are handicapped by estimated run-time costs. On the other hand, while dynamic schedulers use actual run-time costs, they have to be of low complexity in order to reduce the scheduling overhead. We investigate the viability of integrating these two approaches into a hybrid scheduling framework. The relationship between static schedulers, dynamic heuristics and scheduling events are examined. The results show that a hybrid scheduler can indeed improve the schedules produced by good traditional static list scheduling algorithms.

Palavras-chave: Dynamic scheduling, Processor scheduling, Runtime, Scheduling algorithm, Costs, Distributed computing, Computer architecture, Computational efficiency, Grid computing, Clustering algorithms