并行算法 - 矩阵乘法
矩阵是按固定行数和列数排列的一组数值和非数值数据。 矩阵乘法是并行计算中重要的乘法设计。 在这里,我们将讨论矩阵乘法在网格和超立方体等各种通信网络上的实现。 网状网络和超立方体具有更高的网络连接性,因此它们比其他网络(如环网)允许更快的算法。
网状网络
一组节点形成 p 维网格的拓扑称为网状拓扑。 这里,所有的边都平行于网格轴,并且所有相邻的节点都可以相互通信。
节点总数=(行中节点数)×(列中节点数)
网状网络可以使用以下因素进行评估 −
- 直径
- 二分宽度
直径 − 在网状网络中,两个节点之间的最长距离是其直径。 具有 kP 个节点的 p 维网状网络的直径为 p(k–1)。
二等分宽度 − 二分宽度是将网状网络分成两半所需的最小边数。
使用网状网络进行矩阵乘法
我们考虑了具有环绕连接的 2D 网状网络 SIMD 模型。 我们将设计一种算法,在特定时间内使用 n2 个处理器将两个 n × n 数组相乘。
矩阵 A 和 B 分别具有元素 aij 和 bij。 处理元素PEij表示aij和bij。 排列矩阵 A 和 B,使每个处理器都有一对要相乘的元素。 矩阵A的元素将向左移动,矩阵B的元素将向上移动。 矩阵 A 和 B 中元素位置的这些变化代表每个处理元素 PE,一对要相乘的新值。
算法步骤
- 交错两个矩阵。
- 计算所有乘积 aik × bkj
- 完成第 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
- 二分宽度 = 2k–1
- 边数 = k
使用超立方网络的矩阵乘法
超立方网络的通用规范 −
令 N = 2m 为处理器总数。 令处理器为 P0, P1…..PN-1。
设i和ib为两个整数,0 < i,ib < N-1及其二进制表示形式仅在位置b、0 < b < k–1上不同。
让我们考虑两个n × n矩阵,矩阵 A 和矩阵 B。
步骤 1 − 矩阵 A 和矩阵 B 的元素被分配给 n3 个处理器,使得位置 i、j、k 的处理器将具有 aji 和 bik。
步骤 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。
分块矩阵
块矩阵或分区矩阵是一个矩阵,其中每个元素本身代表一个单独的矩阵。 这些单独的部分称为块或子矩阵。
示例
![分块矩阵](/parallel_algorithm/images/block_matrix.jpg)
![分块矩阵 1](/parallel_algorithm/images/block_matrix1.jpg)
在图(a)中,X是分块矩阵,其中A、B、C、D本身就是矩阵。 图(f)显示了总矩阵。
块矩阵乘法
当两个分块矩阵是方阵时,它们的乘法就像我们执行简单矩阵乘法一样。 例如,
![块矩阵乘法](/parallel_algorithm/images/block_matrix_multiplication.jpg)