Development of DAG Based Scheduling Algorithm for Bounded Number of Processor

Abstract

Parallel computing is a promising approach to meet the computational requirement of large number of current and emerging applications. It is a technique of executing multiple tasks simultaneously on multiple processors. The main goal of parallel computing is to increase the computation speed. Efficient task scheduling and mapping are the big issues in parallel computing environment. Scheduling in parallel and distributed system is considered as NP-complete problem, and heuristic is one of the best ways to solve NP complete problem in polynomial time under some assumption. This research work is focused on one of the classes of heuristic scheduling known as BNP (Bounded Number Processor). BNP scheduling algorithm, often deal with DAG based task set where priority is set by b-level, t-level, SL etc. BNP scheduling algorithm is useful in the allocation of tasks to the distributed database. Subsequentto the review of various research works related to the BNP scheduling algorithm, it is observed that most of the research work focused on homogeneous systems and independent task model, and according to this review approximately 47% of the total reviewed articles cover the homogeneous system model in their study and 39% of research work related to the heterogeneous system model, while only 19% of work based on distributed system. Various BNP scheduling algorithms are available for different environment in which HLFET, DLS, MCP, ETF and HFET are some widely used. newlineIn this study, several algorithms are examined and then compare the performance of some well-known Bounded Number of Processors (BNP) scheduling algorithms namely, HLFET, MCP, ETF and DLS. Evaluation is based on various performanceparameters such as makespan, speedup etc. The focus of algorithms is to minimizing the total schedule length and increasing the efficiency of the system to improve the performance of system. This research work is concerned with the static task scheduling problem, and a dependent task set, which is represented by DAG. In this case, the