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.
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
.
DOI: 10.7527/S1000-6893.2021.25209
[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.
CJA