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

doi:10.7527/S1000-6893.2021.25209

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

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

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

中国航空无线电电子研究所电子部, 上海 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

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

摘要/Abstract

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

中图分类号:

罗泽雄, 曲国远, 严龙, 汤雪乾. 基于重要性抽样的时间触发调度表生成方法[J]. 航空学报, 2022, 43(3): 325209-325209.

LUO Zexiong, QU Guoyuan, YAN Long, TANG Xueqian. A scheduling table generation method for time-triggered flows based on importance sampling[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(3): 325209-325209.

参考文献

[1] 孔韵雯, 李峭, 熊华钢, 等.片间综合化互连时间触发通信调度方法[J].航空学报, 2018, 39(2):321590. KONG Y W, LI Q, XIONG H G, et al.Time-triggered communication scheduling method for off-chip integrated interconnection[J].Acta Aeronautica et Astronautica Sinica, 2018, 39(2):321590(in Chinese).
[2] 谭龙华, 杜承烈, 雷鑫.ARINC653分区实时系统的可调度分析[J].航空学报, 2015, 36(11):3698-3705. TAN L H, DU C L, LEI X.Schedulability analysis for ARINC 653 partitioned real-time systems[J].Acta Aeronautica et Astronautica Sinica, 2015, 36(11):3698-3705(in Chinese).
[3] 何锋, 李二帅, 周璇, 等.机载网络时间触发通信调度设计优化与评价方法[J].航空学报, 2021, 42(7):324258. HE F, LI E S, ZHOU X, et al.Design optimization and evaluation method for time-triggered communication scheduling in airborne networks[J].Acta Aeronautica et Astronautica Sinica, 2021, 42(7):324258(in Chinese).
[4] SAE Aerospace.Time-triggered ethernet:SAE AS6802[S].Warrendale:SAE International, 2011.
[5] NASA.Application specific integrated circuits based on TTEthernet ready for first Orion test flight[EB/OL].[2014-05-20].https://aerospace.honeywell.com/en/press-release-listing/2014/may.
[6] KOPETZ H.The rationale for time-triggered Ethernet[C]//2008 Real-Time Systems Symposium.Piscataway:IEEE Press, 2008:3-11.
[7] STEINER W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//201031st IEEE Real-Time Systems Symposium.Piscataway:IEEE Press, 2010:375-384.
[8] 宋梓旭, 李峭, 汪晶晶, 等.基于可调度性排序的时间触发调度表生成方法[J].北京航空航天大学学报, 2018, 44(11):2388-2395. SONG Z X, LI Q, WANG J J, et al.Time-triggered scheduling table generation method based on schedulability ranking[J].Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(11):2388-2395(in Chinese).
[9] KORST J, AARTS E, LENSTRA J K, et al.Periodic multiprocessor scheduling[M]//Parle'91 Parallel Architectures and Languages Europe.Berlin, Heidelberg:Springer, 1991:166-178.
[10] HE F, LI E S.Deterministic bound for avionics switched networks according to networking features using network calculus[J].Chinese Journal of Aeronautics, 2017, 30(6):1941-1957.
[11] AL SHEIKH A, BRUN O, HLADIK P E, et al.Strictly periodic scheduling in IMA-based architectures[J].Real-Time Systems, 2012, 48(4):359-386.
[12] PIRA C, ARTIGUES C.Line search method for solving a non-preemptive strictly periodic scheduling problem[J].Journal of Scheduling, 2016, 19(3):227-243.
[13] ANIA G, LI Q, YAN R W.An on-line ASAP scheduling method for time-triggered messages[C]//Communications, Signal Processing, and Systems, 2019.Singapore:Springer, 2020:1930-1940.
[14] 汪晶晶, 李峭, 熊华钢, 等.芯片间时间触发通信综合规划方法及其优化[J].北京航空航天大学学报, 2020, 46(1):170-180. WANG J J, LI Q, XIONG H G, et al.Integrated planning method and optimization for off-chip time-triggered communication[J].Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(1):170-180(in Chinese).
[15] COELHO F.Buffer analysis and message scheduling for real-time networks[D].Kaiserslautern:Technische Universität Kaiserslautern, 2017.
[16] Aeronautical Radio, Inc.ARINC.Specification:Application execution:ARINC 653[S].Annapolis:Airlines Electronic Engineering Committee,2011.
[17] CRACIUNAS S S, OLIVER R S.Combined task-and network-level scheduling for distributed time-triggered systems[J].Real-Time Systems, 2016, 52(2):161-200.
[18] ZHOU X, XIONG H G, HE F.Hybrid partition-and network-level scheduling design for distributed integrated modular avionics systems[J].Chinese Journal of Aeronautics, 2020, 33(1):308-323.
[19] 宋梓旭, 李峭, 杨骏峰.基于严格周期与最小抖动准则的混合调度方法[J].电光与控制, 2017, 24(5):68-72, 96. SONG Z X, LI Q, YANG J F.A hybrid scheduling method based on strict periodicity and jitter minimization criteria[J].Electronics Optics & Control, 2017, 24(5):68-72, 96(in Chinese).
[20] 臧光界, 李峭, 王彤, 等.板级互连网关的时间触发消息转发调度方法[J].载人航天, 2021, 27(2):198-206. ZANG G J, LI Q, WANG T, et al.Forwarding and scheduling methods of time-triggered messages in board-spanning gateway[J].Manned Spaceflight, 2021, 27(2):198-206(in Chinese).
[21] 史朝印, 吕震宙, 李璐祎, 等.基于自适应Kriging代理模型的交叉熵重要抽样法[J].航空学报, 2020, 41(1):223123. SHI Z Y, LYU Z Z, LI L Y, et al.Cross-entropy importance sampling method based on adaptive Kriging model[J].Acta Aeronautica et Astronautica Sinica, 2020, 41(1):223123(in Chinese).
[22] 仇佩亮.信息论及其应用[M].杭州:浙江大学出版社, 1999:258-261. QIU P L.Information theory and its applications[M].Hangzhou:Zhejiang University Press, 1999:258-261(in Chinese).
[23] LEWIS J T, RUSSELL R.An introduction to large deviations for tele-traffic engineers[C]//ACM Performance'96.New York:ACM, 1996:1-45.
[24] FEILER P, HANSSON J.Flow latency analysis with the architecture analysis and design language (AADL):CMU/SEI-2007-TN-010[R].Pittsburgh:Carnegie Mellon University, 2007.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	卓越东, 李峭, 卢广山, 武俊杰. 无线航空电子机内通信MIMO信道仿真[J]. 航空学报, 2024, 45(8): 328969-328969.
[2]	赵长啸, 戴骏, 董方正, 李道俊. 机载时间敏感网络链路安全关键度均衡调度方法[J]. 航空学报, 2024, 45(6): 328870-328870.
[3]	何锋, 张立, 于思凡, 周璇. 基于网络演算的多窗口分区可调度性分析[J]. 航空学报, 2023, 44(2): 326581-326581.
[4]	何锋, 李二帅, 周璇, 赵露茜. 机载时间敏感组网分析综述[J]. 航空学报, 2023, 44(17): 28165-028165.
[5]	罗庆, 张涛, 单鹏, 张文涛, 刘子豪. 基于改进Q学习的IMA系统重构蓝图生成方法[J]. 航空学报, 2021, 42(8): 525792-525792.
[6]	何锋, 李二帅, 周璇, 李浩若, 龚子杰. 机载网络时间触发通信调度设计优化与评价方法[J]. 航空学报, 2021, 42(7): 324258-324258.
[7]	李峭, 李佳, 熊华钢, 杨劲赫. 航空电子微距太赫兹互连DRR访问容量分析[J]. 航空学报, 2021, 42(6): 624082-624082.
[8]	邢怀玺, 张宇晖, 陈游, 周一鹏, 何文波. 基于MCIS技术的相位差变化率单站无源定位[J]. 航空学报, 2021, 42(3): 324278-324278.
[9]	左沅君, 李峭, 熊华钢, 卢广山. 航空电子MB-OFDM-UWB无线互连信道分析与仿真[J]. 航空学报, 2019, 40(7): 322739-322739.
[10]	张洪铭, 顾晓辉, 邸忆. 基于树形马氏链模型的可靠性分析方法[J]. 航空学报, 2019, 40(5): 222643-222643.
[11]	朱敏, 许爱强, 李睿峰, 戴金玲. 基于隶属度和LMK-ELM的航空电子部件诊断方法[J]. 航空学报, 2019, 40(12): 323277-323277.
[12]	阎芳, 邢培培, 赵长啸, 王鹏. 基于联合k/n(G)模型的DIMA系统可靠性建模与分析[J]. 航空学报, 2018, 39(6): 321971-321971.
[13]	赵长啸, 何锋, 阎芳, 王鹏, 熊华钢. 面向风险均衡的AFDX虚拟链路路径寻优算法[J]. 航空学报, 2018, 39(1): 321435-321435.
[14]	赵露茜, 李峭, 林晚晴, 熊华钢. 基于随机网络演算的TTE网络时延分析[J]. 航空学报, 2016, 37(6): 1953-1961.
[15]	代真, 何锋, 张宇静, 熊华钢. AFDX虚拟链路路径实时寻优算法[J]. 航空学报, 2015, 36(6): 1924-1932.