资源描述：
《第六讲矩阵计算并行算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六讲矩阵计算并行算法1主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法2并行算法基础知识一些基本概念加速比其中Ts串行程序运行时间，Tp(q)为q个进程的运行时间并行效率3程序性能优化串行程序性能优化——并行程序性能优化的基础调用高性能库。如：BLAS、LAPACK、FFTW选择编译器优化选项：-O2、-O3合理定义数组维数注意嵌套循环次数：数据访问的空间局部性和时间局部性数据分块循环展开例:ex4performance.c4程序性能优化并行程序性能优化设计好的并行算法和通信模式减少通信次数、提高通信粒度多进
2、程通信时尽量使用高效率的聚合通信算法负载平衡通信与计算的重叠减少进程的空闲时间通过引入重复计算来减少通信5矩阵并行算法一些记号和假定假设有p个处理器，每个处理器上运行一个进程Pj表示第j个处理器，Pmyid表示当前的处理器send(x;j)表示在Pmyid中把数据块x发送给Pj进程recv(x;j)表示从Pj进程接收数据块ximodp表示i对p取模运算程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用6主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分
3、解并行算法下三角线性方程组的并行算法7矩阵向量乘积串行算法实现方法一：i-j循环fori=1tomy(i)=0.0forj=1tony(i)=y(i)+A(i,j)*x(j)endforendfor8矩阵向量乘积串行算法实现方法二：j-i循环例：ex4matvec.fy=0%先赋初值forj=1tonfori=1tomy(i)=y(i)+A(i,j)*x(j)endforendfor9矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分按行划分并行算法将矩阵A按行划分成如下的行块子矩阵将Ai存放在结点Pi中，每个结点计算Aix，最后调用MPI_GATHER或MPI_GATH
4、ERV即可则10矩阵向量乘积并行算法二按列划分并行算法将Ai和xi存放在结点Pi中，每个结点计算AixiT，最后调用MPI_REDUCE或MPI_ALLREDUCE即可将矩阵A按列划分，并对x也做相应的划分其中xi的长度与Ai的列数相同，则有11矩阵向量乘积示例例：按列划分，用p个进程并行计算矩阵向量乘积，其中示例程序：ex4matvec.f12上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并行程序2、按列划分，编写通用并行程序计算上面的乘积13主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法14矩阵
5、矩阵乘积串行算法一：i-j-k循环fori=1tomforj=1tolC(i,j)=0fork=1tonC(i,j)=C(i,j)+A(i,k)*B(k,j)endforendforendfor15矩阵矩阵乘积串行算法二：j-k-i循环C=0forj=1tolfork=1tonfori=1tomC(i,j)=C(i,j)+A(i,k)*B(k,j)endforendforendfor16并行矩阵乘积假定：基于A、B的不同划分，矩阵乘积的并行算法可分为行列划分行行划分列列划分列行划分m,l,n均能能p整除，其中p为进程个数17行列划分行列划分：A按行划分、B按列划分令C=(Cij
6、)，其中Cij=AiBj将Ai,Bj和Cij(j=0,1,...,p-1)存放在第i个处理器中(这样的存储方式使得数据在处理器中不重复)Pi负责计算Cij(j=0,1,...,p-1)由于使用p个处理器，每次每个处理器只计算一个Cij,故计算出整个C需要p次完成Cij的计算是按对角线进行的18行列划分并行算法一：行列划分fori=0top-1j=(i+myid)modpCj=A*Bsrc=(myid+1)modpdest=(myid-1+p)modpif(i!=p-1)send(B,dest)recv(B,src)endifendfor本算法中，Cj=Cmyid,j,A=Amy
7、id,B在处理器中每次循环向前移动一个处理器，即每次交换一个子矩阵数据块，共交换p-1次19行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程序：ex4matmul01.f20行行划分行行划分：A按行划分、B按行划分21行行划分22列列划分列列划分：A按列划分、B按列划分23列列划分24列行划分列行划分：A按列划分、B按行划分25列行划分26Cannon算法27Cannon算法28Cannon算法29Cannon算法示例以3×3分块为例：9个进程，进行三轮计算A、B的起始存放位置：A
