| Flexible Constructions for Distributed Matrix Multiplication
|Weiqi Li, Zhen Chen, Zhiying Wang, Syed Jafar, Hamid Jafarkhani, University of California, Irvine, United States
|D4-S2-T1: Coded Distributed Matrix Multiplication I
|Thursday, 15 July, 22:20 - 22:40
|Thursday, 15 July, 22:40 - 23:00
The distributed matrix multiplication problem with unknown number of stragglers is considered, where the goal is to allow a master to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across N servers. We assume there are at most N - R stragglers but the exact number is not known a priori. Motivated by reducing the latency, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing job for each server is separated into 2 layers, constructed based on Entangled Polynomial (EP) codes by Yu el al. The final results can be obtained when a larger number of servers complete the task from the first layer or a smaller number of servers complete the tasks from both 2 layers. The required finite field size of the proposed solution is less than 2N. Moreover, the optimal partitioning of the input matrices is discussed. Our constructions can also be generalized to batch matrix multiplication.