Load Balancing Factor of DAG Based BNP Scheduling Algorithms

Abstract

Effective scheduling of applications is crucial for achieving optimal performance in uniform computing environments. The scheduling problem is known to be NP-complete in both general and specific cases. Given its paramount importance, various BNP algorithms, including HLFET, MCP, ETF, and DLS, have been extensively explored, primarily designed for parallel processing systems. This study evaluates the performance of these four algorithms utilizing a Direct/Arbitrary Task Graph (DAG) comprising 11 tasks, focusing on key performance parameters such as efficiency and load balancing. The MCP algorithm demonstrates superior efficiency, while HLFET excels in terms of load balancing.