華柬师免天学|数学科学学院 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 − =