多维环面网络上的矩阵乘法

### 多维环面网络上的矩阵乘法 在多维环面网络中进行矩阵乘法是一个重要的研究领域，本文将介绍几种相关的算法，包括矩阵布局、SUMMA算法、Cannon算法、分裂维度的Cannon算法，并对它们的通信成本进行分析，最后给出实验结果。 #### 1. 矩阵布局 矩阵是二维数据数组，为了实现负载均衡，需要将二维数组嵌入到高维环面网络中。这里不考虑数据复制的算法。对于任意的 $l$ 元 $d$ 立方体 $\Pi_{dD}$（$d$ 是 2 的倍数），可以将其嵌入到一个正方形二维网格中。具体做法是将 $d$ 个维度中的奇数 $d/2$ 维度折叠到正方形网格的一个维度，偶数 $d/2$ 维度折叠到另一个维度。 对于一个具有 $d$ 维索引 $I_d \in \{0, 1, \ldots, l - 1\}^d$ 的处理器，其二维索引 $(i, j)$ 的嵌入定义为： $G_{dD\rightarrow2D}[I_d] = \begin{pmatrix} \sum_{i = 0}^{d/2 - 1} l^i I_d[2i], \sum_{i = 0}^{d/2 - 1} l^i I_d[2i + 1] \end{pmatrix}$ 我们用 $\Pi_{dD}[I_d]$ 表示具有网格索引 $I_d$ 的处理器。 #### 2. 相关算法 ##### 2.1 SUMMA算法 SUMMA算法利用行和列多播来进行并行矩阵乘法。该算法基于二维网格，每个进程拥有矩阵 $A$、$B$ 和 $C$ 的一个块。在每一步，算法执行 $A$ 和 $B$ 部分的外积。 算法步骤如下： ```plaintext Algorithm 1. [C] = SUMMA(A, B, C, n, m, k, Π2D) Input: m × k matrix A, k × n matrix B distributed so that Π2D[i, j] owns m/√p × k/√p sub - matrix A[i, j] and k/√p × n/√p sub - matrix B[i, j], for each i, j ∈[0, √p - 1] Output: square m × n matrix C = A · B distributed so that Π2D[i, j] owns m/√p × n/√p block sub - matrix C[i, j], for each i, j ∈[0, √p - 1] //In parallel with all processors for all i, j ∈[0, √p - 1] do for t = 1 to t = √p do Multicast A[i, t] along rows of Π2D Multicast B[t, j] along columns of Π2D C[i, j] := C[i, j] + A[i, t] · B[t, j] end end ``` SUMMA算法通过多播进行所有通信，其通信性能取决于架构上多播的性能。在环面网络架构上，最有效的多播方式是使用矩形集合通信，它利用整个处理器网格的边不相交生成树。 ##### 2.2 Cannon算法 Cannon算法是一种并行矩阵乘法算法，它通过在处理器网格的列和行之间移动块来实现。算法首先分别将 $A$ 和 $B$ 的块向左和向上错开，然后分别将 $A$ 和 $B$ 的块向右和向下移动。 算法步骤如下： ```plaintext Algorithm 2. [C] = Cannon(A, B, C, n, m, k, p, Π2D) Input: m × k matrix A, k × n matrix B distributed so that Π2D[i, j] owns m/√p × k/√p sub - matrix A[i, j] and k/√p × n/√p sub - matrix B[i, j], for each i, j ∈[0, √p - 1] Output: square m × n matrix C = A · B distributed so that Π2D[i, j] owns m/√p × n/√p block sub - matrix C[i, j], for each i, j ∈[0, √p - 1] //In parallel with all processors for all i, j ∈[0, √p - 1] do for t = 1 to √p - 1 do if t ≤ i then A[i, j] ← A[i, ((j + 1) mod √p)] /** */ [f]stagger A end if t ≤ j then B[i, j] ← B[((i + 1) mod √p), j] /** */ [f]stagger B end end C[i, j] := A[i, j] · B[i, j] for t = 1 to √p - 1 do A[i, j] ← A[i, ((j - 1) mod √p)] /** */ [f]shift A rightwards B[i, j] ← B[((i - 1) mod √p), j] /** */ [f]shift B downwards C[i, j] := C[i, j] + A[i, j] · B[i, j] end end ``` 当将 $d$ 维网格嵌入到二维网格后，可以按照有序的二维处理器网格分布矩阵来运行Cannon算法。但在这个嵌入网络中，Cannon算法只能利用 $1/d$ 的链路。 ##### 2.3 分裂维度的Cannon算法（SD - Cannon） 分裂维度的Cannon算法通过更多的维度移动来实现。每个处理器通过单个链路向相邻处理器发送单个消息来完成移动。由于移动是沿着 $l$ 元 $d$ 立方体网络的维度进行的，因此有 $2d$ 条链路可用。 以下是相关算法： ```plaintext Algorithm 3. Shift< dim, dir >(l, M, p, ΠdD, Id) Input: ΠdD[Id] owns sub - matrix M. Sd ← Id if dir = +1 then ```