并行计算课件

并行计算——结构•算法•编程主讲:雷向东中南大学信息科学与工程学院Central

South

UniversityCollege

of

Information

Science

and

Engineering第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第十章线性方程组的求解三角形方程组的求解三对角方程组的求解稠密线性方程组的求解稀疏线性方程组的求解10.1

三角形方程组的求解基本术语上三角方程组的求解5基本术语线性方程组的定义和符号a1,1x1a2,1x1+

a1,2x2+

a2,1x2+

…

+

a1,nxn

=

b1+

…

+

a2,nxn

=

b2+

an,1x2+

…

+

an,nxn

=

bnan,1x1记为AX=b

n

nn

bn

b

b

=

x

x=

aA

=

x

a

a

a

a2

b1

x1

n1

n

22221a1n

a11

a12a2

,2n

,10.1

三角形方程组的求解基本术语上三角方程组的求解上三角方程组的求解上三角方程组的回代解法并行化SISD上的回代算法

Beginfor

i=n

downto

1

do(1.1)xi=bi/aii(1.2)for

j=1

to

i-1

dobj=bj-ajixiaji=0endforendforEnd可并行化7上三角方程组的求解上三角方程组的回代解法并行化(2)SIMD-CREW上的并行回代算法划分:p个处理器行循环带状划分算法Beginfor

i=n

downto

1

doxi=bi/aiifor

all

Pj,

where

1≤j≤p

dofor

k=j

to

i-1

step

p

dobk=bk-akixiaki=0endforendforendforEnd //

p(n)=n,

t(n)=nP81PjP1Pj行1j1+pj+p第十章线性方程组的求解三角形方程组的求解三对角方程组的求解稠密线性方程组的求解稀疏线性方程组的求解10.2

三对角方程组的求解直接求解法奇偶规约法11三对角方程组的直接求解法Gauss消去法(难以并行化)①消元②回代注：由于三对角的方程组的特殊性，一次消元或一次回代，只涉及邻近一个方程，故难以并行化。10.2

三对角方程组的求解直接求解法奇偶规约法三对角方程组的直接求解法13奇偶规约求解法(可并行化)三对角方程可以写成如下形式i=1~nfixi-1+gixi+hixi+1=bif1=hn=0串行算法描述①利用上下相邻方程消去偶序号方程中的奇下标变量:f2i-1x2i-2+g2i-1x2i-1+h2i-1x2if2ix2i-1

+

g2ix2i

+

h2ix2i+1=b2i-1=b2if2i+1x2i

+g2i+1x2i+1+h2i+1x2i+2

=

b2i+12i-1方程乘上某个数消去2i方程中的f2ix2i-1项,2i+1方程乘上某个数消去2i方程中的h2ix2i+1项,使2i方程变为αix2i-2+βix2i+γix2i+2=ηii=1,2,…,n/2三对角方程组的直接求解法②重复①最终可得:14case

1:case

2:g1x1+h1x2f2x1+g2x2+h2x3=b1=b2....或f3x2

+g3x3+h3x4=b3f4x3

+g4x4

=b4可以分别得到g1x1+h1x2

=b1f2x1+g2x2

=b2g1x1+h1x2

=b1f2x1+g2x2+h2x3

=b2f3x2+g3x3

=b3解得x1,x2

或x1,x2,x3③回代求解x并行化分析:①、②消去奇下标可以并行化；③回代求解可以并行化第十章线性方程组的求解三角形方程组的求解三对角方程组的求解稠密线性方程组的求解稀疏线性方程组的求解10.3

稠密线性方程组的求解有回代的高斯消去法无回代的高斯-约旦法迭代求解的高斯-赛德尔法有回代的高斯消去法算法基本原理求解过程分为消元和回代两个阶段，消元是将系数矩阵A化为上三角阵T，然后对TX=c进行回代求解。消元过程中可以应用选主元方法，增加算法的数值稳定性。下面是消元过程图：17有回代的高斯消去法并行化分析消元和回代均可以并行化；选主元也可以并行化；消元过程的并行化图示：处理器按行划分主元行待改变的元素不变化的元素待消为0的元素图10.1已消为0的元素可并行化部分1810.3

稠密线性方程组的求解有回代的高斯消去法无回代的高斯-约旦法迭代求解的高斯-赛德尔法无回代的高斯-约旦法20串行算法原理①消元:通过初等行变换,将(A,b)化为主对角线矩阵,

(方便起见,记b为A的第n+1列)j②求解:x

=a’

/a’j,n+1

jj222221nn n,n+1

2,n+1

n,n+1

2,n+1

2na¢

a¢a¢a¢a1,n+1

a11aaa1,n+1

annan1

an

2aa1na11

a12

a

a无回代的高斯-约旦法21SIMD-CREW上的并行算法处理器:n2+n个处理器,这些处理器排成n×(n+1)的矩阵,处理器编号为Pik,i=1~n,

k=1~n+1并行化分析//第j次消元①消元的并行化: //

O(n)

for

j=1

to

n-1,

each

Pik

Par-doPij(i<>j):

aij

<—

0Pik(i<>j,

k=j+1~n+1):

aik

<—

aik-ajk(aij/ajj)end

for②求解:for

each

Pjj(j=1~n)Par-do:xj

<—aj,n+1/ajj//O(1)(3)时间分析:t(n)=O(n),

p(n)=O(n2),c(n)=O(n3)成本最优？无回代的高斯-约旦法22成本最优？串行算法的最优时间：由于x=A-1b①A-1b(假设已有A-1):

O(n2)②求A-1:a(n/2)2次n/2×n/2矩阵的加i(n)=i(n/2)+6m(n/2)+2a(n/2)a(n/2)=n2/2,

m(n/2)=O((n/2)x)2<x<2.5=>i(n)=O(nx) 综上，串行算法的最优时间为O(nx)2<x<2.521

11

122221

11110

I

0AA

AB

-1A

-1

AA

-1-

A A

-1

AA

-1

I

I0

-

Ai(n/2)

6次n/2×

n/2矩阵的乘

m(n/2)

I

-

A

-1

A

A

-1

0

∴求A-1需要:A2次-1

n=/2

×n/2矩11阵的12

逆11 12

I

I

0

II

0

B

0

0

A11

=

21 22

21

11

A11

A12

A

=

其中，B

=A10.3

稠密线性方程组的求解有回代的高斯消去法无回代的高斯-约旦法迭代求解的高斯-赛德尔法迭代求解的高斯-赛德尔法串行算法原理则认为迭代是收敛的。并行化分析由于每次迭代需要使用本次迭代的前面部分值，因而难以得到同步的并行算法，下面给出一个异步的并行算法。

=

-ij

>ikij

jij

j如果对某个k,

给定的ii误差j<允i

许值c有ia

x

-

baxa

xk

+1

+k

+11x24nki

i-

x

<

ci=1k

+1迭代求解的高斯-赛德尔法25MIMD异步并行算法N个处理器(N≤n)生成n个进程,每个进程计算x的一个分量算法Beginoldi

xi0,newi

xi0(2)生成进程i(3)进程irepeatoldi

newinewi

(bi-∑k<iaik×oldk-∑k>iaik×oldk)/aiiuntil

∑i=1~n|

oldi

-

newi

|<cxi

newiEnd第十章线性方程组的求解三角形方程组的求解三对角方程组的求解稠密线性方程组的求解稀疏线性方程组的求解10.4

稀疏线性方程组的求解线性方程组的并行化方法稀疏线性方程组的迭代解法高斯-赛德尔迭代法的并行化线性方程方程的并行化方法28线性方程组选择算法的考虑因素系数矩阵A的结构Gaussian

elimination,

etciterative

methodsubstitution,

odd-even

reductionmultigrid,

etcdenseSparsetriangularcertain

PDEs计算精度要求Gaussian

elimination: more

accurate,

moreexpensiveConjugate

gradients: less

accurate,

lessexpensive计算环境要求architecture,

available

languages,

compiler

qualitylibraries?线性方程方程的并行化方法29求解方法的并行化(1)直接解法的并行化(用于稠密线性方程组)Gauss消去法(包括选主元的Gauss消去法)Gauss-Jordan消去法LU分解法

(2)迭代法的并行化(用于稠密和稀疏线性方程组)JacobiGauss-Seidel(可异步并行化)Jacobi

OverRelaxation(JOR)Gauss-Seidel

OverRelaxation(SOR)Conjugate

Gradient10.4

稀疏线性方程组的求解线性方程组的并行化方法稀疏线性方程组的迭代解法高斯-赛德尔迭代法的并行化31稀疏线性方程方程的迭代解法迭代解法kkiikkiiiikiiiki(5)

Conjugate

Gradient(4)

SOR

:

xa

x

)

/

a(3)

JOR

:

xa

x

)

/

aa

x

)

/

a(1)

Jacobi

:

x

ij

ji

ij

ji

ij

jk

+1k

+1i

ij

j

iij

„ii

ij

j

ij

j

iij<i j

>ik

+1j

>ik

+1k

+1j

„ik

+1-

a

x

-

a

x

)

/

aa

x

-=

(b

-(2)

Gauss

-

Seidel

:

x=

(b

-+w

(b=

(1-w

)x+w

(b

-j<i=

(1-w

)x10.4

稀疏线性方程组的求解线性方程组的并行化方法稀疏线性方程组的迭代解法高斯-赛德尔迭代法的并行化高斯-赛德尔迭代法的并行化由PDE离散产生的稀疏线性方程组(1)Laplace方程求u(x,y)满足上面的方程，且满足边值j(x,y)+ =

g(x,

y)

(x,

y)

˛

D

=[0,1]·[0,1]¶x2

¶y2¶2u(x,

y)

¶2u(x,

y)33高斯-赛德尔迭代法的并行化(2)由五点格式的离散化(假设g(x,y)=0)代入Laplace方程34N

N41

,

E为单位阵

1E+

u

] 0

<

i,

j

<

N+

u

u

=

1

[u

+

u»

[u(x,

y

+

h)