Fast Preemptive Task Scheduling Algorithm for Homogeneous and Heterogeneous Distributed Memory Systems

This paper presents a fast preemptive list heuristic scheduling algorithm, called the Fast Preemptive Scheduling Algorithm (FPS), for both homogeneous and heterogeneous distributed memory systems. Time complexity of FPS is just O(|V|*(log|V|+log|P|)+|E|). Such an algorithm is useful during the compilation of the parallel applications. A preemptive schedule can better utilize the resources and offers a lot of flexibility. In order to schedule tasks, FPS simulates preemptive task execution at a very low overhead and requires very little runtime support. The experimental results show that, the scheduling cost of FPS is lower than that of other well known non-preemptive and preemptive list heuristic scheduling algorithms for both homogeneous and heterogeneous systems. Also the scheduling performance of FPS is same or better than that of those algorithms.