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

并行计算课程 矩阵向量乘积并行算法 (基于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