矩阵乘法并行算法分析矩阵乘法的串行算法矩阵乘法的并行算法块矩阵乘法中常用算法分析实验总结矩阵乘法的串行算法矩阵乘法的串行算法矩阵乘法的串行算法矩阵乘法的并行算法矩阵乘法的并行算法D行，列=2*k*(n-n’)，C行，列=m*k*n/p。将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵:for(i=0;i<n;i++)并行在多CPU环境下才能得到充分的体现，由于实验室没有多CPU环境，因此在程序中仅模拟了多CPU环境下的单CPU的执行过程，得到执行时间。Cp,q=Cp,q+Ap,r*Br,q表示利用矩阵乘法将子矩阵Ap,r和Br,q相乘，再利用矩阵加法将乘积累加到子矩阵Cp,q上。划分成子矩阵：通过块矩阵乘法实现。c[i][j]=c[i][j]+a[i][k]*b[k][j]；由于本程序中所有子矩阵块的计算都一样，所以只启动了一个线程，通过该线程的运行时间便可以得出并行条件下的程序执行时间。b)通过实现Runnable接口的方法该算法中的数据交换量与计算量和行列划分算法相同。用n2个处理器时时间复杂度为O(n)。块矩阵乘法：将矩阵划分为若干子矩阵，子矩阵作为单个矩阵元素参与运算，假设分为s2个子矩阵〔行列s等分），每个子矩阵有n/s*n/s个元素，若用Ap,q表示第p行第q列的子矩阵，则算法如下：for(i=0;i<n;i++)Cp,q=Cp,q+Ap,r*Br,q；用imodp表示i对p取模运算。矩阵乘法的并行算法矩阵乘法的并行算法b)通过实现Runnable接口的方法块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析缺陷：虽然引用多处理器可降低时间复杂度，但降低的时间复杂度是针对计算而言，增加处理器会导致显著的通信开销的增加。Java语言中，有两种方法支持多线程技术：Cp,q=Cp,q+Ap,r*Br,q；除上述算法外，还可以通过Canon算法或是递归算法来实现块矩阵并行计算，由于篇幅原因，在此不作详细介绍，具体可以参见课本。程序是通过多线程(在多cpu机上)实现运算的并行，操作系统将线程映射到cpu上。如果用D行，列表示算法中数据的交换量，C行，列表示算法中的计算量，则有：算法中使用的参数命名约定：将矩阵A和B分别划分为如下的行块子矩阵和列块子矩阵:该算法中的数据交换量与计算量和行列划分算法相同。数据的交换量大小是由m和n决定的，当m<=n时，D列，列<=D行，列。当处理器数目小于n时，该方法是所有并行实现的核心。设设m=m’*p，k=k’*p和n=n’*p。块矩阵乘法：将矩阵划分为若干子矩阵，子矩阵作为单个矩阵元素参与运算，假设分为s2个子矩阵〔行列s等分），每个子矩阵有n/s*n/s个元素，若用Ap,q表示第p行第q列的子矩阵，则算法如下：用n2个处理器时时间复杂度为O(n)。块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析块矩阵乘法中常用算法分析实验实验实验实验实验总结谢谢