矩阵计算并行算法

第六讲

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

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

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

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

Pj

表示第j

个处理器，Pmyid

表示当前的处理器

send(x;j)

表示在Pmyid

中把数据块x

发送给Pj

进程

recv(x;j)

表示从Pj

进程接收数据块x

imod

p

表示i

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

矩阵向量乘积的并行算法矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法7精选ppt矩阵向量乘积串行算法实现方法一：i-j

循环fori=1tomy(i)=0.0

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

end

forend

for8精选ppt矩阵向量乘积串行算法实现方法二：j-i

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

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

end

forend

for9精选ppt矩阵向量乘积并行算法一矩阵的划分方法：按行划分和按列划分按行划分并行算法将矩阵A

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

存放在结点Pi

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

或MPI_GATHERV

即可则10精选ppt矩阵向量乘积并行算法二按列划分并行算法将Ai

和xi

存放在结点Pi

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

或MPI_ALLREDUCE即可将矩阵A

按列划分，并对x

也做相应的划分其中

xi

的长度与

Ai

的列数相同，则有11精选ppt矩阵向量乘积示例例：按列划分，用p

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

矩阵矩阵乘积的并行算法矩阵的LU分解并行算法下三角线性方程组的并行算法14精选ppt矩阵矩阵乘积

串行算法一：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精选ppt矩阵矩阵乘积

串行算法二：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精选ppt并行矩阵乘积假定：基于A、B

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

均能能p

整除，其中p

为进程个数17精选ppt行列划分

行列划分：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精选ppt行列划分

并行算法一：行列划分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精选ppt行列划分程序示例例：按行列划分并行计算矩阵乘积，其中示例程序：ex4matmul01.f20精选ppt行行划分

行行划分：A

按行划分、B按行划分21精选ppt行行划分22精选ppt列列划分

列列划分：A

按列划分、B按列划分23精选ppt列列划分24精选ppt列行划分

列行划分：A

按列划分、B按行划分25精选ppt列行划分26精选pptCannon算法27精选pptCannon算法28精选pptCannon算法29精选pptCannon算法示例

以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

B2230精选pptCannon算法示例第二轮：计算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

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

矩阵的LU分解并行算法下三角线性方程组的并行算法36精选ppt线性方程组直接解法37精选ppt线性方程组直接解法38精选ppt矩阵LU分解39精选ppt矩阵LU分解40精选ppt矩阵LU分解41精选ppt矩阵LU分解42精选ppt上机作业编写LU分解的并行程序，其中43精选ppt主要内容并行