基于可调度性排序的时间触发调度表生成方法

doi:10.13700/j.bh.1001-5965.2018.0043

北京航空航天大学学报 ›› 2018, Vol. 44 ›› Issue (11): 2388-2395.doi: 10.13700/j.bh.1001-5965.2018.0043

基于可调度性排序的时间触发调度表生成方法

宋梓旭, 李峭, 汪晶晶, 熊华钢

北京航空航天大学电子信息工程学院, 北京 100083

收稿日期:2018-01-17 修回日期:2018-04-20 出版日期:2018-11-20 发布日期:2018-11-27
通讯作者: 李峭,E-mail:avionics@buaa.edu.cn E-mail:avionics@buaa.edu.cn
作者简介:宋梓旭,男,硕士研究生。主要研究方向:航空电子系统设计、综合模块化航空电子系统、实时通信;李峭,男,博士,讲师,硕士生导师。主要研究方向:航空电子网络、分布式实时系统;汪晶晶,女,硕士研究生。主要研究方向:航空电子系统综合化互连;熊华钢,男,博士,教授,博士生导师。主要研究方向:航空电子综合、高速数据总线。
基金资助:
国家自然科学基金（61301086）；中央高校基本科研业务费专项资金（YWF-14-DZXY-018）

Time-triggered scheduling table generation method based on schedulability ranking

SONG Zixu, LI Qiao, WANG Jingjing, XIONG Huagang

School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China

Received:2018-01-17 Revised:2018-04-20 Online:2018-11-20 Published:2018-11-27
Supported by:
National Natural Science Foundation of China (61301086); the Fundamental Research Funds for the Central Universities of China (YWF-14-DZXY-018)

摘要/Abstract

摘要： 时间触发以太网（TTE）静态调度表的生成依据可满足性模理论（SMT）；如果时间触发（TT）流量集合的规模较大，需要分批选取流量子集进行增量化调度求解，选取的次序对于计算耗时具有显著的影响。采用严格周期利用率因子（SPU）量化各条流量的可调度性，按照调度难度降序分批选取流量组成流量子集，并依次对流量子集进行SMT求解，同时采用可调度性检查和约束缩减措施，提出并形成了一种基于可调度性排序的增量化时间触发调度表生成方法。在求解过程中，如果出现局部不可调度的情况，则进行回溯操作；同时引入干涉时间作为已调度集合对于未调度集合的联合约束条件，大规模缩减了这两种集合之间的约束数量，进一步提高了求解效率。案例研究表明，与随机排序、周期升序和可调度难度升序的增量化调度方法相比，该方法的回溯次数随系统规模增长的速度显著降低。

关键词: 时间触发以太网(TTE), 时间触发(TT)流量, 增量化调度, 可调度性, 流量排序, 约束缩减

Abstract: The time-triggered Ethernet (TTE) static scheduling table is generated based on the satisfiability modulo theories (SMT). If the time-triggered (TT) traffic set is of a large scale, the subsets of traffic need to be selected in batches into the incremental scheduling table generation, where the order of selection has a significant impact on the calculation time consumption. An incremental time-triggered scheduling table generation method based on schedulability ranking is proposed and formed:strict-periodic utilization (SPU) is used to measure the schedulability of TT traffic; TT traffic subsets are selected in batches according to scheduling difficulty descending order, and solved by SMT subset by subset in turn; meanwhile, schedulability check and contention-free constraints reduction are involved. During the solving process, a back-track operation is performed in the case of partly-non-schedulable situation; meanwhile, the interference time is used as the joint constraint condition of the scheduled set on the unscheduled set, and the number of constraints between the two sets is reduced on a large scale, which further improves the solving efficiency. Case study shows that this method's growth rate of the backtracking times with the scale of the problem is lowered down significantly, compared with incremental scheduling method using random order, period ascending order, or scheduling difficulty ascending order.

Key words: time-triggered Ethernet (TTE), time-triggered (TT) traffic, incremental schedule, schedulability, traffic ranking, constraint reduction

中图分类号:

V247
TP393

宋梓旭, 李峭, 汪晶晶, 熊华钢. 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 2388-2395.

SONG Zixu, LI Qiao, WANG Jingjing, XIONG Huagang. Time-triggered scheduling table generation method based on schedulability ranking[J]. JOURNAL OF BEIJING UNIVERSITY OF AERONAUTICS AND A, 2018, 44(11): 2388-2395.

参考文献

[1] STEINER W,BAUER G,HALL B,et al.TTEthernet dataflow concept[C]//Proceedings of 8th IEEE International Symposium on Network Computing and Applications.Piscataway,NJ:IEEE Press,2009:319-322.
[2] SAE AS-2 Committee.Time-triggered Ethernet:SAE AS6802[S].Warrendale,PA:SAE International,2011.
[3] 张英静,熊华钢,刘志丹,等.可用于航空电子系统的时间触发以太网[J].电光与控制,2015,22(5):49-53.ZHANG Y J,XIONG H G,LIU Z D,et al.Application of TTE communication technology in avionics system[J].Electronics Optics & Control,2015,22(5):49-53(in Chinese).
[4] STEINBACH T,LIM H T,KORF F,et al.Tomorrow's in-car interconnect? A competitive evaluation of IEEE 802.1 AVB and Time-Triggered Ethernet (AS6802)[C]//Proceedings of IEEE Conference on Vehicular Technology.Piscataway,NJ:IEEE Press,2012:1-5.
[5] STEINER W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of 31st IEEE Real-Time Systems Symposium (RTSS).Piscataway,NJ:IEEE Press,2010:375-384.
[6] DE MOURA L,BJORNER N.Satisfiability modulo theories:Introduction and applications[J].Communications of the ACM,2011,54(9):69-77.
[7] POZO F,RODRIGUEZNAVAS G,STEINER W,et al.Period-aware segmented synthesis of schedules for multi-hop time-triggered networks[C]//Proceedings of IEEE,International Conference on Embedded and Real-Time Computing Systems and Applications.Piscataway,NJ:IEEE Press,2016:170-175.
[8] 陈进朝,杜承烈.单处理器平台下的严格周期任务可调度性判定[J].计算机工程,2016,42(5):288-291.CHEN J C,DU C L.Schedulability test for strictly periodic tasks on uniprocessor platform[J].Computer Engineering,2016,42(5):288-291(in Chinese).
[9] CHEN J,DU C,XIE F,et al.Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems[J].Real-Time Systems,2016,52(3):239-271.
[10] KORST J,AARTS E H L,LENSTRA J K,et al.Periodic multiprocessor scheduling[C]//Parallel Architectures and Languages Europe(PARLE).Berlin:Springer-Verlag,1991,LNCS505:166-178.
[11] KERMIA O.Timing analysis of TTEthernet traffic[J].Journal of Circuits Systems & Computers,2015,24(9):1550140.
[12] POZO F,STEINER W,RODRIGUEZ-NAVAS G,et al.A decomposition approach for SMT-based schedule synthesis for time-triggered networks[C]//Emerging Technologies & Factory Automation.Piscataway,NJ:IEEE Press,2015:1-8.
[13] 张英静,何锋,卢广山,等.基于TTE的改进加权轮询调度算法[J].北京航空航天大学学报,2017,43(8):1577-1584.ZHANG Y J,HE F,LU G S,et al.A modified weighted round robin scheduling algorithm in TTE[J].Journal of Beijing University of Aeronautics and Astronautics,2017,43(8):1577-1584(in Chinese).
[14] POZO F,RODRIGUEZ-NAVAS G,HANSSON H,et al.SMT-based synthesis of TTEthernet schedules:A performance study[C]//IEEE International Symposium on Industrial Embedded Systems.Piscataway,NJ:IEEE Press,2015:1-4.
[15] SHEIKH A A.Strictly periodic scheduling in IMA-based architectures[J].Real-Time Systems,2012,48(4):359-386.

基于可调度性排序的时间触发调度表生成方法

Time-triggered scheduling table generation method based on schedulability ranking

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	尚利宏, 谭特, 周密. 实时单核和谐周期分区系统时间窗口分配算法[J]. 北京航空航天大学学报, 2018, 44(1): 43-49.
[2]	张英静, 何锋, 卢广山, 熊华钢. 基于TTE的改进加权轮询调度算法[J]. 北京航空航天大学学报, 2017, 43(8): 1577-1584.
[3]	陈瑶, 李峭, 鲁俊, 熊华钢. 改进的多处理器混合关键性系统可调度性分析[J]. 北京航空航天大学学报, 2016, 42(9): 1918-1926.
[4]	周天然, 张勇涛, 何锋, 熊华钢. 基于AFDX的航空电子系统可调度性分析[J]. 北京航空航天大学学报, 2012, 38(1): 75-79.