面向通用一致性优化的通信高效的异步ADMM算法  

Communication Efficient Asynchronous ADMM for General Form Consensus Optimization

作　　者：王冬霞 雷咏梅[1] 张泽宇 WANG Dong-xia;LEI Yong-mei;ZHANG Ze-yu(School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学计算机工程与科学学院,上海200444

出　　处：《计算机科学》2022年第11期309-315,共7页Computer Science

基　　金：国家自然科学基金(U1811461)。

摘　　要：分布式交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)是求解大规模机器学习问题使用最广泛的方法之一。现有大多数分布式ADMM算法都基于完整的模型更新。随着系统规模及数据量的不断增长,节点间的通信开销逐渐成为限制分布式ADMM算法发展的瓶颈。为了减少节点间通信开销,提出了一种通信高效的通用一致性异步分布式ADMM算法(General Form Consensus Asynchronous Distributed ADMM,GFC-ADADMM),该算法通过分析高维稀疏数据集的特性,节点间利用关联模型参数代替完整模型参数进行通信,并对模型参数进行过滤以进一步减少节点间传输负载。同时结合过时同步并行(Stale Synchronous Parallel,SSP)计算模型、allreude通信模型及混合编程模型的优势,利用异步allreduce框架并基于MPI/OpenMP混合编程模型实现GFC-ADADMM算法,提高算法计算与通信效率。文中利用GFC-ADADMM算法求解稀疏logistic回归问题,实验测试表明,与现有分布式ADMM算法相比,GFC-ADADMM算法可减少15%~63%的总运行时间,且算法收敛时可达到更高的准确率。The distributed alternating direction method of multipliers(ADMM)is one of the most widely used methods for solving large-scale machine learning applications.However,most distributed ADMM algorithms are based on full model updates.With the increasing of system scale and data volume,the communication cost has become the bottleneck for the distributed ADMM when big data are involved.In order to reduce the communication cost in a distributed environment,a general form consensus asynchronous distributed alternating direction method of multipliers(GFC-ADADMM)is proposed in this paper.First,in the GFC-ADADMM,the associated model parameters rather than full model parameters are transmitted among nodes to reduce the transmission load,and the associated model parameters are filtered according to the characteristics of high-dimensional sparse data sets to further reduce the transmission load.Second,the GFC-ADMM is implemented by an asynchronous allreduce framework,which combines the advantage of the asynchronous communication protocol and the allreduce communication mode.Third,combining the advantages of the stale synchronous parallel(SSP)computing model,allreduce communication model,and hybrid programming model,the asynchronous allreduce framework and MPI/OpenMP hybrid programming model are adopted to implement the GFC-ADADMM,which improves calculation efficiency and communication efficiency of the algorithm.Finally,the sparse logistic regression problem is solved by the GFC-ADADMM.Evaluation with large-scale datasets shows that compared with state-of-the-art asynchronous distributed ADMM algorithms,the GFC-ADADMM can reduce the total running time by 15%-63%,and has higher accuracy in convergence.

关 键 词：分布式交替方向乘子法 通用一致性优化 稀疏allreduce 混合编程模型 LOGISTIC回归 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]