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

doi:10.7527/S1000-6893.2021.25209

Abstract

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

CLC Number:

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.

References

[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.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Feng HE, Li ZHANG, Sifan YU, Xuan ZHOU. Schedulability analysis for multi-window partition based on network calculus model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(2): 326581-326581.
[2]	CHEN Zhiyuan, LI Luyi. Efficient methods for reliability sensitivity analysis of inputs with distribution parameter uncertainty [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 325881-325881.
[3]	LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792.
[4]	HE Feng, LI Ershuai, ZHOU Xuan, LI Haoruo, GONG Zijie. Design optimization and evaluation method for time-triggered communication scheduling in airborne networks [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(7): 324258-324258.
[5]	LI Qiao, LI Jia, XIONG Huagang, YANG Jinhe. Accessing capacity of Deficit Round-Robin (DRR) in avionics very-short range THz interconnections [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(6): 624082-624082.
[6]	XING Huaixi, ZHANG Yuhui, CHEN You, ZHOU Yipeng, HE Wenbo. Single station passive localization with phase difference change rate based on MCIS technology [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(3): 324278-324278.
[7]	ZHAO Changxiao, HE Feng, LI Hao, WANG Peng. Dynamic reconfiguration method based on effectiveness for advanced fighter avionics system [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(6): 523416-523416.
[8]	SHI Zhaoyin, LYU Zhenzhou, LI Luyi, WANG Yanping. Cross-entropy importance sampling method based on adaptive Kriging model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(1): 223123-223123.
[9]	LIU Yanfang, LYU Jianghua, MA Shilong, LI Tao. Decoupling method for test process and test devices in parallel testing of avionics systems [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(8): 322818-322818.
[10]	ZUO Yuanjun, LI Qiao, XIONG Huagang, LU Guangshan. Analysis and simulation of avionics MB-OFDM-UWB wireless interconnection channel [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(7): 322739-322739.
[11]	ZHANG Hongming, GU Xiaohui, DI Yi. Reliability analysis method based on Tree Markov Chain model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(5): 222643-222643.
[12]	XU Jian, WU Lei, CHU Jiangping, HE Ke. Performance analysis of information reconfiguration technology on civil aircraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(2): 522442-522442.
[13]	YOU Lingfei, ZHANG Jianguo, ZHOU Shuang, DU Xiaosong. A new method for fatigue reliability calculation of aero-engine limited life parts [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(12): 223228-223228.
[14]	WANG Rongwei, HE Feng, ZHOU Xuan, LU Jun, LI Ershuai. Avionics cloud multi-layer task scheduling model for UAV swarm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(11): 323183-323183.
[15]	YAN Fang, XING Peipei, ZHAO Changxiao, WANG Peng. Reliability modeling and analysis of DIMA system based on joint k/n(G) model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(6): 321971-321971.