Squeezed Polynomial Codes: Communication-Efficient Coded Computation in Straggler-Exploiting Distributed Matrix Multiplication

IEEE Access

卷:8

Jungwoo Lee¹  Sangwoo Hong¹  Heecheol Yang² 

[1] Department of Electrical and Computer Engineering, Communications and Machine Learning Laboratory, Seoul National University, Seoul, South Korea;

[2] School of Electronic Engineering, Kumoh National Institute of Technology, Gumi, South Korea;

关键词: Distributed computing;    coded computation;    matrix multiplication;    polynomial codes;   

DOI  :  10.1109/ACCESS.2020.3031590

来源: DOAJ

【 摘 要 】

In a distributed computing environment, there may exist slow processing workers, which are known as “stragglers”, and they can slow down the whole computing process. In this article, we consider coded computation for matrix multiplication tasks in distributed computing, which can mitigate the effect of stragglers by a coding approach. We propose a new communication-efficient coded computation scheme, namely squeezed polynomial codes, for a straggler-exploiting scenario where multiple sub-tasks are assigned to the workers to partially leverage the computation capability of stragglers. The key idea of squeezed polynomial codes is to overlap the encoded matrices in assigning multiple sub-tasks with appropriate polynomial functions in order to reduce the task-allocation communication load from a master to its workers. We compare squeezed polynomial codes with the existing schemes for distributed matrix multiplication in a communication load perspective. Consequently, we show that squeezed polynomial codes can efficiently reduce the communication load while ensuring the optimal recovery condition at a master to obtain final product.

【 授权许可】

Unknown