о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



عй̵õŻ

ժҪ̼߱ĿЧʵҪ.ڷֲʽ洢ĲϵͳУݷֲĺûӦóҪӰ.ǽڵݶͷֲƵԻõȫݷֲģͣһʹ̵õĿԿƣδ̵ãԼݷֲϢڹ̵õռ봫ɸЧʵĿǼҪ.Ӧù̵ʵС̵õĿܺܺõݾֲҪ.
ؼʡбݾֲԣʵݷֲģ
ͼšTP311
A METHOD FOR PROCEDURE CALL OPTIMIZING
FENG Xiao-Bing and ZHANG Zhao-Qing
(Center of High Performance Computing, Institute of Computing Technology, 
Chinese Academy of Sciences, Beijing 100080)
AbstractGlobal data distribution analysis is a key technology for parallel compilers. Compiler should let computing and data used by these computing locate at the same processor, otherwise, the performance of applications will be very poor. Interprocedure analysis is necessary for global data distribution analysis. When mapping functions of a formal array and actual array associated with this formal array are not compatible, the cost of this procedure callsite will be very high. Two issues must be solved:  how to process procedure calls;  how to collect array distribution information and transfer the useful information among procedures. In this paper, a method for solving these two issues is introduced. All callsites of a procedure are classified into patterns according to their calling contexts, with each pattern calling a special body of this procedure. Information used to classify the callsites can be applied for pattern body's parallel optimizing, too. This is called instantiation. This method can be used to decrease the cost of procedure call and to obtain a global optimizing data distribution model.
Key wordsparallel compiler, data locality, instantiation, data distribution model
1
дϵͳĹ㷺Ӧôٽ˲бо߲бٵҪ.رǶھзֲʽдϵͳӦóݿռڷֲʽ洢еӳʽصӰųִЧ.ȷӦóȫݷֲָģͣȡøõݾֲԣӦóܵһؼأ13.
ȫŻݷֲָģ͵Ƶܻر̵ܹõĴ.һԷյĳ壬ڱʱõʽȫϢԼŹ̵Ķ̬Ϊ̶ԲȫĲԼֵҲӰŵߵΪ.ڵ߶ڱùڲϢģģòڳŻʱعƣӶʹúܶŻл޷ɣصӰ˲ŻЧ.رǶڷֲʽϵͳϵĲг̼Żʩʹù̵õĿ.
1.̵ÿܵ´ͨ
program samplesubroutine f(c)
real a(100,100),b(100,100)real c(100,100)
integer I,J
s1: f(a)do I = 1,100
do J = 1,100
s2: f(b)c(I,J) = I3+J
enddo
endreturn
end
FORTRANУfеѭǿԲеģfбΣfڵõs1õʵڲaڵõs2õʵڲb.бķóaĵһάֲˣbõڶάֲˣʱȷfʽcݷֲģʽأԹf⴦fεʱʵݷֲģʽìܵģfεñȻӳ䣨remapͨţЩܻӴ̵õĿ.δеĹ̵ãһ3ַ145ݣ
(1)Ƕ루inlineķ÷ڹ̱ôֱǶһڽгŻʱȫػõߺͱߵϢ.ַᵼ³ĹͣϵͳκĵĻжһõõĹǶ󣬲ùǶķпܶԵȻЧ.
(2)̼ڷһʱڵϢָеõϢۺϣÿõıù̵Ϣһµ.Ϊ˳ȷԱȻĳЩڲñعƣӰŻЧ.
(3)̷ܣݹ̵õĶͬһ̵Ĳͬõз࣬ÿӦ˹̵һʵ.Դеһ̿ѱΪѱѡ.
ڱУǽһ̼Ż㷨ܣȫݷֲͼָģʽƵԽ͹̵ÿ߲г.ļǸݵõϢԹ̵ýʵ.ǵĹһFortranԲбԭӦCԲбĿ.
2ݷֲӳı任
ݷֲģʽڹ̼ռȽϣǱ㷨Ҫɲ֣Ϊжһ̵õǷԹͬһʵ壬漰ĲȫȵݷֲģʽǷͬ.⣬ĳЩݷֲϢȫŻݷֲͼָģʽƵҪָ壬ҪھܹķΧڽɢڹ̵ôܽߵݷֲϢݸߣҲܽߵݷֲϢ.
2.1
ȣ˵һβķֲģʽ.Fortran׼6й涨ʽ鲢ռʵʵڴռ䣬жĲǲ֮ϵʵ.ἰβķֲģʽʱζβ鱻ֲˣָʵϺβϵʵβ(shape)ʱӦķֲģʽ.
1.ֲģʽһ.βʵȵԪظǰ£ڹ̵ͬõͬһβCϵʵABֱݷֲģʽDADB.AβCʵʱֲģʽDACʽΪDC1.BβCʵʱֲģʽDBCʽΪDC2.DC1DC2ͬõ㴦βCķֲģʽһµ.ȫԼFortranеĹͬԼ.
2.õһ.һFõF1F2
ٶڱֲβ飬䡰Ρͬģ
ڸӦβķֲģʽһµģ
г˹ӦĹķֲģʽһµģ
ȫ飬Ӧȫõ㴦һµģ
̵ĹGF1GʵG1F2GʵG2G1G2һµģ
ƵõF1F2һµ.
ʱõ̵ͬһʵ.õӦڲͬ࣬òͬʵ.
2.2ԹֲһЩƼ䴦
FortranУCOMMONEQUIVALENCEָ˲ͬݶĶϵָ˴洢ϣ6ݵĹϵ.
2.洢ϵ
SUBROUTINE f1SUBROUTINE f2
COMMON/com1/a(100),b(20,20),c(50),d(150)COMMON /com1/x(100),y(400),z(200)
REAL e(100)
EQUIVALENC (a(51), e(1))END

END
2Уabexyͬһ洢Уf1еabc3ֲģʽƵҪͳһǣֿܷ.ͬcdzҲͬһ洢УcdķֲģʽҲҪͳһ.򣬿ʹzͬһʱ̶Ӧݷֲģʽ.HPF7ݵľ飬Թȼ۱ݷֲģʽƵһЩ.
3.ϱһռЩԵĴ洢һΨһ洢еһ.ϱĴСָϱд洢Ԫĸ.
4.һϱУһԱĴ洢ǡÿԸϱеĴ洢УԱΪϱļϸ.
2Уabexyһϱ飬СΪ500ʵ5鶼ϱļϸӣcdzһϱ飬СΪ200ʵzϱļϸ.һһϵеĳɷ(component)ÿɷֻһϱ飬һκμϱı.2Уcom1ɷ֣Ϊϱ.
ڴϱĳԱʱÿһϱ鵱һģ飬ģȻϱļϸ.гֵļϱĳԱϸӼƫͿԱ֤ͬһʱ̣һϱֻӦһֲַģʽ.
2.3ֲģʽ任ķ
ԼһֻӦһݷֲģʽ.FortranеĹڸеοܲһ£Ҫ任.ϵβʵ鶼пܴԼлݷֲģʽҪϵΡʵݷֲģʽбȽϻ任.
ֲģʽ任ĻԭҪ㴮гĴ洢˳.βһԪʵһԪڷǷֲ״̬´ڽϹϵ鶼ֲˣԪӦϹϵ.
ڶӦβʵ飬һ֪ݷֲģʽʧһԣԼʵݷֲģʽ֪Ҫβķֲģʽ.ȣȷʵֲݿĴСʵ鱻ֲ󣬱ֲͬһڵϵݿĴСΣݷֲݿĴСȷβһάҪֲѰβĳһάٶǵjάjάĿࣨstrideСڻڱֲݿĴСj+1άĿ಻СڱֲݿĴСȻ󣬸ݸάԪسȺͱֲݿĴСȷάķֲģʽ.ܾȷȷֲģʽı任ع̵ĵõΪһʵ壬ڵõǰ붯ֲ̬ģʽĻ.
µķȽݷֲģʽǷһ£AзֲģʽDABзֲģʽDBԼٶΪABǶӦβʵ飬AķֲģʽDA֪ǰķBķֲģʽDB䣬DBDBͬΪABݷֲģʽһµ.
3Ż̵õ㷨
Ͻڽܵݷֲӳı任ϣǹŻ̵õ㷨
ٳʼչͼһ̬õӦͼеһڵ.ÿڵΪδ侲̬ƵļôȣȷȨֵ.ỵ̈ʼһpatternļϣÿ̶Ӧһ.ڱ׶ΣÿϾΪ.
Զɨͼеÿڵ{//Ϣռʹ
ϽڵĽԶ´֪ݷֲϢ
еĹ2.2ڵĽܽзǣ
¼(a)صβα(b)βķֲ̬(c)ȫ飨飩ķֲ̬.3ϢǶԵõзҪ.õӦpatternУռϢڵ.
}
۸ÿڵȨֵӴСѡȡڵз{
ڵѱǵϢѯѱĵõ㣻
һõpϢڵһ£μ2ǸڵѱΪѷڵΪáָýڵp.
{
ռϢԹ̽йڷŻ4.õΪѷ.ռڷ»õϢص·ϡ´ռϢ{
õǰ̽ڵδµϢ뵽ڵϢУ
ѵڵǰڵıǡѷ򡰸áֹϴ´ֹѵҶڵǽڵѱ
ϴֹڸڵ´ֹҶڵ㣬ֹĳһڵq{
qıǡáõΪѷԭýڵĹڷϢ
qıǡѷĵõ㸴õ㣬ù̵ĹϢƣѡһqĽڵ㣬ΪѷڵϢǸڵϣиýڵqĵõ㸴Ǹڵ.
}
}
}
}
δÿ̵pattern{
ÿpatternϦУС2нܵ˼Ԫ֣໥һµĵõ㱻ͬһӼ.ÿӼǹ̵һʵӼеĵõʵ.
}
ڴɽ׶ΣɵӼʵصĵõ.
ͼеÿڵҪһǼ¼ڵݷֲϢһ¼̵õصϢ.ǰһÿڵ㶼ģֻбΪѷĽڵŻԼٴ洢.
ݲǡٷֲ⣬һֲˣֻһݷֲӳ亯.㷨ĵڢڡУݷֲģʽĴҪָݷֲģʽĴ.
Program f
Dimension a(100,100),b(100,100)
Cdistribution a(BLOCK,*), b(*,BLOCK)
 
s1: call g(a,)
 
s2: call g(b,)
 
s3: call h(a,)
 
end

subroutine g(c,)
dimension c(100,100)
 
s4: do m=1,100
s5: do n=1,100
c(m,n)=
enddo
enddo
 
end

subroutine h(d,)
dimension d(100,100)
 
s6: call g(d,)
 
endڲڽÿ̵patternռ̵о̬õ.
ݺͼ㻮ֵƵУԽӰڷʼʱȫ飨飩еݷֲģʽֻҪЩϢȷˣͬһݺͼ㻮ƵõĽҲȷģֻҪжһδĵõѾеݷֲϢͬһ̵ĳѷĵõͬͿΪõԸѷõϢ.ִԼٹڷ߱Ч.ڲУһЩڵΪáһķ.ף8еĹ㷨УһֻҪڱзָѭУȻֲˣڲж»õݷֲϢĴѴĹ̵õֹķ.Ϊһõѱ󣬶Ӧ̵ĳδֲвκαзָѭУõķԼݷֲģʽĴֲܱĿЧʲû壬㷨ʹ÷ֲģʽĴڴֹӦĵõ㴦ͨţάݷֲһ.
ڲУرǿһǣһpõֱӦڲͬʵpõڵq1q2ҲǲͬḶ́ǷֱӦͬһ̵Ĳͬʵpõ㴦ͬһ.ɶ2׵صõ.
4Ӧþ
һFortranӦչĳͼͼ1ʾ.

ͼ1չĵͼ
ӦóԱָfaĵһάBLOCKķʽֲbĵڶάBLOCKķʽֲ.жԹgĵù3s1s2s6ڵͼзֱg1g2g3.һgеѭs4s5ǿɲѭ.ͨڵõs1gβcõݷֲģʽǣBLOCK*ڵõs2õݷֲģʽǣ*BLOCKڵõs6gβֱӽϵhβddݷֲģʽ̳еĵõs3aԼs6βcõݷֲģʽǣBLOCK*s1ͬõs1s6ԹΪһࣨõ㣬ӰϢһµģӦgʵУѭs4ָõs2ǵһ࣬ӦgʵУѭs5ָ.ˣĿйgʵ3õķֱʵӶõõ.hһΣֻһʵ.
5ᡡ
ܵķݹ̵õĵĲ̵ͬýз࣬ͬøù̵Ĳͬʵһڲʱڵõ㴦ӳ任⣬ӶС̵õĿ.һ棬ÿʵһȷݵģʵеĹڲŻԸϸӶȡøߵĲִЧ.̵ʵļ߲бҪ.
õҡ߿ƼƻĿ͹ҸܼĿ.
߼飺У196911ʿҪоΪ뼼.
죬Ů193811оԱʿʦҪоΪб뼰
.
ߵλйѧԺ㼼оġ100080
ο
1Chau-WenTseng. An optimizing fortran D compiler for MIMD distributed-memory machinesPh D dissertation, Rice University, Houston Texas, USA, 1992
2Lam M S. Locality optimization for parallel machines. In: Third Joint International Conf on Vector and Parallel Processing, 1994
3Ken Kennedy. Compiler technology for machine-independent parallel programming. International Journal of Parallel Programming, 199422(1)7998
4Cooper K D, Hall M W, Ken Kennedy. A methodology for procedure cloning. Computing Language199319(2)105117 
5Cooper K D, Kennedy K, Torczon L. The impact of interprocedural analysis and optimization in the Rn programming environment. ACM Trans Programming Language Systems, 19868(4) 491523
6Fortran . ׼Fortran 90Գ. ѧԷ磬1994
(Fortran Group. Standard of Fortran 90(in Chinese). Beijing: Xueyuan Press, 1994)
7High Performance Fortran Forum, High Performance Fortran Language Specification, Version 1.0. Houston: Rice University, 1993
8 . дϵͳѭָݷֲо۲ʿģ. йѧԺ㼼о 1998
(Lin JinResearch on loops and data distribution for SIMD systemPh D dissertation. Institute of Computing Technology, the Chinese Academy of Sciences, Beijing: 1998)
ԭյڣ1999-02-10޸ĸյڣ1999-05-22.
