面向异构处理平台任务调度的麻雀优化算法

doi:10.16180/j.cnki.issn1007-7820.2024.01.005

摘要/Abstract

摘要：

针对当前异构信号处理平台中各处理器任务数量分配不均衡、处理器性能发挥不完全以及系统运行效率低的问题,文中提出一种面向异构处理平台的麻雀优化算法。该算法利用了麻雀算法较强的全局寻优能力和麻雀种群内部的高效工作机制。在经典麻雀算法基础上,文中提出了符合任务调度的二进制异或编解码规则,将离散的任务分配方案映射为连续的麻雀位置信息。将处理器负载均衡指数作为适应度函数,选取每次迭代中的最优解;在麻雀遍历任务时,采用任务优先级分流排序策略。对通信密集型任务和计算密集型任务采取不同的计算式得到更符合任务特点的遍历顺序,生成随机任务图,并将所提算法同ICPA(Improved Critical Path Algortthm)算法进行对比。仿真结果表明,相比于ICPA算法,所提算法的负载均衡指数平均优化率为60%,各处理器负载情况更加均衡,能更好地发挥异构处理平台的整体效能。

关键词: 异构处理平台, 任务调度, 麻雀算法, 负载均衡, DAG, 编码规则, 适应度函数, 信号处理

Abstract:

In view of the problems of unbalanced distribution task quantity of the each precessor,incomplete performance of the each processor and inefficient system operation in heterogeneous signal processing platform,a sparrow optimization algorithm for heterogeneous processing platform is proposed in this study, which takes advantage of the strong global optimization ability of sparrow algorithm and efficient working mechanism within sparrow population.Based on the classical sparrow algorithm, this study proposes a binary or codec rule that meets the task scheduling, and maps discrete task assignment scheme to continuous sparrow position information.The processor load balance index is taken as the fitness function and the optimal solution is selected in each iteration. When the sparrow traverses the task, the task priority shunt sorting strategy is adopted to adopt different computing formulas for communication-intensive tasks and computing dense tasks to obtain the order of traversing more in accordance with the characteristics of the task, and generates random tasks.Finally, the proposed algorithm is compared with the ICPA(Improved Critical Path Agorithm). The simulation results show that when compared with the ICPA, the an average optimization rate of load balance index of the proposed algorithm is 60%, and the load of each processor is more balanced, and the overall performance of the heterogeneous processing platform can be better utilized.

Key words: heterogeneous processing platform, task scheduling, sparrow algorithm, load balancing, DAG, coding rules, adaptation function, signal processing

中图分类号:

TN911

沈小龙,马金全,冀亚玮,谢宗甫,李宜亭,李宇东. 面向异构处理平台任务调度的麻雀优化算法[J]. 电子科技, 2024, 37(1): 33-40.

SHEN Xiaolong,MA Jinquan,JI Yawei,XIE Zongfu,LI Yiting,LI Yudong. Sparrow Optimization Algorithm for Task Scheduling of Heterogeneous Processing Platform[J]. Electronic Science and Technology, 2024, 37(1): 33-40.

图/表 19

图1

图2

表1

图3

图4

表2

表3

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

参考文献 15

[1]	李娜, 高博, 谢宗甫. 分层异构信号处理平台调度方法研究[J]. 电子科技, 2022, 35(2):7-13.
	Li Na, Gao Bo, Xie Zongfu. Research on scheduling method of layered heterogeneous signal processing platform[J]. Electronic Science and Technology, 2022, 35(2):7-13.
[2]	赵传奇, 岳春生. 分布式异构信号处理平台虚拟监管系统设计与实现[J]. 信息工程大学学报, 2019, 20(2):180-183,191.
	Zhao Chuanqi, Yue Chunsheng. Design and implementation of virtual monitoring system for distributed heterogeneous signal processing platform[J]. Journal of Information Engineering University, 2019, 20(2):180-183,191.
[3]	江超. 异构计算平台静态任务调度算法综述[J]. 网络新媒体技术, 2021, 10(4):1-10.
	Jiang Chao. A survey on static task scheduling algorithms in heterogeneous computing platforms[J]. Network New Media Technology, 2021, 10(4):1-10.
[4]	沈小龙, 马金全, 岳春生, 等. 面向异构处理平台的任务调度算法[J]. 信息工程大学学报, 2022, 23(4):415-420.
	Shen Xiaolong, Ma Jinquan, Yue Chunsheng, et al. Task scheduling algorithm for heterogeneous processing platform[J]. Journal of Information Engineering University, 2022, 23(4):415-420.
[5]	刘林东, 邬依林. 基于HEFT和CPOP的相关任务表调度算法[J]. 计算机系统应用, 2019, 28(3):118-125.
	Liu Lindong, Wu Yilin. List scheduling algorithm of dependent tasks based on HEFT and CPOP[J]. Computer Systems & Applications, 2019, 28(3):118-125.
[6]	Wang G, Guo H, Wang Y. A novel heterogeneous scheduling algorithm with improved task priority[C]. New York: IEEE the Seventeenth International Conference on High Performance Computing and Communications, 2015:598-607.
[7]	马金全, 王学成, 李建军. 分层排序的列表任务调度技术的研究[J]. 通信学报, 2018, 39(S2):106-111.
	Ma Jinquan, Wang Xuecheng, Li Jianjun. Research on list task scheduling technology by hierarchical sort[J]. Journal on Communications, 2018, 39(S2):106-111.
[8]	Xue J, Shen B. A novel swarm intelligence optimization approach:Sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1):22-34.
[9]	郭松林, 巴艳坤, 李春. 改进SSA算法优化BP神经网络的电力负荷预测模型[J]. 黑龙江科技大学学报, 2022, 32(3):401-405.
	Guo Songlin, Ba Yankun, Li Chun. Power load forecasting model based on improved SSA algorithm and optimized BP neural network[J]. Journal of Heilongjiang University of Science and Technology, 2022, 32(3):401-405.
[10]	邹定江, 刘天羽, 王勉, 等. 改进麻雀算法优化Elman神经网络的短期电力负荷预测[J]. 上海电机学院学报, 2022, 25(4):221-227.
	Zou Dingjiang, Liu Tianyu, Wang Mian, et al. Short-termpower load forecasting based on improved sparrow algorithm optimized by Elman neural network[J]. Journal of Shanghai Dianji University, 2022, 25(4):221-227.
[11]	赵长春. 混合改进麻雀搜索算法求解作业车间调度问题[D]. 郑州: 中原工学院, 2022:21-41.
	Zhao Changchun. Hybrid improved sparrow search al-gorithm for job-shop scheduling problem[D]. Zhengzh-ou: Zhongyuan University of Technology, 2022:21-41.
[12]	胡建华, 黄宇龙, 张坚, 等. 基于麻雀搜索算法优化双隐含层BP神经网络的张力减径钢管壁厚预测[J]. 塑性工程学报, 2022, 29(8):145-151. doi: 10.3969/j.issn.1007-2012.2022.08.018
	Hu Jianhua, Huang Yulong, Zhang Jian, et al. Wall thick-ness prediction of steel pipe during tension reduction based on double hidden layer BP neural network optimized by sparrow search algorithm[J]. Journal of Plastic Engineering, 2022, 29(8):145-151. doi: 10.3969/j.issn.1007-2012.2022.08.018
[13]	杨书恒. 基于麻雀搜索算法优化BP神经网络的光伏系统最大功率点追踪的研究[J]. 科技与创新, 2022(16):62-63,66.
	Yang Shuheng. Research on maximum power point tracking of photovoltaic system based on sparrow search algorithm optimized BP neural network[J]. Science and Technology & Innovation, 2022(16):62-63,66.
[14]	李丹丹, 马金全, 杨平平. 信号处理平台中可重构组件的设计与实现[J]. 计算机工程, 2018, 44(5):33-39. doi: 10.19678/j.issn.1000-3428.0046594
	Li Dandan, Ma Jinquan, Yang Pingping. Design and implementation of reconfigurable components in signal processing platform[J]. Computer Engineering, 2018, 44(5):33-39. doi: 10.19678/j.issn.1000-3428.0046594
[15]	沈小龙, 马金全, 胡泽明, 等. 面向异构信号处理平台的负载均衡算法[J/OL].(2022-07-18) [2022-09-12]http://kns.cnki.net/kcms/detail/51.1267.TN.20220915.1719.009.html.
	Shen Xiaolong, Ma Jinquan, Hu Zeming, et al. Load bal-ancing algorithm for heterogeneous signal processing platform[J/OL].(2022-07-18)[2022-09-12]http://kns.cnki.net/kcms/detail/51.1267.TN.20220915.1719.009.html.

环境	配置选项	配置信息
硬件	处理器	Intel(R) Core(TM) i5-1135G7 @2.40 GHz
	内存	16 GB
	系统	Windows 10 64位
软件	工具	MATLAB R2017a

参数	取值
m	500
genmax	1 000
safe	0.6
N_discover	0.5
N_vigilant	0.3