航空学报 > 2022, Vol. 43 Issue (3): 325209-325209   doi: 10.7527/S1000-6893.2021.25209

基于重要性抽样的时间触发调度表生成方法

罗泽雄, 曲国远, 严龙, 汤雪乾   

  1. 中国航空无线电电子研究所 电子部, 上海 200233
  • 收稿日期:2021-01-05 修回日期:2021-02-24 出版日期:2022-03-15 发布日期:2021-04-29
  • 通讯作者: 汤雪乾 E-mail:tang.xueqian@163.com

A scheduling table generation method for time-triggered flows based on importance sampling

LUO Zexiong, QU Guoyuan, YAN Long, TANG Xueqian   

  1. Department of Electronics, Chinese Aeronautical Radio Electronics Research Institute, Shanghai 200233, China
  • Received:2021-01-05 Revised:2021-02-24 Online:2022-03-15 Published:2021-04-29

摘要: 时间触发以太网(TTE)是分布式综合模块化航空电子(DIMA)系统互连中的骨干网络,需要生成无冲突的时间触发(TT)流量调度表。形式化SMT求解可以抽象地表述多种调度约束;但TT流量间,以及TT流量与分区调度之间存在作业链依赖关系,较复杂的约束会降低求解器的效率。将重要性抽样(IS)方法应用于TT调度表的启发式求解,通过统计“尽可能快”(ASAP)求解的尝试偏移量的经验分布,扭转该变量的抽样分布进行迭代寻优;并针对调度的可行性及作业链的及时性,将IS求解分为2个阶段进行。案例研究表明:第1阶段的IS会演化得出易于保证严格周期调度或抖动较小的尝试偏移量分布,第2阶段IS则会进一步根据作业链的最坏总延迟最小准则进行迭代优化,并且对于分区调度与TT流量调度存在或不存在同步关系的场景都具有适用性。

关键词: 航空电子, 时间触发调度表, 时间触发以太网, 重要性抽样, 作业依赖

Abstract: Time-triggered Ethernet (TTE) is the backbone interconnections in the distributed integrated modular avionics systems, with a congestion-free time-triggered (TT) scheduling table being needed to be generated.Although the formal method using SMT can describe multi-typed scheduling constraints abstractly, more complicated constraints could reduce the efficiency of scheduling generation due to the existence of job chain dependencies among TT flows and between TT flow and partition scheduling.Importance sampling (IS) is used for a kind of heuristic TT scheduling generation, in which the possibility density distribution (PDF) of start trying offsets is twisted by experimental PDFs according to statistical values of the start-trying offsets using the "As Soon As Possible" (ASAP) method.IS-based scheduling table generation is divided into two stages to obtain more feasible scheduling and more timely job chains, respectively.The case study shows that in the first stage, a set of distribution for start-trying offsets is gained to make TT flows easy to be strictly periodically scheduled; in the second stage, optimal offsets are conducted to make shorter job chains delays according to the "best of the worst" criterion, and IS is applicable for the scenarios with or without synchronization between time-triggered network and partition-scheduled processing modules.

Key words: avionics, time-triggered scheduling table, time-triggered Ethernet, importance sampling, job dependency

中图分类号: