基于多核处理器的关联任务并行感知调度算法

doi:10.19678/j.issn.1000-3428.0057225

计算机工程 ›› 2021, Vol. 47 ›› Issue (7): 212-217. doi: 10.19678/j.issn.1000-3428.0057225

基于多核处理器的关联任务并行感知调度算法

梁秋玲¹, 张向利², 张红梅², 闫坤¹

1. 桂林电子科技大学信息与通信学院, 广西桂林 541004;
2. 桂林电子科技大学信息与通信学院认知无线电与信息处理省部共建教育部重点实验室, 广西桂林 541004

收稿日期:2020-01-15 修回日期:2020-02-20 发布日期:2020-04-21
作者简介:梁秋玲(1994-),女,硕士,主研方向为分布式计算;张向利(通信作者)、张红梅,教授、博士;闫坤,副教授、博士。
基金资助:
广西云计算与大数据协同创新中心开放项目“大数据分布式存储与处理系统设计与实现”（YD1904）；广西研究生教育创新计划（2017YJCX22）。

Parallel Perceptual Scheduling Algorithm for Related Tasks Based on Multi-Core Processors

LIANG Qiuling¹, ZHANG Xiangli², ZHANG Hongmei², YAN Kun¹

1. School of Information and Communication, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China;
2. Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education, School of Information and Communication, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China

Received:2020-01-15 Revised:2020-02-20 Published:2020-04-21

摘要/Abstract

摘要： 关联任务在多核处理器上并行调度所产生的通信时延，会对任务调度长度和处理器利用率造成负面影响，为了改善多核系统对关联任务的处理性能，针对关联任务在多核处理器上的调度特点，提出一种并行感知调度算法。计算各任务与终点间的最长路径值，按照该值的降序来分配任务调度次序，在分配处理器内核时兼顾关联度和任务最早可执行时间，设置最佳匹配评价函数。实验结果表明，与busHEFT和DTSV算法相比，该算法具有更短的任务调度时延、更少的通信量以及更高的处理器利用率。

关键词: 多核系统, 总线, 关联任务, 通信时延, 任务调度

Abstract: The communication delay caused by the parallel scheduling of related tasks on multi-core processors has a negative impact on the task scheduling length and processor utilization.In order to improve the performance of multi-core systems in processing related tasks,this paper proposes a parallel perceptual scheduling algorithm based on the scheduling characteristics of related tasks on multi-core processors.The algorithm calculates the value of the longest path from each task to the end point,and assigns the tasks in descending order of the calculated value.The relation and the earliest execution time are both considered when assigning processor cores,and the best matching evaluation function is created.Experimental results show that this algorithm has fewer task scheduling delay,less communication traffic and higher processor utilization compared with busHEFT,DTSV and other algorithms.

Key words: multi-core system, bus, related task, communication delay, task scheduling

中图分类号:

TP391

梁秋玲, 张向利, 张红梅, 闫坤. 基于多核处理器的关联任务并行感知调度算法[J]. 计算机工程, 2021, 47(7): 212-217.

LIANG Qiuling, ZHANG Xiangli, ZHANG Hongmei, YAN Kun. Parallel Perceptual Scheduling Algorithm for Related Tasks Based on Multi-Core Processors[J]. Computer Engineering, 2021, 47(7): 212-217.

http://www.ecice06.com/CN/Y2021/V47/I7/212

图/表 7

20210721091155

20210721091159

20210721091202

20210721091206

20210721091210

20210721091213

20210721091216

参考文献

[1] 陈刚,关楠,吕鸣松,等.实时多核嵌入式系统研究综述[J].软件学报,2018,29(7):2152-2176. CHEN G,GUAN N,LÜ M S,et al.State-of-the-art survey of real-time multicore system[J].Journal of Software,2018,29(7):2152-2176.(in Chinese)
[2] 周楠,胡娟,胡海明.多核处理器发展趋势及关键技术[J].计算机工程与设计,2018,39(2):393-399. ZHOU N,HU J,HU H M.Development trend and key techniques of multi-core processor[J].Computer Engineering and Design,2018,39(2):393-399.(in Chinese)
[3] 何军,王飙.多核处理器的结构设计研究[J].计算机工程,2007,33(16):208-210. HE J,WANG B.Research on architecture design of multi-core processor[J].Computer Engineering,2007,33(16):208-210.(in Chinese)
[4] 盛肖炜.多核处理器内部核间通信研究[D].沈阳:沈阳理工大学,2013. SHENG X W.Research on inter core communication in multi-core processors[D].Shenyang:Shenyang Ligong University,2013.(in Chinese)
[5] WANG T Y,NIU L W,REN S L,et al.Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guarantee[C]//Proceedings of 2015 Design,Automation & Test in Europe Conference & Exhibition.New York,USA:ACM Press,2015:1335-1340.
[6] LAKSHMANAN K,KATO S,RAJKUMAR R.Scheduling parallel real-time tasks on multi-core processors[C]//Proceedings of the 31st IEEE Real-Time Systems Symposium.Washington D.C.,USA:IEEE Press,2010:259-268.
[7] SAIFULLAH A,AGRAWAL K,LU C,et al.Multi-core real-time scheduling for generalized parallel task models[C]//Proceedings of 2011 IEEE Real-Time Systems Symposium.Washington D.C.,USA:IEEE Press,2012:217-226.
[8] SANJOY B,VINCENZO B,ALBERTO M S,et al.A generalized parallel task model for recurrent real-time processes[C]//Proceedings of 2012 IEEE Real-Time Systems Symposium.Washington D.C.,USA:IEEE Press,2012:63-72.
[9] KARAGIANNIS G,ALTINTAS O,EKICI E,et al.Vehicular networking:a survey and tutorial on requirements,architectures,challenges,standards and solutions[J].IEEE Communications Surveys & Tutorials,2011,13(4):584-616.
[10] WANG Y,SHAO Z,CHAN H C B,et al.Memory-aware task scheduling with communication overhead minimization for streaming applications on bus-based multiprocessor system-on-chips[J].IEEE Transactions on Parallel & Distributed Systems,2014,25(7):1797-1807.
[11] 赵瑞姣,朱怡安,李联.基于异构多核系统的混合关键任务调度算法[J].计算机工程,2018,44(2):51-55. ZHAO R J,ZHU Y A,LI L.Mixed-criticality task scheduling algorithm based on heterogeneous multi-core system[J].Computer Engineering,2018,44(2):51-55.(in Chinese)
[12] ROSEN J,ANDREI A,ELES P,et al.Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip[C]//Proceedings of IEEE International Real-Time Systems Symposium.Washington D.C.,USA:IEEE Press,2007:1445-1462.
[13] GU Z H,HE X Q,YUAN M X.Optimization of static task and bus access schedules for time-triggered distributed embedded systems with model-checking[C]//Proceedings of the 44th Annual Design Automation Conference.Washington D.C.,USA:IEEE Press,2007:294-299.
[14] CHEN Y S,SHIH C S,KUO T W.Dynamic task scheduling and processing element allocation for multi-function SoCs[C]//Proceedings of the 13th IEEE Real-Time and Embedded Technology and Applications Symposium.Washington D.C.,USA:IEEE Press,2007:81-90.
[15] WANG Y,LIU D,QIN Z W,et al.Optimally removing intercore communication overhead for streaming applications on MPSoCs computers[J].IEEE Transactions on Computers,2013,62(2):336-350.
[16] 黄姝娟,朱怡安,李兵哲,等.具有依赖关系的周期任务实时调度方法[J].计算机学报,2015,38(5):999-1006. HUANG S J,ZHU Y,LI B Z,et al.Real-time scheduling method for dependency period tasks[J].Chinese Journal of Computers,2015,38(5):999-1006.(in Chinese)
[17] 丁男,聂率航,许力,等.面向车联网应用的数据关联性任务调度算法[J].计算机学报,2017,40(7):1614-1625. DING N,NIE S H,XU L,et al.Data related task scheduling for vehicular ad hoc networks[J].Chinese Journal of Computers,2017,40(7):1614-1625.(in Chinese)
[18] 任良育,赵成萍,严华.基于任务复制与冗余消除的多核调度算法[J].计算机工程,2019,45(5):59-65. REN L Y,ZHAO C P,YAN H.Multi-core scheduling algorithm based on task duplication and redundancy elimination[J].Computer Engineering,2019,45(5):59-65. (in Chinese)
[19] HUNG S H,TU C H,YANG W L.A protable efficent intercore communication scheme for embedded multicore platforms[J].Journal of System Architecture,2011,57(2):193-205.
[20] MELANI A,BERTOGNA M,BONIFACI V,et al.Response-time analysis of conditional DAG tasks in multiprocessor systems[C]//Proceedings of 2015 Euromicro Conference on Real-Time Systems.Washington D.C.,USA:IEEE Press,2015:211-221.
[21] 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.

选择文件类型/文献管理软件名称

选择包含的内容

基于多核处理器的关联任务并行感知调度算法

Parallel Perceptual Scheduling Algorithm for Related Tasks Based on Multi-Core Processors

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	黄姣英, 李胜玉, 高成, 杨达明. 一种时序型总线硬件木马的植入与检测[J]. 计算机工程, 2021, 47(3): 160-165.
[2]	张浩, 魏敬和. 高效率PLB2AXI总线桥的设计与验证[J]. 计算机工程, 2020, 46(8): 228-234.
[3]	张庭芳, 黄海林, 郭劲林, 曹铭. CAN控制系统的时延分析及混合算法[J]. 计算机工程, 2020, 46(5): 305-311.
[4]	尹加豹, 朱涛, 崔凯华. VxWorks系统下CAN驱动的设计与优化[J]. 计算机工程, 2020, 46(3): 192-197.
[5]	熊文, 于全喜, 吴任博, 伦惠勤, 孔海斌, 谭军光. 基于演化博弈的弹性调控平台任务调度研究[J]. 计算机工程, 2019, 45(7): 86-94.
[6]	任良育,赵成萍,严华. 基于任务复制与冗余消除的多核调度算法[J]. 计算机工程, 2019, 45(5): 59-65.
[7]	彭晓燕,张彬,贾明菲,温开虎. FlexRay总线静态段消息重传调度策略[J]. 计算机工程, 2019, 45(5): 99-104.
[8]	张翌维, 林霖, 赵建, 李发君, 梁立新. 基于LBlock算法的密码SoC安全存储总线设计[J]. 计算机工程, 2019, 45(10): 130-133.
[9]	郑楚红, 彭勇, 徐一鸣, 廖毅. 云制造环境下基于改进NSBBO的任务调度算法[J]. 计算机工程, 2019, 45(10): 26-32.
[10]	杨平平,岳春生,胡泽明. 异构信号处理平台中层次性流水线调度算法[J]. 计算机工程, 2018, 44(11): 83-89.
[11]	高峰,邓霏,陈泉根. 基于分层模型的半实物仿真测试平台设计[J]. 计算机工程, 2018, 44(1): 104-109,115.
[12]	张晶,孙少杰,范洪博. 一种基于开销优化的高稳定性任务调度算法[J]. 计算机工程, 2017, 43(7): 60-63,69.
[13]	张晶,孙少杰,范洪博,付鑫,张果. 高实时性异构多核处理器任务调度算法[J]. 计算机工程, 2017, 43(5): 55-59.
[14]	彭自然,王国军. 一种移动终端最优节能实时任务调度算法[J]. 计算机工程, 2017, 43(5): 67-74.
[15]	李瑞祥,林志涛,马德. 基于总线负载的自适应频率调节系统[J]. 计算机工程, 2017, 43(4): 52-59.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于多核处理器的关联任务并行感知调度算法

Parallel Perceptual Scheduling Algorithm for Related Tasks Based on Multi-Core Processors

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献

相关文章 15

编辑推荐

Metrics

本文评价