矩阵计算并行算法.ppt

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