A heuristic algorithm for dynamic task scheduling in highly parallel computing systems

摘要

In this paper we have introduced the K1 heuristic algorithm for dynamic task scheduling with precedence constraints and communication delays. The execution of a task set repeats in cycles, while the execution and communication profile of a task set changes in time. During a task set execution, a new schedule is generated by tuning the previous schedule. The scheduling is distributed -- performed on the processors of a highly parallel computer architecture. Only the tasks that can have an influence on dominant sequence reduction are considered for reordering/migration. The applied techniques are load balancing, task reordering, and data-wait reduction. We have analyzed the impact of the K l scheduling cost on response time. The simulation results show that the periodic activation of the K1 scheduler significantly decreases the scheduling overhead and still generates much better response time than that of a fixed schedule.