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.
