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

矩阵乘法并行算法分析,矩阵乘法的串行算法 矩阵乘法的并行算法 块矩阵乘法中常用算法分析 实验 总结,矩阵乘法的串行算法,基本计算方式 算法实现 算法分析,矩阵乘法的串行算法,基本计算方式： 算法实现： for (i=0; in; i+) for (j=0; jn; j+) for (l=0; ln; l+) cij=cij+aik*bkj；,矩阵乘法的串行算法,算法分析： 该算法需要进行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语言中，有两种方法支持多线程技术： a) 通过对Thread类的继承 b) 通过实现Runnable接口的方法 两种方法的共同点：都要实现一个run()方法，当线程启动后，便进入run()方法，执行其中的代码。,实验,程序说明 程序中通过继承Runable接口来实现，原因在于Java类只能单继承，如果采用第一种方法，即继承了Thread类后，就不能再继承其他的类了，使得程序丧失了灵活性。而通过实现Runnable接口的方法，可以很好的解决这个问题。,实验,程序实现 构造了一个conMatrix 的矩阵类用于初始化矩阵(矩阵用二维数组表示)。 构造了继承自conMatrix的Matrix类，并在类中实现Runable接口。 通过矩阵相乘方法“chengfa(,int n)”中的第3个参数n，来决定将这两个矩阵分成多少个子块进行计算。并通过获得运算前后系统时间来得到运算的时间，显示在运算结果后。,实验,程序实现 在Matrix类启动线程，在其run()方法中调用chengfa()得到运算时间。 由于本程序中所有子矩阵块的计算都一样，所以只启动了一个线程，通过该线程的运行时间便可以得出并行条件下的程序执行时间。 通过比较不同分块下的执行时间，证明并行算法确实能提高乘法执行的效率。,总结,通过实验结果证明了