基于三模冗余的分布式可靠编码方案
(兰州交通大学 电子与信息工程学院,甘肃 兰州 730070)
摘要
针对传统编码分布式计算方案中Shuffle阶段数据交换量过大导致的系统时延高以及可靠性低等问题,提出了一种基于三模冗余的编码分布式计算方案(Triple Modular Redundancy-Coded Distributed Computing, TMR-CDC)。首先创建了TMR-CDC模型,该模型将同一数据在不同节点进行冗余备份,在保证有足够中间值计算最终结果的同时减少数据传输量。其次在数据传输过程中融入校验机制检测计算结果的正确性,并设计了TMR-CDC算法实现该方案。最后通过实验表明,TMR-CDC方案将Shuffle阶段的运行时间占编码分布式计算总运行时间的比值从C-CDC方案的34.53%和S-CDC方案的33.27%降低到26.39%。并且TMR-CDC方案设置的容错机制显著提高了系统的可靠性。
关键词
编码分布式计算;可靠编码;数据洗牌;三模冗余;通信负载优化
参考文献
- [1] 郑腾飞,周桐庆,蔡志平,等.编码计算研究综述 [J].计算机研究与发展,2021,58(10):2187-2212.
- [2] ZHANG Z Y,CHERKASOVA L,LOO B T. Performance Modeling of MapReduce Jobs in Heterogeneous Cloud Environments [C]//2013 IEEE Sixth International Conference on Cloud Computing.Santa Clara:IEEE,2013:839-846.
- [3] LI S,MADDAH-ALI M A,AVESTIMEHR A S. Compressed Coded Distributed Computing [C]//2018 IEEE International Symposium on Information Theory (ISIT).Vail:IEEE,2018:2032-2036.
- [4] DEAN J,GHEMAWAT S. MapReduce: Simplified Data Processing on Large Clusters [J].Communications of the ACM,2008,51(1):107-113.
- [5] CHEN H N,LONG J F,MA S,et al. On the Optimality of Data Exchange for Master-aided Edge Computing Systems [J].IEEE Transactions on Communications,2023,71(3):1364-1376.
- [6] LI S,YU Q,MADDAH-ALI M A,et al. A Scalable Framework for Wireless Distributed Computing [J].IEEE/ACM Transactions on Networking,2017,25(5):2643-2654.
- [7] 董洪岩.基于分组复制的编码分布式计算方案的研究 [D].桂林:广西师范大学,2023.
- [8] HORII S. Improved Computation-communication Trade-off for Coded Distributed Computing Using Linear Dependence of Intermediate Values [C]//2020 IEEE International Symposium on Information Theory (ISIT).Los Angeles:IEEE,2020:179-184.
- [9] LI S Z,YU Q,MADDAH-ALI M A,et al. A Scalable Coded Computing Framework for Edge-facilitated Wireless Distributed Computing [C]//2016 IEEE/ACM Symposium on Edge Computing(SEC).Washington:IEEE,2016:79-80.
- [10] PARRINELLO E,LAMPIRIS E,ELIA P. Coded Distributed Computing with Node Cooperation Substantially Increases Speedup Factors [C]//2018 IEEE International Symposium on Information Theory (ISIT).Vail:IEEE,2018:1291-1295.
- [11] EZZELDIN Y H,KARMOOSE M,FRAGOULI C. Communication vs Distributed Computation: An Alternative Trade-off Curve [C]//2017 IEEE Information Theory Workshop (ITW).Kaohsiung:IEEE,2017:279-283.
- [12] NG J S,LIM W Y B,LUONG N C,et al. A Survey of Coded Distributed Computing [J/OL].arXiv:2008.09048 [cs.DC].[2020-08-20].https://arxiv.org/abs/2008.09048.
- [13] LI S,MADDAH-ALI M A,AVESTIMEHR A S. Coded MapReduce [C]//2015 53rd Annual Allerton Conference on Communication,Control,and Computing (Allerton).Monticello:IEEE,2015:964-971.
- [14] JIANG J,WANG W,ZHOU L. Cascaded Coded Distributed Computing Schemes Based on Symmetric Designs [J].IEEE Transactions on Communications,2022,70(11): 7179-7190.
- [15] 黎卫东.面向矩阵向量相乘的编码分布式计算方法研究 [D].南京:南京大学,2020.
- [16] 王艳,李念爽,王希龄,等.编码技术改进大规模分布式机器学习性能综述 [J].计算机研究与发展,2020,57(3):542-561.
- [17] 张基,谢在鹏,毛莺池,等.MapReduce框架下结合分布式编码计算的容错算法 [J].计算机工程,2021,47(4):173-179.
- [18] REISIZADEH A,PRAKASH S,PEDARSANI R,et al. Coded Computation Over Heterogeneous Clusters [J].IEEE Transactions on Information Theory,2019,65(7): 4227-4242.
- [19] LEDMI A,BENDJENNA H,HEMAM S M. Fault tolerance in Distributed Systems: A Survey [C]//2018 3rd International Conference on Pattern Analysis and Intelligent Systems (PAIS).Tebessa:IEEE,2018:1-5.
- [20] 汪强,袁由光.高性能容错处理核心的研究 [J].计算机与数字工程,2000(3):5-11.
- [21] LYONS R E,VANDERKULK W. The Use of Triple-modular Redundancy to Improve Computer Reliability [J].IBM Journal of Research and Development,1962,6(2):200-209.
- [22] 姬生鹏.基于更少输出函数和主辅助压缩的编码分布式计算方案 [D].桂林:广西师范大学,2023.
- [23] LI X,LIN Y. A Triple Modular Eager Redundancy Fault Tolerant Technique for Distributed Stream Architecture [J].Computer Engineering and Science,2015,37(12):2233.
- [24] 逄博.面向星地融合网的分布式编码计算卸载策略研究 [D].哈尔滨:哈尔滨工业大学,2021.
- [25] 苑燕飞.基于编码技术的分布式计算方法研究 [D].西安:西安电子科技大学,2021.
基金项目
甘肃省重点研发计划基金资助项目(20YF8GA123)
作者简介
赵庶旭(1976—),男,汉族,山东青岛人,教授,博士,研究方向:智能交通、边缘计算;李雪飞(1997—),男,汉族,甘肃定西人,硕士在读,研究方向:编码分布式计算、边缘计算;王小龙(1989—),男,汉族,甘肃定西人,讲师,博士,研究方向:边缘联盟、边缘计算。