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

2022-04-26罗泽雄曲国远严龙汤雪乾

航空学报 2022年3期

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

中国航空无线电电子研究所电子部，上海 200233

航空电子系统经历了分立式、联合式、综合式和先进综合式的发展阶段，目前正在发展分布式综合模块化航空电子(Distributed Integrated Modular Avionics，DIMA)体系架构，并使分时分区处理与时间触发通信综合化互连技术相结合。

SAE AS6802标准定义的时间触发以太网(Time-Triggered Ethernet，TTE)是可以容纳时间触发(Time Trigered,TT)、速率约束(Rate Constraint，RC)事件触发和“尽力传”(Best Effort，BE)流量的混合关键性综合化互连技术，其中TT流量具有严格的时间确定性，适用于安全和任务关键性的航空电子信息传输，并已经用于美国航空航天局(NASA)载人飞船。在基于协议控制帧(Protocol Control Frame，PCF)的分布式时钟同步机制的支持下，根据离线生成的调度表进行TT流量调度，并在预留保护间隔的条件下允许RC和BE流量在“孔隙”(Porosity)中传输。

将周期性的TT流量作为虚拟链路(Virtual Link，VL)，并将实时调度和网络拓扑的约束转化为可满足性模理论(Satisfiability Modulo Theories，SMT)问题，利用形式化求解器求解。可以采用根据可调度的难度由难到易排序的方法，增量化SMT求解提高求解效率。时间触发调度表也可以借鉴IMA系统中严格周期调度，文献[11]采用混合整数线性规划(MILP)方法和博弈理论进行建模和求解，文献[12]则对MILP模型进行了线搜索解释。

形式化描述不便于描述作业链等较为复杂的应用要求，可以采用启发式算法。文献[13-15]则分别采用了“尽可能快”(As Soon As Possible，ASAP)、免疫算法和树搜索算法求解TT调度表；其中，文献[15]给出了根据交换转发的延迟将路径上各物理链路的待调度时隙左移并回卷，随后将它们已占用的时隙以“或”逻辑相掩(Masked)，求得空闲时隙的方法。

文献[16]创造性地给出了处理任务与通信任务的联合调度，但处理任务的粒度较细，与分时分区的航空电子ARINC 653操作系统的应用场景有所不同。文献[18]则将分区作为整体考虑，实现了求解增量化和生命周期的大增量化，并在SMT+MILP的基础上引入了MAX-SAT问题，以不满足的可能性最小为优化条件。

文献[15]为每条VL构造相掩的时隙轴，采用ASAP调度表生成算法；借鉴文献[18]的思想，对于无法严格周期调度的VL可以放宽到最小抖动时隙分配，并且采用重要性抽样(Importance Sampling，IS)方法进行优化。

早在20世纪40年代的曼哈顿工程中，IS方法就被发明用于大幅度加快稀有事件仿真的速度；随后被广泛应用于失效概率评估等工程领域，但它也是一种通过扭曲样本概率分布进行启发式寻优的方法，可根据应用设置各种优化准则，包含考虑作业之间复杂的时序依赖关系(类似于文献[21])。

本文所述研究工作的创新性思路为：① 对于TT VL的可调度性和某些VL作业链延迟的2种不同的优化准则，提出两阶段的基于IS的TT调度表生成方法，克服了SMT求解器只能得到可行解且求解过程为“黑盒”的不足；② 给出面向应用的TT VL作业链的描述方法和串联、汇合关系下延迟的累加方法，既考虑TT通信任务实例(即：作业)之间的时序依赖关系，又能通过最坏情况下最好准则评价任务组的性能，并可以灵活适用于网络与处理分区同步或不同步的情况。

1 时间触发流量模型

设TT通信任务的集合{,∈}为周期性的，周期为{Ф}；设每个TT通信任务的数据包长度是给定的，且以时间为单位，记为{}。时间触发调度表的集成循环(Integrated Cycle，IC)为{Ф}中的最小值，而集群循环(Cluster Cycle，CC)为各个周期的最小公倍数。

考虑到TT流量和RC流量共用物理链路，为了能够使处理TT流量的嵌入式程序及时阻断RC流量，设置保护间隔(Guard Margin)。

为了进一步实现多孔调度，TT网络规划中一般限定“孔”的最小值。一般要求“孔”中至少能够容纳一个最长帧。对于物理码速率为1 Gbit/s 或100 Mbit/s的TTE网络，传输一帧长度为1 518字节的以太网最长帧耗时分别约为12 μs 或120 μs，物理链路速率为1 Gbit/100 Mbit/s条件下,TTTech公司的TT-Plan软件默认的TT窗口之间最小间隔值分别为20、200 μs。

调度的时候不妨令TT通信实例长度=++，即TT调度表考虑各条TT VL的实例分别以占用时间轴，这样调度的效果就同时考虑了保护间隔和多孔调度要求。

TT通信调度表将时间轴分解为时隙，时隙长度等于常量，则周期Ф、TT通信实例长度(对变长时间段除以并上取整，占据1个或多个时隙)、IC循环和CC循环的长度和都可以用时隙为单位整数表示。

与文献[7]类似，要求为所有的物理链路生成TT调度表，且调度表的长度等于CC中时隙的数目。注意到TTE网络是采用交换机互连，对于每条VL，交换机的技术时延以及与数据包长度有关的存储转发延迟。在图1的例子中，设从ES发出的某条VL经过交换机Sw和Sw，先验已知分别延迟与。如果还没有对这条VL分配时隙，要决定可以分配给该VL(设为VL)的实例的空闲时隙，可以ES接入物理链路的调度表为基准，将第2级和第3级物理链路的调度表分别左移,和sum,=,+,，并将早于基准0点的部分回卷之后接到后面；随后将各物理链路现有的调度表中已经占用的部分逻辑“或”相掩之后，形成“合成时隙”，其时间轴上的空闲时隙才是可以无冲突占用的。

值得说明的是，在TTE网络中，每个IC均有PCF同步过程，同步过程时间段是不能被TT占用的开销。

如果采用ASAP方法进行严格周期调度，则对于未调度的VL，在现有的“合成时隙”下指定一个尝试偏移量起点,0，如果实例时间段的集合{[,,,+-1]}都处于空闲区间，则找到了一个可行解，其中,=,0+×Ф，= 0,1,…,-1,=Ф；如果实例时间段与已占据的时隙冲突，则尝试偏移量右移一个时隙，重复此操作。ASAP方法取最早找到的一个可行偏移量作为VL的起始相位,0。经过ASSP方法找到可行偏移量的VL的调度信息为{Ф,, ,0}。

图1 时隙的左移、回卷和相掩Fig.1 Shift, wrap and masking of slots

如果遍历所有的起点都找不到严格调度的可行解，可以从某个尝试点出发选定第一个实例可行的尝试偏移量,0，其他实例依次遍历空闲的时隙，并利用类似于文献[19]的方法评价该方案与严格周期方案相比的抖动。可以枚举尝试偏移量,0的取值，选择所有方案中抖动量最小的。但调度信息需要记录所有实例的相位，得到的调度信息为{Ф,,{,0,,1, …,,-1}}。

与SMT调度方法一样，本文所述的方法也是依次进行时隙尝试和分配的，显然先尝试的VL获得严格周期调度的机会大。根据文献[8]采用严格周期利用率(Strict-Periodic Utilization, SPU)对各TT VL的可调度性进行排序，先调度难调度的流量，可以提高系统整体的可调度性。

2 两阶段重要性抽样

2.1 重要性抽样过程

重要性抽样是一种面向实验或仿真的迭代优化方法。其思路为，将待确定的参数作为随机变量，设定其离散的概率密度函数；每次从各个随机变量的样本空间抽样，并记录样本值；利用优化准则对实验或仿真结果进行评价。运行多次仿真，将评价结果排序，设定一个比例作为阈值，有0<<1。选出较优的样本，使被选出的样本数目与样本总数的比例为，对所选出的样本值进行统计，形成经验分布概率密度函数,sa；并设定一个更新因子，0 <<1，令

+1=(1-)+,sa

(1)

随后利用更新的概率密度函数+1改变样本空间的总体，重新进行抽样，迭代上述过程，直至找到满足指标要求的参数设置，或者使评价结果的统计量在误差范围内不再变化。

具体到TT调度表生成问题，需要解决TT调度表的可调度性问题，以及给定作业链的延迟时间较短的优化目标。

这2个优化目标属于不同性质的问题，所以它们的评价指标很难结合表达，所以采用两阶段重要性抽样。

第1阶段以可调度性(即：作业尽可能按照严格周期进行调度，不能遵循严格周期调度，则要求每个作业发生时间偏离周期的间隔抖动较小)为优化准则，迭代一定轮次，尝试各VL偏移量,0的取值使得整个TT调度的可调度性较好，减少ASAP盲目尝试的次数。

在第2阶段，保留第1阶段扭曲的各VL尝试偏移量,0的分布，描述并评价作业链起始到结束的延迟，并适当结合可调度性(如：不可调度的罚函数)进行重要性抽样，启发式得出近优的TT调度表，同时保证可调度性和作业链及时性。

2个阶段所采用的IS算法过程类似，所不同的只是评价方法和停止条件，如图2所示。

图2 时间触发调度表生成的重要性抽样Fig.2 Important sampling for TT scheduling generation

2.2 第1阶段：优化可调度性

在第次迭代的第轮尝试中，对于第条TT VL，第1阶段的评价方法主要考虑3方面的因素，计算代价的数值,,，如表1所示，有,,=1,,,+2,,,。求和得到本轮次总代价,。

在表1中，为指示函数，在脚标中逻辑函数成立的情况下为1，否则为0；例如：表1中,0<,0表示在,0<,0成立的条件下取值为1，否则为0。对于非严格周期调度的情况，在代价2中加上整个CC的时隙数作为惩罚；而完全不可调度，则选取一个很大的罚值，经验上可以取的10倍。

在进行重要性抽样之前，已经对每条物理链路进行了利用率检查，保证TT流量加上保护间隔导致的利用率小于1。但在这种情况以及允许有抖动的条件下，仍可能出现TT VL不可调度的情况，原因在于被占用的时隙之间连续存在的空闲时隙过短，无法容纳未调度的数据包。

在计算经验分布函数的过程中，将记录3种指标：第次迭代中代价{,}(=1,2,…,)的最小值,min、经过排序后最小的·尝试的部分和,TH，以及本次迭代所用的时间。这3个指标的减小都能说明可调度性得到了改善，其中减小的意义在于，进行最小抖动的非严格周期调度所需时间远大于严格周期可调度情况下的ASAP，越短说明本次迭代整体上有更多的TT VL满足严格周期可调度条件，所选的尝试偏移量越合理。

除了达到迭代的轮次退出最外层循环之外，还通过上述3个参数,min、,TH、判定停止条件，由于随机因素的影响，某个参数可能在不同的

表1 第1阶段的评价方法Table 1 Evaluation methods in the first stage

迭代轮次有所起伏，所以规定只有这3个参数全都不再减小的时候，才退出循环。

2.3 第2阶段：优化作业链延迟时间

第2阶段的重要性抽样是在第1阶段得到的可调度性增强的样本空间概率密度分布的基础上进行的。

由于第2阶段主要关注作业链的延迟时间，因此代价,等于系统中各条作业链的延迟之和，其计算方法在第4节说明。除此之外，仅考虑不可调度时，设定极大的罚值，令,=。

除了指定迭代的次数，第2阶段的迭代终止条件是找到每次迭代所有轮次的最小值,，代表的是所有轮次中作业链最坏延迟之和的最好情况，符合“最坏最好”的实时系统寻优的原则。同时还要记录这些最小值对应的TT调度表参数。

设置迭代次数的经验上限值，如果迭代次数达到经验上限值时，,min的当前值没有比已记录的历史值更小，即可以提前退出最外层循环。

此时，取所有迭代中最小值，并根据记录的参数得到严格周期可调度性和作业链及时性双重最优的TT调度表。

在实际工作中，也可以适当减少第1阶段的迭代次数，在保证样本空间概率密度分布具有一定的可调度性优化的同时，对于尝试偏移量保持足够的随机性，避免过早陷于局部最优。

2.4 抽样实验的渐近等概特性

根据信息论的类型理论，随机事件发生的概率由样本总体中的典型事件决定，具有渐近等概(Asympotic Equipartition Property，AEP)特性，非典型事件的发生概率是稀有的。利用ASAP得到可调度结果和作业链延迟优化的可调度结果的事件是稀有的，设分别对应集合Г和Г，如图3所示。

图3 样本总体和集合的示意图Fig.3 Diagram for total samples and sample sets

(2)

(3)

尽管两阶段抽样很难降低迭代的次数，但它的优势在于：

1) 迭代中构造经验分布函数(图2中标注 ① 到标注 ②)的每次尝试为常规抽样，特别是刚开始迭代时参数近乎均匀分布，均可得到加速。

2) 第2阶段评价指标计算的开销较大，分成两阶段进行层次化评价，可减小这部分开销。

3) 工程设计中往往也被分为2个阶段，第1阶段得到可调度性强的参数分布，便于第2阶段集中精力针对不同条件进行分区和通信联合调度的性能比较。

3 作业链的时序关系和延迟计算

航空电子处理任务的实例对应嵌入式终端或分区的一次运行，通信任务的实例是一次数据帧的端到端传输，将它们统称为作业(Job)。

类似于在航空电子体系架构描述中对于流时延的时序依赖关系累加，应用要求一些作业之间保证时序依赖关系。最常见的应用场景是嵌入式系统周期性采样物理量，通过数据集中到综合化处理模块进行处理，处理模块在给定的分区窗口开始的时候从ARINC 653操作系统规定的“伪分区”读取采样数据，处理后在分区窗口结束前由ES发送，或是进行分区间通信传递给其他模块。这种场景下的依赖关系可分解为串联、汇合和分叉，可以用运筹学的任务图表示(这种任务图中的任务是指作业，如图4所示)。对于任务图中的关键路径所对应的作业链，计算从所有作业的起始时刻到完成时刻的最坏情况下的累积值。

既有的时序依赖关系的分析(例如：Job-Shop问题)仅针对作业；但考虑到系统中大多数任务是周期性的，受文献[20]的启发，可以兼顾任务，即选取任务图中关键路径所对应的作业链作为“主干”，选取它的起始任务在一个周期内的作业为定时的起点，分别计算它周期内每个作业所对应的链上到终点最坏时间延迟，并将延迟的最大值作为评价指标。如果主干链上的中间作业依赖于某些前续作业的串联或汇合，则可以使该作业为终点，计算该分支最坏延迟下作业的偏移量。

图4 作业之间依赖关系的类型Fig.4 Types of job dependencies

TT调度表保证了交换式网络中作业之间是无冲突的，因此对于具有依赖关系的作业，不需要考虑它们相遇的交换机输出链路的时隙分配关系，只需要直接考虑目的ES接入物理链路上的时隙占用情况。

例如在图5中，生成的TT调度表给定了嵌入式系统Emb的任务的作业在源端Src(ES)的接入物理链路上的偏移量src,,，以及源端ES到目的端Dest(ES)交换路径上的延迟偏移量之和sum,(交换网络偏移量即图1中的左移值，当路径确定后为先验已知)。则目的端接入物理链路的时隙位置为

dest,,=src,,+sum,

(4)

同理,可计算嵌入式系统Emb的任务的作业在目的端接入物理链路的时隙位置dest,,。则当Emb与Emb产生的数据包在目的端交汇(图4(b))时，需要等待时间为

dest_delay,,=dest,,-dest,,

(5)

考虑到时间的不可逆性，如果物理量需要因果性，即要求引发作业的物理事件的先后关系在目的ES也必须得到保持，则必须研究目的接入链路与源接入链路上各作业的时隙之间的对应关系。将这种因果性的先后关系称为串联,如图4(a) 所示。

图6用时序图给出了串联关系分析的例子，由于传输延迟，嵌入式系统Emb的通信任务的实例落后通信任务的实例超过一个周期，在必须考虑因果性的处理节点4，不能利用离它最近的的数据。因此串联关系需要将目的端接入物理链路的时隙反向回溯，检查它们源端时的时序先后关系，进而确定在目的端接入物理链路上属于不同任务的作业之间的时隙先后关系。

对于图4(c)所示的分支关系，则可以分解为2个串联依赖关系，分别计算两路作业之间的延迟。

作业链同样适用于表达TT数据包与分区处理之间的时序关系。类似于文献[17]，分时分区调度可以被抽象为TT自链路(Self Link)，当处理任务与通信任务不存在同步时，以分区调度的周期作为最坏延迟，当它们之间存在同步时，可以根据分区调度窗口与TT调度表的偏移量，进行一次“汇合”依赖关系的延迟计算。

图5 源端和目的端接入物理链路的时隙分配Fig.5 Time slot allocations of access of source and destination end-system to physical links

图6 串联作业的时序图Fig.6 Sequence diagram of series jobs

4 案例分析

4.1 拓扑结构与流量配置

给定如图7所示的TTE网络拓扑结构配置，对于所提出的两阶段基于IS的调度表生成方法进行案例分析。该案例设置有4个交换节点，交换节点之间采用全双工互连，每个交换节点各接入4个ES。所有的物理链路均为全双工。图7在ES和交换机的图标中标明了各个节点的标号，在节点之间的有向连线上标出了物理链路的编号，要求为每条物理链路生成TT VL的调度表。设物理链路码速率为100 Mbit/s，IC=1 ms，时隙=8 μs，保护间隔为2个时隙，“孔”的最小值为200 μs(25个时隙)。该案例的VL配置如表2所示。

图7 时间触发网络案例的拓扑结构Fig.7 Topology of a time-triggered network

表2 案例中的VL配置Table 2 Configuration of VLs in case

4.2 作业链的设定

为了体现航空电子系统综合化处理和分区间通信的特点，设定一条包含6条VL的作业链，其时序依赖关系如图8所示。

图8 作业链依赖关系示例Fig.8 Example of dependencies within a job chain

如图8，设定VL、VL、VL承载的信息具有物理上因果性要求，因此可以表达为VL串联VL、VL串联VL；随后它们都通过物理链路12进入ES，并在综合化分区中处理；设定应用还需要从VL到综合化分区处理之后的结果，它和综合化分区的结果是汇合关系。设处理后会形成VL的数据载荷，这需要处理分区到ES网络接口伪分区，具有一个常量的分区间通信延迟，随后以VL的周期串联VL发送到ES。

如果案例场景的设定受到2种因素的影响，记为、，前者为分区处理是否与网络同步的设定，后者为分时分区调度窗口，则仿真场景可以用(,)表示，和的设定情况分别见表3和表4。其中，表3中的分区相位为分区的释放时刻在整个分区调度周期内的位置；表4中设定了典型的分区周期值，实际应用中分区调度的时间粒度随着处理机能力的不同而有差异，每个分区的时间窗口可以是十几微秒到几百微秒，所以分区调度周期一般可以为几百微秒到几毫秒。

表3 分区与时间触发网络同步关系的场景设定

表4 分区调度周期的场景设定

4.3 重要性抽样与调度表生成的优化

设定第1阶段的较优样本比例阈值为=0.5，更新因子为=0.2。

观测第次迭代中代价的最小值,min、经过排序后代价最小部分的代价之和,TH，以及第次迭代所用的时间。由于前两者的取值范围不同，不便在一张图形下绘制；且在不同的计算机上程序执行的具体数值相差较大；所以将这3种参数的所有数据各自除以其第1次迭代时得到的值进行归一化。图9给出了图7、表2所设定算例第1阶段迭代32次的结果。

如图9所示，可见在利用IS仿真计算进行尝试偏移量分布的启发式优化过程中，3种评价参数指标均呈现下降的趋势，但由于仿真的随机抽样特性，过程中存在着局部的起伏。

由于第1阶段相当于“粗筛”出易于调度的ASAP和最小抖动时隙分配的尝试起始点，而第2阶段则要精细地考察任务链的延迟，因此IS过程中经验上取较小的较优样本比例阈值，即令=0.1；更新因子仍取=0.2。

在实际应用中，为了保证第2阶段的优化仍具有抽样的随机性，可以采用使第1阶段迭代次数减半的方法，在优化效果和样本的随机性之间取得权衡。

图9 案例第1阶段IS优化的评价指标Fig.9 Evaluation metrics for the first stage IS optimization in case

可以选取第2阶段中代价最小的TT时隙分配方案作为最终的TT调度表。也可以保持第1阶段结束后经过了优化的尝试偏移量分布，再进行若干次仿真实验，选择代价最小的某次TT时隙分配方案作为最终的TT调度表。

在案例研究中，根据表3和表4的设定分别进行了基于IS的仿真实验和分析计算(,)，求得图8定义任务链起始到终止的延迟，并选择在最坏情况下延迟最小的结果作为TT调度表的输出。

不同(,)仿真场景所对应的作业链延迟最小值如图10所示。可见，当分时分区与时间触发网络同步时，可以降低作业链的延迟，特别是对于分区调度周期较长的应用效果更明显。然而，实际应用中分区与网络TT消息的同步的驱动程序改造和协议开销也不能忽略，需要服从于整体系统和网络的规划，可以仅选定部分关键的处理模块和TT VL进行精确时钟同步，其他流量仍保持事件触发的解决方案。

图10 案例第2阶段基于IS求得的任务链延迟Fig.10 Job chain delay values from the second stage IS optimization in case

4.4 调度表生成方法下作业链的延迟性能

针对图7、表2设定的案例，分别采用SMT求解器、基本的树搜索算法生成时间触发调度表。前者又分为两种方法，不进行可调度性排序的SMT方法每次求得可行解，得到10种不同的可行TT调度表；基于SPU排序的增量化SMT方法进行可调度性排序预处理，限定的求解次序降低了可行调度的多样性，用这样方法得到3种不同的可行TT调度表。树搜索算法的效果则受到VL求解次序的很大影响。

参照表3、表4，在不同的分区和网络同步场景下分别采用不排序SMT方法、可调度排序增量化SMT方法、树搜索方法计算图8所示作业链的延迟，与本文提出的两阶段IS方法计算结果进行对比，如图11所示。其中:IS为本文两阶段IS方法；增量SMT为可调度排序增量化SMT方法；SMT最大为采用不排序SMT方法后得到的最大值；SMT最小为采用不排序SMT方法后得到的最小值；SMT平均为采用不排序SMT方法后得到的平均值。不排序的SMT方法分别取最大、最小和平均值；由于样本少，只取排序的增量化SMT方法得到的最小延迟；对于树搜索算法，使与作业链有关的VL依次优先输入，得出1种可行调度表及其相应的延迟。

图11 不同TT调度表生成方法下作业链延迟Fig.11 Job chain delay values via different TT time table scheduling methods

由于第2阶段的重要性抽样依据作业链延迟最小的原则评价样本的重要程度加以筛选，作业链的延迟性能明显优于其他方法。相反，基于SPU的增量化SMT方法虽然具有可调度性保证和快速性的优势，但目前还无法将作业链延迟优化融入预处理排序过程。如图11(c)，不排序的SMT方法求解的可行范围略小于(因为IS方法允许无法严格周期调度的VL采用最小时延抖动调度)；但由于不论是可调度性排序还是树搜索排序，只要它们没有融入作业链优化的内容，在一般性条件下，其可行范围和与第二阶段优化求解的样本集合均有偏离。

借鉴文献[17]，使用基本SMT求解器可以通过添加约束实现分区处理和通信的联合优化，但该SMT求解器是“黑盒”，很难掌控求解过程，且求解速度较慢。表5列出了不排序SMT方法、可调度排序增量化SMT方法、树搜索方法与本文所提方法相比的优缺点。