基于改进蚁群的异构平台负载均衡调度算法  

Load Balancing Scheduling Algorithm for Heterogeneous Platform Based on Improved Ant Colony Optimization

作　　者：李宇东 马金全[1] 胡泽明[1] 岳春生[1] 谢宗甫 LI Yudong;MA Jinquan;HU Zeming;YUE Chunsheng;XIE Zongfu(Information Engineering University,Zhengzhou 450001,China;Unit 65022,Shenyang 110000,China)

机构地区：[1]信息工程大学,河南郑州450001 [2]65022部队,辽宁沈阳110000

出　　处：《信息工程大学学报》2024年第1期30-38,共9页Journal of Information Engineering University

摘　　要：针对目前异构平台中信号处理任务的调度算法单一、处理器资源浪费等问题,提出了一种面向异构系统的Q学习改进蚁群算法的负载均衡调度算法。算法针对计算密集型和通信密集型任务的不同需求,设计了分流排序法进行任务优先级排序;通过场景适配将Q学习和蚁群算法,与异构平台中的任务调度进行映射。通过奖励函数计算Q-Table,作为蚁群算法的初始信息素,加快了蚁群的收敛速度;根据处理器的实时负载,设计负载矩阵,实现了动态调整系统负载均衡;利用伪随机比例规则选择处理器,通过任务之间的约束关系形成调度列表来完成任务的分配。最后,通过随机生成的有向无环图进行仿真实验,结果表明算法在减小最大完工时间(调度长度)和提高处理器利用率方面均有明显的改进。To address the problems of single scheduling algorithms and wasted processor resources for signal processing tasks in current heterogeneous platforms,a load balancing scheduling algorithm with Q-learning enhanced ant colony algorithm for heterogeneous systems is proposed.The algorithm is designed to prioritize tasks by a triage sorting method for the different needs of computation-intensive and communication-intensive tasks.Q-learning and ant colony algorithms are mapped to task scheduling in heterogeneous signal processing platforms through scenario adaptation.The Q-table is dynamically computed using the reward function and is used as the initial pheromone of the ant colony algorithm,which speeds up the convergence of the ant colony.The load matrix is designed to dynamically adjust system load balancing according to the real-time load on the processor.Pseudo-random scaling rules are used to make processor selections.Tasks are assigned by creating a schedule list with constraint relationships between tasks.Finally,simulation experiments are performed with randomly generated directed acyclic graphs.The results show significant improvements in both the reduction of the maximum completion time(scheduling length)and the increase in processor utilization.

关 键 词：任务调度 异构信号处理平台 Q学习 蚁群算法 

分 类 号：TN911.7[电子电信—通信与信息系统]