Hybrid List-Scheduling Algorithm Based on Task Duplication and Pre-Scheduling
In heterogeneous computing systems,efficient task-scheduling algorithms are crucial for achieving high performance.The list scheduling algorithm is a classical static heuristic algorithm employed to address task-scheduling issues.However,because of differences in the computational and communication costs for tasks in heterogeneous systems,the task scheduling problem is inherently more complex than in homogeneous systems.Current research primarily focuses on developing lower-time complexity algorithms that minimize the scheduling length.To address these challenges,a hybrid list-scheduling algorithm,referred to as Direct Partial Least Squares(DPLS),is proposed that incorporates task replication and pre-scheduling.This algorithm adopts a task duplication strategy to selectively duplicate and schedule key predecessor tasks on the same processor as the current task,thereby reducing the waiting time of the data-dependent communication on the key predecessor task and advancing the completion time of the current task.The DPLS algorithm consists of two stages:pre-and secondary scheduling.The pre-scheduling phase generates the basic scheduling scheme,and the secondary scheduling phase refines it.This improves the calculation method for task priority by considering the impact of task execution cost in the priority calculation process,leading to a more rational task prioritization.The experimental results indicate that DPLS has the same time complexity as classical algorithms.For a time complexity of O(n2·p)for n tasks and p processors,DPLS can generate scheduling schemes with shorter lengths and outperform other list scheduling algorithms,achieving performance improvements of 12.563％and 7.786％compared to HEFT and PEFT,respectively.
万方数据
维普
