ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ڶͲ⸺ؾĲ񻮷
 Խ ά ŵ¸
ժҪĻڷֲʽмϵͳ,һάͲֵģ3񻮷ֲԡʽֽⷽʽֽ͡ϵķʽ,ǽ˱Ƚ,˼ʱ䡢ڸؾ߲ܵ񻮷ַ,ʵӦж72ڵĴģͲģ.ʵ,òԻֲĲ,ڼٱȵ.÷Ҳݲе񻮷.
ؼ м,ؾ,񻮷,Ͳֵģ.
ͼšTP319

Parallel Tasks Partitioning of Load-balancing for a Multiple Layers
Numerical Simulation of Reservoir
SHU Ji-wu1,2 ZHAO Jin-xi1,2 ZHOU Wei-si3 ZHANG De-fu1,2
1(State Key Laboratory for Novel Software Technology Nanjing University Nanjing 210093)
2(Department of Computer Science and Technology Nanjing University Nanjing 210093)
3(The Academy of Geological Sciences Shengli Oil-Field Dongying 257000)
Abstract In this paper, three tasks division strategies of load-balancing are given, which include a round-robin fashion, a domain partitioning fashion and a fashion of round-robin combining with domain partitioning, and a comparison is made. Then tasks division methods are proposed which can reduce solving times and benefit load-balancing and increases parallel efficiency for a simulation of reservoir of multiple layers two-dimension two-phase flow numerical problems on distributed memory parallel systems. This approach is applied to a large scale reservoir simulation which has over 720 000 grid points. The practical results show that the tasks generated by the strategy are well-balanced and benefit to improve speedup. This approach is apt to the problems for domain parallel or data parallel.
Key words Parallel computing, load-balancing, task dividing, numerical simulation of reservoir.
ͲģҪļʱ,мʹöǿƶ[1].ʯ͹˾òдɱ,.ڵһЩʯ͹˾ҲͶʹòмͲģ,ߴٶ,̴ʱ.صĹ.[2]÷ֲʽм(ipcs/860)һֵͲģ.[3]˽ֽⷨͶͲģһַ.[4]Transputerϵͳʵ˶άͲģĲ.Ͳֵģ,άͲֵģӦ÷ǳ㷺.ԴĲмΪ۱.ڲͬʱ䲽Сͬ.ͼ1ʾһʱ䲽Ĵм(KCʾͲ).еҪʱǻڽѹ.ÿһʱ䲽һ1ͲҪ;ڲͬʱ䲽,ͲKCʱǱ仯,ʱϴ.Ŀǰ,Ĳдһ㶼ְͲ㲢еĲ,Ҳеİάֽⷽ.[4]ÿͲѹ໥,ʽͲӳ䵽ദлв,ڲͬʱ䲽,Ǳ仯,ʱСڻԶСڴʱ,غܲ,ò,ҲδܳھĲ,ٱȲ;,ÿһʱ䲽ⱥͶȷѹֵ,ǵȴϵѹ,͵岢˻ͬ.ͨȽϼ񻮷ֲ,һּʱ䡢ڸؾߴܵ񻮷ֲ(з3).òԻֵĲ[3,4]ֲзؾ,мٱȸ,ڴģͲģʵӦȡõЧ.

ͼ1ѹм
1񻮷ֶԲܵӰ
ڲм,ĻӦĹģʹĽṹ,Ӱ쵽ܷЧطӲлܺͼʱ,ǶС仯.һĲл,䲢мṹͺʹȷ,ٱȽȡ: ľ; ֮ͬͨźķ; ִٶ.3໥.
ͨʱ;:һͨ,ͨӳ;һǼͨ.ǰϵͳӲṹܼϵͳй,벢й.ҲӰ츺ؾһ,ѡʵĲƲд򡢸ƲдܵҪ;,Դʱ.
Amdahl֪,߲жȿ߲.ھмʵʿɴﵽĲжȵ,ݹģݱȡھ,ܿƵ.ӸĽṹһǶ,ϸȿ㷨Ĳж,Ӷ߲ϵͳ.
ϸʹϵͳʵʲ,ʹؾ.ϸȵͬʱ,ͨ.ͨŶԲм˵һֶ⿪,ܽӰ.ڴģϵͳ,ϸȵĲʱ,ϵͳʱΪϸ,ͬʱΪͨſֻ֮ȫ,ᵼ½,˱ڲжȼֵؽԲܵʹƽ.
ʱһΪ벢мĴʱֵ.ﶨһʱ䲽ļٱSpΪ
. (1)
Tpʾ۵Ĳ㷨ʹp̨ʱ,T1ʾ㷨ڵϵʱ,tdʾݸʹӽսʱ,tcommʾ֮ͨźͬʱ,tcalcʾһʱ䲽ļʱ.
2ֲ
2.1з1ʵ
ø⡰ÿһʱ䲽ÿѹ໥ġһ,㡰ʽݵ.p,ĳһʱ䲽,kҪ,ôڵiϷĲ㼯ΪRi{k|(k mod p)i}(i0,,p- 1).ͼ2ʾΪpϵĲ.

ͼ2Pм
ֲз,ͲΪм,ǴȲ.Ҫŵÿһʱ䲽ѹûд֮ͨźͬ,ֻзݸʹӽսʱ.Ҫ:ÿһʱ䲽,Ĳһͬ,ʹĸز,ÿһʱ䲽,ͶȵҪȴϵѹ,ɵ岢˻ͬ,Ӷʹٱ½.ĳЩʱ䲽,Ϊ1ʱ˻Ϊд.Ըòз,ʽ(1)ɱΪ
, (2)
tjΪjļʱ.ȷʱ䲽,ݸʹӽսʱtdһ,ҪʹSp,
. (3)
Ȼַ,ȴ,ڲͬʱ䲽仯ĳЩʱ䲽Сڴ,ֲԾ,Ҳδõ,ٱȲ,Чʵ.Щģ,ٱܵ.ĿǰõĶԲΪ[4]ķ.
2з2ʵ
p,ĳһʱ䲽,k,ÿһֽⷨ,ÿһӦļΪp(),԰ʽݵ,ڵiϷΪkĵiɵļ,Qi={q|(q mod p)=i},i=0,,p- 1,q=1,,kp.
÷ϸ˷1Ĳ,ͲΪм,ڴƽ,رǵÿ㻮ֵ봦ʱ,ÿһ,ھ.ʵʵͲģ,ڼһ㶼ǴΧ,ΪмǴȲ,ΪǷ1ȵϸ.ͼ3ʾ,ĳһʱ䲽,ÿһ򻮷Ϊp,pϲĹ.

ͼ3Pм
ʵ,ֽⷨͨҪڱ߽ݽ,ͨ.رǶԴģ,ϸȸƸؾʱ̵ʱͨӵʱ.ĳһʱ䲽,k< pʱ,k<<pʱ,÷1ַȽ,tcommĿһҪСڸزƽͬȴʱ,ʱϸ1ַĲȿԻøߵļٱ.k>>pʱ,tcommż,ΪӰٱȵҪ,ʱûе1ַļٱȸ.ڸòз,ʽ(1)ɱΪ
, (4)
tqΪqļʱ,tisΪiͨͬʱ.Ҫʹʽ(4)еSp,
. (5)
2.3 з3ʵ
,1㡫k- p*n,÷2,ÿ㻮Ϊp(),p*(k- p*n),k- p*nλͨͬ.򡰾ʽݿ鵽p,Qi={q|(q mod p)=i},i=0,,p- 1,q=1,,(k- pn)p,Ϊ.k- p*n+1~k,÷1,ԲΪȵĹp*n,㡰ʽݵp,Ri={j|(j mod p)=i},i=0,,p- 1,j=k- pn+1,,k.ͼ4ʾΪpϵĲʵֹ.÷ۺ˷1ͷ2,ͬʱֲͬĲм ͲͲ,ڸƽ,ּͨͬ,˷ַĲ,ǵŵ.

ͼ4pм
k<<pʱ,3ǲָֽⷽ򲢾ȵӳ䵽,ĸҲƽ.kС,ͨͬҲ.2ɿǴ.k>>pʱ,3ۺ˷1뷽2,ĸػƽ.
ַҲͨſ,ֻȷ2ͨſҪС,ʱСܶ,뷽2нϸߵļٱ.Ըòз,ʽ(1)ɱΪ
. (6)
ڲͬʱ䲽仯,÷ʹĸػƽ,˱ȷ1ͷ2Ч.Ҫʹʽ(6)Sp,
. (7)
Ƚʽ(2)ʽ(6)֪,
 (8)
ʱ,3ȷ1Ч.ϸһļʹ,ϵͳȵϸ.Ƚʽ(4)ʽ(6)ɵ,
 (9)
ʱ,3ȷ2Ч.ȫϸͨ,ͨſ½,˱ڲжȼгԲʹƽ.
ʵӦʹPVMл,Ϊ˼ͨſ,ɲüͨŷʽ,ͨŴ,Ӷͨʱ,tcomm.,ÿһͨſԷֳ:һǽڱ߽;һǷͱڱ߽ݵĹ,PVMͲ첽,ص.,ͨſҪڽշ.
3ֵ
ȡѹбΪ||pi+1-pi||2 5103,pi+1,piֱΪI+1͵iѹ.Nx,NyֱʾͲX,Yϵ񻮷,NkʾͲ.ѡȡʵͲģ¼.ģ1: NxNyNkΪ1427512,ڵΪ127 800,ÿ׶NMP8ʱ䲽.ģ2: NxNyNkΪ14612516,ڵΪ292 000,ÿ׶NMP8ʱ䲽.ģ3: NxNyNkΪ21120317,ڵΪ728 161,ÿ׶NMP23ʱ䲽.3ģN117׶εļk1ʾ.ʵӦ,Ϊ߲Ч,ѹͨż.м㻷ͨPVM̫ڹSGI Challengeлɵ,ÿChallenge.3Ȼַ3ģͷֱ,2뷽3ÿ㻮ֵΪ4,мٱȽ2.
1

ʱ׶N1234567891011121314151617
ģ1: k55566779101010111112121212
ģ2: k111277911111111121212121212
ģ3: k1717171717171717171717171717171717

 
2

ģ1ģ2ģ3
S1p(1)3.02.452.30
S2p(2)2.742.031.70
S3p(3)3.162.742.72

 
÷23ģ͵Ч,Ҫн׶,ʱ䲽϶,ʱ䲽ֱܼΪ136,136,391,ֱܼΪ1 200,1 1526 647,ÿһʱ䲽вͨͬ,ϸͨͬ.33ģ͵Spи.ж72ڵĴģͲģʵ3ʵ,3ֲĲ,ڽһ߼ٱ.
עͣоõ863߿ƼĿ
߼飺䣺1969ʿҪоΪдֲʽ
Խ1950ʿڣҪоΪѧֵ
άģ1942ڼ߹ʿʦҪоΪ㼼Ͳֵ
ģ⡣
ŵ¸1937ڣʿʦҪоΪд
ֲʽ
ߵλ䡢Խŵ¸Ͼѧ¼صʵ Ͼ 210093
䡢Խŵ¸Ͼѧѧ뼼ϵ Ͼ 210093
άģʤʿѧоԺ Ӫ 257000
ο
1Kendall R P et al. Large Scale Reservoir Simulation in the Concurrent Processing 
Milieu. Los Alamitos, CA: IEEE Computer Society Press, 1991
2Killough J E et al. Simulation of compositional reservoir phenomena on a 
distribute memory parallel computer. In: Killough J E et al eds. The 1991 SPE 
Symposium on Reservoir Simulation. Anaheim: University of Anaheim Press, 1991. 
6982
3Bhogeswara Rao, Killough J E. Parallel linear solvers for reservoir simulation: a
generic approach for existing and emerging computer architectures. In: Killough 
J E et al eds. Proceedings of the 12th SPE Symposium on Reservoir Simulation. 
Houston: University of Houston Press, 1993. 7182
4,Ƶ.άͲģĲ.:÷ȱ.ȫ4첢㷨ѧ
ļ.:չҵ,1993.255260
(Xu Xiang-ming, Sun Jia-chang et al. Parallel experiment for multiple layers 
two-dimension two-phases flow reservoir simulation. In: Li Xiao-mei et al eds. 
Proceedings of the 4th Parallel Algorithms Conference. Beijing: Aviation 
Industry Press, 1993. 255260)
ո:1998-05-12޸:1998-10-09
