矩阵乘法并行算法分析教材.ppt

矩阵乘法并行算法分析 矩阵乘法的串行算法 矩阵乘法的并行算法 块矩阵乘法中常用算法分析 实验 总结 矩阵乘法的串行算法 基本计算方式 算法实现 算法分析 矩阵乘法的串行算法 基本计算方式： 算法实现： for (i=0; in; i++) for (j=0; jn; j++) for (l=0; ln; l++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； 矩阵乘法的串行算法 算法分析： 该算法需要进行n3个乘法运算和n3个加法运算，顺序代码的时间复杂度为O(n3)。 矩阵乘法的并行算法 引入原因 解决手段 块矩阵算法 矩阵乘法的并行算法 引入原因： 通过观察串行算法，可以发现两个外层循环的每一次迭代不依赖于其他任何迭代，并且内层循环的各个步骤可以并行执行。 矩阵乘法的并行算法 解决手段： 引入多个处理器：当用n个处理器进行n*n矩阵乘法时，可以容易的获得并行的时间复杂度为O(n2)。用n2个处理器时时间复杂度为O (n)。 缺点：虽然引用多处理器可降低时间复杂度，但降低的时间复杂度是针对计算而言，增加处理器会导致显著的通信开销的增加。实际中一般结合块矩阵实现。 划分成子矩阵：通过块矩阵乘法实现。 矩阵乘法的并行算法 块矩阵乘法：将矩阵划分为若干子矩阵，子矩阵作为单个矩阵元素参与运算，假设分为s2个子矩阵（行列s等分），每个子矩阵有n/s*n/s个元素，若用Ap,q表示第p行第q列的子矩阵，则算法如下： for (p=0; ps; p++) for (q=0; qs; q++) for (r=0; rm; r++) Cp,q=Cp,q+Ap,r*Br,q； 矩阵乘法的并行算法 说明： Cp,q=Cp,q+Ap,r*Br,q表示利用矩阵乘法将子矩阵Ap,r和Br,q相乘，再利用矩阵加法将乘积累加到子矩阵Cp,q上。 当处理器数目小于n时，该方法是所有并行实现的核心。 矩阵乘法的并行算法 块矩阵乘法示例： 块矩阵乘法中常用算法分析 行列划分算法 行行划分算法 列列划分算法 其它算法 块矩阵乘法中常用算法分析 算法中使用的参数命名约定： 假设有p个处理机，Pj表示第j个处理机，Pmyid表示当前运行程序的处理机，send(x，j) 和recv(x，j)分别表示在Pmyid中把x传送到Pj和从Pj中接收x。讨论的算法都是在Pmyid处理机上的。用i mod p表示i对p取模运算。 A和B分别是m*k和k*n矩阵，C是m*n矩阵。设设m=m’*p，k=k’*p和n=n’*p。 主要讨论实验中使用的行列划分算法。 块矩阵乘法中常用算法分析 行列划分算法 将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵: Ci,j=Ai*Bj，其中Ci,j是m’*n’矩阵，Ai、Bi和Ci,j存放在Pi中，这种存放方式使数据在处理机种不重复。 块矩阵乘法中常用算法分析 行列划分算法 由于使用p个处理机, 每次每台处理机计算出一个Ci,j，计算C需要p次来完成。Ci,j的计算是按对角线进行的，计算方法如下： for (i=0; ip-1; i++){ l=i+myid mod p； Cl=A*B； mp1=myid+1 mod p；mm1=myid-1 mod p； if (i!=p-1) { send(B，mm1)；recv(B，mp1);} } 块矩阵乘法中常用算法分析 行列划分算法 算法分析： 在这个算法中，Cl=Cmyid，l，A=Amyid，B在处理机中每次循环向前移动一个处理机，每次交换数据为k*n’矩阵，交换次数为p-1 次。如果用D行，列表示算法中数据的交换量，C行，列表示算法中的计算量，则有： D行，列=2*k*(n-n’)， C行，列=m*k*n/p。 块矩阵乘法中常用算法分析 行行划分算法 将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵： Ci为和相对应的C的第i个块，从而有： 该算法中的数据交换量与计算量和行列划分算法相同。 块矩阵乘法中常用算法分析 列列划分算法 将矩阵A 和B 均划分为列块子矩阵，划分方式如下： 则 数据的交换量大小是由m和n决定的，当m=n时，D列，列=D行，列。由于二者的计算量相同，因此按交换量大小即可选择高效算法。 块矩阵乘法中常用算法分析 其它算法 除上述算法外，还可以通过Canon算法或是递归算法来实现块矩阵并行计算，由于篇幅原因，在此不作详细介绍，具体可以参见课本。 实验 Java并行计算原理 程序说明 程序实现 实验 Java并行计算原理 程序是通过多线程(在多cpu机上)实现运算的并行，操作系统将线程映射到cpu上。 Java语言中，有两种方法支持多线程技术：