留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于可调度性排序的时间触发调度表生成方法

宋梓旭 李峭 汪晶晶 熊华钢

宋梓旭, 李峭, 汪晶晶, 等 . 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 2388-2395. doi: 10.13700/j.bh.1001-5965.2018.0043
引用本文: 宋梓旭, 李峭, 汪晶晶, 等 . 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 2388-2395. doi: 10.13700/j.bh.1001-5965.2018.0043
SONG Zixu, LI Qiao, WANG Jingjing, 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. doi: 10.13700/j.bh.1001-5965.2018.0043(in Chinese)
Citation: SONG Zixu, LI Qiao, WANG Jingjing, 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. doi: 10.13700/j.bh.1001-5965.2018.0043(in Chinese)

基于可调度性排序的时间触发调度表生成方法

doi: 10.13700/j.bh.1001-5965.2018.0043
基金项目: 

国家自然科学基金 61301086

中央高校基本科研业务费专项资金 YWF-14-DZXY-018

详细信息
    作者简介:

    宋梓旭  男, 硕士研究生。主要研究方向:航空电子系统设计、综合模块化航空电子系统、实时通信

    李峭  男, 博士, 讲师, 硕士生导师。主要研究方向:航空电子网络、分布式实时系统

    汪晶晶  女, 硕士研究生。主要研究方向:航空电子系统综合化互连

    熊华钢  男, 博士, 教授, 博士生导师。主要研究方向:航空电子综合、高速数据总线

    通讯作者:

    李峭, E-mail:avionics@buaa.edu.cn

  • 中图分类号: V247;TP393

Time-triggered scheduling table generation method based on schedulability ranking

Funds: 

National Natural Science Foundation of China 61301086

the Fundamental Research Funds for the Central Universities of China YWF-14-DZXY-018

More Information
  • 摘要:

    时间触发以太网(TTE)静态调度表的生成依据可满足性模理论(SMT);如果时间触发(TT)流量集合的规模较大,需要分批选取流量子集进行增量化调度求解,选取的次序对于计算耗时具有显著的影响。采用严格周期利用率因子(SPU)量化各条流量的可调度性,按照调度难度降序分批选取流量组成流量子集,并依次对流量子集进行SMT求解,同时采用可调度性检查和约束缩减措施,提出并形成了一种基于可调度性排序的增量化时间触发调度表生成方法。在求解过程中,如果出现局部不可调度的情况,则进行回溯操作;同时引入干涉时间作为已调度集合对于未调度集合的联合约束条件,大规模缩减了这两种集合之间的约束数量,进一步提高了求解效率。案例研究表明,与随机排序、周期升序和可调度难度升序的增量化调度方法相比,该方法的回溯次数随系统规模增长的速度显著降低。

     

  • 图 1  端系统接入的交换机示意图

    Figure 1.  Schematic diagram of switch accessed by end systems

    图 2  带有30个端系统的雪花型拓扑

    Figure 2.  A snowflake topology with 30 end systems

    图 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.012

    ZHANG 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.050

    CHEN 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.shtml

    ZHANG 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
  • 加载中
图(4) / 表(2)
计量
  • 文章访问数:  739
  • HTML全文浏览量:  177
  • PDF下载量:  243
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-01-17
  • 录用日期:  2018-04-20
  • 网络出版日期:  2018-11-20

目录

    /

    返回文章
    返回
    常见问答