矩陣計(jì)算并行算法

第六講

矩陣計(jì)算并行算法1精選ppt主要內(nèi)容并行算法基礎(chǔ)知識(shí)矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法2精選ppt并行算法基礎(chǔ)知識(shí)一些基本概念加速比其中Ts

串行程序運(yùn)行時(shí)間，Tp(q)為q

個(gè)進(jìn)程的運(yùn)行時(shí)間并行效率3精選ppt程序性能優(yōu)化串行程序性能優(yōu)化——并行程序性能優(yōu)化的基礎(chǔ)調(diào)用高性能庫(kù)。如：BLAS、LAPACK、FFTW選擇編譯器優(yōu)化選項(xiàng)：-O2、-O3合理定義數(shù)組維數(shù)注意嵌套循環(huán)次數(shù)：數(shù)據(jù)訪問(wèn)的空間局部性和時(shí)間局部性數(shù)據(jù)分塊循環(huán)展開(kāi)例:ex4performance.c4精選ppt程序性能優(yōu)化并行程序性能優(yōu)化設(shè)計(jì)好的并行算法和通信模式減少通信次數(shù)、提高通信粒度多進(jìn)程通信時(shí)盡量使用高效率的聚合通信算法負(fù)載平衡通信與計(jì)算的重疊減少進(jìn)程的空閑時(shí)間通過(guò)引入重復(fù)計(jì)算來(lái)減少通信5精選ppt矩陣并行算法一些記號(hào)和假定假設(shè)有p

個(gè)處理器，每個(gè)處理器上運(yùn)行一個(gè)進(jìn)程

Pj

表示第j

個(gè)處理器，Pmyid

表示當(dāng)前的處理器

send(x;j)

表示在Pmyid

中把數(shù)據(jù)塊x

發(fā)送給Pj

進(jìn)程

recv(x;j)

表示從Pj

進(jìn)程接收數(shù)據(jù)塊x

imod

p

表示i

對(duì)p取模運(yùn)算程序設(shè)計(jì)與機(jī)器實(shí)現(xiàn)是密不可分的，計(jì)算結(jié)果的好壞與編程技術(shù)有很大的關(guān)系，尤其是在并行計(jì)算機(jī)環(huán)境下，開(kāi)發(fā)高質(zhì)量的程序?qū)Πl(fā)揮計(jì)算機(jī)的性能起著至關(guān)重要的作用6精選ppt主要內(nèi)容并行算法基礎(chǔ)知識(shí)

矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法7精選ppt矩陣向量乘積串行算法實(shí)現(xiàn)方法一：i-j

循環(huán)fori=1tomy(i)=0.0

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

end

forend

for8精選ppt矩陣向量乘積串行算法實(shí)現(xiàn)方法二：j-i

循環(huán)例：ex4matvec.fy=0%先賦初值forj=1ton

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

end

forend

for9精選ppt矩陣向量乘積并行算法一矩陣的劃分方法：按行劃分和按列劃分按行劃分并行算法將矩陣A

按行劃分成如下的行塊子矩陣將Ai

存放在結(jié)點(diǎn)Pi

中，每個(gè)結(jié)點(diǎn)計(jì)算Aix，最后調(diào)用MPI_GATHER

或MPI_GATHERV

即可則10精選ppt矩陣向量乘積并行算法二按列劃分并行算法將Ai

和xi

存放在結(jié)點(diǎn)Pi

中，每個(gè)結(jié)點(diǎn)計(jì)算AixiT，最后調(diào)用MPI_REDUCE

或MPI_ALLREDUCE即可將矩陣A

按列劃分，并對(duì)x

也做相應(yīng)的劃分其中

xi

的長(zhǎng)度與

Ai

的列數(shù)相同，則有11精選ppt矩陣向量乘積示例例：按列劃分，用p

個(gè)進(jìn)程并行計(jì)算矩陣向量乘積，其中示例程序：ex4matvec.f12精選ppt上機(jī)作業(yè)上機(jī)作業(yè)：1、編寫(xiě)按行劃分計(jì)算矩陣向量乘積的通用并行程序2、按列劃分，編寫(xiě)通用并行程序計(jì)算上面的乘積13精選ppt主要內(nèi)容并行算法基礎(chǔ)知識(shí)矩陣向量乘積的并行算法

矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法14精選ppt矩陣矩陣乘積

串行算法一：i-j-k

循環(huán)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

循環(huán)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

為進(jìn)程個(gè)數(shù)17精選ppt行列劃分

行列劃分：A

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

=

AiBj

將Ai,Bj

和Cij(j=0,1,...,p-1)存放在第i個(gè)處理器中

(這樣的存儲(chǔ)方式使得數(shù)據(jù)在處理器中不重復(fù))

Pi

負(fù)責(zé)計(jì)算Cij(j=0,1,...,p-1)

由于使用p

個(gè)處理器，每次每個(gè)處理器只計(jì)算一個(gè)Cij,

故計(jì)算出整個(gè)C

需要p

次完成

Cij

的計(jì)算是按對(duì)角線進(jìn)行的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在處理器中每次循環(huán)向前移動(dòng)一個(gè)處理器，即每次交換一個(gè)子矩陣數(shù)據(jù)塊，共交換

p-1次19精選ppt行列劃分程序示例例：按行列劃分并行計(jì)算矩陣乘積，其中示例程序：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個(gè)進(jìn)程，進(jìn)行三輪計(jì)算

A、B

的起始存放位置：A00

A01

A02A10

A11

A12A20

A21

A22B00

B01

B02B10

B11

B12B20

B21

B22第一輪：計(jì)算A00

A00

A00A11

A11

A11A22

A22

A22B00

B01

B02B10

B11

B12B20

B21

B2230精選pptCannon算法示例第二輪：計(jì)算B10

B11

B12B20

B21

B22B00

B01

B02A01

A01

A01A12

A12

A12A20

A20

A20第三輪：計(jì)算B20

B21

B22B00

B01

B02B10

B11

B12A02

A02

A02A10

A10

A10A21

A21

A2131精選pptCannon算法32精選pptCannon算法33精選pptCannon算法示例34精選ppt上機(jī)作業(yè)按行行劃分并行計(jì)算矩陣乘積，其中編寫(xiě)用第二種方式實(shí)現(xiàn)上述矩陣乘積的Cannon并行算法35精選ppt主要內(nèi)容并行算法基礎(chǔ)知識(shí)矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法

矩陣的LU分解并行算法下三角線性方程組的并行算法36精選ppt線性方程組直接解法37精選ppt線性方程組直接解法38精選ppt矩陣LU分解39精選ppt矩陣LU分解40精選ppt矩陣LU分解41精選ppt矩陣LU分解42精選ppt上機(jī)作業(yè)編寫(xiě)LU分解的并行程序，其中43精選ppt主要內(nèi)容并行