面向异构处理平台的最长路径列表调度算法

Longest Path List Scheduling Algorithm for Heterogeneous Processing Platform

任务调度算法的研究一直是异构计算技术研究中的热点,充分挖掘异构处理平台的并行优势,可最大限度实现平台资源的高效利用。通过分析异构处理平台的执行特点,设计符合异构处理平台的任务调度策略,提出面向异构处理平台的最长路径列表调度算法(Longest path list scheduling algorithm,LPLS)。算法在任务优先级阶段,基于最长路径列表计算优先级,最耗时路径上的任务被优先调度;在处理器选择阶段,遵循任务完成时间最小的原则,所选择的处理器可使下阶段任务的完成时间更短,异构平台整体处理时间更小。仿真实验结果表明,相比于经典的HEFT算法,LPLS算法是一种负载更加均衡的算法,具有调度长度更短、效率更高等优势。

To fully exploit the parallel advantages of heterogeneous processing platforms and maximize the efficient utilization of platform resources,the research of task scheduling algorithm has always been a hotspot in heterogeneous computing technology research.By analyzing the execution characteristics of heterogeneous processing platform,a task scheduling strategy is designed,and the longest path list scheduling algorithm(LPLS)for heterogeneous processing platform is proposed.In the task priority stage,the priority is calculated based on the longest path list,so that the tasks on the most time-consuming path are scheduled first;in the processor selection stage,the selected processor may make the task in the next stage get shorter completion time,thus making the overall processing time of heterogeneous platforms smaller.Simulation results show that LPLS algorithm is a more balanced load algorithm compared with the classical HEFT algorithm,and the algorithm has the advantages of shorter scheduling length and higher efficiency.