Irregular Product Coded Computation for High-Dimensional Matrix Multiplication

Abstract

In this paper, we consider the straggler problem of the high-dimensional matrix multiplication over distributed workers. To tackle this problem, we propose an irregular-product-coded computation, which is a generalized scheme of the standard-product-coded computation proposed in [1]. Introducing the irregularity to the product-coded matrix multiplication, one can further speed up the matrix multiplication, enjoying the low decoding complexity of the product code. The idea behind the irregular product code introduced in [2] is allowing different code rates for the row and column constituent codes of the product code. We provide a latency analysis of the proposed irregular-product-coded computation. In terms of the total execution time, which is defined by a function of the computation time and decoding time, it is shown that the irregular-product-coded scheme outperforms other competing schemes including the replication, MDS-coded and standard-product-coded schemes in a specific regime.