“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
复制标题
DOI：
10.1109/tit.2019.2927558
复制
发表时间：
2017-04
影响因子：
2.5
通讯作者：
Sanghamitra Dutta;V. Cadambe;P. Grover
中科院分区：
文献类型：
--
作者：
Sanghamitra Dutta;V. Cadambe;P. Grover
我们考虑使用一组$P$并行或分布式处理节点计算矩阵向量积$Ax$的问题，这些节点易于“离散”，即，不可预测的延迟每个处理节点只能访问长度为$N$的向量$x$的一部分$（{s}/{N}）$，并且所有处理节点计算相同数量的点积。我们提出了一种新的纠错码，我们称之为“Short-Dot”，它引入了冗余的，较短的点积，使得只有一个子集的节点的输出是足够的计算$Ax$。为了解决计算矩阵向量积时的离散问题，先前的工作使用复制或纠删编码来编码矩阵A的部分，但在每个处理节点处计算的点积的长度仍然是N。在我们的工作中，关键的新奇是，而不是计算长的点积所需的原始矩阵矢量积，我们构建了大量的冗余和短的点积，只需要一小部分的$x$在计算过程中被访问。因此，Short-Dot在通信受限的场景中非常有用，因为它只允许每个处理节点访问$x$的一小部分。此外，我们表明，在特定的制度，其中可用的处理节点的数量大于点产品的总数，短点有较低的预期计算时间下离散指数模型相比，现有的策略，例如复制，在缩放意义上。我们还推导出点积长度和恢复阈值之间的权衡的基本限制，即，所需的处理节点数，表明Short-Dot接近最优。
We consider the problem of computing a matrix-vector product $Ax$ using a set of $P$ parallel or distributed processing nodes prone to “straggling,” i.e., unpredictable delays. Every processing node can access only a fraction $({s}/{N})$ of the $N$ -length vector $x$ , and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call “Short-Dot”–that introduces redundant, shorter dot products such that only a subset of the nodes’ outputs are sufficient to compute $Ax$ . To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix $A$ , but the length of the dot products computed at each processing node is still $N$ . The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of $x$ to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of $x$ to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.