编码分布式矩阵乘法（Coded Distributed Matrix Multiplication, CDMM）问题简单介绍

利用编码技术缓解分布式计算系统的掉队效应

[T_I_T]

1154人浏览 · 2022-12-08 20:38:28

[T_I_T] · 2022-12-08 20:38:28 发布

许多现代分布式计算框架都会遇到大规模分布式矩阵乘法问题，即计算两个大规模矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 的乘积，如MapReduce、Spark。由于分布式计算系统会出现的无法预测的时延，主节点（master node）必须等到最慢的工作节点(worker node)完成计算才能恢复计算结果，这种现象称作掉队效应（straggler effect）。实验证明在Amazon EC2上，等待掉队者（stragglers）完成计算的时间比等待普通节点完成计算的时间长5到8倍。编码分布式矩阵乘法（Coded Distributed Matrix Multiplication, CDMM）通过引入冗余，即用纠删码对矩阵A和B编码，使得主节点在收到一定数量（而非全部）工作节点的计算结果后就能解码出 $\mathbf{A}\mathbf{B}$ ，从而缓和掉队效应。

CDMM的问题描述包括三部分。假设分布式计算系统包括1个主节点和N个工作节点。

1.编码（Encoding）：主节点按照函数集 $f=(f_1,f_2,\cdots,f_N)$ 和 $g=(g_1,g_2,\cdots,g_N)$ 将输入矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 编码为 $\tilde{\mathbf{A}}_i=f_i(\mathbf{A}),i=1,2,\ldots,N$ 和 $\tilde{\mathbf{B}}_i=f_i(\mathbf{B}),i=1,2,\ldots,N$ 。

2.分发和计算：主节点将 $\tilde{\mathbf{A}}_i,\tilde{\mathbf{B}}_i$ 发送给工作节点i，工作节点计算 $C_i=h_i(\tilde{\mathbf{A}}_i,\tilde{\mathbf{B}}_i)$ 并将结果返回给主节点。

3.解码（Decoding）：主节点收到R个工作节点的计算结果后，使用选择函数集 $d=(d_\mathcal{R},\mathcal{R}\subset\{1,2,\ldots,N\},|\mathcal{R}|=R)$ 中节点集合对应的解码函数,解码出 $\mathbf{A}\mathbf{B}=d_\mathcal{R}(\{C_i\}_{i\in\mathcal{R}})$ 。R称作恢复阈值（recovery threshold）。最优恢复阈值定义为 $R^*=\min(f,g,h,d)$ 。

例1：先把 $\mathbf{A}$ 矩阵划分为

$\mathbf{A}=\begin{bmatrix} \mathbf{A}_{0,0}&\mathbf{A}_{0,1}\\ \mathbf{A}_{1,0}&\mathbf{A}_{1,1} \end{bmatrix}$ ,

把矩阵 $\mathbf{B}$ 划分为

$\mathbf{B}=\begin{bmatrix} \mathbf{B}_{0,0}&\mathbf{B}_{0,1}\\ \mathbf{B}_{1,0}&\mathbf{B}_{1,1} \end{bmatrix}$ ,

则 $\mathbf{A}\mathbf{B}$ 可表示为

$\mathbf{A}\mathbf{B}=\begin{bmatrix} \mathbf{A}_{0,0}\mathbf{B}_{0,0}+\mathbf{A}_{0,1}\mathbf{B}_{1,0}&\mathbf{A}_{0,0}\mathbf{B}_{0,1}+\mathbf{A}_{0,1}\mathbf{B}_{1,1}\\ \mathbf{A}_{1,0}\mathbf{B}_{0,0}+\mathbf{A}_{1,1}\mathbf{B}_{1,0}&\mathbf{A}_{1,0}\mathbf{B}_{0,1}+\mathbf{A}_{1,1}\mathbf{B}_{1,1} \end{bmatrix}$ ,

令

$\tilde{\mathbf{A}}_i=\mathbf{A}_{0,0}+\mathbf{A}_{0,1}x_i+\mathbf{A}_{1,0}x_i^2+\mathbf{A}_{1,1}x_i^3$ ,

$\tilde{\mathbf{B}}_i=\mathbf{B}_{0,0}x_i^a+\mathbf{B}_{0,1}x_i^b+\mathbf{B}_{1,0}x_i^c+\mathbf{B}_{1,1}x_i^d$ ,

则

$\tilde{\mathbf{A}}_i\tilde{\mathbf{B}}_i=(\mathbf{A}_{0,0}\mathbf{B}_{0,0}+\mathbf{A}_{0,1}\mathbf{B}_{1,0})x_i^2+ (\mathbf{A}_{0,0}\mathbf{B}_{0,1}+\mathbf{A}_{0,1}\mathbf{B}_{1,1})x_i^6+ (\mathbf{A}_{1,0}\mathbf{B}_{0,0}+\mathbf{A}_{1,1}\mathbf{B}_{1,0})x_i^3+ (\mathbf{A}_{1,0}\mathbf{B}_{0,1}+\mathbf{A}_{1,1}\mathbf{B}_{1,1})x_i^7+ \mathbf{A}_{0,0}\mathbf{B}_{1,0}+(\mathbf{A}_{0,0}\mathbf{B}_{1,1}+\mathbf{A}_{0,1}\mathbf{B}_{0,0})x_i^4+\mathbf{A}_{0,1}\mathbf{B}_{0,1}x_i^8+\mathbf{A}_{1,0}\mathbf{B}_{1,0}x_i+(\mathbf{A}_{1,0}\mathbf{B}_{1,1}+\mathbf{A}_{1,1}\mathbf{B}_{0,0})x_i^5+\mathbf{A}_{1,1}\mathbf{B}_{0,1}x_i^9$ ,

它可以看作degree为9的多项式

$p(x)=(\mathbf{A}_{0,0}\mathbf{B}_{0,0}+\mathbf{A}_{0,1}\mathbf{B}_{1,0})x^2+ (\mathbf{A}_{0,0}\mathbf{B}_{0,1}+\mathbf{A}_{0,1}\mathbf{B}_{1,1})x^6+ (\mathbf{A}_{1,0}\mathbf{B}_{0,0}+\mathbf{A}_{1,1}\mathbf{B}_{1,0})x^3+ (\mathbf{A}_{1,0}\mathbf{B}_{0,1}+\mathbf{A}_{1,1}\mathbf{B}_{1,1})x^7+ \mathbf{A}_{0,0}\mathbf{B}_{1,0}+(\mathbf{A}_{0,0}\mathbf{B}_{1,1}+\mathbf{A}_{0,1}\mathbf{B}_{0,0})x^4+\mathbf{A}_{0,1}\mathbf{B}_{0,1}x^8+\mathbf{A}_{1,0}\mathbf{B}_{1,0}x+(\mathbf{A}_{1,0}\mathbf{B}_{1,1}+\mathbf{A}_{1,1}\mathbf{B}_{0,0})x^5+\mathbf{A}_{1,1}\mathbf{B}_{0,1}x^9$

在 $x_i$ 点的估值,因此用户最少只需要得到 $p(x)$ 在10个点的估值就可以使用多项式插值得到 $x^2,x^6,x^3,x^7$ 的系数,即 $\mathbf{A}\mathbf{B}$ 的4个分块,所以该方案的恢复阈值为10. [1]中的方案的恢复阈值为9,感兴趣可自行参阅.

此外,[1]中证明如果矩阵被划分为块,矩阵被划分为块,采用线性编码方案的恢复阈值满足 $R\ge \min\{N,pmn+p-1\}$ ,并提出了达到该下界的方案,称作entangled polynomial code.

[1] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Straggler mitigation in distributed matrix multiplication: Fundamental limits and optimal coding,” IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1920–1933, Mar. 2020.

深开鸿技术专区

更多推荐

【ShiMetaPi M4-R1】上手：RK3568B2 |开源鸿蒙（OpenHarmony) 开发板上手指南

深开鸿技术专区

波音787项目：AR技术重塑航空制造的数字化转型

深开鸿技术专区

三、计算机网络与分布式系统（上）

本文系统介绍了计算机网络基础知识与协议体系。第一部分讲解数据通信基础，包括信道特性、数据编码方式和差错控制技术（奇偶校验、海明码、CRC）。第二部分详细解析网络体系结构，重点对比OSI七层模型与TCP/IP协议簇，涵盖IP、TCP、UDP等核心协议的工作原理及特点。第三部分深入探讨网络地址管理，包括IPv4分类、子网划分、超网构造技术（CIDR）以及IPv6的优势与过渡方案。全文通过理论阐述与实例