留言板

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

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

基于DDQN的片上网络混合关键性消息调度方法

李国梁 李峭 徐亚军 熊华钢

李国梁, 李峭, 徐亚军, 等 . 基于DDQN的片上网络混合关键性消息调度方法[J]. 北京航空航天大学学报, 2022, 48(7): 1233-1241. doi: 10.13700/j.bh.1001-5965.2021.0006
引用本文: 李国梁, 李峭, 徐亚军, 等 . 基于DDQN的片上网络混合关键性消息调度方法[J]. 北京航空航天大学学报, 2022, 48(7): 1233-1241. doi: 10.13700/j.bh.1001-5965.2021.0006
LI Guoliang, LI Qiao, XU Yajun, et al. A DDQN-based mixed-criticality messages scheduling method for network-on-chip[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(7): 1233-1241. doi: 10.13700/j.bh.1001-5965.2021.0006(in Chinese)
Citation: LI Guoliang, LI Qiao, XU Yajun, et al. A DDQN-based mixed-criticality messages scheduling method for network-on-chip[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(7): 1233-1241. doi: 10.13700/j.bh.1001-5965.2021.0006(in Chinese)

基于DDQN的片上网络混合关键性消息调度方法

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

国家自然科学基金 62071023

详细信息
    通讯作者:

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

  • 中图分类号: V247;TP393

A DDQN-based mixed-criticality messages scheduling method for network-on-chip

Funds: 

National Natural Science Foundation of China 62071023

More Information
  • 摘要:

    对片上网络(NoC)承载的混合关键性消息进行实时调度是其应用于航空电子系统片上多核通信的关键。为解决可满足性模理论(SMT)法求解效率低、低优先级消息等待延迟大的问题,提出了一种基于双深度Q网络(DDQN)的混合关键性消息调度方法。将虫孔交换机制下的消息调度问题建模为马尔可夫决策过程,建立包含环境、动作、状态、奖励的多层感知调度模型;随机生成多组分布不同的混合关键性消息作为训练样本,采用DDQN算法求解该调度模型;在此基础上,提出并实现了带孔隙DDQN算法,在保证时间触发(TT)消息可调度前提下为速率约束(RC)消息预留用于虫孔交换的时隙。算例研究表明:所提方法的求解时长及TT消息确定性端到端延迟的平均值均低于SMT法;带孔隙DDQN算法的RC消息延迟较不带孔隙DDQN算法和SMT法显著降低。

     

  • 图 1  航电网络系统架构

    Figure 1.  System architecture of avionics network

    图 2  虚通道路由器结构

    Figure 2.  Router architecture with virtual channel

    图 3  Q学习训练过程

    Figure 3.  Training process of Q-learning

    图 4  目标网络机制

    Figure 4.  Target network mechanism

    图 5  虚通道缓存对消息传输的影响

    Figure 5.  Impact of virtual channel cache on message transmission

    图 6  多层感知神经网络模型

    Figure 6.  Multilayer perception model of neural network

    图 7  DDQN算法与拓扑分解法运行时间对比

    Figure 7.  Execution time comparison between DDQN algorithm and TBDA-SMT method

    图 8  DDQN算法与拓扑分解法平均派发时刻及端到端延迟对比

    Figure 8.  Comparison of average dispatch time and end-to-end delay between DDQN algorithm and TBDA-SMT method

    图 9  不同算法下的RC消息等待延迟

    Figure 9.  RC message delays in different algorithms

    表  1  RC消息参数

    Table  1.   Properties of RC message

    编号 源节点及目的节点 BAG/ms 生成时刻/时隙
    RC1 n6n0 8 3
    RC2 n0n10 32 6
    RC3 n15n14 16 8
    RC4 n7n14 4 7
    RC18 n0n11 2 8
    RC19 n5n7 16 2
    RC20 n0n13 1 8
    下载: 导出CSV
  • [1] WOLFIG R, JAKOVLJEVIC M. Distributed IMA and DO-297: Architectural, communication and certification attributes[C]//Proceedings Digital Avionics Systems Conference. Piscataway: IEEE Press, 2008: 1. E. 4-1-1. E. 4-10.
    [2] 孔韵雯, 李峭, 熊华钢, 等. 片间综合化互连时间触发通信调度方法[J]. 航空学报, 2018, 39(2): 321590. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201802023.htm

    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). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201802023.htm
    [3] MURSHED A, OBERMAISSER H, AHMADIAN H, et al. Scheduling and allocation of time-triggered and event-triggered services for multi-core processors with networks-on-a-chip[C]//2015 IEEE 13th International Conference on Industrial Informatics(INDIN). Piscataway: IEEE Press, 2015: 1424-1431.
    [4] 易伟, 王佳文, 潘红兵, 等. 基于蚁群混沌遗传算法的片上网络映射[J]. 电子学报, 2011, 39(8): 1832-1836. https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201108019.htm

    YI W, WANG J W, PAN H B, et al. Ant colony chaos genetic algorithm for mapping task graphs to a network on chip[J]. Acta Electronica Sinica, 2011, 39(8): 1832-1836(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201108019.htm
    [5] SAHU P K, SHAH T, MANNA K, et al. Application mapping onto mesh-based network-on-chip using discrete particle swarm optimization[J]. IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2014, 22(2): 300-312. doi: 10.1109/TVLSI.2013.2240708
    [6] CHAI S, LI Y, WANG J, et al. A list simulated annealing algorithm for task scheduling on network-on-chip[J]. Journal of Computers, 2014, 9(1): 176-182.
    [7] SHI Y F, LI Q, YANG J H, et al. A topology-based decomposition approach for time-triggered message scheduling in network-on-chip[C]//2019 IEEE/AIAA 38th Digital Avionics Systems Conference(DASC). Piscataway: IEEE Press, 2019: 1-8.
    [8] 鲁俊, 何锋, 熊华钢, 等. 软件定义时间触发网络的调度算法优化[J]. 北京航空航天学报, 2021, 47(5): 1004-1014. https://www.cnki.com.cn/Article/CJFDTOTAL-BJHK202105014.htm

    LU J, HE F, XIONG H G, el al. Scheduling algorithms optimization in software defined time-triggered ethernet[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(5): 1004-1014(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-BJHK202105014.htm
    [9] LI Z H, WAN H, PANG Z Y, el al. An enhanced reconfiguration for deterministic transmission in time-triggered networks[J]. IEEE/ACM Transactions on Networking, 2019, 27(3): 1124-1137. doi: 10.1109/TNET.2019.2911272
    [10] MIZRAHI T, MOSES Y. Software defined networks: It's about time[C]//The 35th Annual IEEE International Conference on Computer Communications. Piscataway: IEEE Press, 2016: 1-9.
    [11] MARK R, NATE F, JENNIFER R, et al. Abstractions for network update[J]. SIGCOMM Computer, 2012, 42(4): 323-334. doi: 10.1145/2377677.2377748
    [12] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Playing Atari with deep reinforcement learning[C]//Proceedings of Workshops at the 26th Neural Information Processing Systems 2013, 2013: 201-220.
    [13] SILVER D, HUANG A, MADDISON C, et al. Mastering the game of go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489. doi: 10.1038/nature16961
    [14] 李浩若, 何锋, 郑重, 等. 基于强化学习的时间触发通信调度方法[J]. 北京航空航天大学学报, 2019, 45(9): 1894-1901. doi: 10.13700/j.bh.1001-5965.2018.0789

    LI H R, HE F, ZHENG Z, el al. Time-triggered communication scheduling method based on reinforcement learning[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(9): 1894-1901(in Chinese). doi: 10.13700/j.bh.1001-5965.2018.0789
    [15] HASSELT H, GUEZ A, SILVER D. Deep reinforcement learning with double Q-learning[C]//Assocition for the Advance of Artificial Intelligence, 2015: 2094-2100.
    [16] 何锋. 机载网络技术基础[M]. 北京: 国防工业出版社, 2018: 192-196.

    HE F. Fundamentals of airborne network[M]. Beijing: National Defense Industry Press, 2018: 192-196(in Chinese).
    [17] 王炜, 乔林, 汤志忠. 片上网络互连拓扑综述[J]. 计算机科学, 2011, 38(10): 1-5. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201110002.htm

    WANG W, QIAO L, TANG Z Z. Survey on the networks-on-chip interconnection topologies[J]. Computer Science, 2011, 38(10): 1-5(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201110002.htm
    [18] 黄忠凡. 片上网络路由器设计与实现[D]. 西安: 西安电子科技大学, 2013: 14-16.

    HUANG Z F. The router design and implementation of network on chip[D]. Xi'an: Xidian University, 2013: 14-16(in Chinese).
    [19] SU Y S, FAN R, FU X M, et al. An adaptive deep Q-network-based energy and latency-aware routing protocol design for underwater acoustic sensor networks[J]. IEEE Access, 2019, 7: 9091-9104. doi: 10.1109/ACCESS.2019.2891590
    [20] MNIH V, KAVUKCUOGLU K, SILVER D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529-533. doi: 10.1038/nature14236
  • 加载中
图(9) / 表(1)
计量
  • 文章访问数:  45
  • HTML全文浏览量:  24
  • PDF下载量:  1
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-01-06
  • 录用日期:  2021-04-11
  • 刊出日期:  2021-04-26

目录

    /

    返回文章
    返回
    常见问答