SCALABLE LOW COMPLEXITY TASK SCHEDULING ALGORITHM FOR CLUSTER OF WORKSTATIONS

Abstract

Static scheduling is the temporal and spatial mapping of a program to the resources of parallel system. Scheduling algorithms use the Directed Cyclic Graph (DAG) to represent sub-tasks and the precedence constraints of the program to be parallelized. It has been shown to be NP-Complete in general as well as in several restricted cases. This paper proposes a scalable, low complexity performance effective task scheduling algorithm whose time complexity is Ο((e) (p + log v)). It provides effective result for applications represented by DAGs. Experiments have been conducted based on randomly generated graphs which show that the proposed algorithm outperforms the existing algorithms.

Keywords

• DAG
• Task graph
• Cluster computing system
• Scheduling scalability
• Speedup
• Efficiency