1
B ? (bij ) ? R 1n?n , bij ? i ? j ? 1
示例程序：ex4matmul01.f
20
行行划分
?行行划分：A 按行划分、 B 按行划分
4
程序性能优化
? 并行程序性能优化
? 设计好的并行算法和通信模式 ? 减少通信次数、提高通信粒度 ? 多进程通信时尽量使用高效率的聚合通信算法 ? 负载平衡 ? 减少进程的空闲时间 ? 通信与计算的重叠 ? 通过引入重复计算来减少通信
5
矩阵并行算法
? 一些记号和假定
?假设有 p 个处理器，每个处理器上运行一个进程 ?Pj 表示第 j 个处理器，Pmyid 表示当前的处理器 ?send(x; j) 表示在 Pmyid 中把数据块 x 发送给 Pj 进程 ?recv(x; j) 表示从 Pj 进程接收数据块 x ?i mod p 表示 i 对 p 取模运算
3
程序性能优化
? 串行程序性能优化 —— 并行程序性能优化的基础
? 调用高性能库。如：BLAS、LAPACK、FFTW ? 选择编译器优化选项：-O2、-O3 ? 合理定义数组维数 ? 注意嵌套循环次数：数据访问的空间局部性和时间局部性 ?循环展开 例: ex4performance.c ? 数据分块
end for
15
矩阵矩阵乘积
C ? A ? B A? R m?l , B ? R l?n
?串行算法二 ：j-k-i 循环
C=0 for j=1 to l
for k=1 to n for i=1 to m C(i,j)=C(i,j)+A(i,k)*B(k,j) end for
end for end for
A ? (aij ) ? R 1nn? ,
aij
?
i
?
1 j?
1
x ? [1, 1, K , 1]T ? R 1n ,
示例程序：ex4matvec.f
12
上机作业
? 上机作业：
1、编写按行划分计算矩阵向量乘积的通用并行程序 2、按列划分，编写通用并行程序计算上面的乘积
13
主要内容
? 并行算法基础知识 ? 矩阵向量乘积的并行算法
?按列划分并行算法
将矩阵 A 按列划分，并对 x 也做相应的划分
其中 xi 的长度与 Ai 的列数相同，则有
将 Ai 和 xi 存放在结点 Pi 中，每个结点计算 Ai xiT， 最后调用 MPI_REDUCE 或 MPI_ALLREDUCE 即可
11
矩阵向量乘积示例
?例：按列划分，用 p 个进程并行计算矩阵向量乘积，其中
第六讲 矩阵计算并行算法
1
主要内容
? 并行算法基础知识 ? 矩阵向量乘积的并行算法 ? 矩阵矩阵乘积的并行算法 ? 矩阵的 LU 分解并行算法 ? 下三角线性方程组的并行算法
2
并行算法基础知识
? 一些基本概念
? 加速比
其中 Ts 串行程序运行时间，Tp(q) 为 q 个进程的运行时间
? 并行效率
16
并行矩阵乘积
C ? A ? B A? R m?l , B ? R l?n
? 假定：
m, l, n 均能能 p 整除，其中 p 为进程个数
?基于 A、B 的不同划分，矩阵乘积的并行算法可分为
?行列划分 ?行行划分 ?列列划分 ?列行划分
17
行列划分
?行列划分：A 按行划分、 B 按列划分
?令 C = (Cij)，其中 Cij = AiBj
7
矩阵向量乘积
y ? Ax A? R m?n, x ? R n
? 串行算法
?实现方法一：i-j 循环 for i=1 to m y(i)=0.0 for j=1 to n y(i)=y(i)+A(i,j)*x(j) end for end for
8
矩阵向量乘积
? 串行算法
?实现方法二：j-i 循环 y=0 % 先赋初值 for j=1 to n for i=1 to m y(i)=y(i)+A(i,j)*x(j) end for end for
? 矩阵矩阵乘积的并行算法
? 矩阵的 LU 分解并行算法 ? 下三角线性方程组的并行算法
14
矩阵矩阵乘积
C ? A ? B A? R m?l , B ? R l?n
?串行算法一 ：i-j-k 循环
for i=1 to m for j=1 to l C(i,j)=0 for k=1 to n C(i,j)=C(i,j)+A(i,k)*B(k,j) end for end for
程序设计与机器实现是密不可分的，计算结果的好坏与编 程技术有很大的关系，尤其是在并行计算机环境下，开发 高质量的程序对发挥计算机的性能起着至关重要的作用
6
主要内容
? 并行算法基础知识
? 矩阵向量乘积的并行算法
? 矩阵矩阵乘积的并行算法 ? 矩阵的 LU 分解并行算法 ? 下三角线性方程组的并行算法
end for
? 本算法中， Cj = Cmyid, j , A = Amyid , B 在处理器中每次循环向前移 动一个处理器，即每次交换一个子矩阵数据块，共交换 p-1 次
19
行列划分程序示例
? 例：按行列划ij ) ? R 1nn? ,
aij
?
i?
1 j?
?将 Ai, Bj 和 Cij ( j = 0, 1, ..., p-1) 存放在第 i 个处理器中 (这样的存储方式使得数据在处理器中不重复 )
?Pi 负责计算 Cij ( j = 0, 1, ..., p-1)
?由于使用 p 个处理器，每次每个处理器只计算一个 Cij, 故计算出整个 C 需要 p 次完成
例：ex4matvec.f
9
矩阵向量乘积
? 并行算法一
?矩阵的划分方法：按行划分和按列划分
?按行划分并行算法
将矩阵 A 按行划分成如下的行 块子矩阵
则
将 Ai 存放在结点 Pi 中，每个结点计算 Ai x，最后 调用 MPI_GATHER 或 MPI_GATHERV 即可
10
矩阵向量乘积
? 并行算法二
?Cij 的计算是按对角线进行的
18
行列划分
? 并行算法一：行列划分
for i=0 to p-1 j=(i+myid) mod p Cj=A*B src = (myid+1) mod p dest = (myid-1+p) mod p if (i!=p-1) send(B,dest) recv(B,src) end if