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.
Index Terms:
Fast, Preemptive, Task, Scheduling, Homogeneous, Heterogeneous, Distributed, Memory, Systems
Citation:
Maruf Ahmed, Sharif M.H. Chowdhury, Masud Hasan, "Fast Preemptive Task Scheduling Algorithm for Homogeneous and Heterogeneous Distributed Memory Systems," snpd, pp.720-725, 2008 Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2008