并行计算课程 矩阵矩阵乘积并行算法 (基于MPI) 潘建瑜 华东师范大学
1 矩阵矩阵乘积并行算法 潘建瑜 华东师范大学 （基于 MPI） 并行计算课程
华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents 矩阵乘积串行算法 六种不同计算顺序 2 矩阵乘积并行算法 行列划分、行行划分、列列划分、列行划分 Cannon算法 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 目录页 Contents 1 2 矩阵乘积串行算法 矩阵乘积并行算法 —— 行列划分、行行划分、列列划分、列行划分 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU —— Cannon 算法 —— 六种不同计算顺序
案 串行算法 ——六种不同计算顺序 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 串行算法 —— 六种不同计算顺序
C=AB (A∈R,B∈R"） B C ×n m×n m×L 六种不同顺序的循环：K、K、JK、JK、KL、JKI,详见课程主页
C AB = ( , ) m l l n A B × × ∈ ∈ = 𝑚𝑚 × 𝑛𝑛 𝑚𝑚 × 𝑙𝑙 𝑙𝑙 × 𝑛𝑛 𝐶𝐶 𝐴𝐴 𝐵𝐵 六种不同顺序的循环：IKJ、KIJ、IJK、JIK、KJI、JKI，详见课程主页
华东师范大学数学科学学院 目录页 School of Mathematical Sciences,ECNU Contents 矩阵乘积串行算法 六种不同计算顺序 2 矩阵乘积并行算法 行列划分、行行划分、列列划分、列行划分 Cannon算法 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 目录页 Contents 1 2 矩阵乘积串行算法 矩阵乘积并行算法 —— 行列划分、行行划分、列列划分、列行划分 华东师范大学 数学科学学院 School of Mathematical Sciences, ECNU —— Cannon 算法 —— 六种不同计算顺序
一些记号和设定 口假设有p个处理器/进程/结点，每个结点运行一个进程 口P,表示第j个结点，Pma表示当前结点或进程 口send(c;)表示在Pa中把数据x发送给P 口recv(x;)表示Pma从P接收数据块x 口imodp表示i对p做模运算
一些记号和设定 假设有 p 个处理器/进程/结点，每个结点运行一个进程 Pj 表示第 j 个结点，Pmyid 表示当前结点或进程 send(x; j) 表示在 Pmyid 中把数据 x 发送给 Pj recv(x; j) 表示 Pmyid 从 Pj 接收数据块 x i mod p 表示 i 对 p 做模运算
并行算法 C=AxB 并行计算 → 由用户分配数据与计算任务 对A、B进行分块 行列划分、行行划分、列列划分、列行划分 十为了描述方便，假定m,l,n均能能p整除，其中p为进程个数
并行算法 C AB = × 由用户分配 数据 与 计算任务 对 A、B 进行分块 行列划分、行行划分、列列划分、列行划分 † 为了描述方便，假定 m, l, n 均能能 p 整除，其中 p 为 进程 个数。 并行计算
案 并行算法 一行列划分 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 并行算法 —— 行列划分
并行算法：行列划分 行列划分 47 「A,B。 AB AoB- AB= A [B,B…B]= AB。 ABr- : =[c] A-Bo A1B A1B1 数据存储与计算方案 存储方案：AB,和C(=0,1,p-1)存放在第i个处理器中，按循环方式交换数据B: 口P:负责计算C(j=0,1,,p-1) 口由于使用p个处理器，每次每个处理器只计算一个C,故计算出整个C需要p次完成 ▣ C,的计算是按对角线进行的
并行算法：行列划分 行列划分 00 01 0 1 0 1 10 11 1 1 01 1 1 10 11 1 1 p p p ij p p p p p A AB AB AB A AB AB AB AB B B B C A AB AB AB − − − − − − − − = = = 存储方案：Ai , Bi 和 Cij ( j = 0, 1, ..., p-1) 存放在第 i 个处理器中，按循环方式交换数据 Bi Pi 负责计算 Cij ( j = 0, 1, ..., p-1) 由于使用 p 个处理器，每次每个处理器只计算一个 Cij，故计算出整个 C 需要 p 次完成 Cij 的计算是按对角线进行的 数据存储与计算方案
Ao0 A02 B00 Boi B02 C Cu A10 An A12 × B10 B11 B12 20 21 22 A20 A22 B20 B21 22 0号进程 1号进程 2号进程 A00 Boo A10 Au A12 B A20 A22 Bo2 B10 B B12 七00 0 02 B20 10 B21 20 22
0 号进程 1 号进程 2 号进程 A00 A01 A02 A10 A11 A12 A20 A21 A22 B00 B01 B02 B10 B11 B12 B20 B21 B22 C00 C01 C02 C10 C11 C12 C20 C21 C22 = × A00 A01 A02 B00 B10 B20 C00 C01 C02 A10 A11 A12 B01 B11 B21 C10 C11 C12 A20 A21 A22 B02 B12 B22 C20 C21 C22
