Main Article Content
Abstract
Scheduling and Execution of parallel tasks of a single job on different processors at the same time in parallel computing environment is very challenging. Various scheduling algorithms have been developed in this field. Generally scheduling algorithms are of two types: Scheduling with task duplication and Scheduling without task duplication. As the time grows, new algorithms have been developed so as to reduce the total time of execution of tasks known as schedule length. We propose Breadth first search based task duplication algorithm for compile-time scheduling of parallel programs on parallel processing systems.Proposed algorithm traverses the Directed Acyclic Graph (DAG) of tasks known as task graph, using breadth first search mechanism, taking advantage of task duplication and task insertion on different processors. The main objective of this scheduling algorithm is to minimize schedule length and time complexity of algorithm with the realistic assumptions. Proposed algorithm has been tried on various task graphs and it provides good results in terms of schedule length and time complexity.