Coded Matrix Chain Multiplication
Coded Matrix Chain Multiplication
复制标题
DOI：
10.1109/iwqos52092.2021.9521282
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Xiaodi Fan;Angel Saldivia;Pedro Soto;Jun Li
中科院分区：
文献类型：
--
作者：
Xiaodi Fan;Angel Saldivia;Pedro Soto;Jun Li
矩阵乘法是许多机器学习模型中的基本构件。由于输入矩阵可能太大而无法在单个服务器上相乘，因此将输入矩阵分成多个子矩阵并在不同的服务器上执行乘法是很常见的。然而，在分布式基础设施中，经常会看到性能低于其他服务器的掉队服务器。为了减轻潜在落后者的不利影响，最近提出了各种用于分布式矩阵乘法的编码方案。现有的大多数工作只考虑了最简单的两个矩阵相乘的情况，而本文研究了更一般的多个矩阵相乘的情况，并提出了一种编码方案，该方案可以在一轮中直接解码结果，而不是在多轮计算中。与多轮完成矩阵链乘法相比，我们的编码方案可以显著节省高达90.3%的完成时间。
The matrix multiplication is a fundamental building block in many machine learning models. As the input matrices may be too large to be multiplied on a single server, it is common to split input matrices into multiple submatrices and execute the multiplications on different servers. However, in a distributed infrastructure it is common to observe stragglers whose performance is lower than other servers at some time. In order to mitigate the adversarial effects of potential stragglers, various coding schemes for the distributed matrix multiplication have been recently proposed. While most existing works have only considered the simplest case where only two matrices are multiplied, we investigate a more general case in this paper where multiple matrices are multiplied, and propose a coding scheme that the result can be directly decoded in one round, instead of in multiple rounds of computation. Compared to completing the matrix chain multiplication in multiple rounds, our coding scheme can achieve significant savings of completion time by up to 90.3%.