并行算法-矩阵乘法

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

网状网络

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

总节点数=（行节点数）×（列节点数）

可以使用以下因素评估网状网络 -

  • 直径
  • 二分宽度

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

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

使用网状网络的矩阵乘法

我们考虑了具有环绕连接的 2D 网状网络 SIMD 模型。我们将设计一种算法，在特定时间内使用 n 2 个处理器将两个 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 维立方体。

2k节点超立方体的特点

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

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

超立方网络的一般规范 -

  • 令N = 2 m为处理器总数。令处理器为 P 0, P 1 …..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 3 个处理器，使得位置 i、j、k 的处理器将具有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。

块矩阵

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

例子

块矩阵 块矩阵1

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

块矩阵乘法

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

块矩阵乘法