Low complexity task scheduling for large scale homogeneous and heterogeneous parallel processors

Abstract

A distributed memory system can take advantage of fast communication networks to achieve phenomenal computing power. One of the important problems of distributed memory systems is the task scheduling problem, which has been proven to be NP-Hard in general. This thesis presents two list heuristic scheduling algorithms, one is non-preemptive and other one is preemptive. The first algorithm presented is a compiletime non-preemptive list heuristic scheduling algorithm, called the low cost critical path algorithm (LCCP) for distributed memory system. The LCCP has low scheduling cost for both homogeneous and heterogeneous systems. Its time complexity is O(IVI * log IFI + lEI), where V is the set of tasks, E is the set of edges and P is the set of processors. In some recent papers, list heuristic scheduling algorithms keep their scheduling cost low by using a heap and a queue, where the heap always keeps a fixed number of tasks and the excess tasks are inserted in the queue. When heap haS less than fixed number of tasks, some tasks of queue are extracted and inserted in the heap. The best known list scheduling algorithm based on this strategy requires two heap restoration operations per task, one for extraction and another for insertion. Our LCCP algorithm improves on this by using only one such operation for both the extraction and insertion, which reduces scheduling cost without compromising the scheduling performance, and we show this both in theory and practice. The second algorithm presented in this thesis is a fast compile time preemptive list heuristic scheduling algorithm, called the fast preemptive task scheduling algorithm (FPS). Time complexity of FPS is O(IVI * (log IVI + log IPI) + lEI). Such an algorithm is useful during compilation of parallel applications. A preemptive schedule can better utilize resources and offersa lot of flexibility. In order to schedule tasks the FPS simulates preemptive task execution at a very low overhead and requires very little runtime support. The experimental results show that the scheduling cost and performance of FPS is better than that of other well known non-preemptive and preemptive list heuristic scheduling algorithms for both homogeneous and heterogeneous systems.