华东师范大学：《高等数值分析（高性能计算/并行计算）》课程教学资源（讲义）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：按行分块、按列分块、二维分块