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

doi:10.16180/j.cnki.issn1007-7820.2024.03.011

摘要/Abstract

摘要：

针对异构信号处理平台中已有调度算法的调度长度较大导致信号处理应用实时性下降问题,文中提出一种面向异构信号处理平台的量子调度算法。该算法采用任务优先级分流排序策略,得到更加准确的任务调度顺序。使用量子比特对任务分配方案进行编码,增加任务分配方案的多样性,且编码规则有助于跳出局部最优找到全局最优解。按照最小计算开销原则和任务复制思想进行处理器分配,减少任务间通信开销,并通过量子旋转门对量子编码方案进行更新,不断逼近最优解。仿真结果表明,所提算法能够减少调度长度,提升信号处理应用的实时性,进而提高平台的工作效率。

关键词: 任务调度, 异构信号处理平台, DAG, 量子算法, 量子比特, 量子旋转门, 调度长度, 信号处理

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

中图分类号:

TN911

沈小龙, 马金全, 胡泽明, 李娜, 李宇东. 面向异构信号处理平台的量子调度算法[J]. 电子科技, 2024, 37(3): 84-90.

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.

图/表 13

图1

图2

表1

图3

表2

量子旋转角取值"

当前编码	最优解编码	当前量子比特位置	旋转角
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

表2

图4

表3

图5

表4

图6

表5

图7

图8

参考文献 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