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

• 论文 • 上一篇    下一篇

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

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

  1. 北京航空航天大学 电子信息工程学院, 北京 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   

  1. 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)

摘要: 时间触发以太网(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

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发