矩阵计算并行算法课件

第六讲

矩阵计算并行算法1第六讲

矩阵计算并行算法1主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法2主要内容并行算法基础知识2并行算法基础知识一些基本概念加速比其中Ts

串行程序运行时间，Tp(q)为q

个进程的运行时间并行效率3并行算法基础知识一些基本概念加速比其中Ts串行程序运程序性能优化串行程序性能优化——并行程序性能优化的基础调用高性能库。如：BLAS、LAPACK、FFTW选择编译器优化选项：-O2、-O3合理定义数组维数注意嵌套循环次数：数据访问的空间局部性和时间局部性数据分块循环展开例:ex4performance.c4程序性能优化串行程序性能优化——并行程序性能优化的基础程序性能优化并行程序性能优化设计好的并行算法和通信模式减少通信次数、提高通信粒度多进程通信时尽量使用高效率的聚合通信算法负载平衡通信与计算的重叠减少进程的空闲时间通过引入重复计算来减少通信5程序性能优化并行程序性能优化设计好的并行算法和通信模式矩阵并行算法一些记号和假定假设有p

个处理器，每个处理器上运行一个进程

Pj

表示第j

个处理器，Pmyid

表示当前的处理器

send(x;j)

表示在Pmyid

中把数据块x

发送给Pj

进程

recv(x;j)

表示从Pj

进程接收数据块x

imod

p

表示i

对p取模运算程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用6矩阵并行算法一些记号和假定假设有p个处理器，每个处理主要内容并行算法基础知识

矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法7主要内容并行算法基础知识7矩阵向量乘积串行算法实现方法一：i-j

循环fori=1tomy(i)=0.0

forj=1tony(i)=y(i)+A(i,j)*x(j)

end

forend

for8矩阵向量乘积串行算法实现方法一：i-j循环fori=矩阵向量乘积串行算法实现方法二：j-i

循环例：ex4matvec.fy=0%先赋初值forj=1ton

fori=1tomy(i)=y(i)+A(i,j)*x(j)

end

forend

for9矩阵向量乘积串行算法实现方法二：j-i循环例：ex4m矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分按行划分并行算法将矩阵A

按行划分成如下的行块子矩阵将Ai

存放在结点Pi

中，每个结点计算Aix，最后调用MPI_GATHER

或MPI_GATHERV

即可则10矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分矩阵向量乘积并行算法二按列划分并行算法将Ai

和xi

存放在结点Pi

中，每个结点计算AixiT，最后调用MPI_REDUCE

或MPI_ALLREDUCE即可将矩阵A

按列划分，并对x

也做相应的划分其中

xi

的长度与

Ai

的列数相同，则有11矩阵向量乘积并行算法二按列划分并行算法将Ai和xi矩阵向量乘积示例例：按列划分，用p

个进程并行计算矩阵向量乘积，其中示例程序：ex4matvec.f12矩阵向量乘积示例例：按列划分，用p个进程并行计算矩阵向上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并行程序2、按列划分，编写通用并行程序计算上面的乘积13上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并主要内容并行算法基础知识矩阵向量乘积的并行算法

矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法14主要内容并行算法基础知识14矩阵矩阵乘积

串行算法一：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

forend

for15矩阵矩阵乘积串行算法一：i-j-k循环fori=1t矩阵矩阵乘积

串行算法二：j-k-i

循环C=0for

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

forend

for16矩阵矩阵乘积串行算法二：j-k-i循环C=016并行矩阵乘积假定：基于A、B

的不同划分，矩阵乘积的并行算法可分为行列划分行行划分列列划分列行划分m,l,n

均能能p

整除，其中p

为进程个数17并行矩阵乘积假定：基于A、B的不同划分，矩阵乘积的并行列划分

行列划分：A

按行划分、B按列划分令C=(Cij)，其中Cij

=

AiBj

将Ai,Bj

和Cij(j=0,1,...,p-1)存放在第i个处理器中

(这样的存储方式使得数据在处理器中不重复)

Pi

负责计算Cij(j=0,1,...,p-1)

由于使用p

个处理器，每次每个处理器只计算一个Cij,

故计算出整个C

需要p

次完成

Cij

的计算是按对角线进行的18行列划分行列划分：A按行划分、B按列划分令C=行列划分

并行算法一：行列划分fori=0

to

p-1

j=(i+myid)modpCj=A*Bsrc=(myid+1)modpdest=(myid-1+p)modp

if(i!=p-1)

send(B,dest)

recv(B,src)

end

ifend

for

本算法中，Cj

=

Cmyid,j,

A=

Amyid,

B在处理器中每次循环向前移动一个处理器，即每次交换一个子矩阵数据块，共交换

p-1次19行列划分并行算法一：行列划分fori=0top-1行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程序：ex4matmul01.f20行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程行行划分

行行划分：A

按行划分、B按行划分21行行划分行行划分：A按行划分、B按行划分21行行划分22行行划分22列列划分

列列划分：A

按列划分、B按列划分23列列划分列列划分：A按列划分、B按列划分23列列划分24列列划分24列行划分

列行划分：A

按列划分、B按行划分25列行划分列行划分：A按列划分、B按行划分25列行划分26列行划分26Cannon算法27Cannon算法27Cannon算法28Cannon算法28Cannon算法29Cannon算法29Cannon算法示例

以3×3分块为例：9个进程，进行三轮计算

A、B

的起始存放位置：A00

A01

A02A10

A11

A12A20

A21

A22B00

B01

B02B10

B11

B12B20

B21

B22第一轮：计算A00

A00

A00A11

A11

A11A22

A22

A22B00

B01

B02B10

B11

B12B20

B21

B2230Cannon算法示例以3×3分块为例：9个进程，进Cannon算法示例第二轮：计算B10

B11

B12B20

B21

B22B00

B01

B02A01

A01

A01A12

A12

A12A20

A20

A20第三轮：计算B20

B21

B22B00

B01

B02B10

B11

B12A02

A02

A02A10

A10

A10A21

A21

A2131Cannon算法示例第二轮：计算B10B11Cannon算法32Cannon算法32Cannon算法33Cannon算法33Cannon算法示例34Cannon算法示例34上机作业按行行划分并行计算矩阵乘积，其中编写用第二种方式实现上述矩阵乘积的Cannon并行算法35上机作业按行行划分并行计算矩阵乘积，其中编写用第二种方式主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法

矩阵的LU分解并行算法下三角线性方程组的并行算法36主要内容并行算法基础知识36线性方程组直接解法37线性方程组直接解法37线性方程组直接解法38线性方程组直接解法38矩阵LU分解39矩阵LU分解39矩阵LU分解40矩阵LU分解40矩阵LU分解41矩阵LU分解41矩阵LU分解42矩阵LU分解42上机作业编写LU分解的并行程序，其中43上机作业编写LU分解的并行程序，其中43主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法

下三角线性方程组的并行算法44主要内容并行算法基础知识44三角方程并行求解45三角方程并行求解45三角方程并行求解46三角方程并行求解46三角方程并行求解47三角方程并行求解47三角方程并行求解48三角方程并行求解48三角方程并行求解49三角方程并行求解49三角方程并行求解50三角方程并行求解50上机作业用算法3编写并行程序求解下三角方程组其中51上机作业用算法3编写并行程序求解下三角方程组其中51第六讲

矩阵计算并行算法52第六讲

矩阵计算并行算法1主要内容并行算法基础知识矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法53主要内容并行算法基础知识2并行算法基础知识一些基本概念加速比其中Ts

串行程序运行时间，Tp(q)为q

个进程的运行时间并行效率54并行算法基础知识一些基本概念加速比其中Ts串行程序运程序性能优化串行程序性能优化——并行程序性能优化的基础调用高性能库。如：BLAS、LAPACK、FFTW选择编译器优化选项：-O2、-O3合理定义数组维数注意嵌套循环次数：数据访问的空间局部性和时间局部性数据分块循环展开例:ex4performance.c55程序性能优化串行程序性能优化——并行程序性能优化的基础程序性能优化并行程序性能优化设计好的并行算法和通信模式减少通信次数、提高通信粒度多进程通信时尽量使用高效率的聚合通信算法负载平衡通信与计算的重叠减少进程的空闲时间通过引入重复计算来减少通信56程序性能优化并行程序性能优化设计好的并行算法和通信模式矩阵并行算法一些记号和假定假设有p

个处理器，每个处理器上运行一个进程

Pj

表示第j

个处理器，Pmyid

表示当前的处理器

send(x;j)

表示在Pmyid

中把数据块x

发送给Pj

进程

recv(x;j)

表示从Pj

进程接收数据块x

imod

p

表示i

对p取模运算程序设计与机器实现是密不可分的，计算结果的好坏与编程技术有很大的关系，尤其是在并行计算机环境下，开发高质量的程序对发挥计算机的性能起着至关重要的作用57矩阵并行算法一些记号和假定假设有p个处理器，每个处理主要内容并行算法基础知识

矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法58主要内容并行算法基础知识7矩阵向量乘积串行算法实现方法一：i-j

循环fori=1tomy(i)=0.0

forj=1tony(i)=y(i)+A(i,j)*x(j)

end

forend

for59矩阵向量乘积串行算法实现方法一：i-j循环fori=矩阵向量乘积串行算法实现方法二：j-i

循环例：ex4matvec.fy=0%先赋初值forj=1ton

fori=1tomy(i)=y(i)+A(i,j)*x(j)

end

forend

for60矩阵向量乘积串行算法实现方法二：j-i循环例：ex4m矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分按行划分并行算法将矩阵A

按行划分成如下的行块子矩阵将Ai

存放在结点Pi

中，每个结点计算Aix，最后调用MPI_GATHER

或MPI_GATHERV

即可则61矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分矩阵向量乘积并行算法二按列划分并行算法将Ai

和xi

存放在结点Pi

中，每个结点计算AixiT，最后调用MPI_REDUCE

或MPI_ALLREDUCE即可将矩阵A

按列划分，并对x

也做相应的划分其中

xi

的长度与

Ai

的列数相同，则有62矩阵向量乘积并行算法二按列划分并行算法将Ai和xi矩阵向量乘积示例例：按列划分，用p

个进程并行计算矩阵向量乘积，其中示例程序：ex4matvec.f63矩阵向量乘积示例例：按列划分，用p个进程并行计算矩阵向上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并行程序2、按列划分，编写通用并行程序计算上面的乘积64上机作业上机作业：1、编写按行划分计算矩阵向量乘积的通用并主要内容并行算法基础知识矩阵向量乘积的并行算法

矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法65主要内容并行算法基础知识14矩阵矩阵乘积

串行算法一：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

forend

for66矩阵矩阵乘积串行算法一：i-j-k循环fori=1t矩阵矩阵乘积

串行算法二：j-k-i

循环C=0for

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

forend

for67矩阵矩阵乘积串行算法二：j-k-i循环C=016并行矩阵乘积假定：基于A、B

的不同划分，矩阵乘积的并行算法可分为行列划分行行划分列列划分列行划分m,l,n

均能能p

整除，其中p

为进程个数68并行矩阵乘积假定：基于A、B的不同划分，矩阵乘积的并行列划分

行列划分：A

按行划分、B按列划分令C=(Cij)，其中Cij

=

AiBj

将Ai,Bj

和Cij(j=0,1,...,p-1)存放在第i个处理器中

(这样的存储方式使得数据在处理器中不重复)

Pi

负责计算Cij(j=0,1,...,p-1)

由于使用p

个处理器，每次每个处理器只计算一个Cij,

故计算出整个C

需要p

次完成

Cij

的计算是按对角线进行的69行列划分行列划分：A按行划分、B按列划分令C=行列划分

并行算法一：行列划分fori=0

to

p-1

j=(i+myid)modpCj=A*Bsrc=(myid+1)modpdest=(myid-1+p)modp

if(i!=p-1)

send(B,dest)

recv(B,src)

end

ifend

for

本算法中，Cj

=

Cmyid,j,

A=

Amyid,

B在处理器中每次循环向前移动一个处理器，即每次交换一个子矩阵数据块，共交换

p-1次70行列划分并行算法一：行列划分fori=0top-1行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程序：ex4matmul01.f71行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程行行划分

行行划分：A

按行划分、B按行划分72行行划分行行划分：A按行划分、B按行划分21行行划分73行行划分22列列划分

列列划分：A

按列划分、B按列划分74列列划分列列划分：A按列划分、B按列划分23列列划分75列列划分24列行划分

列行划分：A

按列划分、B按行划分76列行划分列行划分：A按列划分、B按行划分25列行划分77列行划分26Cannon算法78Cannon算法27Cannon算法79Cannon算法28Cannon算法80Cannon算法29Cannon算法示例

以3×3分块为例：9个进程，进行三轮计算

A、B

的起始存放位置：A00

A01

A02A10

A11

A12A20

A21

A22B00

B01

B02B10

B11

B12B20

B21

B22第一轮：计算A00

A00

A00A11

A11

A11A22

A22

A22B00

B01

B02B10

B11

B12B20

B21

B2281Cannon算法示例以3×3分块为例：9个进程，进Cannon算法示例第二轮：计算B10

B11

B12B20

B21

B22B00

B01

B02