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

article/2025/9/19 18:25:21

许多现代分布式计算框架都会遇到大规模分布式矩阵乘法问题，即计算两个大规模矩阵 $\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{AB}$ ，从而缓和（mitigate）掉队效应。

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

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

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

3.解码（Decoding）：主节点收到节点集合 $\mathcal{R}$ (大小为R)中的工作节点的计算结果后，使用按照函数集 $\boldsymbol{d}=\{d_\mathcal{R}:\mathcal{R}\subseteq[N]\}$ 解码出 $\mathbf{AB}=d_\mathcal{R}(\{\mathbf{\tilde{A}}_i\mathbf{\tilde{B}}_i:i\in\mathcal{R}\})$ 。

计算策略 $(\boldsymbol{f},\boldsymbol{g},\boldsymbol{d})$ 下，集合 $\mathcal{R}$ 的大小R称作恢复阈值（recovery threshold）。最优恢复阈值定义为 $R^*\triangleq\min_{(\boldsymbol{f},\boldsymbol{g},\boldsymbol{d})\in\mathcal{L}} R(\boldsymbol{f},\boldsymbol{g},\boldsymbol{d})$ ，其中 $\mathcal{L}$ 表示所有可行策略的集合。