异构多平台信号处理任务调度研究

doi:10.16180/j.cnki.issn1007-7820.2024.01.004

摘要/Abstract

摘要：

简单的并行计算或单一异构平台已经无法满足计算量大、复杂度高的信号处理和任务调度需求,异构多平台系统已经成为信号处理和任务调度的发展趋势。针对提高平台的吞吐量、处理器的利用率以及任务的感知等问题,文中对异构多平台信号处理模型进行了研究,并利用有向无环图对调度任务和软硬件资源建模。基于已提出的调度算法,对任务调度进行了归纳总结、对比分析,发现基于任务感知的混合调度算法能够较好地满足平台调度需求。利用基于任务感知的混合调度算法解决信号处理中的任务调度将是未来研究发展的趋势。

关键词: 异构多平台信号处理, 软件体系, 硬件架构, 任务调度, 任务感知, 算法分类, 有向无环图, 混合算法

Abstract:

The simple parallel computing or single heterogeneous platform can no longer meet the requirements of signal processing and task schedulingwith large computation and high complexity, so heterogeneous multi platform system has become the development trend of signal processing and task scheduling. In view of improving the throughput of the platform, utilization rate of the processor and perception of the task,this study investigates the signal processing model of heterogeneous multi-platform, and the scheduling tasks and hardware and software resources are modeled by directed acyclic graph.Based on the proposed scheduling algorithms, the task scheduling is summarized and compared. It is found that the hybrid scheduling algorithm based on task perception can meet the platform scheduling requirements well.It is a trend of future research to use mixed scheduling algorithm based on task perception to solve task scheduling in signal processing.

Key words: heterogeneous platform signal processing, software system, hardware architecture, task scheduling, task perception, algorithm classification, directed acyclic graph, hybrid algorithm

中图分类号:

TN104

李宇东,马金全,谢宗甫,沈小龙. 异构多平台信号处理任务调度研究[J]. 电子科技, 2024, 37(1): 24-32.

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.

图/表 7

图1

图2

图3

图4

表1

表2

图5

参考文献 55

[1]	李启锐, 彭心怡. 基于深度强化学习的云作业调度及仿真研究[J]. 系统仿真学报, 2022, 34(2):258-268. doi: 10.16182/j.issn1004731x.joss.21-0337
	Li Qirui, Peng Xinyi. Job scheduling and simulation in cloud based on deep reinforcement learning[J]. Journal of System Simulation, 2022, 34(2):258-268. doi: 10.16182/j.issn1004731x.joss.21-0337
[2]	张鹤于. 基于强化学习的异构计算平台调度算法研究[D]. 西安: 西安电子科技大学, 2021:33-40.
	Zhang Heyu. Research on scheduling algorithm of heterogeneous computing platform based on reinforcement learning[D]. Xi'an: Xidian University, 2021:33-40.
[3]	李玮瑶. 基于资源感知的大数据处理任务调度方法[J]. 信息与电脑(理论版), 2019, 31(24):106-107.
	Li Weiyao. Resource-aware large data processing task scheduling method[J]. Information & Computer, 2019, 31(24):106-107.
[4]	郭晓勇. 基于资源感知的动态云任务调度算法研究[D]. 呼和浩特: 内蒙古大学, 2021:19-23.
	Guo Xiaoyong. Research on dynamic cloud task scheduling algorithm based on resource awareness[D]. Hohhot: Inner Mongolia University, 2021:19-23.
[5]	杜姗姗, 冯瑞. 混合任务调度方法研究及其应用[J]. 微型电脑应用, 2015, 31(1):14-16,21.
	Du Shanshan, Feng Rui. Hybrid task schedule and its application[J]. Microcomputer Applications, 2015, 31(1):14-16,21.
[6]	李娜, 高博, 谢宗甫. 分层异构信号处理平台调度方法研究[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]	杨平平, 岳春生, 胡泽明. 异构信号处理平台中层次性流水线调度算法[J]. 计算机工程, 2018, 44(11):83-89. doi: 10.19678/j.issn.1000-3428.0048806
	Yang Pingping, Yue Chunsheng, Hu Zeming. Multi-level pipeline scheduling algorithm in heterogeneous signal processing platform[J]. Computer Engineering, 2018, 44 (11):83-89. doi: 10.19678/j.issn.1000-3428.0048806
[8]	Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling:A survey[M]. Vancouver: Annals of Discrete Mathematics, Elsevier, 1979:55-90.
[9]	罗乐, 王春华, 张多利, 等. 一种多核系统改进型列表调度算法[J]. 电子科技, 2020, 33(6):52-57.
	Luo Le, Wang Chunhua, Zhang Duoli, et al. A multicore system improved list scheduling algorithm[J]. Electronic Science and Technology, 2020, 33(6):52-57.
[10]	Jackson J R. Simulation research on job shop production[J]. Naval Research Logistics Quarterly, 1957, 4(3):287-295. doi: 10.1002/nav.v4:4
[11]	江超. 异构计算平台静态任务调度算法综述[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.
[12]	钱晓龙, 唐立新, 刘文新. 动态调度的研究方法综述[J]. 控制与决策, 2001(2):141-145.
	Qian Xiaolong, Tang Lixin, Liu Wenxin. Dynamic scheduling:A survey of research methods[J]. Control and Decision, 2001(2):141-145.
[13]	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
[14]	Liu G Q, Poh K L, Xie M. Iterative list scheduling for heterogeneous computing[J]. Journal of Parallel and Distributed Computing, 2005, 65(5):654-665. doi: 10.1016/j.jpdc.2005.01.002
[15]	Hagras T, Janecek J. A simple scheduling heuristic for heterogeneous computing environments[C]. Ljubljana: Parallel and Distributed Computing, International Symposium on IEEE Computer Society, 2003:1512-1520.
[16]	Radulescu A, Van Gemund A J C. Fast and effective task scheduling in heterogeneous systems[C]. Cancun: Proceedings of the Ninth Heterogeneous Computing Workshop, 2000:319-326.
[17]	Dorostkar F, Mirzakuchaki S. List scheduling for heterogeneous computing systems introducing a performance-effective definition for critical path[C]. Mashhad: The Ninth International Conference on Computer and Knowledge Engineering,IEEE, 2019:9-16.
[18]	Arabnejad H, Barbosa J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(3):682-694. doi: 10.1109/TPDS.2013.57
[19]	Ilavarasan E, Thambidurai P, Mahilmannan R. Performance effective task scheduling algorithm for heterogeneous computing system[C]. Lillie: The Fourth International Symposium on Parallel and Distributed Computing, 2005:630-638.
[20]	Ijaz S, Munir E U. MOPT:List-based heuristic for scheduling workflows in cloud environment[J]. The Journal of Supercomputing, 2019, 75(7):3740-3768. doi: 10.1007/s11227-018-2726-6
[21]	李显宁, 钟诚. 异构计算环境下并行任务调度算法研究进展分析[C]. 长春: 全国理论计算机科学学术年会论文集, 2006:528-535.
	Li Xianning, Zhong Cheng. Research progress of parallel task scheduling algorithm in heterogeneous computing environments[C]. Changchun: Proceedings of the National Annual Conference of Theoretical Computer Science, 2006:528-535.
[22]	Boeres C, Rebello V E F. A cluster-based strategy for scheduling task on heterogeneous processors[C]. Iguacu: The Sixteenth Symposium on Computer Architecture and High Performance Computing,IEEE, 2004:786-792.
[23]	Kim S J. A general approach to mapping of parallel computations upon multiprocessor architectures[C]. Fairfax: Proceedings of the International Conference on Parallel Processing IEEE Computer Society, 1988:538-550.
[24]	Yu D, Ying Y, Zhang L, et al. Balanced scheduling of distributed workflow tasks based on clustering[J]. Knowledge-Based Systems, 2020, 199(8):105930. doi: 10.1016/j.knosys.2020.105930
[25]	Vidyarthi D P, Tripathi A K, Sarker B K, et al. Cluster-based multiple task allocation in distributed computing system[C]. Santa Fe: The Eighteenth International Parallel and Distributed Processing Symposium, 2004:195-206.
[26]	Yang T, Gerasoulis A. DSC:Scheduling parallel tasks on an unbounded number of processors[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(9):951-967. doi: 10.1109/71.308533
[27]	Cirou B, Jeannot E. Triplet:A clustering scheduling algorithm for heterogeneous systems[C]. Valencia: Proceedings of the International Conference on Parallel Processing Workshops, 2001:309-315.
[28]	Dogan A, Ozguner R. LDBS:A duplication based scheduling algorithm for heterogeneous computing systems[C]. Vancouver: Proceedings of the International Conference on Parallel Processing, 2002:55-62.
[29]	Hagras T, Janecek J. A high performance,low complexity algorithm for compile-time task scheduling in heterogeneous systems[C]. Cork: The Eighteenth International Parallel and Distributed Processing Symposium, 2004:319-327.
[30]	Bozdag D, Catalyurek U, Ozguner F. A task duplication based bottom-up scheduling algorithm for heterogeneous environments[C]. Rhodes: Proceedings of IEEE the Twentieth International Parallel & Distributed Processing Symposium, 2006:302-311.
[31]	Ilavarasan E, Thambidurai P. Levelized scheduling of directed a-cyclic precedence constrained task graphs onto heterogeneous computing system[C]. Besancon: The First International Conference on Distributed Frameworks for Multimedia Applications, 2005:865-871.
[32]	Baskiyar S, Dickinson C. Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication[J]. Journal of Parallel and Distributed Computing, 2005, 65(8):911-921. doi: 10.1016/j.jpdc.2005.01.006
[33]	He K, Meng X, Pan Z, et al. A novel task-duplication based clustering algorithm for heterogeneous computing environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(1):2-14. doi: 10.1109/TPDS.2018.2851221
[34]	Dorronsoro B, Pinel F. Combining machine learning and genetic algorithms to solve the independent tasks scheduling problem[C]. Exeter: The Third IEEE International Conference on Cybernetics, 2017:48-57.
[35]	Fang Y Q, Xia X, Ge J W. Cloud computing task scheduling algorithm based on improved genetic algorithm[C]. Chengdu: IEEE the Third Information Technology, Networking, Electronic and Automation Control Conference, 2019:1314-1325.
[36]	Zhou Z, Li F, Zhu H, et al. An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments[J]. Neural Computing and Applications, 2020, 32(6):1531-1541. doi: 10.1007/s00521-019-04119-7
[37]	Xiang B, Zhang B, Zhang L. Greedy-Ant: Ant colony system-inspired workflow scheduling for heterogeneous computing[J]. IEEE Access, 2017, 5(6):11404-11412. doi: 10.1109/ACCESS.2017.2715279
[38]	Ramash R. Dynamic job shop scheduling-A review of simulation research[J]. OMEGA International Journal of Management Science, 1990, 18(1):43-57.
[39]	Liu H, Dong J J. Dispatching rule selection using artificial neural networks for dynamic planning and scheduling[J]. Journal of Intelligent Manufacturing, 1996, 7(3):243-250. doi: 10.1007/BF00118083
[40]	Fox M S, Smith S F. ISIS-A knowledge-based system for factory scheduling[J]. Expert Systems, 1984, 1(1):25-49. doi: 10.1111/exsy.1984.1.issue-1
[41]	Smith S F, Hynynen J E. Integrated decentralization of production management:An approach for factory scheduling[J]. Intelligent and Integrated Manufacturing Analysis and Synthesis, 1987, 61(2):427-439.
[42]	Collinot A, Le Pape C, Pinoteau G. SONIA:A knowledge-based scheduling system[J]. Artificial Intelligence in Engineering, 1988, 3(2):86-94. doi: 10.1016/0954-1810(88)90024-6
[43]	Bensana E, Bel G, Dubois D. OPAL:A multi-knowledge-based system for industrial job-shop scheduling[J]. The International Journalof Production Research, 1988, 26(5):795-819.
[44]	何世文, 袁军, 安振宇, 等. 基于图神经网络的联合用户调度与波束成形优化算法[J]. 通信学报, 2022, 43(7):73-84. doi: 10.11959/j.issn.1000-436x.2022133
	He Shiwen, Yuan Jun, An Zhenyu, et al. GNN-based optimization algorithm for joint user scheduling and beamforming[J]. Journal on Communications, 2022, 43(7):73-84. doi: 10.11959/j.issn.1000-436x.2022133
[45]	徐胜超, 叶力洪. 基于长短期记忆神经网络的容器云队列在线任务动态分配[J]. 计算机与现代化, 2022, 28(7):79-84.
	Xu Shengchao, Ye Lihong. Container cloud queue online task dynamic allocation based on long short-term memory neural network[J]. Computer and Modernization, 2022, 28(7):79-84.
[46]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(8):1331-1340.
	Luo Lei, Chen Zhaoyun, Wang Lixuan. User QoS-aware deep learning tasks dynamic scheduling on GPU cluster[J]. Computer Engineering & Science, 2021, 43(8):1331-1340.
[47]	Li N, Gao B, Xie Z, et al. Q-learning based intelligent ant colony scheduling algorithm in heterogeneous system[C]. Chengdu: IEEE the Fourth International Conference on Electronics Technology, 2021:490-501.
[48]	张影. 基于机器学习的异构多核系统在线映射方法研究[D]. 合肥: 合肥工业大学, 2019:19-29.
	Zhang Ying. A machine learning based mapping approach for heterogeneous multi-processors system[D]. Hefei: Hefei University of Technology, 2019:19-29.
[49]	高放. 面向片上异构多核系统的机器学习算法并行化技术研究[D]. 北京: 北京工业大学, 2017:43-58.
	Gao Fang. Research on parallelization of machine learning algorithm for on-chip heterogeneous multi-core systems[D]. Beijing: Beijing University of Technology, 2017:43-58.
[50]	陈亮, 阎春平, 陈建霖, 等. 基于深度学习神经网络和量子遗传算法的柔性作业车间动态调度[J]. 重庆大学学报, 2022, 45(6):40-54.
	Chen Liang, Yan Chunping, Chen Jianlin, et al. Dynamic scheduling of flexible job shop based on deep Q-learning neural network and quantum genetic algorithm[J]. Journal of Chongqing University, 2022, 45(6):40-54.
[51]	童钊, 邓小妹, 陈洪剑, 等. 云环境下基于强化学习的多目标任务调度算法[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 Systems, 2020, 41(2):285-290.
[52]	Rashidi S, Sharifian S. A hybrid heuristic queue based algorithm for task assignment in mobile cloud[J]. Future Generation Computer Systems, 2017, 68(3):331-345. doi: 10.1016/j.future.2016.10.014
[53]	Senthil Kumar A M, Venkatesan M. Multi-objective task scheduling using hybrid genetic-ant colony optimization algorithm in cloud environment[J]. Wireless Personal Communications, 2019, 107(4):1835-1848. doi: 10.1007/s11277-019-06360-8
[54]	Chen X, Long D. Task scheduling of cloud computing using integrated particle swarm algorithm and ant colony algorithm[J]. Cluster Computing, 2019, 22(2):2761-2769. doi: 10.1007/s10586-017-1479-y
[55]	Cho K M, Tsai P W, Tsai C W, et al. A hybrid meta-heuristic algorithm for VM scheduling with load balancing in cloud computing[J]. Neural Computing and Applications, 2015, 26(6):1297-1309. doi: 10.1007/s00521-014-1804-9

算法类型		典型算法		优化目标		指标参数		应用场景
HA	列表调度	HEFT^[13]、MOPT^[20]		最小化完成时间最小化调度长度		调度长度比、加速比、松弛度、效率、归一化调度长度		异构系统
	列表调度	PETS^[19]、PEFT^[18]、CIPOP^[17]		最小化完成时间最小化调度长度		调度长度比、加速比、松弛度、效率、归一化调度长度		异构系统
	聚类调度	DSC^[26]、RBCA^[24]、LCM^[23]		最小化并行时间、避免依赖性失衡、解决运行时不平衡、最小化最差调度长度		更优调度频率、执行完成时间、调度长度比、最小调度长度		不限数量处理器、云计算、分布式计算
	复制调度	DBUS^[30]、TDCA^[33]		最小化调度长度		归一化调度长度、平均调度长度		异构系统
MHA		EGA-TS^[35]、MGGS^[36]、 Greedy-Ant^[37]	最小化调度长度/执行时间、减少迭代次数、负载均衡		调度长度比、加速比、负载均衡、 QoS、平均调度长度		云计算、异构计算
AIA		机器学习算法^[48-49]、深度学习算法^[46???-50]、强化学习算法^[1,51]	最小完成时间、任务开销、减少迭代次数		调度长度比、平均调度长度、迭代次数、功耗		云计算、异构系统
THA		TPN-GA^[4]、GA-ACO^[52-53]、 ACO-PSO^[54-55]	最小化完成时间、QoS满意度、响应时间、最小调度长度		调度长度比、响应时间、功耗、最小调度长度		云计算、异构系统、分布式计算等

算法类型	优点	缺点	适用场景
HA	离线算法,复杂度低,减少调度中的开销	计算量较大,灵活性差,耗时较长, 需建立符合实际问题的启发式规则	多用于异构系统静态任务调度
MHA	减少计算量,提高优化效率,不过分依赖实际问题模型	调度开销大,依赖初始值的设定, 结果不可预计	最小化调度长度,参数寻优的任务调度
AIA	简化模型复杂度,具有更高的容错率, 应用更广泛	数据模型的选择对结果影响较大, 训练时间较长	多目标,实时任务调度系统
THA	智能决策分配调度任务到合适的处理器上,实现资源的动态分配	算法仍处于深度开发探索阶段	多种调度场景