论文部分内容阅读
在大数据时代,数据信息的爆炸式增长对数据分析处理技术和计算能力提出了更高的要求,将传统集中式数据处理方法转换成分布式方法成为一种自然选择。高性能计算和分布式计算的发展为大数据处理提供了强有力的平台。大数据的多样性及高性能计算系统体系结构的复杂性,给实现高效分布式算法提出了新的挑战:利用分布式算法求解大规模问题时,如何合理分配数据、协调节点间通信、均衡工作负载是提高算法性能的关键问题。分布式算法的核心思想是分而治之,将大规模任务划分为多个小规模任务分布到不同计算节点并行执行。大多分布式机器学习问题可转换为最优化问题求解,交替方向乘子法（Alternating Direction Method of Multipliers,ADMM）是一种典型的优化算法,也是求解大规模机器学习问题最有效的优化算法之一,因其高分解性和良好的收敛性而广受关注。ADMM算法框架本质上是分解协作的过程,可将大规模问题分解为多个可并行执行的子问题,通过协调子问题的解得到全局解。高性能计算系统体系结构的复杂性使得分布式ADMM计算模式及通信策略变得更加复杂,增加了并行程序实现的难度。因此需对分布式算法的算法原理和执行过程进行深入研究,才能设计出具有较高可扩展性的计算框架。本文对分布式ADMM实现时的算法模型、通信策略、编程模型等关键问题进行研究,设计实现分布式ADMM计算框架。本文研究内容及创新点如下:（1）本文对分布式ADMM算法模型进行研究,提出一种基于分组的异步分布式ADMM（Group-based Asynchronous Distributed ADMM,GAD-ADMM）,主要解决因节点间计算和通信的不均衡性带来的算法收敛速度慢的问题。GADADMM结合多核分布式系统底层通信机制及数据集模型相似性对工作进程进行分组,通过分组策略聚合参数提高算法收敛速度。同时该算法模型利用分组变量代替局部变量更新全局变量,通过放松全局一致性约束条件进一步提高算法收敛速度。理论和实验表明:在求解L2正则化优化问题时,GAD-ADMM能有效提高收敛速度;（2）针对分布式ADMM处理高维稀疏数据时通信开销大的问题,本文提出一种基于层次化稀疏allreduce通信模型的异步惰性ADMM（Asynchronous Lazy ADMM based on Hierarchical Sparse Allreduce Communication model,HSACALADMM）。针对高维数据稀疏性,提出延时聚合参数策略对传输参数过滤,减少节点间通信负载,并设计基于稀疏数据的层次化allreduce算法以提高节点间通信效率。进一步提出了一种计算-通信-管理（Calculator-Communicator-Manager,CCM）框架,利用该框架实现HSAC-ALADMM提高系统计算和通信效率。“天河二号”和“自强4000”等高性能计算集群上测试结果表明,与其他异步分布式ADMM相比,HSAC-ALADMM可减少30%-93%的通信时间,且具有更好的可扩展性;（3）针对单节点计算资源的增加带来算法通信和内存开销大的问题,本文设计基于混合编程模型的异步分布式ADMM（Asynchronous Distributed ADMM based on Hybrid Programming model,HPAD-ADMM）。该算法节点间基于MPI分布式内存方式实现并行化,节点内基于Open MP共享内存方式实现细粒度并行。同时,针对带L1正则logistic回归（L1-regularized Logistic Regression,L1-LR）和Lasso两类问题,设计不同的并行化算法求解子问题。“天河二号”上实验测试表明,与基于纯MPI编程模型的分布式ADMM相比,HPAD-ADMM可减少21%-73%的总运行时间,且HPAD-ADMM可有效减少单节点内存开销,提高算法可扩展性;（4）本文设计并实现分布式ADMM计算框架。该框架主要应用于求解logistic回归（Logistic Regression,LR）和线性支持向量机（Support Vector Machine,SVM）等线性分类问题。用户使用该框架实现分布式ADMM,不需要过多关注分布式系统底层实现机制,有效缩短其软件开发周期。本文从不同层面提高分布式ADMM性能,并将分布式ADMM的关键部分抽象出来,为用户提供高效的分布式ADMM计算框架,协助用户快速开发面向高性能计算系统并行程序。