Coded Distributed Computing Schemes Based On Partition Designs And Placement Delivery Arrays

Distributed computing improves computing efficiency by breaking a computing task into many smaller parts and distributing them to multiple computers.It has been found that data exchange takes up a large part of the total execution time in distributed computing,so coding is introduced into distributed computing to reduce communication load.Some researches show that the coded distributed computing scheme to achieve the optimal communication load needs a large number of input files and output functions,which is difficult to be applied in practice.Therefore,how to reduce the number of input files and output functions while ensuring a low communication load is a research problem that needs to be solved and is full of challenges.In this paper,the performance optimization of distributed computing scheme is studied,and two classes of coded distributed computing scheme are constructed.The main work is as follows:（1）Proposed a coding distributed computing scheme based on a partition design.In this scheme,column elements of partition design are associated with distributed computing nodes,row elements are associated with input files,nodes of the same partition are responsible for computing the same output functions,so the number of input files is equal to the number of rows of partition design,and the number of output functions is equal to the number of partitions of partition design.After a class of transformation,there is a one-to-one correspondence between the position of each item and the condition of the file stored by each node.In this way,the nodes in one partition send coded multicast signals to all nodes in different partitions,so that the communication load generated is controlled in a very low range.Theoretical analysis shows that the scheme can not only greatly reduce the number of input files and output functions,but also keep the advantage of relatively low communication load.（2）A distributed computing scheme of multi-job compression coding based on transmission array placement is proposed.This scheme is suitable for parallel execution of Map Reduce jobs with multiple linear functions.In the content placement stage,each submatrix of a particular integer corresponds to a transmission group.In the content transfer phase,each submatrix of a particular integer corresponds to a transport group.In the process of processing multiple Map Reduce jobs in parallel,the intermediate values of the same function are first combined into a compressed value using compression technology,and then these compressed values are divided into blocks.Finally,these compressed value blocks are encoded into multicast signals and transmitted across different Map Reduce jobs.Theoretical analysis shows that this scheme can significantly reduce the communication load of distributed computing.At the same time,a large number of numerical results show that the scheme requires only a small number of Map Reduce jobs.In this paper,the coded distributed computing scheme based on partition design keeps the advantage of low communication load while greatly reducing the number of input files and output functions.The distributed computing scheme of multi-job compression coding based on the placement of transmission array can significantly reduce the communication load and the number of parallel running jobs.