矩陣計算并行算法

第六講

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

串行程序運行時間，Tp(q)為q

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

個處理器，每個處理器上運行一個進程

Pj

表示第j

個處理器，Pmyid

表示當前的處理器

send(x;j)

表示在Pmyid

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

發(fā)送給Pj

進程

recv(x;j)

表示從Pj

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

imod

p

表示i

對p取模運算程序設計與機器實現(xiàn)是密不可分的，計算結果的好壞與編程技術有很大的關系，尤其是在并行計算機環(huán)境下，開發(fā)高質量的程序對發(fā)揮計算機的性能起著至關重要的作用6精選ppt主要內容并行算法基礎知識

矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法7精選ppt矩陣向量乘積串行算法實現(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矩陣向量乘積串行算法實現(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

存放在結點Pi

中，每個結點計算Aix，最后調用MPI_GATHER

或MPI_GATHERV

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

和xi

存放在結點Pi

中，每個結點計算AixiT，最后調用MPI_REDUCE

或MPI_ALLREDUCE即可將矩陣A

按列劃分，并對x

也做相應的劃分其中

xi

的長度與

Ai

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

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

矩陣矩陣乘積的并行算法矩陣的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

為進程個數(shù)17精選ppt行列劃分

行列劃分：A

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

=

AiBj

將Ai,Bj

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

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

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在處理器中每次循環(huán)向前移動一個處理器，即每次交換一個子矩陣數(shù)據(jù)塊，共交換

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上機作業(yè)按行行劃分并行計算矩陣乘積，其中編寫用第二種方式實現(xiàn)上述矩陣乘積的Cannon并行算法35精選ppt主要內容并行算法基礎知識矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法

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