Hierarchical Parallel Model And Research Of The Distributed ADMM Algorithm

Nowdays,the increasing demand for computing brings forward higher requirements for the design of parallel algorithms.Message Passing Interface(MPI)is a kind of Message Passing Interface standard.The parallel program base on MPI may face serious unbalanced process arrival in multi-core environment because of the difference of intra-node and inter-node communication.In addition,in the structure of distributed storage access system,data may need to be sent by the master node to the other computing nodes,so the data transmission will take up a lot of network bandwidth.Many distributed machine learning algorithms in general can be formulated as the global consensus optimization problems,such as linear regression,support vector machines,Logistic regression,which be well suited to solve by Alternating Direction Method o f Multipliers(ADMM).ADMM algorithm is a simple method for solving decomposable convex optimization problems,especially in solving large-scale problems.The objective function of the original problem can be decomposed equally into several solvable sub-problems by using the ADMM algorithm.The synchronous distributed ADMM require global data exchange in one iteration,what will bring large global communication and synchronization overhead.At the same time,the scalability of the algorithm is also limited.In this paper,the problem of research is around parallel algorithm performance optimization,we propose a hierarchical parallel model,which is for reducing the communication time of parallel algorithms and network bandwidth of data distribution.In addition,we propose two asynchronous distributed ADMM,one is an asynchronous distributed ADMM algorithm based on hierarchical parallel model;the other one is an asynchronous distributed ADMM algorithm base on SSP model.The purpose of this paper is to design a distributed ADMM algorithm with high efficiency and high scalability.The main work of this paper is focused on the following points:1.In this paper a hierarchical parallel model is proposed;O n the one hand,we construct a hierarchical co mmunication model through multi-core aware MPICH middleware,and then improve communication efficiency by using effective communication optimization strategy.On the other hand,the method of data preprocessing is used to reduce the bandwidth of data distribution.2.This paper introduces the construction of the hierarchical communication model,communication optimization strategy,the method of data preprocessing by Matrix multiplication and ELM algorithm.The efficiency and scalability of two parallel algorithms based o n hierarchical parallel model are verified by experiments.3.This paper proposes a hierarchical butterfly communication model,which is applied to asynchronous distributed ADMM.The hierarchical model distinguishes between intra-node and inter-node communications,which can improve the scalability of parallel algorithm;the inter-node communication is butterfly communication model,which is reduce the overhead of communication and we analyzed the convergence of the algorithm theoretically.4.This paper proposes asynchronous distributed ADMM base on SSP model.It can reduce the synchronization overhead of synchronous ADMM algorithm in each iteration by using SSP model which is the data parallel model of open source Petuum framework,and the proof of convergence and experimental verification is given.In this paper,the programming model and algorithm are tested on Shanghai University 4000 cluster.The test results show the availability of hierarchical programming model and the acceleration effect of distributed ADMM algorithm.