华东师范大学：《高等数值分析（高性能计算/并行计算）》课程教学资源（讲义）05 矩阵 - 矩阵乘积并行算法（OpenMP）

華柬师免天学|数学科学学院 School of Mathematical Sciences.East China Normal University 矩阵乘积并行算法 (OpenMP) http://math.ecnu.edu.cn/-jypan

http://math.ecnu.edu.cn/~jypan 矩阵乘积并行算法 （OpenMP）

华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents 矩阵矩阵并行乘积 串行算法 自动并行 手工并行 http://math.ecnu.edu.cn/~jypan

http://math.ecnu.edu.cn/~jypan 目录页 Contents  串行算法  自动并行  手工并行 矩阵矩阵并行乘积 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU

矩阵乘积串行算法 C=AB A∈RMxL,B∈RxN ■串行算法 ●K顺序 for(i=0;i<M;i++) for(j=0;j<N;j++) for(k=0;k<L;k++) c[i][j]=C[i][j]+A[i][k]*B[k][]; KJ顺序、KIJ顺序、JK顺序、KⅡ顺序、JKI顺序 快速算法：Strassen算法等 示例程序：hw01 http://math.ecnu.edu.cn/-jypan 3

http://math.ecnu.edu.cn/~jypan 3 矩阵乘积串行算法  串行算法 C AB = , M L L N A B × × ∈ ∈   for(i=0; i<M; i++) for(j=0; j<N; j++) for(k=0; k<L; k++) C[i][j]=C[i][j] + A[i][k]*B[k][j]; ► IJK 顺序 ► IKJ 顺序、KIJ 顺序、JIK 顺序、KJI 顺序、JKI 顺序 示例程序：hw01 ► 快速算法：Strassen 算法等

并行算法： 自动并行 C-AB A∈RMxL,B∈RxN 自动并行 循环共享结构 #pragma omp parallel for shared(A,B,C)...... for(i=0;i<M;i++) for(j=0;j<N;j++) { c[i][j]=0; for(k=0;k<L;k++) c[i][j]=C[i][j]+A[i][k]*B[k][j]; OMP matmul_for.c http://math.ecnu.edu.cn/-jypan

http://math.ecnu.edu.cn/~jypan 4 并行算法：自动并行 自动并行 循环共享结构 #pragma omp parallel for shared(A,B,C) ...... for(i=0; i<M; i++) for(j=0; j<N; j++) { C[i][j]=0; for(k=0; k<L; k++) C[i][j]=C[i][j] + A[i][k]*B[k][j]; } OMP_matmul_for.c C AB = , M L L N A B × × ∈ ∈  

并行：手工并行 Ao AoBo A0B1· AoBp-1 A1 A1Bo A1B1· A1Bp-1 AB= [B0B1…Bp-1]= AoBp-1 [Ap-1] Ap-1B0Ap-1B1·Ap-1Bp-1」 手工并行 任务分配：由用户分配计算任务 (即每个线程负责计算C的哪些部分) C:按行分块、按列分块、二维分块 假定：M,L,N均能能p整除，其中p为线程个数 http://math.ecnu.edu.cn/-jypan 5

http://math.ecnu.edu.cn/~jypan 5 并行：手工并行 假定：M, L, N 均能能 p 整除，其中 p 为线程个数 手工并行 任务分配：由用户分配计算任务 （即每个线程负责计算 C 的哪些部分） C：按行分块、按列分块、二维分块

并行：按行分配任务 AB A AB 记A= C=AB= An-1 A1B 按行分配任务 ● 第i号线程负责计算C:,其中C:=A,B 实际计算时，对A的划分可以采用连续方式或卷帘方式 http://math.ecnu.edu.cn/-jypan 6

http://math.ecnu.edu.cn/~jypan 6 并行：按行分配任务  第 i 号线程负责计算 Ci ，其中 Ci = Ai B  实际计算时，对 A 的划分可以采用连续方式或卷帘方式 按行分配任务 0 1 p 1 A A A A −       =          0 1 p 1 A B A B C AB A B−       = =          记

举例 例：按行分配任务，并行计算矩阵乘积，其中 4-[a]em,4= 1 B=by ERmM,by=i+j-1 (取n=1024,p=4) OMP_MatMul_rc.c http://math.ecnu.edu.cn/-jypan 7

http://math.ecnu.edu.cn/~jypan 7 举例 例：按行分配任务，并行计算矩阵乘积，其中 1 , 1 n n Aa a ij ij i j × =∈ =     + −  , 1 n n B b b ij ij ij × = ∈ =+−      OMP_MatMul_rc.c （取 n=1024, p=4）

并行：按列分配任务 B=[B,B,B,] C=[AB,AB..AB 按列分配任务 ●第i号线程负责计算C,其中C:=Ab ● 实际计算时，对B的划分可以采用连续方式或卷帘方式 http://math.ecnu.edu.cn/-jypan

http://math.ecnu.edu.cn/~jypan 8 并行：按列分配任务  第 i 号线程负责计算 Ci ，其中 Ci = Abi  实际计算时，对 B 的划分可以采用连续方式或卷帘方式 按列分配任务 01 1 , ,, C AB AB ABq− =      01 1 ,,, B BB B q− =     

并行：二维划分 A- ABo AB AoB-1 ABo AB C= AB An-B。Ap-1B, Ap-1B-1 行列划分 线程总数为nthreads=-pxq,其中p和q为两个正整数 ● 第(G》号线程负责计算C,其中C=A,B, ● 实际计算时，也可以采用卷帘方式分配任务（即划分矩阵A和B) http://math.ecnu.edu.cn/-jypan

http://math.ecnu.edu.cn/~jypan 9 并行：二维划分  线程总数为 nthreads=p×q，其中 p 和 q 为两个正整数  第 (i, j) 号线程负责计算 Cij ，其中 Cij = Ai Bj  实际计算时，也可以采用卷帘方式分配任务（即划分矩阵 A 和 B） 行列划分 01 1 ,,, B BB B q− =      00 01 0 1 10 11 1 1 10 11 1 1 q q p p p q AB AB AB AB AB AB C AB AB AB − − − − − −     =         0 1 1 , p A A A A −       =         