Anytime coding for distributed computation
Anytime coding for distributed computation
复制标题
分布式计算的随时编码
DOI：
10.1109/allerton.2016.7852337
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Draper
中科院分区：
文献类型：
--
作者：
Nuwan S. Ferdinand;S. Draper
提出了一种新的编码方案，通过近似计算的形式来提高分布式计算的速度。众所周知，任务复制可以极大地缓解云计算中的“掉队者效应”，在这种情况下，整体计算可能会因处理节点（或“掉队者”）的减慢而显著延迟。也有证据表明，在某些情况下，纠错编码的思想比纯粹的复制更有效地处理掉队者。本文提出的方法通过“随时”近似计算的方法建立在这些早期观察的基础上。在这种范例中，随着时间的推移，可以产生精度越来越高的近似解。要做到这一点，我们首先将计算任务分解为不同优先级的任务。接下来，我们应用线性纠错编码来生成分配给不同处理器的子任务。所使用的分解对我们获得的任何时间性能的类型有很大的影响。我们根据近似解的期望代价在一般框架下研究了该格式。我们在向量矩阵乘法的背景下进一步探讨了这种方法。提出的结构进行了数值研究，与以前的工作相比，在精度/延迟权衡方面有了显着改善。
A novel coding scheme is proposed to speed up distributed computation through a form of approximate computing. It is known that task replication can greatly mitigate the “straggler effect” in cloud computing, wherein an overall computation can be significantly delayed by slowed processing nodes (or “stragglers”). It has also been demonstrated that, in certain contexts, ideas of error-correction coding can more efficiently deal with stragglers than pure replication. The approach proposed herein builds on these earlier observations through an “anytime” approach to approximate computing. In this paradigm, over time one can produces approximate solutions of increasing accuracy. To accomplish this we first decompose a computational job in to tasks of various priorities. Next, we apply linear error correction coding to produce subtasks that are assigned to different processors. The decomposition used has a big effect on the type of anytime performance we attain. We study this scheme in a general framework in terms of the expected cost of the approximate solution. We further explore the approach in the context of vector-matrix multiplication. The proposed construction is numerically studied and, in comparison to previous work, demonstrates a significant improvement in the accuracy/latency trade-off.