ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



ǾͲģ⸺ƽķ㷨*
1,2Խ1,2 ά3 ŵ¸1,2
ժҪڷֲʽмϵͳ,һǾͲֵģ,ֽⷽ,˲ĸƽģͼƽһЧ㷨,ӶͲֵģӳ䵽л,Чز.ںͲֵģⲢо,ʵ,㷨߼ٱ.
ؼʡͲֵģ,ֽ,ƽ,㷨.
ͼšTP301
Zonal Parallel Algorithm of Load-balancing on Nonuniform Domain Simulation of Reservoir 
SHU Ji-wu1,2 ZHAO Jin-xi1,2 ZHOU Wei-si3 ZHANG De-fu1,2 
Abstract Based on the distributed parallel environment, for one of the nonuniform domain numerical simulation problems of reservoir, the authors give a load-balance model of parallel computing and a zonal parallel algorithm of load-balance using domain decomposition method, so some well and effective solutions which balancly map the nonuniform domain numerical simaulation of reservoir to parallel environment are found. In the study of block oil reservoir numerical simulation parallel software, the practical results show that the zonal parallel algorithm can improve the performance in speedup.
Key wordsNumerical simulation of reservoir, domain decomposition, load-balancing, parallel algorithm.
Ͳֵģ,޲Ϊƫ΢̵ַ.Ҫļʱ,,ļٶȳΪǷǳĵ.ֽⷨӦ˶ġӦмԭƫ΢ֵַ㷨.ˡֶ֮˼,ܵѧ͹̽йע.÷ġģͼ,ָɶĹģС,ԭתΪ.һɸһ,еӳ䵽ʱ,ͨϴĽ,Ĳ,˽ٶ,йӦǰ.
ֽⲢм,ڽϲлϵṹʱ,ҪĻּƽ.ף1ݻڶάӵķֲʽдṹ,ڸֽⷽļ㸴ԺͨźķѵĻ϶ٱȺЧʽ˷.ף2ݶ񻮷벢мЧʽ,Ѱŵ.Ƕ,򻮷ΪȴС,ΪȫͬļͨҪ.ʵʵ,Ͳģ,ǲȵ,ѡʱ,Ϊ˱ڴ,ѡһ,糤.򻮷ֳ봦ĿͬĵȴС,ٶȾͲͬ,Ӧ䵽Ͻĸز.,ҪάһȶĸЧд,øƽķм㷽.Ͳֵģ,ֽⷽǾĺѹΪ,˲ĸƽģͼƽһַ㷨.
1 ֽⲢ㷨
ֽⷨҪ3:ӽṹ,ص;Schwarz,ص;ӽṹSchwarzĽ.
Schwarz͵ֽ㷨˵䲢Ļ.һģΪ:
(1)
򦸽зֽ:зֽ⦸=i,iǿ,Ҷÿiҵji,Цiɦj.
⣨1ƽĲSchwarz£3:
1: ѡʼP0,n0.
2: мϱֵ
(2)
3: Pn+1iĶ嵽ʽ(3),
(3)
ȡƽ
(4)
n=n1,ﵽ⾫,ֹ;,ת2.
,һֵ,ӦֽⷨĻΪ:
.ʵ,ָΪ.
.,ڽԴ.
.ݺ.
.ѭ:
do{
PiĵѭУ:
do{

}whileδﵽӦ
߽ڵ㣨صֽ⣩򹫹صֽ⣩
}whileδﵽ
.,õĽ. 
2 ƽķ㷨
ֽⷽ,ǵȴϵϢ,,岢˻ͬ.Ϊ˽,Ҫ: Ҫ紫; ҪøЧ㷨,ʹøٶ; Ҫøƽķ,ʹÿɵʱ.ҪֽⷽǾĸƽ.
2.1 ǾĻ
ڷǾͲֵģ,еڰġڵ㣨Ľڵ㣩,ﵽʱ,еڰٵġڵ㡱,ﵽʱܶ.ֵĿڴĸ,ڿʼʱ,ܹƳ,ΪܽϺõʹƽ,ĿԶڴĸ,,ڻֵ̫,ٶȼ.ﻮֵĿڴĸ,,ݱϵľֲ״̬Ϣȫ״̬̬ظıĻ,ӶﵽܾеĿ.
账Ϊ:P={P1,P2,P3,...,Pm},PiΪi,Ϊm.ΪһͲģ,ֽΪm,зֽ⦸=i,򼯦={1,2,...,m },iΪi.
ÿһ漰Ĳе͸ƽ㷨,Pmax-iterεִܵʱ4Ϊ
5
kΪ,iΪPii=1,2,...,P,,iʾPiڵkεִʱ,,iʾPiڵkεƽ㷨ʱ.е,ͬͨǽе,Piһεʱ3صӰ.
Tapp,i(k)=f(tcomp,tcomm,tid),6
tcompһεļʱ,tcommǵͨʱ,tidͬȴʱ.ڵ,ĻӦִܵʱ価ΪĿ.
2.2 мļ˵
,ͲֵģֽⲢм¼˵:
1 ǲȵ,ѡļһ,糤.ɢͬ,ⷽԲͬ,ҲԲͬ.
2 ڲм㻷,ĴڻûĽ̬ı仯,Ϣͨӳٷ仯,ﲻ紫ܼܵı仯.ͬһϵ֮ͨŴΪ0,ͬһϵ֮ͨŴֻı߽С򹫹Сй.
3 ϼͨŲص.
4 ֽⲢеʱ,ÿһĶε,ֱֱﵽ.ĵڸĵٵö.ｫÿһÿһĵΪһ,Ǩʹı߽ƶ,Сı仯,ӶһֵǨƵ.Ľֵʹÿһε̺.
5 ʵӦ,Ŀһ,Ͳģһܴ,ֺļٶĽڵÿεĵֵ㷨й.
6 ,ǳΣ壩,Ļ봦һһӦ,Ŀ봦Ŀ.ÿֻڵĴ.
2.3 ƽģͼ㷨
ĵΪk=1,2,...,ÿһ,ɸݴϢƽ㷨,ƽ㷨漰ʱ̿kʾ.
1. wk:ϵͳkʱ̵״̬-ķֲ.wik:Pik,ʱk+1ֲ:kʱ̵ֲƽ񴫵.PiĸƽģͿɱΪ
wi(k+1)=wi(k)-wi,l.d,s(k)+wi,l.d,r(k),7
wi,l.d,sk,wi,l.d,r(k)ֱʾƽķͺͽյ.
2. Ak:,PĲϵͳ,һppľ,ÿֻڵĴ·.PiPjǨ,ӦԪΪ1,, ӦԪΪ0.
3. Mk:Ǩ,һppľ.ÿֻڵĴǨ.Mij:PiPjǨ,Pi͸PjɱʾΪ:Mijk.wik.
4. H:ǨƵ·.Hij:PiPjǨ,ӦԪΪ1,, ӦԪΪ0.,Mij0Hij=1.
Ķ,ʽ7Ϊ
wi(k+1)=wi(k)-Mij(k)Aii(k)wi(k)+Mji(k)Ajj(k)wj(k).8
ʽ,1ʾӴPiڴǨ;2ʾPiڴPiǨ.:Mii(k)=-Mij(k),ƽģͿԱΪ
w(k+1)=w(k)+M(k)TA(k)w(k).9
5. :ֲ.
= 
6. :PiڴֲƽϢ.
= 
dΪPiڴ,RiΪPiڴ.
 ͿɷֱΪֲȫϢ;ֲϢ.
,Pikεɵʱ,iΪkʱ̵wi(k),øƽķ㷨ɱΪ:
1 Ϊ1,...,m,Ӧط䵽P1,...,Pm.ʼΪS={1,2,...,m}.
2 ӦֽⲢ㷨,ڴϲִ,ֱﵽ;ֱͳʱ,i,Ϊwi(k).
3 ı߽ڵ򹫹.
4 ﵽ,ֹ;,ת5.
5 Sѡi(k)=maxp(k),pSĴPiPl,Pll(k)=min
p(k),pS.i-lܦ(Ϊĸز,ת2;,ת6.
6 PiڴѡPj,j(k)=minwp(k),pRii򼯼ΪRi,i-j,PiĲǨƵPj,ij֮».PiǨƵPjԼΪ:wi(k)-k(k);,ת7.
7 S=S-{i},S,ת5;,S={1,2,...,m},ת2.
3 ʵ
ںֵģⲢло,ʹֽⲢм,˽ϺõЧ.һͲģкѹģ,
(10)

Ct=Cr+CoSo+CwSw+CgSg, Pcow=Po-Pw, Pcgo=Pg-Po, So+Sw+Sg=1 
,±o,w,gֱΪ͡ˮ,±scΪ׼,BΪϵ,RsoΪܽͱ,qΪעɳ,SΪͶ,PΪѹ,PcΪëѹ,Ϊ϶,Ϊܶ,L1Ϊ߽,tΪʱ,fǹʱѹ.
ģ͵ִͱֵ,Ӧõӽṹ͵ֽⷽ,ɢģʹ˵ɻΪһϵӱ߶ԽǿԷ.򦸷ֳɻཻmi,i1,2,...,m,òΪh,7ָʽɢ,ɵõԷ5.
11
ʽA1,1,A2,2,...,Am,mֱӦ1,2,...,mϵľ.ʽ10õ,ǰһ׶εĽƽΪһ׶εĳʼ,ʹ.ÿһеÿAj,jpj=fj-j,m+1pm+1j=1,2,...,m,ԶӦط䵽mϲ,ÿһ,Ըݸƽ㷨,»,γµķ
12
γɵ:Aj,jpj=fj-Aj,m+1pm+1j=1,2,...,m,ԶӦmϲ.,ƽ㷨,ǰľ.ʵΪ:x,y,zֱΪ170505,ڵģΪ42500ģ,ƽzʷ,зǾȵطֲࡰڵ㡱.ֽⷨм30׶ΣʱΣ.бΪ:Pi+1-Piޡ10-4,Pi+1,PiֱΪĵi1͵iѹ.LUԤ弫Сʣ෨GMRESm,ȡGMRESm㷨еĽضϲmΪ10,бΪpm-p1ޡm*10-4,pm,p1ֱΪGMRESm㷨ĵm͵1ѹ.㻷PVMֱ̫ͨ2345SGI indyɼֲַʽмϵͳ.ͼ1˸úֵģͲøƽⷽ޸ƽʱļٱȵıȽ.ʵ,øƽⷽʹϵͳмٱ1040.4Ĳϵͳ޸ƽʱ,ģͼ30׶εļٱΪ2.51,ñĵĸƽ㷨ٱΪ3.25,ٱ29.5%.

ͼ1ٱȱȽ
оõ863߿ƼĿ.
߽ܣ,1969,ʿ,ҪоΪдͷֲʽ.
Խ,1950,ʿ,ڣҪоΪѧ,ֵ.
ά,1942,ڼ߹,ҪоΪ㼼Ͳģ.
ŵ¸,1937,,ʿʦ,ҪоΪ,д,ֲʽ.
ͨѶϵ:䣬 100084,廪ѧѧ뼼ϵ
ߵλ䡡Խŵ¸Ͼѧ¼صʵҡϾ 210093Ͼѧѧ뼼ϵϾ210093
άġʤʿѧоԺ Ӫ 257000
ο
1 Hoffmann K H, Zou Jun. Parallel efficiency of domain decomposition methods. Parallel Computing, 1993,1912:13751391
2Chan T F, Shao J P. Parallel complexity of domain decomposition methods and optimal coarse grid size. Parallel Computing, 1995,217:10331049
3,ʯ,񱦵.ֽⷨƫ΢ֵַ¼.:ѧ,1992(L? Tao, Shi Ji-min, Lin Zhen-bao et al. Domain Decomposition MethodsNew Technology for Numerical Solver of Partial Differential Equations. Beijing: Beijing Science and Technology Press, 1992)
4Franklin M A, Govindan V. A general matrix iterative model for dynamic load balancing. Parallel Computing, 1996,227:969989
5Խ,,ŵ¸.ͶԳƲԷķֽⷽ.ߵѧУѧѧ,1997,191:8392(Zhao Jin-xi, Shu Ji-wu, Zhang De-fu et al. A direct method for solving symmetric indefinite arrow linear system. Numerical Mathematics, A Journal of Chinese Universities, 1997,191:8392)
1997-11-13յԭ,1998-03-03յ޸ĸ
