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

In this paper we have introduced the K1 heuristic algorithm for dynamic tas k scheduling with precedence constraints and communication delays. The exec ution of a task set repeats in cycles, while the execution and communicatio n 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 d istributed - performed on the processors of a highly parallel computer arch itecture. Only the tasks that can have an influence on dominant sequence re duction are considered for reordering/migration. The applied techniques are load balancing, task reordering, and data-wait reduction. We have analyzed the impact of the K1 scheduling cost on response time. The simulation resu lts show that the periodic activation of the K1 scheduler significantly dec reases the scheduling overhead and still generates much better response tim e than that of a fixed schedule. (C) 2001 Elsevier Science B.V. All rights reserved.