并行算法 - 矩阵乘法

矩阵是按固定行数和列数排列的一组数值和非数值数据。 矩阵乘法是并行计算中重要的乘法设计。 在这里，我们将讨论矩阵乘法在网格和超立方体等各种通信网络上的实现。 网状网络和超立方体具有更高的网络连接性，因此它们比其他网络(如环网)允许更快的算法。

网状网络

一组节点形成 p 维网格的拓扑称为网状拓扑。 这里，所有的边都平行于网格轴，并且所有相邻的节点都可以相互通信。

节点总数=(行中节点数)×(列中节点数)

网状网络可以使用以下因素进行评估 −

• 直径
• 二分宽度

直径 − 在网状网络中，两个节点之间的最长距离是其直径。 具有 kP 个节点的 p 维网状网络的直径为 p(k–1)。

二等分宽度 − 二分宽度是将网状网络分成两半所需的最小边数。

使用网状网络进行矩阵乘法

我们考虑了具有环绕连接的 2D 网状网络 SIMD 模型。 我们将设计一种算法，在特定时间内使用 n² 个处理器将两个 n × n 数组相乘。

矩阵 A 和 B 分别具有元素 a_ij 和 b_ij。 处理元素PE_ij表示a_ij和b_ij。 排列矩阵 A 和 B，使每个处理器都有一对要相乘的元素。 矩阵A的元素将向左移动，矩阵B的元素将向上移动。 矩阵 A 和 B 中元素位置的这些变化代表每个处理元素 PE，一对要相乘的新值。

算法步骤

• 交错两个矩阵。
• 计算所有乘积 a_ik × b_kj
• 完成第 2 步后计算总和。

算法

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

超立方网络

超立方体是一种 n 维构造，其中边相互垂直且长度相同。 n 维超立方体也称为 n 立方体或 n 维立方体。

具有 2^k 个节点的超立方体的功能

• 直径 = k
• 二分宽度 = 2^k–1
• 边数 = k

使用超立方网络的矩阵乘法

超立方网络的通用规范 −

• 令 N = 2^m 为处理器总数。 令处理器为 P_0, P₁…..P_N-1。

• 设i和i^b为两个整数，0 < i,i^b < N-1及其二进制表示形式仅在位置b、0 < b < k–1上不同。

• 让我们考虑两个n × n矩阵，矩阵 A 和矩阵 B。

• 步骤 1 − 矩阵 A 和矩阵 B 的元素被分配给 n³ 个处理器，使得位置 i、j、k 的处理器将具有 a_ji 和 b_ik。

• 步骤 2 − 所有位置 (i,j,k) 的处理器都计算乘积

  C(i,j,k) = A(i,j,k) × B(i,j,k)

• 步骤 3 − C(0,j,k) = ΣC(i,j,k) 与 0 ≤ i ≤ n-1 之和，其中 0 ≤ j, k < n–1。

分块矩阵

块矩阵或分区矩阵是一个矩阵，其中每个元素本身代表一个单独的矩阵。 这些单独的部分称为块或子矩阵。

示例

在图(a)中，X是分块矩阵，其中A、B、C、D本身就是矩阵。 图(f)显示了总矩阵。

块矩阵乘法

当两个分块矩阵是方阵时，它们的乘法就像我们执行简单矩阵乘法一样。 例如，