矩阵乘法并行算法分析

《矩阵乘法并行算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、矩阵乘法并行算法分析矩阵乘法的串行算法矩阵乘法的并行算法块矩阵乘法中常用算法分析实验总结矩阵乘法的串行算法基本计算方式算法实现算法分析矩阵乘法的串行算法基本计算方式：算法实现：for(i=0;i

2、每一次迭代不依赖于其他任何迭代，并且内层循环的各个步骤可以并行执行。矩阵乘法的并行算法解决手段：引入多个处理器：当用n个处理器进行n*n矩阵乘法时，可以容易的获得并行的时间复杂度为O(n2)。用n2个处理器时时间复杂度为O(n)。缺点：虽然引用多处理器可降低时间复杂度，但降低的时间复杂度是针对计算而言，增加处理器会导致显著的通信开销的增加。实际中一般结合块矩阵实现。划分成子矩阵：通过块矩阵乘法实现。矩阵乘法的并行算法块矩阵乘法：将矩阵划分为若干子矩阵，子矩阵作为单个矩阵元素参与运算，假设分为s2个子矩阵（行列s等分），每个子矩阵有n/s*n/s个元素

3、，若用Ap,q表示第p行第q列的子矩阵，则算法如下：for(p=0;p

4、理机，Pj表示第j个处理机，Pmyid表示当前运行程序的处理机，send(x，j)和recv(x，j)分别表示在Pmyid中把x传送到Pj和从Pj中接收x。讨论的算法都是在Pmyid处理机上的。用imodp表示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中，这种存放方式使数据在处理机种

5、不重复。块矩阵乘法中常用算法分析行列划分算法由于使用p个处理机,每次每台处理机计算出一个Ci,j，计算C需要p次来完成。Ci,j的计算是按对角线进行的，计算方法如下：for(i=0;i

6、-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行，列。由于二者的计算量相同，因此按交换量大小即可选择高效算法。块矩阵乘法中常用算法分析其它算法除

7、上述算法外，还可以通过Canon算法或是递归算法来实现块矩阵并行计算，由于篇幅原因，在此不作详细介绍，具体可以参见课本。实验Java并行计算原理程序说明程序实现实验Java并行计算原理程序是通过多线程(在多cpu机上)实现运算的并行，操作系统将线程映射到cpu上。Java语言中，有两种方法支持多线程技术：a)通过对Thread类的继承b)通过实现Runnable接口的方法两种方法的共同点：都要实现一个run()方法，当线程启动后，便进入run()方法，执行其中的代码。实验程序说明程序中通过继承Runable接口来实现，原因在于Java类只能单继承，如

8、果采用第一种方法，即继承了Thread类后，就不能再继承其他的类了，使得程序丧失了灵活性。而通过实现Runn