On the Optimal Recovery Threshold of Coded Matrix Multiplication
On the Optimal Recovery Threshold of Coded Matrix Multiplication
复制标题
DOI：
10.1109/tit.2019.2929328
复制
发表时间：
2020-01-01
影响因子：
2.5
通讯作者：
Grover, Pulkit
中科院分区：
文献类型：
--
作者：
Dutta, Sanghamitra;Fahim, Mohammad;Grover, Pulkit
我们为分布式矩阵-矩阵乘积提供了新的编码计算策略，其在恢复阈值方面优于最近的“多项式码”构造，即，成功工人的数量。当每个矩阵的固定1/m分数可以存储在每个工作节点时，Polynomial码需要m（2）个成功的工作者，而我们的MatDot码只需要2 m- 1个成功的工作者。然而，MatDot码具有较高的计算成本，每个工人和更高的通信成本从每个工人到融合节点。我们还提供了一个系统的MatDot码的建设。此外，我们提出了“PolyDot”编码，插值多项式代码和MatDot代码之间的权衡计算/通信成本和恢复阈值。最后，我们展示了一种新的编码技术乘以n矩阵（n >= 3）使用的想法从MatDot和PolyDot码。
We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When a fixed 1/m fraction of each matrix can be stored at each worker node, Polynomial codes require m(2) successful workers, while our MatDot codes only require 2m - 1 successful workers. However, MatDot codes have higher computation cost per worker and higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Furthermore, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off computation/communication costs and recovery thresholds. Finally, we demonstrate a novel coding technique for multiplying n matrices (n >= 3) using ideas from MatDot and PolyDot codes.