Analysis Comparison and Performance Evaluation of BNP Scheduling Algorithm

This paper surveys algorithms that allocate a parallel program represented by an edge-directed acyclic graph (DAG) based on homogenous processors. The objective is to minimize the execution time, evaluate and compare the performance of the indivuial algorithms and select the best algorithm. Different algorithms are analyzed and classified into four groups. The algorithm in first group schedule the DAG to bounded number of processor (BNP). The algorithm in second group schedule the DAG to unbounded number of processor (UNP).). The algorithm in third group schedule the DAG to task duplication based (TDB). The algorithm in the fourth group perform allocation and mapping on arbitrary processor network topologies (APN). BNP algorithm based upon homogenous environment and it classifies them into four parts (HLFET HIGHEST LEVEL First ESTIMATED time, DLS Dynamic level Scheduling, MCP Modified Critical Path, and EFT Estimated Task First).BNP algorithm is study and discussed, and to measure the performance of BNP algorithm and evaluate the best algorithm