Fast and Efficient Distributed Matrix-vector Multiplication Using Rateless Fountain Codes
Fast and Efficient Distributed Matrix-vector Multiplication Using Rateless Fountain Codes
复制标题
DOI：
10.1109/icassp.2019.8682347
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Ankur Mallick;Malhar Chaudhari;Gauri Joshi
中科院分区：
文献类型：
--
作者：
Ankur Mallick;Malhar Chaudhari;Gauri Joshi
我们提出了一种无重量的喷泉编码策略，以减轻挣扎的节点的问题 - 计算分布式矩阵 - 矢量乘法中无法预测的速度或失败的节点。然后，可以将原始矩阵矢量产物进行编码的行执行行矢量产品。由节点完成。与最近提议的固定速率擦除编码策略相比，快速节点可以从慢节点中窃取工作总体延迟和较小的计算开销。
We propose a rateless fountain coding strategy to alleviate the problem of straggling nodes – computing nodes that unpredictably slowdown or fail – in distributed matrix-vector multiplication. Our algorithm generates linear combinations of the m rows of the matrix, and assigns them to different worker nodes, which then perform row-vector products with the encoded rows. The original matrix-vector product can be decoded as soon as slightly more than m row-vector products are collectively completed by the nodes. This strategy enables fast nodes to steal work from slow nodes, without requiring the knowledge of node speeds. Compared to recently proposed fixed-rate erasure coding strategies which ignore partial work done by straggling nodes, rateless codes have a significantly lower overall delay, and a smaller computational overhead.