13行列划分矩阵乘法 个m×n阶矩阵A=[a乘以一个n×k的矩阵B=[b就可以得到一个m×k的矩阵 C=[c],它的元素c为A的第i行向量与B的第j列向量的内积。矩阵相乘的关键是相乘的 两个元素的下标要满足一定的要求(即对准)。为此常采用适当旋转矩阵元素的方法(如后面将 要阐述的 Cannon乘法),或采用适当复制矩阵元素的办法(如DNS算法),或采用流水线的 办法使元素下标对准,后两种方法读者可参见文献[]l 131矩阵相乘及其串行算法 由矩阵乘法定义容易给出其串行算法18.5,若一次乘法和加法运算时间为一个单位时 间,则显然其时间复杂度为O(mk) 算法18.5单处理器上矩阵相乘算法 输入:Amxn,Bn×k 输出:C for i=0 to m-1 do for j=0 to k-l do for 0 to n-l do c{=c[i/+a[i]*b[r引 132简单的矩阵并行分块乘法算法 矩阵乘法也可以用分块的思想实现并行,即分块矩阵乘法( Block Matrix Multiplication) 将矩阵A按行划分为P块(P为处理器个数),设u=「m/p,每块含有连续的u行向量,这些 行块依次记为A0A1,…,41,分别存放在标号为0,1,…,p-1的处理器中。对矩阵B按列划分 为P块,记v=[k/p,每块含有连续的v列向量,这些列块依次记为BnB,…Bn1,分别 存放在标号0,1,…p1为的处理器中。将结果矩阵C也相应地同时进行行、列划分,得到 pXP个大小为u×v的子矩阵,记第i行第j列的子矩阵为C,显然有C=A,XB,其中, A1大小为a×n,B大小为n×v 「处理器编号存储内容 存储内容 Ar Bll PI 图12矩阵相乘并行算法中的数据交换1.3 行列划分矩阵乘法 一个 m×n 阶矩阵 A=[aij]乘以一个 n×k 的矩阵 B=[bij]就可以得到一个 m×k 的矩阵 C=[cij]，它的元素 cij 为 A 的第 i 行向量与 B 的第 j 列向量的内积。矩阵相乘的关键是相乘的 两个元素的下标要满足一定的要求(即对准)。为此常采用适当旋转矩阵元素的方法(如后面将 要阐述的 Cannon 乘法)，或采用适当复制矩阵元素的办法(如 DNS 算法)，或采用流水线的 办法使元素下标对准，后两种方法读者可参见文献[1]。 1.3.1 矩阵相乘及其串行算法 由矩阵乘法定义容易给出其串行算法 18.5，若一次乘法和加法运算时间为一个单位时 间，则显然其时间复杂度为 O(mnk) 。 算法 18.5 单处理器上矩阵相乘算法 输入：Am×n，Bn×k 输出：Cm×k Begin for i=0 to m-1 do for j=0 to k-1 do c[i,j]=0 for r=0 to n-1 do c[i,j]= c[i,j]+a[i,r]*b[r,j] end for end for end for End 1.3.2 简单的矩阵并行分块乘法算法 矩阵乘法也可以用分块的思想实现并行，即分块矩阵乘法(Block Matrix Multiplication)， 将矩阵 A 按行划分为 p 块(p 为处理器个数)，设 u = m/ p ，每块含有连续的 u 行向量，这些 行块依次记为 A0,A1, …,Ap-1，分别存放在标号为 0,1,…, p-1 的处理器中。对矩阵 B 按列划分 为 P 块，记 v = k / p ，每块含有连续的 v 列向量，这些列块依次记为 B0,B1, …,Bp-1，分别 存放在标号 0,1, …, p-1 为的处理器中。将结果矩阵 C 也相应地同时进行行、列划分，得到 p×p 个大小为 u×v 的子矩阵，记第 i 行第 j 列的子矩阵为 Cij，显然有 Cij= Ai×Bj，其中， A i 大小为 u×n，Bj 大小为 n×v。 A0 处理器编号 存储内容 B0 0 A1 B1 A2 B2 Ap-1 Bp-1 1 2 P-1 … … … (a) A0 处理器编号 存储内容 B1 0 A1 B2 A2 B3 Ap-1 B0 1 2 P-1 … … … (b) 图 1.2 矩阵相乘并行算法中的数据交换