Sparse Random Khatri-Rao Product Codes for Distributed Matrix Multiplication
Sparse Random Khatri-Rao Product Codes for Distributed Matrix Multiplication
复制标题
DOI：
10.1109/itw54588.2022.9965842
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Ruowan Ji;A. Heidarzadeh;K. Narayanan
中科院分区：
文献类型：
--
作者：
Ruowan Ji;A. Heidarzadeh;K. Narayanan
我们介绍了两个推广的范例，使用随机Khatri-Rao产品（RKRP）代码的分布式矩阵乘法。本文首先介绍了一类具有稀疏生成矩阵的稀疏随机Khatri-Rao乘积码。当输入矩阵稀疏时，SRKRP码比RKRP码具有更低的编码、计算和通信成本，同时它们表现出与其他现有技术方案相似的数值稳定性。我们实证研究的概率之间的关系的生成矩阵（仅限于一组非离散）的随机选择的SRKRP码是秩亏和各种参数的编码方案，包括稀疏度的生成矩阵和非离散的数量。其次，我们表明，如果主节点可以执行一个非常小的数量的矩阵产品的计算，除了由工人进行的计算，故障概率可以大大提高。
We introduce two generalizations to the paradigm of using Random Khatri-Rao Product (RKRP) codes for distributed matrix multiplication. We first introduce a class of codes called Sparse Random Khatri-Rao Product (SRKRP) codes which have sparse generator matrices. SRKRP codes result in lower encoding, computation and communication costs than RKRP codes when the input matrices are sparse, while they exhibit similar numerical stability to other state of the art schemes. We empirically study the relationship between the probability of the generator matrix (restricted to the set of non-stragglers) of a randomly chosen SRKRP code being rank deficient and various parameters of the coding scheme including the degree of sparsity of the generator matrix and the number of non-stragglers. Secondly, we show that if the master node can perform a very small number of matrix product computations in addition to the computations performed by the workers, the failure probability can be substantially improved.