第六講

矩陣計算并行算法1第六講

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

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

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

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

Pj

表示第j

個處理器，Pmyid

表示當前的處理器

send(x;j)

表示在Pmyid

中把數據塊x

發(fā)送給Pj

進程

recv(x;j)

表示從Pj

進程接收數據塊x

imod

p

表示i

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

矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法7主要內容并行算法基礎知識7矩陣向量乘積串行算法實現方法一：i-j

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

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

end

forend

for8矩陣向量乘積串行算法實現方法一：i-j循環(huán)fori=矩陣向量乘積串行算法實現方法二：j-i

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

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

end

forend

for9矩陣向量乘積串行算法實現方法二：j-i循環(huán)例：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個進程并行計算矩陣向上機作業(yè)上機作業(yè)：1、編寫按行劃分計算矩陣向量乘積的通用并行程序2、按列劃分，編寫通用并行程序計算上面的乘積13上機作業(yè)上機作業(yè)：1、編寫按行劃分計算矩陣向量乘積的通用并主要內容并行算法基礎知識矩陣向量乘積的并行算法

矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法14主要內容并行算法基礎知識14矩陣矩陣乘積

串行算法一：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矩陣矩陣乘積串行算法一：i-j-k循環(huán)fori=1t矩陣矩陣乘積

串行算法二：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矩陣矩陣乘積串行算法二：j-k-i循環(huán)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在處理器中每次循環(huán)向前移動一個處理器，即每次交換一個子矩陣數據塊，共交換

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

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

下三角線性方程組的并行算法44主要內容并行算法基礎知識44三角方程并行求解45三角方程并行求解45三角方程并行求解46三角方程并行求解46三角方程并行求解47三角方程并行求解47三角方程并行求解48三角方程并行求解48三角方程并行求解49三角方程并行求解49三角方程并行求解50三角方程并行求解50上機作業(yè)用算法3編寫并行程序求解下三角方程組其中51上機作業(yè)用算法3編寫并行程序求解下三角方程組其中51第六講

矩陣計算并行算法52第六講

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

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

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

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

Pj

表示第j

個處理器，Pmyid

表示當前的處理器

send(x;j)

表示在Pmyid

中把數據塊x

發(fā)送給Pj

進程

recv(x;j)

表示從Pj

進程接收數據塊x

imod

p

表示i

對p取模運算程序設計與機器實現是密不可分的，計算結果的好壞與編程技術有很大的關系，尤其是在并行計算機環(huán)境下，開發(fā)高質量的程序對發(fā)揮計算機的性能起著至關重要的作用57矩陣并行算法一些記號和假定假設有p個處理器，每個處理主要內容并行算法基礎知識

矩陣向量乘積的并行算法矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法58主要內容并行算法基礎知識7矩陣向量乘積串行算法實現方法一：i-j

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

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

end

forend

for59矩陣向量乘積串行算法實現方法一：i-j循環(huán)fori=矩陣向量乘積串行算法實現方法二：j-i

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

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

end

forend

for60矩陣向量乘積串行算法實現方法二：j-i循環(huán)例：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個進程并行計算矩陣向上機作業(yè)上機作業(yè)：1、編寫按行劃分計算矩陣向量乘積的通用并行程序2、按列劃分，編寫通用并行程序計算上面的乘積64上機作業(yè)上機作業(yè)：1、編寫按行劃分計算矩陣向量乘積的通用并主要內容并行算法基礎知識矩陣向量乘積的并行算法

矩陣矩陣乘積的并行算法矩陣的LU分解并行算法下三角線性方程組的并行算法65主要內容并行算法基礎知識14矩陣矩陣乘積

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

for66矩陣矩陣乘積串行算法一：i-j-k循環(huán)fori=1t矩陣矩陣乘積

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

for67矩陣矩陣乘積串行算法二：j-k-i循環(huán)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在處理器中每次循環(huán)向前移動一個處理器，即每次交換一個子矩陣數據塊，共交換

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