ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.334-341



е򸲸Ǽ
갱촫
ժҪü㺯ģͽоȷ,ν֮߼ϵתΪռ֮ĸǹϵ.ڸֳĳαʾʹݦ򡢦򣬲,æ򡢦֮ĸǹϵ֧Ĳȷ,ԵõȷϢ.
ؼʡ,,,˽л,ŷ.
ͼšTP311
Region Coverage Method in Dataflow Analysis
HU Shi-liang ZANG Bin-yu LING Bing ZHU Chuan-qi
(Parallel Processing Institute Fudan University Shanghai 200433)
AbstractFor a precise dataflow analysis within the framework of the computation function model,the logical relationship of branch conditions is represented as the coverage relationship of regions.In this paper,the authors discuss how to represent,compute and propagate the  region, region of the conditional reference.Meanwhile,the methods of resolving the nondeterminism caused by conditional branch statements are also presented in order to get more precise dataflow information.
Key words region, region,array dataflow analysis,array privatization,symbolic analysis.
 򸲸ǵĸԴ.лıҪǸܼеĿѧ.ձص֮һ,ݽṹ,ͱݼ.ˣǲлĹؼ.(array region)ıʾ㼰໥֮ĸǹϵеҪ.
ף1-ǷĸǼԲ˽лж.ʵԱ,-жʵЧõ˽л֮һ.Ǹ÷Ŀǰܴ֧ȷ.˽лڶಢл任Чķ֮һ1,2,бҪ-Ƿ,ʹܹ֧֮ȷ.
ڼ㺯ģͣ3,дõԱʾΪ,ʽڸϵһع.ĸǹϵ,ڼĿ´֧ȷ,ǿͳ.,ĸǼӦڷŷ.
ĵ1ڽĹαʾдĦͦ.2ڲæ򡢦ĸǹϵõȷϢ,͵ʵ.3ͬعбȽ.ó.
1 򡢦ıʾ
һ,νʵĦDom(P)ռпǷǳӵĿռ,Լģж໥֮ĸǹϵһNP.ȴĸӶԴڳ߼屾Ǳڸ.
ֵҵ,ķŻҪпܵ,ֻ账ʵгġӰ첢л任.SPEC95fp,PERFECTȲԳķ:νʵOmegaֱӳֵı(t1,t2,...,tk)ͨԱʾΪ͹.ѦT(t1,t2,...,tk)ΪOmegaĲʽ.ҪжǹϵOmegaڲͬĲռʱ,вķ,ʹǴͬһռ,иǹϵıȽ,滻̲ڸӵıʽڸӵOmega,ʹжOmega֮ĸǹϵùڸ,Ϊ̬ж.ڳP,ֻܽееĲȫ滻ΪIn(P)еı,滻̿,һ.
лҪṹĳ,һɱʽֵ䡢֧䡢ѭԼ˳ṹ.л任ҪŻȷѭ,FORTRANеDOѭ,ΪвԵĳ.DOWHILEREPEAT-UNTIL͵ѭǵݹ,Чزм,ﲻٿ.
1.1 νʵOmegaʾ
֧߼νҪֳĻʽ:ֵϵıȽ,=,,,,,;ͱMOD;ֵԼڴ˻ϵ߼.ף3е1.1֪,߼νʿֱӱʾΪOmegaʽ.
(1) ֵϵıȽ,ͱMODֱӻΪռԼ̡ʽ.,
IF (X4)Ϊ ={Dom(P)|X4}
IF (MOD(X,2)=0)Ϊ ={Dom(P)|mod(X,2)=0}.
(2) ֵ㻯ΪԷ.,
IF (|X|1.0)Ϊ ={Dom(P)|X1.0;X-1.0}.
(3) ߼㻯Ϊ֮Ľ:
IF (C1 .and.C2)Ϊ =1ɦ2,
IF (C1 .OR.C2)Ϊ =1Ȧ2,
IF (.NOT.C1)Ϊ =(1).
:
IF (.NOT.(X4))Ϊ=1={Dom(P)|X4},
IF ((X2).AND.(Y1)) Ϊ =1ɦ2={Dom(P)|X2;Y1},
¼{Dom(P)|p(x1,x2,...,xn)}Ϊ{p(x1,x2,...,xn)},;ʾϵ.
1.2 Ƕ֧µ
Ƕ֧ifڲOmegaΪi,if֮ӦOmega0Ǧiif֧֮νOmegaĽ.
ɦĶ:xP=pxSetP(x),ļֻӦļ.
1:
Step 1.IF (X4) THEN
Step 2.IF (Y0) THEN
Step 3.DO I=1,10
Step 4.w A(I)=...
Step 5.ENDDO
Step 6.ENDIF
Step 7.ENDIF
ڳStep 3Step 5,wA(1:10);ڳStep 2Step 6,Step 2νʵOmegaǦ2={Y0}.鶨wڳStep 2Step 6ΧеĦΪ
26(w)=2Set26(w)={Y0}{A()|=1,...,10}.
ڳStep 1Step 7,Ƕ׵OmegaǦ=1ɦ2={X4;Y0},鶨wĦΪ
17(w)=Set17(w)={X4;Y0}{A()|=1,...,10}.
1.3 ǶDOе
ǶDOеIF,Էǳ.ֻ迼Ƕļֳ.οף3ĺֵȷIFķųڷΧ֮.
ǶDOе߼Ժб.
ǶDOеIF,н,Ƿǵݹ,IFΪѭ֧,ᵽDOѭ֮,1.2ʽ.
ݹ(induction variable),ô߼ǶѭĵռԼ߼ν.xǶڳPnDOѭ,ӦѭΪi1,i2,...,in,t1,t2,...,tkֱӳνP(t1,t2,...,tk)еı,νȷDT=Dt1Dt2...DtkеT,ԱʾΪi1,i2,...,inIn(P)ϵķ̺Ͳʽ.ҪXnѭ֮ϵʱ,ҪOmegaͶ䵽ѭPĶIn(P).Ͷ̰ѭi1,i2,...,inOmegaʽȥ,ʵ,ȥĹDOѭĹ̶Ӧ.ѭô߼ԼתΪԼ.
2:
Step 1.DO LL=1,31
Step 2.N=LL-2
Step 3.DO I=1,31
Step 4.N=N+1
Step 5.IF (N>=31) THEN
Step 6.w Y(I,LL)=Y(I,LL)+S(I,LL)+TEM(I,LL)
Step 7.ENDIF
Step 8.ENDDO
Step 9.ENDDO
ѭ(Step 4Step 7),wΪ
w47=w47Set47(w)={N31}{Y(1,2)|1=LL;2=I}
={1LL,I31;LL+I-231}{Y(1,2)|1=LL;2=I}
={Y(1,2)|1=LL;2=I;1LL,I31;LL+I-231},
ѭ,wPеΪ
wP=wPSetP(w)
=Dom(P){Y(1,2)|1+2-231;1ܦ1,231}
={Y(1,2)|1ܦ1,231;1+2-231},
Step 1Step 9еPĶ
w=Dom(P).
ǶDOѭеIF,߼,õ±ʽкеݹ(Ϊ),ʱ߼ǹڸضʽ߼,Ҫ߼չ.,߼̺൱ḻ͸ӵ,ڲлĿѧʱ,رҪֳģʽ.
(1) ʽ߼Լ.ʱ±ʽһϸ񵥵,ѭĵռСΪn,ݸжԪԸ߼Ƿ2n,ڱֻͨ迼ȫȫ.ȫʱ,ԼһĹԼ,ӦĦΪ߼ʱ;ȫʱ,Լ.ӦĦΪ߼ʱ.μ3.
(2) ʽ߼Ӧµ.ʱ߼е±ʽһ㶼ϸ񵥵,߼ԪصȡֵǷӦԪؽжд.Ҳֻ迼ʽ߼ȫȫ,ӦĦ㷽ͬ,õͬһ㷽ͬ.μ4.
3:
Step 1 KC=0
Step 2 DO K=1,9,1
Step 3 IF (RS(K).GT.CUT2) THEN
Step 4 KC=KC+1
Step 5 ENDIF
Step 6 ENDDO
Step 3еRS(1:9)߼.KCStep 1Step 6ķΧֵȷԶ.KCǷű,Ҫзŷ.KC:RS(K).GT.CUT2,K=1,...,9Լ.KCȡֵΧΪ0KC9.
KC=0ӦStep 3ȫDom(P)еһ

KC=9ӦK,1K9Step 3

4:
Step 1 DO K=2,5,1
Step 2 IF (RS(4+K).LE.CUT2) THEN
Step 3 RL(4+K)=SQRT(RS(4+K))
Step 4 ENDIF
Step 5 ENDDO
Step 1Step 5еIF䵼˳Pеһд,RL(6:9)ĶRS(6:9)(RS(4+K).LE.CUT2)һµ.ȫʱ,,RL(6:9)Ҳȫ,ȫʱ,RL(6:9)Ҳȫûб.
Ҫָ,,ڦıʽгԪ,ǶһΧеÿԪض,,,,бҪеϵͳڱʾ㷽ϽӦ.
1.4 ̼Ĵ
ĳPй̵ʱ,Ҫڵù̺ͱù֮䴫Ϣ.νʵĦҪǹڱԼϵ,ҳʵ֮ĶӦϵб滻.Ŀ̴ӵö,ʱʵвͬ״,ʵҲһԪؿʼ,ˣҪRESHAPE4.
1.5 㼰򸲸ǹϵж
֮Ļ.
nάռ㼯֮ļ͸ǹϵжǺѵ.ʵӦó,߼Ħ򾭳͹,Ǹά֮໥.ף5йDiophantine̡ʽOmegaԷ,ϵཻ͸ǹϵ,ر͹㼯ཻ֮͸ǹϵж.ף5гĲο,һ͹֮͸ǹϵжķ,ﲻ׸.Ҫжǹϵռǳʱ,ĸԴ߼ν֮߼ϵĸ.
2 򸲸ǼеӦ
2.1 е򸲸Ǽ
пæͦĸǹϵ֧䵼µȷ.ף3еĸǶԵԭ.
ȷԭ.ڳPضĶrпΪrṩԴдW:W=NaWrP,жWһضӼW*Ƿͨжȷ:rPP(W*).жһдܷ񸲸Ƕʱ,ֻжrw and SetP(r)SetP(w).
򸲸Ǽǿ˽лж.
ӵƹ㵽,ף1е-Ƿƹ㵽ܹ֧ġ̬ȷ.Լ:BLʾѭĴ,Liʾiѭ,LvʾLi,2iBL.ŵĺף1ͬ,ԼдԵǰ.ƪ,֤.
2.1.ڳ
2.1.ѭLдԸǵ,1iBL-1;Li(W)Li+1(W).
ж׼.ѭL,k,2kBL:UELk,˽л.
ж׼1.ѭL,rRLv,Lv(r)Lv(NaWrLv),r˽л.rRLv˽л,ѭLǿ˽л.
ж׼2.ѭL,rRLv,LдԸ:ҦLv(WLv)Lv(NaWrLv),ôr˽л.rRLv˽л,ѭLǿ˽л.
2.2 ŷе򸲸Ǽ
ڼ㺯ģ,֧䶨ķű,ֵԱʾΪ

p1,...,pn,otherDom(P)һ.ǳֱʾΪ.
P,ԷűSymbolĶr:,rܹExpValiĳҪ:prɦpi;ر,prpi,rһExpVali;,Rһ{ExpVali|iD}еĳֵ.Symbol(pr)ʾ״̬pr¶űSymbolȡıֵʽ.
5:
Step 1 IF (I.LE.6) THEN NB=1
Step 2 ELSEIF (I.GT.6 .AND.I.LE.26) THEN NB=2
Step 3 ELSEIF (I.GT.26 .AND.I.LE.64) THEN NB=3
Step 4 ELSE NB=4
Step 5 ENDIF

Step 10 IF (I.GT.32) ...=...NB...
NB(I>32)ֵȷΪ34,I64,ԽһȷΪ4.
ף6ƹĦ-functionʾӦʾn=1ʱ.,ף6н˱ʾƹ㵽ʾ,,űļֵ
max(Symbol)max(ExpVal1,...,ExpValn,ExpValo),
min(Symbol)min(ExpVal1,...,ExpValn,ExpValo).
űʽݵ,ķ滻,һʽķǳһʽǳӼ.Ƚݷűķ:

(2)iExpVal(2)iʾ2űSym2еiӦOmegaͱʽ.
֮ĸǹϵڸʱ,ýƵж:
(min(Sym1)max(Sym2))(Sym1Sym2).
ʾԷرʾIndex Array.
6:
Step 1 DO J=1,JMAX
Step 2 JPLUS(J)=J+
Step 3 ENDDO
Step 4 JPLUS(JMAX)=1
ԱʾΪ:
2.3 򸲸ǼӦ÷
Perfect BenchmarksMDG.ӳINTERFеѭDO 1000ռMDGʱ90%,ڴͳ޷ȷRLǷ˽л,ʹøѭûбִ.ԸѭбⱾʵļ.
Step1DO I=1,NMOL-1,1
Step2DO J=I+1,NMOL,1
Step3KC=0
Step4DO K=1,9,1
Step5RS(K)=XL(K)*XL(K)+YL(K)*YL(K)+ZL(K)*ZL(K)
Step6IF (RS(K).GT.CUT2) THEN
Step7KC=KC+1
Step8ENDIF
Step9ENDDO
Step 10IF (KC.NE.9) THEN
Step 11DO K=2,5,1
Step 12IF (RS(4+K).LE.CUT2) THEN
Step 13RL(4+K)=SQRT(RS(4+K))
Step 14ENDIF
Step 15ENDDO
Step 16IF (KC.EQ.0) THEN
Step 17DO K=11,14,1
Step 18FTEMP=AB2*EXP(-B2*RL(K-5))/RL((-5)+K)
Step 19FF((-5)+K)=FF((-5)+K)+FTEMP
Step 20ENDDO
Step 21ENDIF
Step 22ENDIF
Step 23ENDDO
Step 24ENDDO
,ϣȷRLǷѭǿ˽л.,ǿǵĵǰPǴStep 3Step 22.
Step 3Step 9ıKCStep 10Step 16б,KCǵ͵IFµķű.ҪƲֵ,μ1.3е3.
Step 11Step 15едμ1.3е4.
Step 16Step 21еIF䵼˳Pе:RL(6:9).
νKC=0֪,RL(6:9)ĶOmegaKC=0Ӧ,SetP(r)=RL(6:9)Step 11Step 15дȫдSetP(w)=RL(6:9):SetP(r)=SetP(w),Ҧrw.

ǰȷԭ֪,˴ȷԴStep 11Step 15д,˲ѭ,ɵ2.1˽лж׼1֪,RL˽л.
SGI Challenge 4L(4)SMPϵʵ,ķ任ʹMDGļٱȴ1.0ߵ3.7.
3 عȽ
߼ϵĸ,еĲл,,SUIF7,AFT8ڽʱһ֧߼.ڴͳĿѧ,Ƚϼ.ӰܵĹؼ,ֻΪ֧,һֵȷԵ,ԶľӰ첻.ſѧ渴ԼлǱӦ÷Χ,ǿʼע⵽δ֧.
Parafrase-2еJoin-functionԼWolfeĦ-function,ʵϲû֧߼.ף2,6ݶԦ-function,ʹܹ֮Я߼,Polaris9ݲлӦڷŷ.ף10GAR(guarded array region),ǶڸϽһ.GAR,ϪGuard߼ν,߼ϵͳ;ʾΪݿռе͹,Ǽϵͳ.ͬϵͳͬһ,ʹGARۺʵ϶൱.,걸߼ϵͳɵʵõı,Ŀǰ˻ɵ.
ڼ㺯ģ͵Ŀ,߼תΪռļ,ʽһµ.˦GARһȻĶĸع.ʵһµϵͳ,ֻϵͳĻǿ.ͨĵʾ֪,򸲸ǷࡢЧ.,ѷűֵʾΪʽ,򸲸ǵĹϵзŷ,ף6ķ.
4  
㺯ģͺ,Զиϵع,õĦһ¸.ͬʱõԪϢõ߼Ϣ,,ͨĸǹϵԽ֧䵼µȷ.,߼Omega򻹿ɵűȡֵϢ.
򸲸ǼǱȽϳļ.Ĳʵʳгĳ¼߼ĦõĦ,æͦĸǹϵСĴ֮»øȷϢ.
оõȻѧ(No.69633030)863߿ƼĿ(No.863-306-ZT01-02-01)ѧĿ͹Ƽصʵһ(No.97JS76.5.2.JW0701).
,1972,˶ʿ,ҪоΪֲʽ.
갱,1965,,ҪоΪд,ܼ.
,1974,˶ʿ,ҪоΪб.
촫,1943,,ʿʦ,ҪоΪд,ܼ.
(ѧдоϺ200433)
갱(ѧдоϺ200433)
(ѧдоϺ200433)
촫(ѧдоϺ200433)
ο
1Chen Tong,Zang Bin-yu,Zhu Chuan-qi.A new method for array privatization.In:Tan Chee Klow ed.Proceedings of High Performance Computing Conference'94.Singapore:National Supercomputing Research Center; National University of Singapore,1994.4350
2Tu Peng,Padua D.Automatic array privatization.In:Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing.Berlin:Springer-Verlag,1993.500521
3Hu Shi-liang,Zang Bin-yu,Zhu Chuan-qi.Enhancing dataflow analysis with computation function model.Journal of Software,2000,11(2):187194
(,갱,촫.ü㺯ģǿ.ѧ,2000,11(2):187194)
4Creusillet B,Irigoin F.Interprocedural array region analysis.In:Huang C-H et al eds.Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing.Columbus,Ohio:Springer-Verlag,1995.4660
5Pugh W.A practical algorithm for exact dependence analysis.Communication of the ACM,1992,35(8):102114
6Tu Peng,Padua D.Gated SSA-based demand-driven symbolic analysis for paralleling compilers.In:Wolfe M,Nicole D et al eds.Proceedings of the International Conference'95 on Supercomputing.Bacelona:ACM Press,July 1995.414423
7Wilson R,French R,Wilson C et al.SUIF:an infrastructure for research on paralleling and optimizing compilers.ACM SIGPLAN Notices,1994,29(12):3137
8Zhu Chuan-qi,Zang Bin-yu,Chen Tong.An automatic parallelizer.Journal of Software,1996,7(3):180186
(촫,갱,ͮ.Զлϵͳ.ѧ,1996,7(3):180186)
9Blume B,Eigenmann R,Faigin K et al.Polaris:the next generation in paralleling compilers.In:Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing.New York:Springer-Verlag,1994.141154
10Trung Nguyen,Gu Jun-jie,Li Zhi-yuan.An interprocedural paralleling compiler and its support for memory hierarchy research.In:Huang C-H et al eds.Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing.Columbus,Ohio:Springer-Verlag,1995.90104
ոڣ1998-09-21
޸ڣ1999-03-09
