面向分布式计算的编码理论及应用技术研究

In distributed computing platforms, due to the existence of failure nodes and stragglers as well as limited communication bandwidth, computation tasks often experience very poor performance. Coding, which can be performed on the algorithm layer and thus can be applied directly on current distributed systems, is a very promising approach to mitigating the effect of stragglers by introducing proper redundant computations, as well as reducing the communication traffic by network coding. However, there lacks a comprehensive coding theory for distributed computation, and application technology needs to be investigated to enhance the performance. Focusing on the key performance metrics including running time, computation load, communication load, and the accuracy of computation, we are dedicated to investigate the straggler-tolerant coding methods and the coding methods for efficient data exchanging. Furthermore, we will develop coding methods and resource allocation methods for multi-stage distributed computation, and develop typical platform oriented coding methods as well as performance optimization techniques. We will demonstrate our research results using some common large-scale data analytics/machine learning problems and standard data sets, mainly on public cloud computing platforms.

在分布式计算平台中，分布式计算任务常因部分节点失效/计算落后及网络带宽资源受限导致性能极其低下。通过编码生成适当的冗余计算及对数据进行编码后通信是解决上述问题的有效途径。此外，编码方法可在算法层面上实现，不需要对分布式系统进行修改，其应用价值立马可见。然而目前编码方法的设计缺乏足够的理论指导，应用技术亦较为不足。项目将围绕运行时间、计算负载、通信负载、计算精度等关键性能指标，对节点失效/计算落后容忍的编码理论、面向高效数据交换的编码方法与通信机制开展理论研究。在此基础上，对面向多阶段分布式计算的编码方法与资源分配、典型分布式计算平台中的编码机制与性能优化技术开展研究。课题将主要在公有云计算平台上，通过常见的大规模数据分析/机器学习问题和标准数据集，对研究成果进行验证。

在分布式计算平台中，分布式计算任务常因部分节点失效/计算落后及网络带宽资源受限导致性能极其低下。通过编码生成适当的冗余计算及对数据进行编码后通信是解决上述问题的有效途径。为此，本项目针对面向分布式计算的编码理论与应用技术，围绕运行时间、计算负载、通信负载、计算精度等关键性能指标，从节点失效/计算落后容忍的编码理论、面向高效数据交换的编码方法与通信机制、面向多阶段分布式计算的编码方法与资源分配、典型分布式计算平台中的编码机制与性能优化技术等四个方面开展研究。取得的主要成果包括：提出了面向异构环境下梯度计算的最优失效容忍的梯度编码方法；提出了面向近似矩阵乘法的基于优先级编码与矩阵奇异值分解的精度可控的编码机制；提出了面向落后节点充分利用的全速编码计算理念，并面向典型计算场景提出了全速编码计算可达的机制；建立了基于线性网络编码的高效可靠数据通信机制，提出了中间值长度异构感知的泛化编码MapReduce框架及面向高效数据交换的通信机制；构建了高效的多阶段联合编码方法及资源分配策略；并结合云计算平台、移动边缘计算平台特点，建立了面向典型应用的高效编码机制与性能优化技术。研究成果将传统的编码理论在分布式计算领域进行了有效延伸与创新，能有效地帮助解决典型分布式计算平台中节点失效、计算落后以及通信瓶颈问题，降低大规模数据处理分析的时延，提升计算效率，为上层各类应用提供关键运行支撑。以上述研究成果为基础，在国际高水平期刊和会议上发表/录用论文22篇，申请国家发明专利9项，其中3项获授权。