分层异构信号处理平台调度方法研究

doi:10.16180/j.cnki.issn1007-7820.2022.02.002

摘要/Abstract

摘要：

异构多处理器的高效性和可靠性能够满足日趋复杂的信号处理任务需求,因此分层异构系统已成为信号处理平台的发展趋势。为提高平台强实时性并解决高吞吐量的问题,文中对分层异构信号处理平台的软硬件模块及架构进行了研究,并采用有向无环图对组件任务及硬件资源进行建模。将已提出的调度算法按照任务类型、调度目标、调度过程和研究方法进行分类,并根据任务调度最新的研究进展提出组合优化算法的概念。文中对经典启发式算法、智能搜索算法、机器学习算法以及组合优化算法的性能进行对比和分析,发现组合优化算法能够满足平台任务调度的需求。

关键词: 分层异构信号处理平台, 软硬件架构, 任务调度, 有向无环图, 算法分类, 智能搜索, 机器学习, 组合优化算法

Abstract:

The efficiency and reliability of heterogeneous multi-processors can meet the requirements of increasingly complex signal processing tasks. Therefore, layered heterogeneous system has become the new research trend of signal processing platform. In order to improve the real-time performance of the platform and solve the problem of high throughput, the software and hardware modules and architecture of the hierarchical heterogeneous signal processing platform are studied, and a directed acyclic graph is used to model component tasks and hardware resources. The proposed scheduling algorithms are classified according to task types, scheduling objectives, scheduling processes and research methods, and the concept of combinatorial optimization algorithms is proposed according to the latest research progress of task scheduling. By comparing and analyzing the performance of classical heuristic algorithm, intelligent search algorithm, machine learning algorithm and combinatorial optimization algorithm, it is found that the combined optimization algorithm can meet the requirements of task scheduling of the platform.

Key words: layered heterogeneous signal processing platform, software and hardware architecture, task scheduling, directed acyclic graph, algorithm classification, intelligent search, machine learning, combinatorial optimization algorithm

中图分类号:

TN104

李娜,高博,谢宗甫. 分层异构信号处理平台调度方法研究[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.

图/表 7

图1

图2

图3

表1

图4

表2

表3

参考文献 27

[1]	Chen D Y, Vanhoy G, Beaufait M, et al. OSSIE/GNU radio generic component[C]. Washington D C: Proceedings of Wireless Telecommunications Symposium, 2011.
[2]	Mez I, Marojevic V, Salazar J, et al. A lightweight operating environment for next generation cognitive radios[C]. Washington D C:Proceedings of the Eleventh Euromicro Conference on Digital System Design Architectures,Methods and Tools, 2008.
[3]	宋杨. 基于遗传算法智能改进优化蚁群算法[J]. 网络安全技术与应用, 2020(10):71-73.
	Song Yang. Intelligent improved ant colony algorithm based on genetic algorithm[J]. Network Security Technology and Application, 2020(10):71-73.
[4]	王兰, 张龙信, 满君丰, 等. 异构计算环境下基于优先队列划分的调度算法[J]. 小型微型计算机系统, 2020, 41(2):303-309.
	Wang Lan, Zhang Longxin, Man Junfeng, et al. Scheduling algorithm based on priority queue partition in heterogeneous computing environment[J]. Mini Computer System, 2020, 41(2):303-309.
[5]	王晓燕. 基于强化学习的改进遗传算法研究[D]. 苏州:苏州大学, 2011.
	Wang Xiaoyan. Research on improved genetic algorithm based on reinforcement learning[D]. Suzhou:Soochow University, 2011.
[6]	高策. 面向机器学习任务的集群调度系统设计与实现[D]. 上海:上海交通大学, 2019.
	Gao Ce. Design and implementation of cluster scheduling system for machine learning tasks[D]. Shanghai:Shanghai Jiao Tong University, 2019.
[7]	谢宗甫, 高博, 刘拥军. 异构信号处理平台任务规划相关技术研究[J]. 信息工程大学学报, 2018, 19(5):568-573.
	Xie Zongfu, Gao Bo, Liu Yongjun. Research on task planning of heterogeneous signal processing platform[J]. Journal of Information Engineering University, 2018, 19(5):568-573.
[8]	杨平平, 岳春生, 胡泽明. 异构信号处理平台中层次性流水线调度算法[J]. 计算机工程, 2018, 44(11):83-89.
	Yang Pingping, Yue Chunsheng, Hu Zeming. Multi-level pipeline scheduling algorithm in heterogeneous signal processing platform[J]. Computer Engineering, 2018, 44(11):83-89.
[9]	Dorronsoro B, Pinel F. Combining machine learning and genetic algorithms to solve the independent tasks scheduling problem[C]. Exeter:Proceedings of the Third IEEE International Conference on Cybernetics, 2017.
[10]	梁秋玲, 张向利, 张红梅, 等. 基于多核处理器的关联任务并行感知调度算法[J]. 计算机工程, 2021, 47(7):212-217.
	Liang Qiuling, Zhang Xiangli, Zhang Hongmei, et al. Parallel perceptual scheduling algorithm for associative tasks based on multi-core processor[J]. Computer Engineering, 2021, 47(7):212-217.
[11]	童钊, 邓小妹, 陈洪剑, 等. 云环境下基于强化学习的多目标任务调度算法[J]. 小型微型计算机系统, 2020, 41(2):285-290.
	Tong Zhao, Deng Xiaomei, Chen Hongjian, et al. Multi-objective task scheduling algorithm based on reinforcement learning in cloud environments[J]. Journal of Chinese Computer System, 2020, 41(2):285-290.
[12]	Li J P, Zheng G W, Zhang H B, et al. Task scheduling algorithm for heterogeneous real-time systems based on deadline constraints[C]. Beijing:Proceedings of the Ninth International Conference on Electronics Information and Emergency Communication, 2019.
[13]	欧阳力多. 基于元启发式算法的异构计算系统静态任务调度的研究[D]. 长沙:湖南大学, 2015.
	Ouyang Liduo. Research on static task scheduling of heterogeneous computing system based on metaheuristic[D]. Changsha:Hunan University, 2015.
[14]	杨鹏飞, 王泉. 片上网络异构多核系统任务调度与映射[J]. 西安交通大学学报, 2015, 49(6):72-76.
	Yang Pengfei, Wang Quan. An effective scheduling and mapping algorithm of tasks for heterogeneous NoC-Based MPSoC[J]. Journal of Xi'an Jiaotong University, 2015, 49(6):72-76.
[15]	白恩慈, 张伟哲, 赵旭. 基于能量感知的实时并行任务蚁群调度算法[J]. 中国科技论文, 2016, 11(20):2348-2350.
	Bai Enci, Zhang Weizhe, Zhao Xu. Energy-aware ACO scheduling on real-time parallel task[J]. China Sciencepaper, 2016, 11(20):2348-2350.
[16]	杜姗姗, 冯瑞. 混合任务调度方法研究及其应用[J]. 微型电脑应用, 2015, 31(1):14-16.
	Du Shanshan, Feng Rui. Hybrid task schedule and its application[J]. Microcomputer Applications, 2015, 31(1):14-16.
[17]	童钊, 肖正, 李肯立, 等. 分布式系统中基于非合作博弈的调度算法[J]. 湖南大学学报(自然科学版), 2016, 43(10):139-147.
	Tong Zhao, Xiao Zheng, Li Kenli, et al. Scheduling algorithm in distributed systems based on non-cooperative game[J]. Journal of Hunan University (Natural Sciences), 2016, 43(10):139-147.
[18]	Sayadi H, Patel N, Sasan A, et al. Machine learning-based approaches for energy-efficiency prediction and scheduling in composite cores architectures[C]. Boston:Proceedings of the Thirty-fifth International Conference on Computer Design, 2017.
[19]	田国忠, 肖创柏. 分布式系统下的DAG任务调度研究综述[J]. 计算机工程与科学, 2015, 37(5):882-894.
	Tian Guozhong, Xiao Chuangbai. Scheduling DAG-based tasks in distributed system: a survey[J]. Computer Engineering & Science, 2015, 37(5):882-894.
[20]	Tang O, Basten T, Geilen M, et al. Mapping of synchronous dataflow graphs on MPSoCs based on parallelism enhancement[J]. Journal of Parallel and Distributed Computing, 2017, 101(3):79-91. doi: 10.1016/j.jpdc.2016.11.012
[21]	Chatterjee N, Paul S, Mukherjee P, et al. Deadline and energy aware dynamic task mapping and scheduling for network-on-chip based multi-core platform[J]. Journal of Systems Architecture, 2017, 74(6):61-77. doi: 10.1016/j.sysarc.2017.01.008
[22]	Cui D L, Peng Z P, Xiong J B, et al. A reinforcement learning-based mixed job scheduler scheme for grid or IaaS cloud[J]. IEEE Transactions on Cloud Computing, 2017(9):1-10.
[23]	Wei Z C, Zhang Y, Xu X W, et al. A task scheduling algorithm based on Q-learning and shared value function for WSNs[J]. Computer Networks, 2017, 126(1):141-149. doi: 10.1016/j.comnet.2017.06.005
[24]	Micolet P J, Smith A, Dubach C. A machine learning approach to mapping streaming workloads to dynamic multicore processors[J]. ACM Sigplan Notices, 2016, 51(5):113-122.
[25]	安鑫, 康安, 夏近伟, 等. 基于机器学习的异构感知多核调度方法[J]. 计算机应用, 2020, 40(10):3081-3087.
	An Xin, Kang An, Xia Jinwei, et al. Heterogeneous sensing multi-core scheduling method based on machine learning[J]. Journal of Computer Applications, 2020, 40(10):3081-3087.
[26]	张翔, 史志才, 陈良. 基于SWA优化级联网络的表情识别方法[J]. 电子科技, 2020, 33(9):16-20.
	Zhang Xiang, Shi Zhicai, Chen Liang. Expression recognition method based on cascade network optimized by SWA[J]. Electronic Science and Technology, 2020, 33(9):16-20.
[27]	侯艳丽. 基于最小二乘支持向量机的移动机器人导航[J]. 电子设计工程, 2011, 19(23):11-12.
	Hou Yanli. Mobile robot mavigation based on least squares support vector machine[J]. Electronic Design Engineering, 2011, 19(23):11-12.

方式项目	DHA	ISA	ML
适用场景	大多用于静态任务和周期任务调度场景	多目标任务调度	随机到达、实时任务调度	各种任务调度场景
优点	离线算法,能够预先安排好调动,减少任务调度过程中的开销	能够获得全局最优解	能在线进行任务分派,有更好的灵活性	能够实现资源的动态分配,通过智能决策为处理器分配合适的调度任务
缺点	缺乏灵活性,资源利用率较低	需要较长的收敛时间,局部搜索能力较弱,算法可预测性差	训练时间较长,对结果缺乏解释能力	算法尚处于探索阶段

算法类别	优化目标	文献	优化/改进方式	算法对比
DH-ISA	执行效率	[3]	ACO结合HEFT,将 HEFT的启发式知识带入ACO的启发函数中	HEFT、SACTS
	执行效率	[16]	改进任务的概率选择公式,并实时调整挥发因子ρ的值	ACO、改进后的ACO
	调度长度	[13]	GA结合HLEFT,通过交叉变异引入新的处理器排列方式	EA、HLEFT、GA
	调度长度	[9]	改进HEFT任务调度排序方法,按照最长路径值降序排列	DTSV、HEFT、busHEFT
	吞吐量	[14]	增强初始解和突变操作产生的子代的并行性	HEFT、CGA、HGA
ISA-ISA	调度长度	[10]	采用禁忌搜索TS设计GA中交叉和变异操作	TS-GA、PTS-PGATS
ISA-ISA	调度长度	[17]	GA结合修正列表调度算法MLSH、GA与ACO结合改进寻优能力	MLSH、GAMLSH、ACO、GAACO

算法类别	优化目标	文献	优化/改进方式	对比算法
ML-ISA	系统性能	[4,6]	ANN、SVM、AdaBoost构建3种性能预测模型,分别与 GA结合在线调度	轮询调度、抽样调度、GA结合ANN
ML-ISA	能耗	[18]	通过SVM学习经验知识对Q值进行更新	SVM-Q、BP-Q、ISVM-Q
ML-DHA	调度长度	[11]	在优先级排序阶段引入Q-Learning,将 HEFT 算法的Upward Rank 值作为 Q-Learning 更新过程中的立即奖励值	HEFT、Q-Learning
ML-DHA	响应时间	[15]	使用马尔可夫决策过程来定义调度问题	MET、MCT、OLB、Q-Learning