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

李国梁; 李峭; 徐亚军; 熊华钢

doi:10.13700/j.bh.1001-5965.2021.0006

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

doi: 10.13700/j.bh.1001-5965.2021.0006

北京航空航天大学电子信息工程学院, 北京 100083

基金项目:

国家自然科学基金 62071023

详细信息

通讯作者:
李峭, E-mail: avionics@buaa.edu.cn

中图分类号: V247;TP393
计量
- 文章访问数: 377
- HTML全文浏览量: 149
- PDF下载量: 21
- 被引次数: 0
出版历程
- 收稿日期: 2021-01-06
- 录用日期: 2021-04-11
- 网络出版日期: 2021-04-26
- 整期出版日期: 2022-07-20

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

School of Electronics and Information Engineering, Beihang University, Beijing 100083, China

Funds:

National Natural Science Foundation of China 62071023

More Information

Corresponding author: LI Qiao, E-mail: avionics@buaa.edu.cn

摘要

摘要:
对片上网络（NoC）承载的混合关键性消息进行实时调度是其应用于航空电子系统片上多核通信的关键。为解决可满足性模理论（SMT）法求解效率低、低优先级消息等待延迟大的问题，提出了一种基于双深度Q网络（DDQN）的混合关键性消息调度方法。将虫孔交换机制下的消息调度问题建模为马尔可夫决策过程，建立包含环境、动作、状态、奖励的多层感知调度模型；随机生成多组分布不同的混合关键性消息作为训练样本，采用DDQN算法求解该调度模型；在此基础上，提出并实现了带孔隙DDQN算法，在保证时间触发（TT）消息可调度前提下为速率约束（RC）消息预留用于虫孔交换的时隙。算例研究表明：所提方法的求解时长及TT消息确定性端到端延迟的平均值均低于SMT法；带孔隙DDQN算法的RC消息延迟较不带孔隙DDQN算法和SMT法显著降低。
- 片上网络(NoC) /
- 时间触发(TT)机制 /
- 双深度Q网络(DDQN) /
- 混合关键性消息 /
- 消息调度
Abstract:
Real-time scheduling of mixed-criticality messages carried by network on chip (NoC) is the key to its application to on-chip muli-core communication in avionics system. A double deep Q-network(DDQN) method was proposed to solve the problem of satisfiability modulo theories (SMT) to low efficiency and high delay of low-priority messages. The message scheduling problem under wormhole switch mechanism was modeled as a Markov decision process, and a scheduling model including environment, action, state and reward was established. Then, DDQN was applied to interact with environment in different message distribution generated randomly, and the empirical sequence obtained through interaction was regarded as the training sample of the neural network. In addition, a scheduling method named pore-DDQN was implemented, that is, a time slot was reserved for rate-constrained (RC) messages on the condition that time-triggered (TT) messages can be scheduled. The case study shows that the solution time and the average end-to-end delay of TT messages of DDQN are lower than that of SMT, and the delay of RC messages with pore-DDQN is significantly lower than that of DDQN and SMT.
- network on chip (NoC) /
- time-triggered (TT) mechanism /
- double deep Q-network (DDQN) /
- mixed-criticality message /
- message scheduling

HTML全文

图 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	n₆→n₀	8	3
RC2	n₀→n₁₀	32	6
RC3	n₁₅→n₁₄	16	8
RC4	n₇→n₁₄	4	7

RC18	n₀→n₁₁	2	8
RC19	n₅→n₇	16	2
RC20	n₀→n₁₃	1	8

下载: 导出CSV

参考文献(20)

[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