矩陣計算并行算法_第1頁
矩陣計算并行算法_第2頁
矩陣計算并行算法_第3頁
矩陣計算并行算法_第4頁
矩陣計算并行算法_第5頁
已閱讀5頁,還剩46頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第六講

矩陣計算并行算法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主要內容并行

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論