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

doi:10.16180/j.cnki.issn1007-7820.2024.01.005

Abstract

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

CLC Number:

TN911

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.

Figures/Tables 19

Figure 1.

Figure 2.

Table 1.

Figure 3.

Figure 4.

Table 2.

Table 3.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Figure 9.

Figure 10.

Figure 11.

Figure 12.

Figure 13.

Figure 14.

Figure 15.

Figure 16.

References 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

Sparrow Optimization Algorithm for Task Scheduling of Heterogeneous Processing Platform

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 19

References 15

Related Articles 15

Metrics

Comments

Recommended 0

任务	处理器P₁	处理器P₂	处理器P₃
1	17	16	9
2	13	19	22
3	11	13	19
4	13	8	17
5	12	13	10
6	13	16	9
7	7	13	11
8	5	11	14
9	18	12	20
10	21	7	16

[1]	LI Yudong,MA Jinquan,XIE Zongfu,SHEN Xiaolong. Research on Task Scheduling of Heterogeneous Platform Signal Processing [J]. Electronic Science and Technology, 2024, 37(1): 24-32.
[2]	HU Yifei,BAO Ziqun,BAO Xiaoan. A Dynamic-Static Load Balancing Algorithm Based on Improved Genetic Algorithm [J]. Electronic Science and Technology, 2023, 36(9): 79-85.
[3]	LUO Xin,FENG Wu,SUN Weijie,LIU Maliang. Design of Multifunctional Array Signal Processing System Based on FPGA [J]. Electronic Science and Technology, 2023, 36(3): 1-6.
[4]	ZHOU Qiping,HE Wei,JIA Lei,GUO Junkai,ZHAO Jianguo. Research on Internet of Vehicles Navigation Technology Based on BDS and Edge Computing [J]. Electronic Science and Technology, 2023, 36(1): 51-59.
[5]	Zhenzhou DENG,Qin HU,Wensheng LAI,Chunlei HAN,Ling TAO. Sparse Quantization Level Method for Scintillation Pulse Based on Feedback Regulation [J]. Electronic Science and Technology, 2022, 35(3): 1-7.
[6]	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.
[7]	FENG Xianding,WEI Jingtao,WU Zhangyong,QIAN Jie,PU Youshang. Research on Load Forecast of Ball Mill Based on PCA-PSO-SVM [J]. Electronic Science and Technology, 2022, 35(1): 29-34.
[8]	GENG Zhaoqian,ZHU Huming,LI Xuming,CHEN Meiqing,YANG Guipeng. A Review: Radar Signal Processing Based on High Performance Computing [J]. Electronic Science and Technology, 2021, 34(9): 1-6.
[9]	WANG Yang,WANG Xiaolei,YUAN Ziang,YUAN Ruming. A Matrix Multiplication Mapping Technology Based on NOC Multi-Core System [J]. Electronic Science and Technology, 2021, 34(5): 54-60.
[10]	SUN Huixia,ZHOU Shangnan,ZHOU Ling,DOU Yongmei. Development of Digital Signal Processing Simulation Platform Based on MATLAB GUI [J]. Electronic Science and Technology, 2021, 34(2): 74-78.
[11]	HE Qiang,YANG Qinghui,ZHANG Huaiwu. A Control Method of Power up Bias Sequence of Radio Frequency Amplifier [J]. Electronic Science and Technology, 2021, 34(2): 1-6.
[12]	ZHOU Xiaobo,ZOU Renling,LU Xuhua,WANG Haibin,ZHANG Junxiang. Research Progress of Surface Electromyography Signal Classifier Based on Artificial Neural Network [J]. Electronic Science and Technology, 2021, 34(2): 62-67.
[13]	CHEN Guizhou. Research on Substation Integrated Automation Control System Based on DSP [J]. Electronic Science and Technology, 2020, 33(9): 75-78.
[14]	LONG Pin. Research on Mobile Signaling Data Acquisition Technology under LTE Core Network Architecture [J]. Electronic Science and Technology, 2019, 32(12): 80-83.
[15]	JI Lili, LI Ye . Virtual Machine Cluster Optimization Based on Migration in Cloud Environment [J]. , 2016, 29(8): 117-.

任务	处理器P₁	处理器P₂	处理器P₃
1	17	16	9
2	13	19	22
3	11	13	19
4	13	8	17
5	12	13	10
6	13	16	9
7	7	13	11
8	5	11	14
9	18	12	20
10	21	7	16

任务	处理器P₁	处理器P₂	处理器P₃
1	17	16	9
2	13	19	22
3	11	13	19
4	13	8	17
5	12	13	10
6	13	16	9
7	7	13	11
8	5	11	14
9	18	12	20
10	21	7	16