PERFORMANCE EVALUATION" DF SCHEDULINNG PRECEDENCE-GRAPHS ON HYPERCUBE

Abstract

The classical multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence-constrained task graph (representing a parallel program ) onto the processors of a multiprocessor in a way that minimizes the completion time. This problem is an NP hard problem and has proven difficult both in theory and practice. Because of the intractability of this problem, research effort has focused on finding polynomial time algorithm that produce suboptimal schedules for some restricted cases of the general scheduling problem. In this thesis a heuristic algorithm for the multiprocessor scheduling problem has been implemented and tested where the effects of considering non-negligible inter-task and inter-processor communications are analyzed. The algorithm incorporates a better 'tie-resolution'. We show that the Inter-Task-Communication considerations are very important for optimal scheduling of tasks on multiprocessor.