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



һʽFortran77лϵͳ
Ĺ⡡֣桡֣γ
ժҪл԰еĴгԶԶתΪг.влϵͳԶлЧֹлЧȻһĲ࣬ڲлߵķԼеϢ޷лɵ.TIPS(Tsinghua interactive parallelizing system)ϵͳͨṩһЩѺõĽʽߣʹûЭ߲лϵͳЧʵһЧ;.
ؼʡлʽϵͳԲѯ,Ԥ.
ͼšTP311
An Interactive Fortran77 Parallelizing System
CHEN Wen-guang YANG Bo WANG Zi-yao ZHENG Feng-zhou ZHENG Wei-min
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
Abstract Parallelizing compiler can transform serial programs to parallel programs automatically or semi-automatically. The up-to-date automatic parallelizing systems cannot generate parallel codes as good as hand coding for many applications. The main reason is that they cannot manipulate the complexities of real applications. What's more, there are some semantic information in the program that the automatic tools can never know without user's knowledge. TIPS (Tsinghua interactive parallelizing system) provides some user-friendly interactive tools so that the compiler and user can cooperate with each other. It is an effective way to improve the capability and efficiency of parallelizing compiler.
Key wordsParallelizing compiler, interactive system, dependence query, incremental compilation, performance estimation.
80ڿʼŲмϵͳķչ𽥿ʼоглϵͳ.оǴԶϵͳʼģ͵KAPVAST.ǣʵӦóУЩԶлϵͳĲлЧ1.ԭڣԶлԶűʵ.лҪдȵĲԣҪϸȵĲ.ڷȲʱ̵ͷʹôͳԷ⵽ʧ.
ڲлۺʵ÷涼ȡһЩչһЩµĲлϵͳ.UIUC(University of Illinois at Urbana-Champaign)Polaris2,3ݣStanfordѧSUIF(Stanford University intermediate format)4ݣѧAFT(automatic Fortran transformer)5ݵ.
ЩһȫԶлߣͨù̼Է˽лԼʶ𡢸ʽĹɱʶԼʱ¼лKAPȴͳϵͳ˽ϴߣĳЩĲлЧѾֹл.ǣһЩԶлЧֹлЧȻкܴ.ԭڣȫԶлϵͳʹõĲл㷨ЧشЩӦó.㷨⣬ȱйصĳϢȫԶл㷨ϰ.
GreenwichѧCAPTools69ݣRiceѧFortran Dϵͳ10,11ݺApplied Parallel Research˾Forge90ȾǽʽĲлϵͳ.
ЩʽлϵͳھܲȡԶлͬʱڲлв鿴޸Ĳлͨ˵߲лЧڲ̶ֲֳȫԶлϵͳĲ.ǣЩʽĹձ鶼ûвµԶлˣǵԶлȽϲ.
TIPS(Tsinghua interactive parallelizing system)һʽĲлϵͳϵͳPolarisϵͳΪǿԶлײ֧.TIPSѺõĽܣͬʱֹ֧洢ϵͳͷֲ洢ϵͳ.
1 TIPSصṹ
1.1ϵͳص
(1) ṩѺõĽֶ.ûķʽûʾ˵л׶εĽܽû֪ʶ(ͨûѯ)ָһĲл.
(2) ʹȽԶл.TIPSǻPolaris.Polarisϵͳв˽лɱʶ𡢹Լʶ𡢷Բԡŷѭ任ȶµԶл.,PolarisϵͳȱҪĹ̼Polarisϵͳ򲹳˹̼ģ.
(3) ͬʱֹ֧洢ϵͳͷֲ洢ϵͳ. 
1.2ϵͳṹ
ƵڻȺϵͳFortran77лϵͳTIPS, ṹͼ1ʾ.

ͼ1
1.2.1 Զлģ
ԶлģTIPSϵͳĻΪ¼.
(1) 
ΪԷ׼.ý׶νеĲ(constant propagation)˽л(scalar privatization)ɱʶ(inductive variables recognition)͹Լʶ(reduction recognition).
(2) ̼
̼׶νеĲ̷ܡ̼̼˽лԼ̼任ȵ.Ĺ̼Ϣ԰Է׶ζԺй̵õѭвлҲĻ.
(3) Է
ֻвصſûͬ²ִУԷʵǶԳԵʶ.ԷͨһϵвɣTIPSвõĲGCD(greatest common divisor)ԡBanerjeeԡOmegaԺRange.ϵͳչRangeԣ԰һԭ޷ΪһЩʽͨģûѯϵͳûĻشȷѭǷԲл.
1.2.2 дģ
(1) 
ģԷ˽л͹ԼʶģĽڳвӦָ䣬ԳӦı任.ɵĲFortranĿʹñͿɲеִд.ĿǰϵͳĹģ֧SGI Power Challenge SMPϵͳ.
(2) ݺͼ㻮ַ
ֲ洢ϵͳĳʽضݺͼл.ģҪǶݷģʽзٲгͨŴͨӶ߲г.
(3) ֲд
ֲдɾָ÷ĲԼݺͼ㻮ַʵʵݺͼ㻮֣Ȼͨ.ڲдʱӦĴ뵽ԴУSPMDĽڱϵͳɻPVMĲд.Դ뾭Fortran룬ɵִдPVMϵͳ֧¾ͿԽвм.
1.2.3 ģ
ģ鸺ԶлģûϢ.Ҫʾлû˵òлԭԼûѯʳϢ.ģҪɲ£
(1) ͼ
ʾĵͼ.ͼеĽѭӳ.ͼÿ󶼸ִʱռı.ѭڵʾѭǷԲУǴѭڵͼлʾ䴮еԭ.ûϸ鿴ΪЩԭϵͳɵģԷǿƲлѭ.
ͼ뽻ģ߽ܽϣʹûѸٶ׼ȷ˽ĸſȷеҪ(ʱ䳤޷еѭ)һԳо.
(2) 
ûʹýʽлߵʱ򣬿ܻԳһЩ޸ģֹһЩ任.ڲлϵͳһִʱȽϳûԳԼ޸ĺҪȫ±룬˷ûĺܶʱ䣬ͲлЧ.
ͨҳû޸Ӱ쵽ĳԪֻЩԪ±룬ӶǿϵͳĽ.
(3) û֪ʶ
Է׶ΣһЩ޷⣬ϵͳȡһЩʽ.û֪ʶУϵͳûѯЩʽûԻش𡰳򡰲һ.ϵͳûĻشȷӦѭǷԲл.
ûԣϵͳѯʵĲʽ⣬Ҳѻش𣬶ϵͳͨû֪ʶԵõõĲлЧ.
(4) ͼ
ͼʾһѭǶ׵ͼ.ϵͳṩ˶ֹ˷ʹûԼڶĳЩо.
(5) ʱԤ
ʱԤԸÿѭʱռı.ʹûܹоЩҪĲ.ʱٵѭʹܲлҲػ̫ľ.
ԳʱԤж̬;ַ̬.̬ͨԴмʱ䲢ʵгʱ.̬ͨĸֲгͿԹƳֵʱ.̬ŵǱȽ׼ȷȱǱȽϷʱ(ģȽϴʱ)ʱ޷г(磬ȱ).ʹþ̬Ա.һ˵̬ԤʱĳȳȣĹģ޹أӦٶȱȽϿ죬׼ȷԲ.
ڱϵͳУṩ˶̬;ַ̬.ûڶԳʱԤʱԸԼҪѡһַ.
(6) 
ʹûԷԴͲл֮ĳ.ڳͼ͵ͼ֮Źϵһѡĳһѭӳʱݶ֮ͬ.󷽱ûԳоͷ.
2 ؼ
2.1
ǽʽϵͳɫϵͳĸַ㷨ûӶγɹǿĲлϵͳ.Ҫû㷨ЧЭܹû㷨֮Чؽ˫Ϣ.ʽϵͳʹ㷨ĲлԱ⣬ʹṩϢԱл㷨.⣬ʽϵͳӦöûӦʱһĹעûʱ䣬ûĹЧ.
˵ڲлУģӦܹ.
(1) ûʾл(ͼͳͼķʽ).ûԲ鿴ĳԵԭ򣬲ҿ޸ͼ.ʹûԿԵĳ.ûܷ֣ʵ㷨ɵαأ˿ֱɾأҲܷ֣޸(ʹĳЩ任ֹд)öγ.
(2) ûԷ㷨ڷ޷һЩ⣬ûĻشĽ.пʮ־޴Ҫرעѡ.Ҫǳִ϶⣬ΪԲлЧӰܽϴ.
(3) ṩʱ֮ȣʹû԰עڲлĹؼ.
(4) 빦ܣû޸˳ֻ֮ܵӰĳԪ±룬±.
(5) ܣùܿ԰ûҵҪĳ(ʱѭߺصѭ).
ܡͼͳͼʾȹļȽϼ򵥣ƪڱȥ.Խ3Ƚϸӵļ뼼̬Ԥ⼼Բѯһ򵥽.
2.1.1 뼼
TIPSϵͳеӳΪ뵥λ.ԭǣͨԴõһЩں͹̼Ϣ(һЩϱʾ).û޸˳ͨȽҳ޸˵ĳԪͨ¼Щϣҳܵ޸ӰԪ.ЩԪ±.
2.1.2 ̬Ԥ⼼
ϵͳо̬Ԥ⼼Ļ˼ǣԤĿһЩ׼򣬻һЩ(+,- ,* ,/,...)ĿԤһʱͳƸóڲֻĸеʱЩʱ֮.
ûпйش洢εϢ(ĴCacheڴķʱĲ)ܻᵼԤʵеĽкܴĲ.Ҫ⣬ݳִйģ洢Ϊ.TIPSϵͳУʹþ̬ԤĿĲΪ˵õ׼ȷִʱ䣬Ϊ˵õִֵʱĸӳ̶ȣԤ⼼ǵϵͳõ.
ǵԤ㷨ѵĹͲԡ﷨ʱԤ3.
ͨѵԻȡڲĿϵʱ.﷨׶εĹǷԴ򲢹﷨ԳӦı任Աкķ.ʱģģĽʱ.
2.1.3 Բѯ
ԲѯԼ򵥵ذѲܽⶼصعΪأͼȻûԼֹڵعϵӶﵽлĿ.ϵͳҲṩֹ.ǣַûԲѺãΪعϵķʱôֱӣҳصĿڶ࣬ûԷЩأЩǼٵ.
չRangeԵ˼룬һ޷ȡһЩʽȻûѯЩʽǷͨûĻشȷǷ.ַŵڼ˲ѯѺԣּûĴķΧ԰˵ܺõؽϽл.
棬ǽܲʽȡ㷨.
RangeԿ֪ĳУjnNiѭԲ.
do i=1, in
do j=1, jn
A(i*N+j)=...
...=A(i*N+j)
enddo
enddo
ϵͳ޷ȷjnNǷԲʱͿһʽÿʽӦһػ.ʵϵͳУͨ±ʽһЩ任ܲĳôֱӣȻͻش.
ѭеÿһԷز˲ʽҪѭΪλЩʽй.ѭΪλûѯ.
磬Perfect BenchmarkеĳAPSIĳΣ
IPP2=IP+2
IPPH=(IP+1)/2

DO J=2, IPPH
JC=IPP2-J
J2=J+J
DO K=1, L1
CH(1,K,J)=CC(IP0,J2-2,K)+CC(IP2,J02,K)
CH(1,K,JC)=CC(1,J2-1,K)+CC(1,J2-1,K)
ENDDO
ENDDO
ϵͳԳȡʽֻҪһͿȷѭǲе.
(1) IP<2
(2) 2+IP>2*IPPH
ûͨIPPH(IP+1)/2Ժ֪ʽ(2)ӶлѭJ.ӿԿûǳ⣬ҲȽ׻ش.ûҪԷ֪ʶͿ԰ϵͳвл.
ƵѭPerfect Benchmarkлкܶ.ǳ13Perfect Benchmark е105Ч.˿Ϊһձ.
2.2̼
̼һʮҪļʹúй̵òٳΪеϰҲ˹ǶĴ뱬ը.TIPSϵͳУ̼Ļ.ϵͳʵֵĹ̼Ҫ̼̼Է̼˽лѭǶ.ƪȥ˹̼㷨.
2.3ֲдɼ
TIPSϵͳķֲдģ鰴ִģͰѳ򻮷Ϊ(region)
Region 1
...
Region 2
...
Region N
RegionһѭҲһδгRegionڲûͨţRegion֮Ҫ¿ԽͨԻüݻǼ.һԣڲRegionҪȫͬ,ÿRegionڿʼִеʱӵȫȷ.Բѭ˵ϵͳͨѭʵռм㻮֣ڶϲִ.ݿռûֱӻ֣㶼ӵݿռ.ĺô˵ַ任ͻ˴гִУȱռڴȽϴ.ĴвɸڵִУӶ˴ִͨſ.I/OڴвɵģҲɸִеģͼؽٽзַͨſ.
TIPSֲģõļݶ׼ʱͨźϲȣĿǰPVM+F77.ڱĵƪȥЩ㷨.
3 ܲ
3.1̬Ԥܲ
Ϊ˲ԹܣǽһϵеĲ.еʵ鶼һ̨ӵ˫CPUUltra 2ϽеģϵͳSolaris 2.5.
3.1.1 ׼ȷԲ
ʹնɴѧһϵгԸԤĹ׼ȷԽ˲ԣȻЩӱȽ϶СҲӳʵӦóص.1ʾ.
1 ׼ȷԲԽ

ʵʱ(s)Ԥʱ(s)(Ԥ-ʵ)/ʵ*100(%)
problem01.f1.441.589.7
problem02.f0.460.460
problem03.f6.423.57-44.4
problem04.f3.874.4515.0
problem05.f3.622.71-25.2
problem07.f1.861.82-2.2
problem08.f1.390.79-43.2
problem09.f0.940.55-41.5

ͨʵԿƵ-50%20%֮.ͨ£ֵСʵʵʱ䣬Ҫڴ洢ʵĲȷ.ѵģͨεķõƽִʱ䣬ˣ洢ķʻǶCacheе.ʵʵӦó˵Cacheе£Ҫڴеҳʵʵִʱ佫Ԥʱ.һӦóУڼʱڴʵʱöʱԤĽȽ׼ȷ.
3.1.2 ȷҪѭ
ԤָûעһЩȽϺʱѭϣЩѭвлԸ߼ٱ.ھ̬ԤʱʱȻܵԤʱʵʱϴ󣬵ǳиռĲȴǺܴ.purdue-setеproblem09.fѭռȫʱıΪ2. 
2ѭԤʵʱռıȽ

ѭʵʱ(s)(%)Ԥʱ(s)(%)
DOIT do#10.211210.13424
DOIT do400.310310.23743
DOIT do500.00100.0010
DOIT do600.305300.13024
DOIT do750.118120.0468

ĽԿʵԤĽڻΪѭռıС,ʹԤԺܺõȷҪѭָӦóĲл. 
3.2ֲܲ
ǲpurdue-set14BenchmarkȫԶкٽԶֲɵܣл8̨2CPUSun Ultra2ϵͳSolaris 2.5ʹ100M̫.ʱ1CPUеʱ䣬ʱ8̨վʹ8CPUеʱ.ΪЩʱ䶼Ƚ϶̣ǰÿ10ȡƽֵΪִʱ䣬3.
3ֲʽɵĲԽ

ʱ(s)8㲢ʱ(s)ٱ˵
Problem01.f3.00.74.29
problem02.f6.41.34.92
problem03.f20.73.85.45
problem04.fȷ
problem05.f1.38.20.159
problem06.f501700.185
problem07.f1.82.00.9
problem08.f0.570.07
problem09.fδͨ
problem11.fδͨ
problem12.f0.4кʱ
problem13.f2.10.63.5
problem14.fδֲ
problem15.fδͨ

ԽУδͨΪʹõĵײԶPolaris˳ЩԳ.ԿĳЩTIPSֲģĲд룬ǶһЩɵĲдЧʺܵͣȷ.ΪֲģɵͨѶ࣬ûпǵĳЩɵ. 
3.3ܲ
û޸ĳ±룬û޸ĳķʽἫӰ.Ϊˣֻ˼򵥵ĲԣԽ޸ĳеһѭȫ±Լ50%ıʱ.
4 Ĺ
Ǽƻ¼ио.
̬Ԥ.̬ԤĿǰ׼ȷҪԭѭƲ׼ȷδcacheӰ.Ǽƻö̬/̬ϻûѯķøӾȷѭֵ.cacheӰ죬ܹcacheģ.
ѯ.ĿǰTIPSУϵͳֻһRangeԲܽвѯ.Ǽƻչѯʹ÷ΧڲѯԲ㷨ѲѯӦ˽лֲɵȷ.
.ǽû޸ĳģʽЩģʽĴԴﵽٶ.
ֲ.Ŀǰɵķֲÿ϶ӵȫݣ˲Ҫڴϴĳ.ǽµķֲģͣʹÿӵСȫݿռľֲݿռ.ͬʱǻҪоͨŻ㷨ǿϵͳȶ.
5 С
Ϊʽϵͳǽ߲лһǰ;ķ.TIPSϵͳµԶлΪѺõĽߣЧذûгл.
*оõ863߿ƼĿ.
߼飺Ĺ,1972,ʿ,ҪоΪб뼼.
,1976,ʿ,ҪоΪб룬.
,Ů1974,˶ʿ,ҪоΪб.֣,1976,˶ʿ,ҪоΪб룬.
֣γ,1946,ڣʿʦ,ҪоΪзֲ.
ͨѶϵ:100084,廪ѧѧ뼼ϵϵͳӦý
ߵλ廪ѧѧ뼼ϵ100084
E-mail: yangbo@est4.cs.tsinghua.edu.cn
ο
1Blume William, Eigenmann Rudolf. Performance analysis of parallelizing compilers on the perfect benchmarks programs. IEEE Transactions on Parallel and Distributed Systems, 1992,3(6):643656
2Blume William, Doallo Ramon et al. Parallel programming with polaris. Computer, 1996,29(12):7882
3Blume William, Doallo Ramon et al. Advanced Program Restructuring for High-Performance Computers with Polaris. Technical Report, 1473, University of Illinois at Urbana-Champaign, Center for Supercomputing Research & Development, 1996
4Amarasinghe S P, Anderson J M et al. The SUIF compiler for scalable parallel machines. In: Bailey D H, Gilbert J R, Mascagni M et al eds. Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing. Philadelphia: Society for Industrial and Applied Mathematics, 1995
5촫,갱,ͮ.Զлϵͳ.ѧ,1996,7(3):180186
(Zhu Chuan-qi, Zang Bin-yu Chen Tong. An automatic parallelizer. Journal of Software, 1996,7(3):180186)
6Ierotheou C S, Johnson et al. Computer aided parallelization tools (CAPTools)conceptual overview and performance on the parallelization of structured mesh codes. Parallel Computing, 1996,22(2):163195
7Johnson S P, Ierotheou C S et al. Automatic parallel code generation for message passing on distributed memory systems. Parallel Computing, 1996,22(2):227258
8Johnson S P, Cross M et al. Exploitation of symbolic information in interprocedural dependence analysis. Parallel Computing, 1996,22(2):197226
9Leggett P F, Marsh A T J et al. Integrating user knowledge with information from parallelization tools to facilitate the automatic generation of efficient parallel FORTRAN code. Parallel Computing, 1996,22(2):259288
10Hiranandani Seema, Kennedy Ken et al. Compiler optimization for Fortran D on MIMD distributed-memory machines. In: Proceedings of the Supercomputing'91. Washington, D C: IEEE, ACM, 1991. 86100
11 Hiranandani Seema, Kennedy Ken et al. The D editor: a new interactive parallel programming tool. In: Proceedings of the Supercomputing'94. Washington, D C: IEEE, ACM, 1994. 733742
1998-11-06յԭ,1999-02-01յ޸ĸ
