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

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

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

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.