ѧ
JOURNAL OF SOFTWARE 
1999 10 5 Vol.10 No.5 1999



ڳƽĿݷֲ 
Žɡơơµл
ժҪ˻ڳƽĿֲ.һֲֵ,Լ򵥵ķʽЧ˲һ¼㻷Ͳɨµֲ.ΪԴͳһ.Ҫ,ΪԶݷֲṩһ˼·.
ؼʡݷֲ,ֲ,һ¼㻷,ƽ.
ͼšTP311
Hyperplane-based Block Data Distribution Strategy
DU Jian-chengHUANG HaoYU Wei-jiangCHEN Dao-xu XIE Li
(State Key Laboratory for Novel Software TechnologyNanjing Uni versityNanjing210093)
(Department of Computer Science and TechnologyNanjing UniversityNanjing210 093)
Abstract In this paper, a hyperplane-based block data distribution strategy is presented which is characterized by the unidirected data distribution. This strategy can solve the data distribution problems under the ununiform computational environme nts and the irregular data reference mode simply and effectively. It can be take n as a supplement for the traditional scheme. Furthermore, this research present s a new thought for the automatic data distribution.
Key words Data distribution, computation distribution, ununiform computational environment , hyperplane.
ݲ,Fortran D,HPF,Lindaȵ,.ڷֲ洢ϵͳ, ݵķֲķֲ.һ˵,(ָͨ)ֲdistribution)3 裺и(partitioning)(alignment)ͷ(allocation).ķֲ ģʽ.ֲҪĿ꣺ƽפͨѶ(residual commu nication)С.פͨѶָĳ˷Ǳؽݶ ֮ƶ.
ܶݲбϵͳݷֲûȥ,Fortran D.Fortran D 1ṩͼֲΪû뵽ĳģ(template) ,ģһռ,Ȼ󽫸ģ尴ĳַʽӳ䵽.ģӳ ䷽ʽBLOCKӳCYCLIC(m)ӳ.
ȷķֲ֮ͿԽмķֲ.ֲǹ,ֲ 㷨Ƚϼ,ֲҲ¸ӵļֲ.ͳݷֲԻڰά ֲ,ܺܺõشģʽµݷֲ.ڳƽĿݷֲ ,ܹһּ򵥵ķʽЧһ¼㻷Ͳµݷֲ . 
1ڳƽĿֲ
1.1ƽгƽ
1.1.1
ѭģ
ǿµѭģ.
DO/DOALLI0=L0;U0:S0
DO/DOALLI1=L1;U1:S1
......
DO/DOALL Ik-1=Lk-1;Uk-1:Sk-1
A0(f0,0 (I0,I1,...,Ik-1),f0,1(I0,I1,..., Ik-1),...,f0,k-1(I0,I1,...,Ik-1))=
F(A1(f1,0(I0,I1,...,Ik-1),f1,1(I0,I1,...,I k-1),...,f1,k-1(I0,I1,...,Ik-1)),...,
Am(fm,0(I0,I1,...,Ik-1),fm,1(I0,I1,...,Ik- 1),...,fm,k-1(I0,I1,...,Ik-1)))
fi,n(0im,0nk-1)a0i,nI0+ a1i,nI1+ ...+ak-1i,nIk-1+aki,nԺ,FǹAi(1im) ,fi,n(0nk-1)ɵĺռΪ

ΪFAIAk,ܶѧ͹еļ㶼ֱ׼ѭʽ.
һЩѭ任Ż,ѭ루loop peeling)ѭֲ(loop dist ribution)Լѭ(loop interchange)ڵõѭı׼.Ҳ ʽĶѭΪһ(phase).
1.1.2ƽгƽ
AΪkά,άΪx0,x1,...,xk-1,Aƽгƽָһƽеk-1 άıAƵռ,άĳƽǸϵһƽС߶Ρ,ά ĳƽǸϵһƽСƽ桱.ǵѭģ,lǶѭΪ еDOALLѭ(0lk-1),lȷAi(0im)ĳƽΪ
.
ilΪ,LllUl,ΪXF(il,I),ilΪóƽ.ƽ ķָ䷨߷,Ϊv=ai,0... ai,l-1ai,l+1...ai,k-1,ai,j(0jk-1,il)(a 0 i,ja1i,j...ak-1i,j)T.vx iάƽ,䷽Ϊ׼,Ϊ,Ҳ䷽Ϊxiv κάƽ,䷽ΪǱ׼.ĳǱ׼ĳƽtAxp0,xp1,..., xpk-2ϵͶӰڸò,xp0,xp1,...,xp k-2ķΪtĿ.ڶάĳƽ,Խ䷽Ϊ3ࣺ 봹ֱᣨy)ƽе,Ϊy,ɱʾΪy=cˮƽᣨx)ƽе,Ϊx,ɱʾΪx =c;κᴹֱ,Ϊz,ɱʾΪy=ax+b,a0.ƽΪóƽ Ԫظ.ǵģ,ѭiĳƽΪt0t1...ti-1t i+1...tk-1,tl=Ul-Ll/Sl+1(0lk-1,li).
 Ȼ,άĳƽһƽе߶.άĳƽһƽеƽ.
ڶѭ,ɸѭǿɲе,ȡĲѭ鳬ƽ. 
1.2ͨ Ѷ
иͷ֮ǰ,˵һͨѶģʽ.ͨѶԷΪ3ࣺ(1)  ٷʱͨѶ,ǰ߳ΪȫͨѶ,߳ΪֲͨѶ,ͳΪͨ Ѷ(allocation communication);(2) פͨѶ(residual communication)ָ, ڵ֮ڼϵͨѶ;(3) ͨѶ(dependence communication)ָ,ڵ֮ϵµһڵһڵ㷢. ͨѶĹΪȫֲֻдĲȡ(G),(S),(R),ͼ1ʾ.G( R)ĿҪȡ()ǷԼĴСй.SĿָ A㴫Bʱ,Ϊ,A,B·,ΪֻҪ͵ й.ȫAķͨѶΪ
DA=n*G(d,|LA|)+n*S(|LA|)+R(d,|LA|),(1
nʾAиĿ,|LA|ʾиþֲ.ںܶ,|LA|=|A|/n,d ʾи,Ҳƽ淽.G(d,|LA|)ʾAаdȡСΪ|LA| ,S(|LA|)ʾʹСΪ|LA|Ŀ,R(d,|LA|)ʾdܴСΪ|LA| ݿĿ.ȫAķ俪Ϊϵͳнڵӿʼ׼ֲܾ鵽յ ĵȴʱе,Ҳڷ߽ڵ㽫AdֳnСΪ|LA|鲢 n֮,ϽһĽڵɽܵʱ.Ǽٶ߽ 㱾μӾֲĴ.ֲLAٷ俪Ϊ
NDA=(n-1)*G(d,|LLA|)+(n-1)*S(|LLA|)+(n-1)*R(d,|LLA|) ,2
|LLA|ֲָLAи֮õÿ,һ|LLA|=|LA|/n.Aط 俪ھֲLAķ俪,ÿֲķ俪ͬ,ǽ n-1n-1ݰͽڵn-1ݰʱ֮.ڿ ͨѶģʱ,Ϊڵļͬ,鱻ȵиͷ.

1.3ݷֲ
1.3.1и
AиָиAγɵĽķ.ѾȷAĳƽ淽 ,Դ˷Ϊи.˷Ϊ׼xi,ͼķֲϼ,ֻ xi򼴶xiάиͷ.ΪǱ׼,漰 ֲʱ,ҪЩ.
,ԶάΪ˵и.ƽ淽Ϊx,xи. ƽ淽Ϊy,yи.ƽ淽Ϊz,ʱַɹѡ (1) zиͷ,ȥγɵľֲԸıṹ,ʹ ֮ڿٴȡ,ҪıӦģʽ,λԲͬģ ʽ,ҪṹĻָ,һĿ.,Ƿıֲṹ, ҪۺϿ;(2) ڿ,zĿи ͷ.x,yάĳȷֱΪn,m,ƽΪy=ax+b(a0),am/n,Ϊy,ʿ yи,a>m/n,Ϊx,ʿɶxи,ֱͼ2(a),(b)ʾ, ߱ʾи.,Ҫͼ2(a)дii+k-1kƽ䵽ĳ,A(i:i+k+a*n,0:n-1)Aȡ,͸ý,nʾxάĳ.1и ݵĴ,GĿϴ,ṹع,RĿҲϴ. 2ַҪÿڵ㴫a*n2,ͼ2(a)Ӱ,nʾx άĳ.,Aֳm,a*n2mݱ.ַŵ,G,R ĲС,Ĵ洢(л)иһʱ,ͨ ķͨѶ,ÿС.

ܲȡ1ֻǵ2ַ,һ,ѱ޸ĲҪط ʱ,Ҫڸڵ֮һάض.Ϊ۷ ,ٶֲδع.ͼ3,Ai-1,Ai,Ai+1Ƿڴڵpi-1 pipi+1ϵľֲ,ǽAyиõڵ3,ֲ ͼб߷.Rku,Rkd(k=i-1,i,i+1)Ǿֲδ,Ϊ˱֤ ֮Ժһ,ҪWkuRk-1d(k=i,i+1);WkdRk +1u(k=i-1,i),ݡʾͲ,ͼ3ʾ.ȻͿڴ˻϶Ծֲٷ.ڶԾֲٷʱ,ھֲ֮ Ųص,ӦעصֵĴ.ͼ4,һƽеˮƽ߱ʾи ,ʵ߱ʾֲʼλ,߱ʾֲĽλ,ڵʵߺ ֮ص.طʱ,Ҫȷֲı߽,ʹøֲ鲻ص. ,ͳһʵ߻Ϊı߽.Ϊض.ضӦ һ»֮.ڴ˻,ͿԽط.


1.3.2ķ
ͬһиĳƽȷ֮,Ӧͬĳƽ䵽ͬĴ ڵ.ǲðзķ.ԭǣ(1) ڽط䣻(2)  ڲһ¼㻷½䣻(3) ٵפͨѶ.
1.3.3ͬһͬĶ 
ǰѭģ,Ai=Aj(1i,jm),Ai,AjڸֵŵҲ, ģʽһ,Դ˿ִ(1) ĸ.,Խеһ ΪB,ԭеĳƽķֲ.ַᵼ¶Ĵ洢ռ俪, פͨѶ.(2) ǵĳƽ淽ͬ,ͬƽ ĳάĽ뱣ֲ,԰ͬи,ý ĸ.ַһפͨѶ,˶Ĵ洢俪.һ ,Ҫ鸴ƿפͨѶۺϿ.
1.3.4ͬͬĶ
APiпѡĳƽ淽ΪSPi={dil|l=1,2,...,ni},A P1,P2,...,Pkг,ΪѰAڸѵи,ǽƽ淽ת ͼG=(V,E).ͼk,ÿniڵ,ÿڵһƽ淽,j SPi,ڲڵvmi,vni+1֮б,ñߵȨA ɷvmiתΪvni+1ٷ俪,ʽ(2)ɵ.ĳƽ 淽ͬ,ȨֵΪ0.ǵ,1k֮ѰһȨֵ֮С·. һ·,ʱ俪ΪO(ki=1ni),ʵеni С,,÷ʵʿе.
1.3.5һ¼㻷е
һ¼㻷,ڵͬļ,ķֲΪ,Զ 鰴ĳоȵиͷ.NOW,˲ͬ͵Ľڵ,΢ վСͻȵ,Щļǲͬģʹͬһ͵豸,ĳʱ, 为Ҳһ,ʴʱṩļҲǲͬ.a1,a2,...,anΪNO WдڵԼ,a1+a2+...+an=1a1a2...an. A0иA1,A2,...,Annģ,Ϊ˴ﵽƽ,Ӧ|A1|= a1|A0|,|A2|=a2|A0|,...,|An|=an|A0|.|Ai|(0in)ʾ Ai.
2ܲԺ
2.1ʵо
1: for (i=0;i<=N;i++)
for (j=1;j<=N;j++)
Ai+j,j:=Ai+j-1,j-1+Bj,i
ͨϵ,1ѭɲл,ԴѭȷA,Bĳƽ.ɵ1.1 .2ڿ֪,Aڡ:=˵ĳƽΪ

ǾɱʾΪy=x+b(bΪ),Ϊx,BĳƽΪ

y=c(cΪ).ͼ5ʾ,A,Bи,иΪƽ淽(עⷽĶ ,μ1.1.2).ͳķʽA鰴ֲ,ǰA(:,block),ǰA(blo ck,:)ֲ,ʹ֮䲻ɲִ.AҲ԰տи.1N= 100,ڵΪ24ʱA,Bֲ,Aտи.

1

ڵAķֲBķֲ
2A50p:50p+150,*,p=0,1B*,50p:50(p+1),p=0,1
4A25p:25p+125,*,p=0,1,2,3B*,25p:25(p+1),p=0,1,2,3

2.2ʵ
6̨RS6000վͨATMɵNOW,PVM,ԻڳƽĿ ֲµĲмо,Ҫֲ봫ͳĿֲһЩȽ. 濼ǿɲм,ԵʶȡǱĵоص,˲ .ǲSPMDģʽMaster/Slaveģʽ,ִйҪݵķֲ 㡢פͨѶԼݵĻ.ִģʽԲûӰ,,ͳһMas ter/Slaveģʽִг.
ʵ1. ѭм.
for (i=0;i<N;i++)
for(j=0;j<N-2;j++)
Ai+j,j:=Ai+j,j+Ai+j+2,j+2
еļ,,ͨѶĶپ˳ִʱ.ͨѶĶ ķֲ.23ԲͬСAĲԽ.hd,bdֱʾ ڳƽݷֲʹͳֲ,,bdΪ(:,Block),ִʱͼٱȾȡ10ִ нƽֵ.
2

ִʱ(ms)ٱ
hdbdhdbd
22 7245 3030.0780.038
41 9973 9090.1020.052
51 8523 6450.1100.055

AΪ2000*1000ʵ
3

ִʱ(ms)ٱ
hdbdhdbd
210 85721 2760.0750.038
47 94515 6580.1030.052
57 33414 4720.1110.056

AΪ4000*2000ʵ󡡡
ӱ23Կ,ͬݷֲģʽԳִʱӰܴ.˵һ, ϲԽļٱԶС1,,ͨѶ(ݵķֲפͨѶ Ļ)̫,ʹòִк.
ʵ2. ԸAбΪ45ϵݽиҶ任.Ƕά Ҷ任,,ҶѾ.Ǵмѭ ʵ.
for (i=0;i<N;i++)
for (j=0;j<N;j++)
for (k=0;k<N;k++) 
DAi,j:=cpladd(cplmul(FFTj,k,SAi+k,k),DAi,j)
еļϴ,ͨоһķֲյִмٱȵӰ .hdֲʱ,DA,SA,FFTĳƽֱΪ

FFTи,Ϊһ.SAҲɰֲ,rdʾ .bdֲʱ,FFT,SAֱ(Block,:),(:,Block)иֲ,align FFT(i,j) w ith SA(j,i),DAи,Ϊһ,еDA㼯 MasterϽۼ,õս.45ԲͬСSAĲԽ, ִʱͼٱȾȡ10ִнƽֵ.
4

ִʱ(ms)ٱ
hdbdhdbdhdbd
2472 830506 681515 9151 .8561.7321.701
4230 455234 519240 0363.8083.7423.656
5185 337190 569192 9584.7354.6054.548

SAΪ1200*600ĸ
5

ִʱ(ms)ٱ
hdbdhdbdhdbd
23 417 5523 585 6283 725 13 81.8771.7891.722
41 668 3191 733 2311 761 7933.8453.7013.641
51 339 7421 378 6141 424 5364.7884.6534.503

SAΪ2000*1000ĸ
ʵģʽʱ,ڳƽĿݷֲҪȴͳݷ Ч.ƽķǱ׼ʱ,һֲֿ,ƽĿ ݷֲ,ԿǶߵ.
3عıȽ
Fortran D,HPFṩ˻άİBLOCKCYCLIC(m)ʽĶ(ά) ԣ1.ַܺܺõشάɨĲģʽ,ά ָ˼ֲĸӶ.ף2˲һ¼㻷µֲ.פͨ ѶΪڱ(internal edges)(external edges)ĳ,ûп ģʽ,ֳܺܺõطӳʵ.ͬʱ,ΪѰ̵ڱߺ߳, и,˼ֲĸ.ף3ݸѭͬһ鱻 Ѱһ»ƽķ,ûпͬһȶд,ѭ任 ϴ.ĸ˻ڳƽĿֲģ.һֵиͷ䷽, ,ͼķֲΪ,ܹάɨĲģʽ,ڲһ¼ 㻷¿Էؽķֲ.ڳƽɿɲѭ,ֲ ͨѶ.ͬʱ,ڲðֲ,ܹ޶ȵפͨѶ.ϣ ԴΪԴͳһ. 
4С
˻ڳƽĿֲ,ȷƽԼΰƽ иͷķ,ͬͲͬͬһ鱻ζдͲһ¼㻷 ķֲ.ʵ,һּ򵥡Чֲ.ϣ ԴΪԴͳһ.Ҫ,ǵĹΪԶݷֲṩһ˼·. ַĽϺԶݷֲ,Ҫһо.

оõ863߿ƼĿ.
߶Ž,1971,ʿ,ҪоΪм.
ƺ,1957,,ҪоΪ,б.
,1973,˶ʿ,ҪоΪԶб.
µ,1948,,ҪоΪֲʽ,м.
л,1942,,ʿʦ,ҪоΪֲʽ,м .
ͨѶϵ:Ž,Ͼ 210093,Ͼѧѧ뼼ϵ
ߵλ:(Ͼѧ¼صʵҡϾ210093) 
         (Ͼѧѧ뼼ϵϾ210093)
ο
[1]Tseng C W. An optimizing Fortran D compiler for MIMD distributed-m emory machinesPh.D. Thesis. Rice University, 1993
[2]Kaddoura M, Ranka S, Wang A. Array decomposition for nonuniform comput ational environments. Journal of Parallel and Distributed Computing, 1996,36(5): 91105
[3]Ramannujam J, Sadayappan P. Compile-time techniques for data distribu ted memory machines. IEEE Transactions on Parallel and Distributed Systems, 1991 ,2(4):472482
1998-01-22յԭ,1998-04-20յ޸ĸ
