-
摘要:
时间触发以太网（TTE）静态调度表的生成依据可满足性模理论（SMT）；如果时间触发（TT）流量集合的规模较大，需要分批选取流量子集进行增量化调度求解，选取的次序对于计算耗时具有显著的影响。采用严格周期利用率因子（SPU）量化各条流量的可调度性，按照调度难度降序分批选取流量组成流量子集，并依次对流量子集进行SMT求解，同时采用可调度性检查和约束缩减措施，提出并形成了一种基于可调度性排序的增量化时间触发调度表生成方法。在求解过程中，如果出现局部不可调度的情况，则进行回溯操作；同时引入干涉时间作为已调度集合对于未调度集合的联合约束条件，大规模缩减了这两种集合之间的约束数量，进一步提高了求解效率。案例研究表明，与随机排序、周期升序和可调度难度升序的增量化调度方法相比，该方法的回溯次数随系统规模增长的速度显著降低。
-
关键词:
- 时间触发以太网(TTE) /
- 时间触发(TT)流量 /
- 增量化调度 /
- 可调度性 /
- 流量排序 /
- 约束缩减
Abstract:The time-triggered Ethernet (TTE) static scheduling table is generated based on the satisfiability modulo theories (SMT). If the time-triggered (TT) traffic set is of a large scale, the subsets of traffic need to be selected in batches into the incremental scheduling table generation, where the order of selection has a significant impact on the calculation time consumption. An incremental time-triggered scheduling table generation method based on schedulability ranking is proposed and formed:strict-periodic utilization (SPU) is used to measure the schedulability of TT traffic; TT traffic subsets are selected in batches according to scheduling difficulty descending order, and solved by SMT subset by subset in turn; meanwhile, schedulability check and contention-free constraints reduction are involved. During the solving process, a back-track operation is performed in the case of partly-non-schedulable situation; meanwhile, the interference time is used as the joint constraint condition of the scheduled set on the unscheduled set, and the number of constraints between the two sets is reduced on a large scale, which further improves the solving efficiency. Case study shows that this method's growth rate of the backtracking times with the scale of the problem is lowered down significantly, compared with incremental scheduling method using random order, period ascending order, or scheduling difficulty ascending order.
-
图 3 无冲突约束规模缩减前后运行时间对比
Figure 3. Comparison of running time before and after contention-free constraints reduction
图 4 不同流量排序方法下的增量化求解回溯次数
Figure 4. Backtracking times of incremental scheduling method under different traffic ranking methods
表 1 4种TT流量类型的数量分布
Table 1. Quantity distribution of four kinds of TT traffic
每个端系统发送TT数 各类型TT流量数量 2 (0，0，1，1) 4 (0，0，2，2) 6 (0，0，3，3) 8 (1，1，3，3) 10 (1，1，4，4) 12 (1，1，5，5) 14 (2，2，5, 5) 16 (2，2，6，6) 18 (2，2，7，7) 
下载: 导出CSV
表 2 不同流量排序方法下的运行时间
Table 2. Running time under different traffic ranking methods
s 排序方法 每个端系统发送TT数 6 8 10 12 14 16 SPU升序 3 17 259 7 530 — — — 随机排序 27 1 951 914 — — — 周期升序 9 22 38 256 2 716 3 609 SPU降序 10 21 41 44 78 662
下载: 导出CSV
-
[1] STEINER W, BAUER G, HALL B, et al.TTEthernet dataflow concept[C]//Proceedings of 8th IEEE International Symposium on Network Computing and Applications.Piscataway, NJ: IEEE Press, 2009: 319-322. [2] SAE AS-2 Committee.Time-triggered Ethernet: SAE AS6802[S].Warrendale, PA: SAE International, 2011. [3] 张英静, 熊华钢, 刘志丹, 等.可用于航空电子系统的时间触发以太网[J].电光与控制, 2015, 22(5):49-53. doi: 10.3969/j.issn.1671-637X.2015.05.012ZHANG Y J, XIONG H G, LIU Z D, et al.Application of TTE communication technology in avionics system[J].Electronics Optics & Control, 2015, 22(5):49-53(in Chinese). doi: 10.3969/j.issn.1671-637X.2015.05.012 [4] STEINBACH T, LIM H T, KORF F, et al.Tomorrow's in-car interconnect A competitive evaluation of IEEE 802.1 AVB and Time-Triggered Ethernet (AS6802)[C]//Proceedings of IEEE Conference on Vehicular Technology.Piscataway, NJ: IEEE Press, 2012: 1-5. [5] STEINER W.An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of 31st IEEE Real-Time Systems Symposium (RTSS).Piscataway, NJ: IEEE Press, 2010: 375-384. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks [6] DE MOURA L, BJORNER N.Satisfiability modulo theories:Introduction and applications[J].Communications of the ACM, 2011, 54(9):69-77. doi: 10.1145/1995376 [7] POZO F, RODRIGUEZNAVAS G, STEINER W, et al.Period-aware segmented synthesis of schedules for multi-hop time-triggered networks[C]//Proceedings of IEEE, International Conference on Embedded and Real-Time Computing Systems and Applications.Piscataway, NJ: IEEE Press, 2016: 170-175. http://ieeexplore.ieee.org/document/7579952/ [8] 陈进朝, 杜承烈.单处理器平台下的严格周期任务可调度性判定[J].计算机工程, 2016, 42(5):288-291. doi: 10.3969/j.issn.1000-3428.2016.05.050CHEN J C, DU C L.Schedulability test for strictly periodic tasks on uniprocessor platform[J].Computer Engineering, 2016, 42(5):288-291(in Chinese). doi: 10.3969/j.issn.1000-3428.2016.05.050 [9] CHEN J, DU C, XIE F, et al.Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems[J].Real-Time Systems, 2016, 52(3):239-271. doi: 10.1007/s11241-015-9226-z [10] KORST J, AARTS E H L, LENSTRA J K, et al.Periodic multiprocessor scheduling[C]//Parallel Architectures and Languages Europe(PARLE).Berlin: Springer-Verlag, 1991, LNCS505: 166-178. [11] KERMIA O.Timing analysis of TTEthernet traffic[J].Journal of Circuits Systems & Computers, 2015, 24(9):1550140. doi: 10.1142/S0218126615501406 [12] POZO F, STEINER W, RODRIGUEZ-NAVAS G, et al.A decomposition approach for SMT-based schedule synthesis for time-triggered networks[C]//Emerging Technologies & Factory Automation.Piscataway, NJ: IEEE Press, 2015: 1-8. https://www.researchgate.net/publication/308853509_A_decomposition_approach_for_SMT-based_schedule_synthesis_for_time-triggered_networks [13] 张英静, 何锋, 卢广山, 等.基于TTE的改进加权轮询调度算法[J].北京航空航天大学学报, 2017, 43(8):1577-1584. http://bhxb.buaa.edu.cn/CN/abstract/abstract14152.shtmlZHANG Y J, HE F, LU G S, et al.A modified weighted round robin scheduling algorithm in TTE[J].Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(8):1577-1584(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract14152.shtml [14] POZO F, RODRIGUEZ-NAVAS G, HANSSON H, et al.SMT-based synthesis of TTEthernet schedules: A performance study[C]//IEEE International Symposium on Industrial Embedded Systems.Piscataway, NJ: IEEE Press, 2015: 1-4. https://www.researchgate.net/publication/314921079_SMT-based_synthesis_of_TTEthernet_schedules_A_performance_study [15] SHEIKH A A.Strictly periodic scheduling in IMA-based architectures[J].Real-Time Systems, 2012, 48(4):359-386. doi: 10.1007/s11241-012-9148-y -
下载:
点击查看大图
计量
- 文章访问数: 877
- HTML全文浏览量: 224
- PDF下载量: 246
- 被引次数: 0
