Rook Coding for Batch Matrix Multiplication
Rook Coding for Batch Matrix Multiplication
复制标题
DOI：
10.1109/tcomm.2022.3165201
复制
发表时间：
2022-06
影响因子：
8.3
通讯作者：
Pedro Soto;Xiaodi Fan;Angel Saldivia;Jun Li
中科院分区：
文献类型：
--
作者：
Pedro Soto;Xiaodi Fan;Angel Saldivia;Jun Li
矩阵乘法是各种分布式计算算法中的基本构建块。为了将大型矩阵相乘，通常的做法是将计算分配到在不同节点上运行的多个任务中。为了容忍此类节点之间的掉队者，通过添加额外的编码任务提出了各种编码方案。然而，大多数现有的矩阵乘法编码方案仅针对一个矩阵乘法构造，而批量矩阵乘法在大规模分布式计算工作负载中很常见。在本文中，我们提出了车编码（RC），一种新的多项式为基础的编码框架，用于计算乘法的$n$对矩阵在批处理。为了在实践中实现更低的编码时间，我们构造RC作为多项式的更简单的形式比现有的编码计划批矩阵乘法，实现了恢复阈值为O（n^{\log _{2} ~3}）$。与现有的编码方案相比，RC在实际中实现了较低的编码复杂度，因为它的编码多项式的形式更简单。通过大量的实验，我们表明，RC可以节省整个工作的时间由于其低开销的编码。
Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to multiply large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate stragglers among such nodes, various coding schemes have been proposed by adding additional coded tasks. However, most existing coding schemes for matrix multiplication are constructed for only one matrix multiplication, while batch matrix multiplication is common in large-scale distributed computing workloads. In this paper, we propose Rook Coding (RC), a novel polynomial-based coding framework for computing the multiplication of $n$ pairs of matrices in batch. Designed to achieve lower encoding time in practice, we construct RC as polynomials of much simpler forms than existing coding schemes for batch matrix multiplication, achieving a recovery threshold of $O(n^{\log _{2} ~3})$ . Compared to existing coding schemes, RC achieves a lower encoding complexity in practice, because of its simpler forms in the encoding polynomials. Through extensive experiments, we show that RC can save the time of the whole job thanks to its low overhead of encoding.