Analysis, Comparison and Performance Evaluation of BNP Scheduling Algorithms in Parallel Processing
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 individual 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 performs allocation and mapping on Arbitrary Processor Network topologies (APN).