Study On Elastic Distributed Computing Methods Based On Coding Theory

Distributed computing is a method that decomposes large-scale tasks into small tasks and uses multiple nodes to complete in parallel.It has the advantages of high speed,low cost and scalability.Distributed computing faces two major challenges.First,the computing time depends on the completion time of the slowest node,and a small number of nodes with delays(stragglers)may occur in the calculation process,which limits the overall calculation speed.Second,the number of nodes in the elastic cluster may change in the calculation process,the existing nodes need to wait for the redistribution of tasks,resulting in a waste of time.Recently,scholars have proposed the distributed calculation of coding elasticity based on information coding theory,which can effectively alleviate the negative impact of the above problems.Matrix vector multiplication has the characteristics of intensive calculation,easy decomposition and easy combination,which is a classical problem in the research of distributed computing.In this thesis,the distributed matrix vector multiplication is taken as the problem model.Based on the existing work,two coding distributed computing schemes and one coding elastic computing scheme are proposed.The main research results are as follows:1.Aiming at the stragglers problem,this thesis studies the Coded Short Dot Products scheme(Short-Dot),which directly abandons the stragglers calculation results,resulting in a waste of computing resources.In this regard,this thesis proposes a Hierarchical Short-Dot(HSD)coding distributed computing scheme.HSD uses layered coding technology to make stragglers undertake a small amount of tasks,which reduces the computational load of other nodes.Simulation results show that HSD is 6.1% faster than Short-Dot when the delay time of nodes accords with shift-exponential distribution.However,HSD needs to perform multiple encoding and decoding operations on the data,and the time cost of this step is large.In this regard,this thesis further proposes a Segmented Short-Dot(SSD)coding distributed computing scheme based on intra-node segmentation.SSD only needs one encoding,which improves the utilization of stragglers nodes by piecewise calculation.The simulation results show that SSD has 15.7% acceleration compared with Short-Dot.2.For elasticity,existing coding solutions include Coded Elastic Computing(CEC)and Multilevel Coded Elastic Computing(MLCEC).When the cluster size changes,both schemes do not need to recode and redistribute tasks,avoiding the waiting of computing nodes.However,both schemes cannot be compatible with different stragglers environments at the same time: CEC scheme has limited computation speed in the presence of multiple stragglers,and MLCEC scheme has limited computation speed in the presence of a small number of serious stragglers.In this thesis,a Non-sequence Coded Elastic Computing(NSCEC)scheme based on non-sequence execution is proposed,and two execution sequences are given,which are Gaussian probability distribution execution sequence(G-NSCEC)and banded distribution execution sequence(B-NSCEC).The time analysis and simulation results show that the NSCEC has faster calculation speed than CEC and MLCEC schemes in multiple stragglers environments,severe stragglers environments and mixed stragglers environments.