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