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

Time-triggered scheduling table generation method based on schedulability ranking

作　　者：宋梓旭 李峭[1] 汪晶晶 熊华钢[1] SONG Zixu;LI Qiao;WANG Jingjing;XIONG Huagang(School of Electronic and Information Engineering,Beijing University of Aeronautics and Astronautics,Beijing 100083,China)

机构地区：[1]北京航空航天大学电子信息工程学院,北京100083

出　　处：《北京航空航天大学学报》2018年第11期2388-2395,共8页Journal of Beijing University of Aeronautics and Astronautics

基　　金：国家自然科学基金(61301086);中央高校基本科研业务费专项资金(YWF-14-DZXY-018)~~

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

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

分 类 号：V247[航空宇航科学与技术—飞行器设计] TP393[自动化与计算机技术—计算机应用技术]