计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 336-341.doi: 10.11896/jsjkx.201200126

• 计算机网络 • 上一篇    下一篇

基于机器学习的分布式星载RTs系统负载调度算法

谭双杰1,2, 林宝军1,2,3,4,5, 刘迎春2,3,4, 赵帅2,4   

  1. 1 上海科技大学信息科学与技术学院 上海201210
    2 中国科学院微小卫星创新研究院 上海201203
    3 中国科学院大学计算机科学与技术学院 北京100094
    4 上海微小卫星工程中心 上海201210
    5 中国科学院空天信息创新研究院 北京100094
  • 收稿日期:2020-12-14 修回日期:2021-04-19 出版日期:2022-02-15 发布日期:2022-02-23
  • 通讯作者: 林宝军(linbaojun@aoe.ac.cn)
  • 作者简介:tanshj@shanghaitech.edu.cn

Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning

TAN Shuang-jie1,2, LIN Bao-jun1,2,3,4,5, LIU Ying-chun2,3,4, ZHAO Shuai2,4   

  1. 1 School of Information Science and Technology,ShanghaiTech University,Shanghai 201210,China
    2 Innovation Academy for Microsatellites,Chinese Academy of Sciences,Shanghai 201203,China
    3 School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100094,China
    4 Shanghai Engineering Center for Microsatellites,Shanghai 201210,China
    5 Aerospace Information Research Institute,Chinese Academy of Sciences,Beijing 100094,China
  • Received:2020-12-14 Revised:2021-04-19 Online:2022-02-15 Published:2022-02-23
  • About author:TAN Shuang-jie,born in 1994,postgra-duate.Her main research interests include distributed computing and embedded software.
    LIN Bao-jun,born in 1963,Ph.D,professor,Ph.D supervisor.His main research interests include computer control technology and satellite overall.

摘要: 分布式星载多RTs(Remote Terminal)系统的任务主要基于功能进行分配,而数据处理任务的突发性往往会使不同计算机之间负载不均衡。运用灵活的负载调度机制,可以有效调节不同计算机间的负载差异,从而在一定程度上提升计算机系统的整体性能。文中提出了一种基于机器学习的分布式星载RTs系统负载调度算法,包含样本采集、任务吞吐率预测模型构建、吞吐率预测和负载调度等4个步骤。在构建任务吞吐率预测模型环节,通过机器学习的线性回归正规方程获取模型权重,缩短了构建模型消耗的时间。在负载调度环节,若RTs的吞吐率之和大于系统总的负载数据量,则按吞吐率比例给各RTs分配数据,否则只给负载数据量小于自身吞吐率的RTs分配一定量的数据。在多台星载计算机电性能产品构建的地面模拟系统上的实验结果表明,该算法可以使系统所有节点的平均CPU利用率提高23.78%,节点间的CPU利用率方差降低至34.59%,同时目标任务的系统总吞吐量显著提升225.97%。也就是说,该方法在确保系统负载均衡性的同时,可有效提高系统的资源利用率,提升星载计算机系统的数据实时处理性能。

关键词: 动态负载均衡, 分布式系统, 机器学习, 任务调度, 星载计算机

Abstract: The tasks of distributed on-board multi-RTs (remote terminals) system are mainly distributed based on functions,while the burstiness of data processing tasks often leads to unbalanced load among different computers.Using a flexible load scheduling mechanism can effectively adjust the load difference between different computers,thereby improving the overall performance of the computer system to a certain extent.A load scheduling algorithm for distributed on-board RTs system based on machine learning is proposed in this paper,which includes four steps:sample collection,task throughput prediction model construction,throughput prediction and load scheduling.In the process of constructing the task throughput prediction model,the weight of the model is obtained through the linear regression normal equation of machine learning,which reduces the time spent in constructing the model.In the load scheduling link,if the total throughput rate of RTs is greater than the total load data volume of the system,data will be allocated to each RT in proportion to the throughput rate;otherwise,only a certain amount of data will be allocated to RTs whose load data volume is less than their own throughput rate.The test results on the ground simulation system constructed by multiple on-board computers electrical performance products show that the algorithm can increase the average CPU utilization rate of all nodes of the system by 23.78%,and reduce the variance of CPU utilization rate between nodes to 34.59%.The total system throughput of the task is significantly increased by 225.97%.In other words,this method can effectively improve system resource utilization while ensuring system load balance,and improve the real-time data processing performance of the on-board computer system.

Key words: Distributed system, Dynamic load balancing, Machine learning, On-board computer, Task scheduling

中图分类号: 

  • TP393
[1]SAEED N,ELZANATY A,ALMORAD H,et al.CubeSat Communications:Recent Advances and Future Challenges[J].IEEE Communication Survey & Tutorials,2020,22(3):1839-1862.
[2]LI H W,WU Q,XU G,et al.Progress and Tendency of Space and Earth Integrated Network[J].Science & Technology Review,2016,34(14):95-106.
[3]HUANG C.Reliable Reconstruction Technology for On-board Computer Based on Loongson and FLASH[D].Beijing:University of Chinese Academy of Sciences,2017.
[4]LU S Q,LIANG H G,LIU D Y.Thoughts on the Status Quo and Development of Localized On-board Computer Technology[J].Computer Knowledge and Technology,2018,6:126-129.
[5]PATNI J C,ASWAL M S.Distributed Load Balancing Modelfor Grid Computing Environment[C]//2015 1st International Conference on Next Generation Computing Technologies.2015:123-126.
[6]PENG T,HOFLINGER K,WEPS B,et al.A Component-Based Middleware for a Reliable Distributed and Reconfigurable Spacecraft Onboard Computer[C]//2016 IEEE 35th Symposium on Reliable Distributed Systems.2016:337-342.
[7]REN J Y,SUN H Y,ZHANG L X,et al.Development status ofspace laser communication and new method of networking[J].Laser & Infrared,2019,49(2):143-150.
[8]LIU L D,QI D Y.An Independent Task Scheduling Algorithmin Heterogeneous Multi-core Processor Environment[C]//2018 IEEE 3rd Advanced Information Technology,Electronic and Automation Control Conference.2018:142-146.
[9]ZHANG J,SUN S J,FAN H B,et al.Task Scheduling Algorithm in Heterogeneous Multi-core Processor with High Real-time Performance[J].Computer Engineering,2017,43(5):55-59.
[10]AN X,ZHANG Y,KANG A,et al.Machine learning based online mapping approach for heterogeneous multi-core processor system[J].Journal of Computer Applications,2019,39(6):1753-1759.
[11]IBM Cloud Education.Machine Learning Focuses on Applica-tions that Learn from Experience and Improve their Decision-making or Predictive Accuracy over Time[EB/OL].(2020-07-15)[2020-10-01].https://www.ibm.com/cloud/learn/machine-learning.
[12]SAMIE F,BAUER L,HENKEL J.From Cloud Down toThings:An Overview of Machine Learning in Internet of Things[J].IEEE Internet of Things Journal,2019,6(3):4921-4934.
[13]NEMIROVSKY D,ARKOSE T,MARKOVIC N,et al.A ma-chine learning approach for performance prediction and scheduling on heterogeneous CPUs[C]//Proceedings of the 2017 IEEE 29th International Symposium on Computer Architecture and High Performance Computing.Piscataway,NJ:IEEE,2017:121-128.
[14]MICOLET P J,SMITH A,DUBACH C.A machine learning approach to mapping streaming workloads to dynamic multicore processors[C]//LCTES 2016:Proceedings of the 2016 17th ACM SIGPLAN/SIGBED Conference on Languages,Compi-lers,Tools and Theory for Embedded Systems.New York:ACM,2016:113-122.
[15]ROTATION.Machine Learning-A Summary of Linear Regression[EB/OL].(2010-01-19)[2020-10-01].https://blog.csdn.net/fengxinlinux/article/details/86556584.
[16]XIE Y X,LI Y W,XIA Z J,et al.An Improved Forward Regression Variable Selection Algorithm for High-Dimensional Linear Regression Models[J].IEEE Access,2020,8:129032-129042.
[17]YUAN D M,PROUTIERE A,SHI G D.Distributed Online Li-near Regressions[J].Transactions on Information Theory,2021,67(1):616-639.
[18]YU D F,LI H J,TANG H,et al.Dynamic Load Balancing Algorithm Design and Application based on Feedback[J].Application Research of Computers,2012,29(2):527-529.
[19]GAST N,IOANNIDIS S,LOISEAU P,et al.Linear Regression from Strategic Data Sources[J].ACM Transactions on Econo-mics and Computation,2020,8(2):1-24.
[20]LIANG J B,ZHANG H H,JIANG C,et al.Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing[J].Computer Science,2021,48(7):316-323.
[1] 冷典典, 杜鹏, 陈建廷, 向阳.
面向自动化集装箱码头的AGV行驶时间估计
Automated Container Terminal Oriented Travel Time Estimation of AGV
计算机科学, 2022, 49(9): 208-214. https://doi.org/10.11896/jsjkx.210700028
[2] 宁晗阳, 马苗, 杨波, 刘士昌.
密码学智能化研究进展与分析
Research Progress and Analysis on Intelligent Cryptology
计算机科学, 2022, 49(9): 288-296. https://doi.org/10.11896/jsjkx.220300053
[3] 李瑶, 李涛, 李埼钒, 梁家瑞, Ibegbu Nnamdi JULIAN, 陈俊杰, 郭浩.
基于多尺度的稀疏脑功能超网络构建及多特征融合分类研究
Construction and Multi-feature Fusion Classification Research Based on Multi-scale Sparse Brain Functional Hyper-network
计算机科学, 2022, 49(8): 257-266. https://doi.org/10.11896/jsjkx.210600094
[4] 张光华, 高天娇, 陈振国, 于乃文.
基于N-Gram静态分析技术的恶意软件分类研究
Study on Malware Classification Based on N-Gram Static Analysis Technology
计算机科学, 2022, 49(8): 336-343. https://doi.org/10.11896/jsjkx.210900203
[5] 何强, 尹震宇, 黄敏, 王兴伟, 王源田, 崔硕, 赵勇.
基于大数据的进化网络影响力分析研究综述
Survey of Influence Analysis of Evolutionary Network Based on Big Data
计算机科学, 2022, 49(8): 1-11. https://doi.org/10.11896/jsjkx.210700240
[6] 陈明鑫, 张钧波, 李天瑞.
联邦学习攻防研究综述
Survey on Attacks and Defenses in Federated Learning
计算机科学, 2022, 49(7): 310-323. https://doi.org/10.11896/jsjkx.211000079
[7] 肖治鸿, 韩晔彤, 邹永攀.
基于多源数据和逻辑推理的行为识别技术研究
Study on Activity Recognition Based on Multi-source Data and Logical Reasoning
计算机科学, 2022, 49(6A): 397-406. https://doi.org/10.11896/jsjkx.210300270
[8] 姚烨, 朱怡安, 钱亮, 贾耀, 张黎翔, 刘瑞亮.
一种基于异质模型融合的 Android 终端恶意软件检测方法
Android Malware Detection Method Based on Heterogeneous Model Fusion
计算机科学, 2022, 49(6A): 508-515. https://doi.org/10.11896/jsjkx.210700103
[9] 李亚茹, 张宇来, 王佳晨.
面向超参数估计的贝叶斯优化方法综述
Survey on Bayesian Optimization Methods for Hyper-parameter Tuning
计算机科学, 2022, 49(6A): 86-92. https://doi.org/10.11896/jsjkx.210300208
[10] 赵璐, 袁立明, 郝琨.
多示例学习算法综述
Review of Multi-instance Learning Algorithms
计算机科学, 2022, 49(6A): 93-99. https://doi.org/10.11896/jsjkx.210500047
[11] 王飞, 黄涛, 杨晔.
基于Stacking多模型融合的IGBT器件寿命的机器学习预测算法研究
Study on Machine Learning Algorithms for Life Prediction of IGBT Devices Based on Stacking Multi-model Fusion
计算机科学, 2022, 49(6A): 784-789. https://doi.org/10.11896/jsjkx.210400030
[12] 许杰, 祝玉坤, 邢春晓.
机器学习在金融资产定价中的应用研究综述
Application of Machine Learning in Financial Asset Pricing:A Review
计算机科学, 2022, 49(6): 276-286. https://doi.org/10.11896/jsjkx.210900127
[13] 么晓明, 丁世昌, 赵涛, 黄宏, 罗家德, 傅晓明.
大数据驱动的社会经济地位分析研究综述
Big Data-driven Based Socioeconomic Status Analysis:A Survey
计算机科学, 2022, 49(4): 80-87. https://doi.org/10.11896/jsjkx.211100014
[14] 李野, 陈松灿.
基于物理信息的神经网络:最新进展与展望
Physics-informed Neural Networks:Recent Advances and Prospects
计算机科学, 2022, 49(4): 254-262. https://doi.org/10.11896/jsjkx.210500158
[15] 冯了了, 丁滟, 刘坤林, 马科林, 常俊胜.
区块链BFT共识算法研究进展
Research Advance on BFT Consensus Algorithms
计算机科学, 2022, 49(4): 329-339. https://doi.org/10.11896/jsjkx.210700011
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!