面向异构信号处理平台的量子调度算法

doi:10.16180/j.cnki.issn1007-7820.2024.03.011

Abstract

Abstract:

In order to solve the problem that the scheduling length of existing scheduling algorithms in heterogeneous signal processing platforms is large, which leads to the decline of real-time performance of signal processing applications, a quantum scheduling algorithm for heterogeneous signal processing platforms is proposed. The algorithm adopts task priority diffluence sorting strategy to obtain more accurate task scheduling order.Quantum bits are used to encode the task allocation scheme, which increases the diversity of the task allocation scheme, and the coding rules help to find the global optimal solution out of the local optimal. According to the principle of minimum computing cost and the idea of task replication, the processor is allocated to reduce the communication cost between tasks, and the quantum coding scheme is updated through the quantum turnstile to constantly approximate the optimal solution. Simulation results show that the proposed algorithm can reduce the scheduling length, improve the real-time performance of signal processing applications, and improve the working efficiency of the platform.

Key words: task scheduling, heterogeneous signal processing platform, DAG, quantum algorithm, quantum bit, quantum revolving gate, dispatch length, signal processing

CLC Number:

TN911

SHEN Xiaolong, MA Jinquan, HU Zeming, LI Na, LI Yudong. Quantum Scheduling Algorithm for Heterogeneous Signal Processing Platform[J].Electronic Science and Technology, 2024, 37(3): 84-90.

Figures/Tables 13

Figure 1.

Figure 2.

Table 1.

Figure 3.

Table 2.

The value of the quantum ration angle"

当前编码	最优解编码	当前量子比特位置	旋转角
0	1	第一象限	+π/25
0	1	第二象限	-π/25
0	1	第三象限	+π/25
0	1	第四象限	-π/25
0	1	$0 >$ 态	±π/25
0	1	$1 >$ 态	0
1	0	第一象限	-π/25
1	0	第二象限	+π/25
1	0	第三象限	-π/25
1	0	第四象限	+π/25
1	0	$0 >$ 态	0
1	0	$1 >$ 态	±π/25

Table 2.

Figure 4.

Table 3.

Figure 5.

Table 4.

Figure 6.

Table 5.

Figure 7.

Figure 8.

References 18

[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]. 电子科技, 2024, 37(1):33-40.
	Shen Xiaolong, Ma Jinquan, Ji Yawei, et al. Sparrow optimization algorithm for task scheduling of heterogeneous processing platform[J]. Electronic Science and Technology, 2024, 37(1):33-40.
[4]	杨平平, 岳春生, 胡泽明. 异构信号处理平台中层次性流水线调度算法[J]. 计算机工程, 2018, 44(11):83-89. doi: 10.19678/j.issn.1000-3428.0048806
	Yang Pingping, Yue Chunsheng, Hu Zeming. Multi-levelpipeline scheduling algorithm in heterogeneous signalprocessing platform[J]. Computer Engineering, 2018, 44(11):83-89. doi: 10.19678/j.issn.1000-3428.0048806
[5]	陈韩, 张晶, 董俊, 等. 子任务调度和时延联合优化的MEC卸载方案[J]. 系统工程与电子技术, 2023, 45(2):572-579. doi: 10.12305/j.issn.1001-506X.2023.02.30
	Chen Han, Zhang Jing, Dong Jun, et al. MEC of floading scheme based on joint optimization of subtask scheduling and delay[J]. Systems Engineering and Electronics, 2023, 45(2):572-579.
[6]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化调度方法[J]. 计算机应用, 2023, 43(1):185-191. doi: 10.11772/j.issn.1001-9081.2021111862
	Jiang Songyan, Liao Xiaojuan, Chen Guangzhu. Optimaltask scheduling method based on satisfiability modulotheory for multiple processors with communication delay[J]. Jounal of Computer Applications, 2023, 43(1):185-191.
[7]	仇宾, 孙曼曼, 崔素丽. 基于剪枝优化的多变邻域节能调度算法[J]. 应用科学学报, 2022, 40(2):349-360.
	Qiu Bin, Sun Manman, Cui Suli. Energy-saving scheduling algorithm for multivariable neighborhood based on pruning optimization[J]. Journal of Applied Science, 2022, 40(2):349-360.
[8]	石威, 郑纬民. 相关任务图的均衡动态关键路径调度算法[J]. 计算机学报, 2001, 24(9):991-997.
	Shi Wei, Zheng Weimin. The balanced dynamic critical path scheduling algorithm of dependent task graphs[J]. Chinese Journal of Computers, 2001(9):991-997.
[9]	Topcuoglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3):260-274. doi: 10.1109/71.993206
[10]	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:112-123.
[11]	沈小龙, 马金全, 岳春生, 等. 面向异构处理平台的任务调度算法[J]. 信息工程大学学报, 2022, 23(4):415-420.
	Shen Xiaolong, Ma Jinquan, Yue Chunsheng, et al. Task scheduling algorithm for heterogeneous processing platforms[J]. Journal of Information Engineering University, 2022, 23(4):415-420.
[12]	沈小龙, 马金全, 胡泽明, 等. 面向异构信号处理平台的负载均衡算法[J]. 电讯技术, 2023, 63(12):1978-1984.
	Shen Xiaolong, Ma Jinquan, Hu Zeming, et al. Load balancing algorithm for heterogeneous signal processing platform[J]. Telecommunication Engineering, 2023, 63(12):1978-1984.
[13]	许德斌. 基于量子密码的数字化档案信息安全防护算法设计[J]. 廊坊师范学院学报(自然科学版), 2022, 22(2):8-12.
	Xu Debin. Design of digital archive information security protection algorithm based on quantum cryptography[J]. Journal of Langfang Normal University(Natural Science Edition), 2022, 22(2):8-12.
[14]	符亚杰, 冯国成. 基于量子免疫优化算法的BP神经网络短期负荷预测方法研究[J]. 电子器件, 2021, 44(3):659-663.
	Fu Yajie, Feng Guocheng. Research on BP neural network short term load forecasting method based on quantum immune optimization algorithm[J]. Chinese Journal of Electron Devices, 2021, 44(3):659-663.
[15]	徐亮. 应用量子粒子群算法优化神经网络的数据库重复记录检测[J]. 微型电脑应用, 2022, 38(1):142-144,149.
	Xu Liang. Using quantum particle swarm to optimize database duplicate record detection based on neural network[J]. Microcomputer Applications, 2022, 38(1):142-144,149.
[16]	赵胶胶. 基于变分量子电路的量子生成对抗网络研究[D]. 南京: 南京信息工程大学, 2022:23-55.
	Zhao Jiaojiao. Research on quantum generation countermeasure network based on variational quantum circuit[D]. Nanjing: Nanjing University of Information Science and Technology, 2022:23-55.
[17]	李丹丹, 马金全, 杨平平. 信号处理平台中可重构组件的设计与实现[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
[18]	王宇平, 李英华. 求解TSP的量子遗传算法[J]. 计算机学报, 2007(5):5748-5755.
	Wang Yuping, Li Yinghua. A novel quantum genetic algorithm for TSP[J]. Chinese Journal of Computers, 2007(5):5748-5755.

参数	取值
G	1 000
size	30
quantum_bit_num	3

算法	调度长度
HEFT	80
文献[11]	67
QSA	69
HSIP	67

Quantum Scheduling Algorithm for Heterogeneous Signal Processing Platform

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 18

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]	ZHU Jiawei, MAO Hang, ZHANG Fengdeng. Research on Hybrid Critical-Level Task Scheduling and Semi-Partition Algorithm in Multi-Core Processor [J]. Electronic Science and Technology, 2024, 37(3): 1-9.
[2]	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.
[3]	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.
[4]	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.
[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]	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.
[11]	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.
[12]	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.
[13]	CHEN Guizhou. Research on Substation Integrated Automation Control System Based on DSP [J]. Electronic Science and Technology, 2020, 33(9): 75-78.
[14]	CHEN Qing,WENG Xufeng. A Robust Image Watermarking Based on Harris Feature Points and Pseudo-Zernike Moments [J]. , 2016, 29(3): 183-.
[15]	ZHANG Jing. The Hardware System Design of A Certain Radar Signal Processing Board [J]. , 2015, 28(6): 147-.

任务	处理器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