Dual Entangled Polynomial Code: Three-Dimensional Coding for Distributed Matrix Multiplication

Matrix multiplication is a fundamental building block in various machine learning algorithms. When the matrix comes from a large dataset, the multiplication will be split into multiple tasks which calculate the multiplication of submatrices on different nodes. As some nodes may be stragglers, coding schemes have been proposed to tolerate stragglers in such distributed matrix multiplication. However, existing coding schemes typically split the matrices in only one or two dimensions, limiting their capabilities to handle large-scale matrix multiplication. Three-dimensional coding, however, does not have any code construction that achieves the optimal number of tasks required for decoding. The best result is twice the optimal number, achieved by entangled polynomial (EP) codes. In this paper, we propose dual entangled polynomial (DEP) codes that significantly improve this bound from $2$x to $1.5$x. With experiments in a real cloud environment, we show that DEP codes can also save the decoding overhead and memory consumption of tasks.