矩阵计算并行算法.ppt
1,第六讲矩阵计算并行算法,2,主要内容,并行算法基础知识 矩阵向量乘积的并行算法 矩阵矩阵乘积的并行算法 矩阵的 LU 分解并行算法 下三角线性方程组的并行算法,3,并行算法基础知识,一些基本概念,并行效率,4,程序性能优化,串行程序性能优化 并行程序性能优化的基础,调用高性能库。如：BLAS、LAPACK、FFTW,选择编译器优化选项：-O2、-O3,合理定义数组维数,注意嵌套循环次数：数据访问的空间局部性和时间局部性,数据分块,循环展开,例:ex4performance.c,5,程序性能优化,并行程序性能优化,设计好的并行算法和通信模式,减少通信次数、提高通信粒度,多进程通信时尽量使用高效率的聚合通信算法,负载平衡,通信与计算的重叠,减少进程的空闲时间,通过引入重复计算来减少通信,6,矩阵并行算法,一些记号和假定,假设有 p 个处理器，每个处理器上运行一个进程 Pj 表示第 j 个处理器，Pmyid 表示当前的处理器 send(x;j)表示在 Pmyid 中把数据块 x 发送给 Pj 进程 recv(x;j)表示从 Pj 进程接收数据块 x i mod p 表示 i 对 p 取模运算,程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用,7,主要内容,并行算法基础知识 矩阵向量乘积的并行算法 矩阵矩阵乘积的并行算法 矩阵的 LU 分解并行算法 下三角线性方程组的并行算法,8,矩阵向量乘积,串行算法,实现方法一：i-j 循环,for i=1 to m y(i)=0.0 for j=1 to n y(i)=y(i)+A(i,j)*x(j)end forend for,9,矩阵向量乘积,串行算法,实现方法二：j-i 循环,例：ex4matvec.f,y=0%先赋初值for j=1 to n for i=1 to m y(i)=y(i)+A(i,j)*x(j)end forend for,10,矩阵向量乘积,并行算法一,矩阵的划分方法：按行划分和按列划分,按行划分并行算法,将矩阵 A 按行划分成如下的行块子矩阵,将 Ai 存放在结点 Pi 中，每个结点计算 Ai x，最后调用 MPI_GATHER 或 MPI_GATHERV 即可,则,11,矩阵向量乘积,并行算法二,按列划分并行算法,将 Ai 和 xi 存放在结点 Pi 中，每个结点计算 Ai xiT，最后调用 MPI_REDUCE 或 MPI_ALLREDUCE 即可,12,矩阵向量乘积示例,例：按列划分，用 p 个进程并行计算矩阵向量乘积，其中,示例程序：ex4matvec.f,13,上机作业,上机作业：,1、编写按行划分计算矩阵向量乘积的通用并行程序2、按列划分，编写通用并行程序计算上面的乘积,14,主要内容,并行算法基础知识 矩阵向量乘积的并行算法 矩阵矩阵乘积的并行算法 矩阵的 LU 分解并行算法 下三角线性方程组的并行算法,15,矩阵矩阵乘积,串行算法一：i-j-k 循环,for i=1 to m for j=1 to l C(i,j)=0 for k=1 to n C(i,j)=C(i,j)+A(i,k)*B(k,j)end for end forend for,16,矩阵矩阵乘积,串行算法二：j-k-i 循环,C=0for j=1 to l for k=1 to n for i=1 to m C(i,j)=C(i,j)+A(i,k)*B(k,j)end for end forend for,17,并行矩阵乘积,假定：,m,l,n 均能能 p 整除，其中 p 为进程个数,18,行列划分,行列划分：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 次完成 Cij 的计算是按对角线进行的,19,行列划分,并行算法一：行列划分,for i=0 to p-1 j=(i+myid)mod p Cj=A*B src=(myid+1)mod p dest=(myid-1+p)mod p if(i!=p-1)send(B,dest)recv(B,src)end ifend for,本算法中，Cj=Cmyid,j,A=Amyid,B 在处理器中每次循环向前移动一个处理器，即每次交换一个子矩阵数据块，共交换 p-1 次,20,行列划分程序示例,例：按行列划分并行计算矩阵乘积，其中,示例程序：ex4matmul01.f,21,行行划分,行行划分：A 按行划分、B 按行划分,22,行行划分,23,列列划分,列列划分：A 按列划分、B 按列划分,24,列列划分,25,列行划分,列行划分：A 按列划分、B 按行划分,26,列行划分,27,Cannon 算法,28,Cannon 算法,29,Cannon 算法,30,Cannon 算法示例,以 33 分块为例：9 个进程，进行三轮计算,A、B 的起始存放位置：,A00 A01 A02A10 A11 A12A20 A21 A22,B00 B01 B02B10 B11 B12B20 B21 B22,第一轮：计算,A00 A00 A00A11 A11 A11A22 A22 A22,B00 B01 B02B10 B11 B12B20 B21 B22,31,Cannon 算法示例,第二轮：计算,B10 B11 B12B20 B21 B22B00 B01 B02,A01 A01 A01A12 A12 A12A20 A20 A20,第三轮：计算,B20 B21 B22B00 B01 B02B10 B11 B12,A02 A02 A02A10 A10 A10A21 A21 A21,32,Cannon 算法,33,Cannon 算法,34,Cannon 算法示例,35,上机作业,按行行划分并行计算矩阵乘积，其中,编写用第二种方式实现上述矩阵乘积的 Cannon 并行算法,36,主要内容,并行算法基础知识 矩阵向量乘积的并行算法 矩阵矩阵乘积的并行算法 矩阵的 LU 分解并行算法 下三角线性方程组的并行算法,37,线性方程组直接解法,38,线性方程组直接解法,39,矩阵 LU 分解,40,矩阵 LU 分解,41,矩阵 LU 分解,42,矩阵 LU 分解,43,上机作业,编写LU分解的并行程序，其中,44,主要内容,并行算法基础知识 矩阵向量乘积的并行算法 矩阵矩阵乘积的并行算法 矩阵的 LU 分解并行算法 下三角线性方程组的并行算法,45,三角方程并行求解,46,三角方程并行求解,47,三角方程并行求解,48,三角方程并行求解,49,三角方程并行求解,50,三角方程并行求解,51,上机作业,用算法 3 编写并行程序求解下三角方程组,其中,
