第六讲矩阵计算并行算法

1、1第六讲矩阵计算并行算法2主要内容主要内容n 并行算法基础知识并行算法基础知识n 矩阵向量乘积的并行算法矩阵向量乘积的并行算法n 矩阵矩阵乘积的并行算法矩阵矩阵乘积的并行算法n 矩阵的矩阵的 LU 分解并行算法分解并行算法n 下三角线性方程组的并行算法下三角线性方程组的并行算法3并行算法基础知识并行算法基础知识n 一些基本概念一些基本概念l 加速比加速比其中其中 Ts 串行程序运行时间，串行程序运行时间，Tp(q) 为为 q 个进程的运行时间个进程的运行时间 l 并行效率并行效率4程序性能优化程序性能优化n 串行程序性能优化串行程序性能优化 并行程序性能优化的基础并行程序性能优化的基础l 调用

2、高性能库。如：调用高性能库。如：BLAS、LAPACK、FFTWl 选择编译器优化选项：选择编译器优化选项：-O2、-O3l 合理定义数组维数合理定义数组维数l 注意嵌套循环次数：注意嵌套循环次数：数据访问的空间局部性和时间局部性数据访问的空间局部性和时间局部性l 数据分块数据分块l 循环展开循环展开 例例: ex4performance.c5程序性能优化程序性能优化n 并行程序性能优化并行程序性能优化l 设计好的并行算法和通信模式设计好的并行算法和通信模式l 减少通信次数、提高通信粒度减少通信次数、提高通信粒度l 多进程通信时尽量使用高效率的聚合通信算法多进程通信时尽量使用高效率的聚合通信算

3、法l 负载平衡负载平衡l 通信与计算的重叠通信与计算的重叠l 减少进程的空闲时间减少进程的空闲时间l 通过引入重复计算来减少通信通过引入重复计算来减少通信6矩阵并行矩阵并行算法算法n 一些记号和假定一些记号和假定l 假设有假设有 p 个处理器，每个处理器上运行一个进程个处理器，每个处理器上运行一个进程 l Pj 表示第表示第 j 个处理器，个处理器，Pmyid 表示当前的处理器表示当前的处理器l send(x; j) 表示在表示在 Pmyid 中把数据块中把数据块 x 发送给发送给 Pj 进程进程l recv(x; j) 表示从表示从 Pj 进程接收数据块进程接收数据块 xl i mod p

4、表示表示 i 对对 p 取模运算取模运算 程序设计与机器实现是密不可分的，计算结果的好坏与编程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用高质量的程序对发挥计算机的性能起着至关重要的作用7主要内容主要内容n 并行算法基础知识并行算法基础知识n 矩阵向量乘积的并行算法矩阵向量乘积的并行算法n 矩阵矩阵乘积的并行算法矩阵矩阵乘积的并行算法n 矩阵的矩阵的 LU 分解并行算法分解并行算法n 下三角线性方程组的并行算法下三角线性方程组的并行算法8矩阵向

5、量乘积矩阵向量乘积n 串行算法串行算法l 实现方法一：实现方法一：i-j 循环循环yAx , m nnAx RRfor i=1 to m y(i)=0.0 for j=1 to n y(i)=y(i)+A(i,j)*x(j) end forend for9矩阵向量乘积矩阵向量乘积n 串行算法串行算法l 实现方法二：实现方法二：j-i 循环循环例：例：ex4matvec.fy=0 % 先赋初值先赋初值for j=1 to n for i=1 to m y(i)=y(i)+A(i,j)*x(j) end forend for10矩阵向量乘积矩阵向量乘积n 并行算法一并行算法一l 矩阵的划分方法：按

6、行划分和按列划分矩阵的划分方法：按行划分和按列划分l 按按行划分并行算法划分并行算法将矩阵将矩阵 A 按行划分成如下的行按行划分成如下的行块子矩阵块子矩阵将将 Ai 存放在结点存放在结点 Pi 中，每个结点计算中，每个结点计算 Ai x，最后，最后调用调用 MPI_GATHER 或或 MPI_GATHERV 即可即可则则11矩阵向量乘积矩阵向量乘积n 并行算法二并行算法二l 按按列划分并行算法划分并行算法将将 Ai 和和 xi 存放在结点存放在结点 Pi 中，每个结点计算中，每个结点计算 Ai xiT，最后调用最后调用 MPI_REDUCE 或或 MPI_ALLREDUCE 即可即可将矩阵将矩

7、阵 A 按列划分，并对按列划分，并对 x 也做相应的划分也做相应的划分其中其中 xi 的长度与的长度与 Ai 的列数相同，则有的列数相同，则有12矩阵向量乘积矩阵向量乘积示例示例n 例：例：按按列划分，用划分，用 p 个进程并行计算矩阵向量乘积，其中个进程并行计算矩阵向量乘积，其中示例程序示例程序：ex4matvec.f(), n nijAa 1R1 1ijaij 1, 1, , 1, Tnx 1R13上机作业上机作业l 上机作业上机作业：1、编写按、编写按行划分计算矩阵向量乘积的通用并行程序划分计算矩阵向量乘积的通用并行程序2、按按列划分，编写通用并行程序计算上面的乘积划分，编写通用并行程序

8、计算上面的乘积14主要内容主要内容n 并行算法基础知识并行算法基础知识n 矩阵向量乘积的并行算法矩阵向量乘积的并行算法n 矩阵矩阵乘积的并行算法矩阵矩阵乘积的并行算法n 矩阵的矩阵的 LU 分解并行算法分解并行算法n 下三角线性方程组的并行算法下三角线性方程组的并行算法15矩阵矩阵矩阵乘积矩阵乘积n 串行算法一串行算法一：i-j-k 循环循环CAB, m ll nABRRfor 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 for16矩阵矩阵矩阵乘积矩阵乘积n

9、 串行算法二串行算法二：j-k-i 循环循环CAB, m ll nABRRC=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 for17并行并行矩阵矩阵乘积乘积n 假定：假定：n 基于基于 A、B 的不同划分，的不同划分，矩阵乘积的并行算法可分为矩阵乘积的并行算法可分为l 行列划分行列划分l 行行划分行行划分l 列列划分列列划分l 列行划分列行划分CAB, m ll nABRRm, l, n 均能能均能能 p 整除，其中整除，其中 p 为进程个数为进程个数18行列划分行

10、列划分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 的计算是按对角线

11、进行的的计算是按对角线进行的19行列划分行列划分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 次

12、次20行列划分程序示例行列划分程序示例n 例：例：按按行列行列划分并行计算矩阵乘积，其中划分并行计算矩阵乘积，其中示例程序示例程序：ex4matmul01.f1(), 1n nijijAaaij 1R(), 1n nijijBbbij 1R21行行划分行行划分n 行行行行划分划分：A 按行划分、按行划分、 B 按行划分按行划分22行行划分行行划分23列列划分列列划分n 列列列列划分划分：A 按列划分、按列划分、 B 按列划分按列划分24列列划分列列划分25列行划分列行划分n 列列行行划分划分：A 按列划分、按列划分、 B 按行划分按行划分26列行划分列行划分27Cannon 算法算法28Can

13、non 算法算法29Cannon 算法算法30Cannon 算法示例算法示例n 以以 33 分块为例：分块为例：9 个进程，进行三轮计算个进程，进行三轮计算l A、B 的起始存放位置：的起始存放位置：A00 A01 A02A10 A11 A12A20 A21 A22B00 B01 B02B10 B11 B12B20 B21 B22l 第一轮：计算第一轮：计算(0)(0)ADBA00 A00 A00A11 A11 A11A22 A22 A22B00 B01 B02B10 B11 B12B20 B21 B2231Cannon 算法示例算法示例l 第二轮：计算第二轮：计算(1)(1)ADBB10 B

14、11 B12B20 B21 B22B00 B01 B02A01 A01 A01A12 A12 A12A20 A20 A20l 第三轮：计算第三轮：计算(2)(2)ADBB20 B21 B22B00 B01 B02B10 B11 B12A02 A02 A02A10 A10 A10A21 A21 A2132Cannon 算法算法33Cannon 算法算法34Cannon 算法示例算法示例35上机作业上机作业l 按按行行行行划分并行计算矩阵乘积，其中划分并行计算矩阵乘积，其中l 编写用第二种方式实现上述矩阵乘积的编写用第二种方式实现上述矩阵乘积的 Cannon 并行算法并行算法1(), 1n nij

15、ijAaaij 1R(), 1n nijijBbbij 1R36主要内容主要内容n 并行算法基础知识并行算法基础知识n 矩阵向量乘积的并行算法矩阵向量乘积的并行算法n 矩阵矩阵乘积的并行算法矩阵矩阵乘积的并行算法n 矩阵的矩阵的 LU 分解并行算法分解并行算法n 下三角线性方程组的并行算法下三角线性方程组的并行算法37线性方程组直接解法线性方程组直接解法38线性方程组直接解法线性方程组直接解法39矩阵矩阵 LU 分解分解40矩阵矩阵 LU 分解分解41矩阵矩阵 LU 分解分解42矩阵矩阵 LU 分解分解43上机作业上机作业l 编写编写LU分解的并行程序，其中分解的并行程序，其中(), 1n nijijAaaij 1R44主要内容主要内容n 并行算法基础知识并行算法基础知识n 矩阵向量乘积的并行算法矩阵向量乘积的并行算法n 矩阵矩阵乘积的并行算法矩阵矩阵乘积的并行算法n 矩阵的矩阵的 LU 分解并行算法