A DAG based Task Scheduling Algorithms for Multiprocessor System - A Survey

The multiprocessor computing is composed of more than one central processing units (CPU) that simultaneously execute the task of a parallel application for obtain quick results, to process a massive amount of data, and to solve a problem in expected time. If Scheduling is done properly in task allocation then they are increase the performance of the system. Task scheduling in a parallel environment is one of the NPproblems, which deals with the optimal assignment of a task. In this paper, various algorithms are surveyed that apportion a parallel program impersonate by an edgeweighted Directed Acyclic Graph (DAG). These include Bounded no. of Processors (BNP), Unbounded no. of Clusters (UNC), Task Duplication Based scheduling (TDB) and Arbitrary Processor Network scheduling algorithm (APN). The objective of this paper is to study and explore several DAG based task scheduling algorithm and the performance of all of the algorithms is evaluated and compared against each other on a unified basis by using various scheduling parameters.