矩阵乘法并行算法分析

矩阵乘法并行算法分析第一页，共二十五页，编辑于2023年，星期日矩阵乘法的串行算法矩阵乘法的并行算法块矩阵乘法中常用算法分析实验总结第二页，共二十五页，编辑于2023年，星期日矩阵乘法的串行算法基本计算方式算法实现算法分析第三页，共二十五页，编辑于2023年，星期日矩阵乘法的串行算法基本计算方式：

算法实现：

for(i=0;i<n;i++) for(j=0;j<n;j++) for(l=0;l<n;l++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；第四页，共二十五页，编辑于2023年，星期日矩阵乘法的串行算法算法分析： 该算法需要进行n3个乘法运算和n3个加法运算，顺序代码的时间复杂度为O(n3)。第五页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法引入原因解决手段块矩阵算法第六页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法引入原因： 通过观察串行算法，可以发现两个外层循环的每一次迭代不依赖于其他任何迭代，并且内层循环的各个步骤可以并行执行。第七页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法解决手段：引入多个处理器：当用n个处理器进行n*n矩阵乘法时，可以容易的获得并行的时间复杂度为O(n2)。用n2个处理器时时间复杂度为O(n)。 缺点：虽然引用多处理器可降低时间复杂度，但降低的时间复杂度是针对计算而言，增加处理器会导致显著的通信开销的增加。实际中一般结合块矩阵实现。划分成子矩阵：通过块矩阵乘法实现。第八页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法块矩阵乘法：将矩阵划分为若干子矩阵，子矩阵作为单个矩阵元素参与运算，假设分为s2个子矩阵（行列s等分），每个子矩阵有n/s*n/s个元素，若用Ap,q表示第p行第q列的子矩阵，则算法如下：

for(p=0;p<s;p++) for(q=0;q<s;q++) for(r=0;r<m;r++) Cp,q=Cp,q+Ap,r*Br,q；第九页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法说明：

Cp,q=Cp,q+Ap,r*Br,q表示利用矩阵乘法将子矩阵Ap,r和Br,q相乘，再利用矩阵加法将乘积累加到子矩阵Cp,q上。当处理器数目小于n时，该方法是所有并行实现的核心。第十页，共二十五页，编辑于2023年，星期日矩阵乘法的并行算法块矩阵乘法示例：第十一页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析行列划分算法行行划分算法列列划分算法其它算法第十二页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析算法中使用的参数命名约定： 假设有p个处理机，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。主要讨论实验中使用的行列划分算法。第十三页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析行列划分算法 将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵:Ci,j=Ai*Bj，其中Ci,j是m’*n’矩阵，Ai、Bi和Ci,j存放在Pi中，这种存放方式使数据在处理机种不重复。第十四页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析行列划分算法

由于使用p个处理机,每次每台处理机计算出一个Ci,j，计算C需要p次来完成。Ci,j的计算是按对角线进行的，计算方法如下：

for(i=0;i<p-1;i++){ l=i+myidmodp；

Cl=A*B；

mp1=myid+1modp；mm1=myid-1modp；

if(i!=p-1){send(B，mm1)；recv(B，mp1);} }第十五页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析行列划分算法算法分析： 在这个算法中，Cl=Cmyid，l，A=Amyid，B在处理机中每次循环向前移动一个处理机，每次交换数据为k*n’矩阵，交换次数为p-1

次。如果用D行，列表示算法中数据的交换量，C行，列表示算法中的计算量，则有：

D行，列=2*k*(n-n’)，C行，列=m*k*n/p。第十六页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析行行划分算法 将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵：Ci为和相对应的C的第i个块，从而有：该算法中的数据交换量与计算量和行列划分算法相同。第十七页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析列列划分算法 将矩阵A和B均划分为列块子矩阵，划分方式如下：则数据的交换量大小是由m和n决定的，当m<=n时，D列，列<=D行，列。由于二者的计算量相同，因此按交换量大小即可选择高效算法。第十八页，共二十五页，编辑于2023年，星期日块矩阵乘法中常用算法分析其它算法 除上述算法外，还可以通过Canon算法或是递归算法来实现块矩阵并行计算，由于篇幅原因，在此不作详细介绍，具体可以参见课本。第十九页，共二十五页，编辑于2023年，星期日实验Java并行计算原理程序说明程序实现第二十页，共二十五页，编辑于2023年，星期日实验Java并行计算原理程序是通过多线程(在多cpu机上)实现运算的并行，操作系统将线程映射到cpu上。Java语言中，有两种方法支持多线程技术：

a)通过对Thread类的继承

b)通过实现Runnable接口的方法两种方法的共同点：都要实现一个run()方法，当线程启动后，便进入run()方法，执行其中的代码。第二十一页，共二十五页，编辑于2023年，星期日实验程序说明程序中通过继承Runable接口来实现，原因在于Java类只能单继承，如果采用第一种方法，即继承了Thread类后，就不能再继承其他的类了，使得程序丧失了灵活性。而通过实现Runnable接口的方法，可以很好的解决这个问题。第二十二页，共二十五页，编辑于2023年，星期日实验程序实现构造了一个conMatrix的矩阵类用于初始化矩阵(矩阵用二维数组表示)。构造了继承自conMatrix的Matrix类，并在类中实现Runable接口。通过矩阵相乘方法“chengfa(…,intn)”中的第3个参数n，来决定将这两个矩阵分成多少个子块进行计算。并通过获得运算前后系统时间来得到运算的时间，显示在运算结果后。第二十三页，共二十五页，编辑于2023年，星期日实验程序实现在Matrix类启动线程，在其run()方法中调用chengfa()得到运算时间。由于本程序中所有子矩阵块的计算都一样，所以只启动了一个线程，通过该线程的运行时间便可以得出并行条件下的程序执行时间。通过比较不同分块下的执行时间，证明并行算法确实能提高乘法执行的效率。第二十四页，共二十五页，编辑于2023年，星期