基于通信开销的多类型DAG任务调度方法  

The multi-type DAG task scheduling method based on communication overhead

作　　者：郝鹏涛 肖锋[1] 黄姝娟[1] 张文娟 陈雯琦 左俊杰 HAO Pengtao;XIAO Feng;HUANG Shujuan;ZHANG Wenjuan;CHEN Wenqi;ZUO Junjie(School of Computer Science and Engineering,Xi'an Technological University,Xi'an 710021,China;School of Science,Xi'an Technological University,Xian 710021,China)

机构地区：[1]西安工业大学计算机科学与工程学院,陕西西安710021 [2]西安工业大学基础学院,陕西西安710021

出　　处：《微电子学与计算机》2024年第5期67-75,共9页Microelectronics & Computer

基　　金：国家自然科学基金面上项目(62171361);陕西省重点研发计划一般项目(2022GY-119);陕西省科技厅自然科学基础研究计划(2021JM-440)。

摘　　要：随着异构多核处理器的性能不断增强,具有关联关系任务的调度问题和调度算法成为研究者们关注的焦点。针对异构多核平台上的有向无环图(Directed Acyclic Graph,DAG)任务模型进行了调度分析。由于异构环境中计算资源类型丰富数量多,实际调度过程中处在不同核上的任务之间的通信开销是存在的。而当前大多数调度算法要么忽略不同核上的任务之间的通信开销,要么优先级判定和选择处理器核执行时不能全面考虑核间任务的通信开销,造成资源浪费,增加了系统调度任务的整体长度。因此,针对具有通信开销的DAG任务模型,讨论了任务间的通信开销对任务调度算法的影响,提出了复合节点生成算法(Composite Node Generation Algorithm,CNGA)任务调度算法。该算法根据任务间通信开销大小进行预处理分配生成复合节点,重构DAG图将任务节点的上行秩和通信占比作为参数决定任务节点的优先级。实验结果与HEFT和CPOP算法比较,在任务通信开销和任务执行开销之比(Communication to Computation Ratio,CCR)一定的情况下响应时间比原有的HEFT和CPOP提升10.19%,稳定性以松弛度和接受率为参数平均提升3.96%。With the increasing performance of heterogeneous multi-core processors,the scheduling problem and scheduling algorithm with relational tasks become the focus of researchers.In this paper,the Directed Acyclic Graph(DAG)task model on heterogeneous multi-core platform is analyzed.Because there are many types of computing resources in heterogeneous environment and they are widely distributed,the communication overhead between tasks on different cores exists in the actual scheduling process.However,most of the current scheduling algorithms either ignore the communication overhead between tasks on different cores,or fail to consider the communication overhead of tasks between cores when deciding and selecting processor cores,resulting in waste of resources and increasing the overall length of the system scheduling tasks.Therefore,for the DAG task model with communication overhead,this paper discusses the influence of the communication overhead between tasks on the task scheduling algorithm,and proposes a Composite Node Generation Algorithm(CNGA)task scheduling algorithm.According to the amount of communication overhead between tasks,the algorithm is preprocessed and allocated to generate composite nodes,and the upstream rank and communication ratio of task nodes are used as parameters to determine the priority of task nodes.Compared with HEFT and CPOP algorithms,the experimental results show that the ratio of task communication overhead to task execution overhead Communication to Computation Ratio(CCR)under certain conditions,the response time is improved by 10.19%compared with the original HEFT and CCOP,and the stability is increased by 3.96%.

关 键 词：DAG 任务调度 通信开销 复合节点 CNGA算法 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]