矩阵计算并行算法.ppt

第六讲

矩阵计算并行算法1精选ppt

主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法2精选ppt

并行算法基础知识一些基本概念加速比其中Ts串行程序运行时间，Tp(q)为q个进程的运行时间并行效率3精选ppt

程序性能优化串行程序性能优化——并行程序性能优化的基础调用高性能库。如：BLAS、LAPACK、FFTW选择编译器优化选项：-O2、-O3合理定义数组维数注意嵌套循环次数：数据访问的空间局部性和时间局部性数据分块循环展开例:ex4performance.c4精选ppt

程序性能优化并行程序性能优化设计好的并行算法和通信模式减少通信次数、提高通信粒度多进程通信时尽量使用高效率的聚合通信算法负载平衡通信与计算的重叠减少进程的空闲时间通过引入重复计算来减少通信5精选ppt

矩阵并行算法一些记号和假定假设有p个处理器，每个处理器上运行一个进程Pj表示第j个处理器，Pmyid表示当前的处理器send(x;j)表示在Pmyid中把数据块x发送给Pj进程recv(x;j)表示从Pj进程接收数据块ximodp表示i对p取模运算程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用6精选ppt

主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法7精选ppt

矩阵向量乘积串行算法实现方法一：i-j循环fori=1tomy(i)=0.0forj=1tony(i)=y(i)+A(i,j)*x(j)endforendfor8精选ppt

矩阵向量乘积串行算法实现方法二：j-i循环例：ex4matvec.fy=0%先赋初值forj=1tonfori=1tomy(i)=y(i)+A(i,j)*x(j)endforendfor9精选ppt

矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分按行划分并行算法将矩阵A按行划分成如下的行块子矩阵将Ai存放在结点Pi中，每个结点计算Aix，最后调用MPI_GATHER或MPI_GATHERV即可则10精选ppt

矩阵向量乘积并行算法二按列划分并行算法将Ai和xi存放在结点Pi中，每个结点计算AixiT，最后调用MPI_REDUCE或MPI_ALLREDUCE即可将矩阵A按列划分，并对x也做相应的划分其中xi的长度与Ai的列数相同，则有11精选ppt

矩阵向量乘积示例例：按列划分，用p个进程并行计算矩阵向量乘积，其中示例程序：ex4matvec.f12精选ppt

上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并行程序2、按列划分，编写通用并行程序计算上面的乘积13精选ppt

主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法14精选ppt

矩阵矩阵乘积串行算法一：i-j-k循环fori=1tomforj=1tolC(i,j)=0fork=1tonC(i,j)=C(i,j)+A(i,k)*B(k,j)endforendforendfor15精选ppt

矩阵矩阵乘积串行算法二：j-k-i循环C=0forj=1tolfork=1tonfori=1tomC(i,j)=C(i,j)+A(i,k)*B(k,j)endforendforendfor16精选ppt

并行矩阵乘积假定：基于A、B的不同划分，矩阵乘积的并行算法可分为行列划分行行划分列列划分列行划分m,l,n均能能p整除，其中p为进程个数17精选ppt

行列划分行列划分：A按行划分、B按列划分令C=(Cij)，其中Cij=AiBj将Ai,Bj和Cij(j=0,1,...,p-1)存放在第i个处理器中

(这样的存储方式使得数据在处理器中不重复)Pi负责计算Cij(j=0,1,...,p-1)由于使用p个处理器，每次每个处理器只计算一个Cij,

故计算出整个C需要p次完成