Polar Coded Distributed Matrix Multiplication
share
We propose a polar coding mechanism for distributed matrix multiplication. Polar codes provably achieve channel capacity and have the advantage of low encoding and decoding complexity. These aspects of polar codes enable a scalable scheme for hundreds of compute nodes in coded computation. We analyze the polarization phenomenon in the context of run times of compute nodes and characterize polarizing matrices over real numbers. We design a sequential decoder specifically for polar codes in erasure channels with real-valued input and outputs. The proposed coded computation scheme is implemented for a serverless computing platform and numerical results are provided. Numerical results illustrate that proposed coded computation scheme achieves significant speed-ups. Finally, experiments are conducted where the performance of the proposed coded computation technique is tested in solving a least squares problem using gradient descent.
READ FULL TEXT