Coded Computing via Binary Linear Codes: Designs and Performance Limits
Coded Computing via Binary Linear Codes: Designs and Performance Limits
复制标题
DOI：
10.1109/jsait.2021.3103772
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
M. Soleymani;Mohammad Vahid Jamali;Hessam Mahdavifar
中科院分区：
文献类型：
--
作者：
M. Soleymani;Mohammad Vahid Jamali;Hessam Mahdavifar
我们考虑编码的分布式计算问题，其中大型线性计算作业（例如矩阵乘法）被分为$ k $较小的任务，使用$（n，k）$线性代码编码，并在$ n $分布式上执行节点。目标是减少计算工作的平均执行时间。我们提供了表征编码分布式计算系统的平均执行时间的问题与分析长度$ n $代码的错误概率的问题。因此，我们使用二进制随机线性代码和任何线性编码的分布式计算系统可以实现的最佳执行时间介绍执行时间的闭合形式表达式。还表明，存在良好的二进制线性代码，不仅（渐近地）（渐近）任何线性代码（不一定是二进制）可以实现的最佳性能，而且在实践中不可避免的圆形错误上在数值上稳定。然后，我们开发了一种低复杂算法，用于通过擦除通道解码芦苇刺激器（RM）代码。我们的解码器仅涉及最多$ \ log n+1 $的相对较小尺寸矩阵的添加，减法和反转，并在实价数据上启用编码的计算。对基本结果以及RM和极性编码计算方案的广泛数值分析表明，在实现近距离性能的同时，在具有低复杂性解码和显式结构的同时，RM编码计算的卓越性。本文提出的框架可以使分布式计算系统的有效设计给定渠道编码理论中丰富的文献。
We consider the problem of coded distributed computing where a large linear computational job, such as a matrix multiplication, is divided into $k$ smaller tasks, encoded using an $(n,k)$ linear code, and performed over $n$ distributed nodes. The goal is to reduce the average execution time of the computational job. We provide a connection between the problem of characterizing the average execution time of a coded distributed computing system and the problem of analyzing the error probability of codes of length $n$ used over erasure channels. Accordingly, we present closed-form expressions for the execution time using binary random linear codes and the best execution time any linear-coded distributed computing system can achieve. It is also shown that there exist good binary linear codes that not only attain (asymptotically) the best performance that any linear code (not necessarily binary) can achieve but also are numerically stable against the inevitable rounding errors in practice. We then develop a low-complexity algorithm for decoding Reed-Muller (RM) codes over erasure channels. Our decoder only involves additions, subtractions, and inversion of relatively small matrices of dimensions at most $\log n+1$ , and enables coded computation over real-valued data. Extensive numerical analysis of the fundamental results as well as RM- and polar-coded computing schemes demonstrate the excellence of the RM-coded computation in achieving close-to-optimal performance while having a low-complexity decoding and explicit construction. The proposed framework in this paper enables efficient designs of distributed computing systems given the rich literature in the channel coding theory.