矩阵-向劣肟并行乘法算法 .ppt

矩阵-向量并行乘法算法 S 张秀清 矩阵-向量乘法思想： 矩阵-向量乘法是将一个n*n阶矩阵A=[aij]乘以n*1的向量B=[b1,b2,…bn]T，得到一个具有n个元素的列向量C=[c1, c2,…cn]T。假设一次乘法和加法运算时间为一个单位时间， 则矩阵向量乘法算法的时间复杂度是O(n2)。 矩阵-向量乘法的串行算法： 算法 单处理器上矩阵-向量乘算法 输入：An*n,Bn*1 输出：Cn*1 Begin for i=0 to n-1 do c[i]=0 for j=0 to n-1 do c[i]=c[i]+a[i,j]*b[j] end for end for End 矩阵-向量乘法的并行算法： 矩阵-向量乘法同样可以有带状划分和棋盘划分两种并行算法， 这里仅讨论行带划分矩阵-向量乘法，列带划分矩阵-向量乘法 是类似的。设处理器，个数为，对矩阵按行划分为块，每块含 有连续的行向量，这些行块依次记为，分别存放在标号为的处 理器中，同时将向量广播给所有处理器。个处理器并行地对存 于局部数组中的行块和向量做乘积操作，具体并行算法框架描 述如下： 矩阵-向量乘并行算法： 算法 行带状划分的矩阵-向量乘并行算法 输入: An*n,Bn*1 输出: Cn*1 Begin 对所有处理器同时执行如下的算法: for i=0 to m-1 do c[i]=0.0 for j=0 to n-1 do c[i]=c[i]+a[i,j]*b[j] end for end for End * *