Flexible Constructions for Distributed Matrix Multiplication
Weiqi Li, Zhe Chen, Zhiying Wang, Syed A. Jafar, Hamid Jafarkhani · 2021
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.