并行计算课程 矩阵向量乘积并行算法 (基于MPI) 潘建瑜 华东师范大学
1 矩阵向量乘积并行算法 潘建瑜 华东师范大学 （基于 MPI） 并行计算课程
案 串行算法 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 串行算法
y=Ax (A∈R",x∈R” fori=1tom/i-j循环 for j=1 to n y(i)=y(i)+A(i,j)*x(j) end for end for forj=1ton/j-i循环 for i=1 to m y(i)=y(i)+A(i,j)*x(j) end for end for
y Ax = ( , ) m n n A x × ∈ ∈ for i=1 to m // i-j 循环 for j=1 to n y(i)=y(i)+A(i,j)*x(j) end for end for for j=1 to n // j-i 循环 for i=1 to m y(i)=y(i)+A(i,j)*x(j) end for end for
数据分配 ij循环 口口 ji循环
... ... ... ... ... i-j 循环 数据分配 j-i 循环
案 并行算法 一按行划分 注：P,表示第i个处理器或第i个进程 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 并行算法 —— 按行划分 注：Pi 表示第 i 个处理器或第 i 个进程
并行算法：按行划分 将矩阵A按行划分成行块子矩阵 数据存储方案 A 矩阵：按行划分，分别存储 A Ax Ax= x= ●向量x:每个结点都存储x 向量y:每个结点计算一分，在0 Ap-ix 号进程中合并，并广播给其他进程 口将A,存放在处理器P,中，每个处理器计算Ax, ▣最后调用MPI GATHER或MPI GATHERV即可
并行算法：按行划分 将矩阵 A 按行划分成行块子矩阵 0 0 1 1 p p 1 1 A Ax A Ax Ax x A Ax − − = = 矩阵：按行划分，分别存储 向量 𝒙𝒙：每个结点都存储 𝒙𝒙 向量 𝒚𝒚：每个结点计算一部分，在 0 号进程中合并，并广播给其他进程 数据存储方案 将 Ai 存放在处理器 Pi 中，每个处理器计算 Ai x， 最后调用 MPI_GATHER 或 MPI_GATHERV 即可
举例 例：按行划分，用p个进程并行计算矩阵向量乘积，其中 1 A=[a,]eR,4=+j- x=l,2,,n∈R” (1)取n=1024,p=4,矩阵划分：按顺序连续划分，即0号进程存储A[0:255,:, 1号进程存储A[256:511,】,依次类推。 MPI_matvec.c MPI_matvec_v.c (2)取n=1024,p=3,4,5,矩阵划分：卷帘方式。 MPI_matvec_swap.c
举例 例：按 行 划分，用 p 个进程并行计算矩阵向量乘积，其中 , n n A aij × = ∈ 1 , 1 ij a i j = + − [1, 2, , ] T n x n = ∈ (1) 取 n=1024, p=4, 矩阵划分：按顺序连续划分，即 0 号进程存储 A[0:255, :]， 1 号进程存储 A[256:511, :]，依次类推。 (2) 取 n=1024, p=3,4,5, 矩阵划分：卷帘方式。 MPI_matvec.c MPI_matvec_v.c MPI_matvec_swap.c
案 并行算法 —按列划分 http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 并行算法 —— 按列划分
并行算法：按列划分 将矩阵A按列划分，并对x也做相应的划分 Ax=[4,44] =Ax+Ax1+…+Ap-1xp-1 口将A,和x,存放在P中，每个处理器计算AxT 口最后调用MPI REDUCE或MPI ALLREDUCE即可
并行算法：按列划分 将矩阵 A 按列划分，并对 x 也做相应的划分 0 1 0 1 1 00 11 1 1 1 ,,, q p p p x x Ax A A A A x A x A x x − − − − = = + ++ 将 Ai 和 xi 存放在 Pi 中，每个处理器计算 Ai xi T 最后调用 MPI_REDUCE 或 MPI_ALLREDUCE 即可
谢谢 THANK YOU http://math.ecnu.edu.cn/~jypan
http://math.ecnu.edu.cn/~jypan 谢 谢 THANK YOU