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



ԶѰʹشѭлģ任*
һ 갱 ʩ  촫
ժҪ֪nάĶشѭ,ȥĲлоȱѰʹѭ㲢лģĿ㷨.½˶شѭлģ任,֤㲢лҪĺϷģǴڵ,֤ͨһ㲢лģ任Ŀ㷨,̽÷ΧڷȫǶ׺ͷǳؾѭЧ;.
ؼʡԷ,Զл任,ѭģ任.
ͼšTP311
Automatically Computing Unimodular Transforming Matrix to
Parallelize Nested Sequential Loops
YU Yi-jun ZANG Bin-yu SHI Wu ZHU Chuan-qi
(Institute of Parallel Processing Fudan University Shanghai 200433)
Abstract Lacking an effective and feasible algorithm to compute the valid unimodular matrix for parallelizing of the outer loops, previous parallelizing researches can not automatically reveal the parallelism in such sequential nested-loops as have n-dimension distance matrix. In this paper, the authors discuss a general outer-loop parallelizing method by valid unimodular transformations, prove the existence of such a valid unimodular transformation, and suggest several practical computing algorithms through the constructive proofs. This discovered unimodular transformation can have the maximal number of parallelizable outer-loops transformed. Thus, the application scope of the algorithms can be enlarged to non-perfect or non-constant dependence distance loops.
Key wordsDependence test, automatic parallelizing transformation, unimodular transformation.
лǴглЧ,ԷִгвԵĳβʩԺϷĲл任,Ӷʹ˳βִУ1.,ЧԷ2ݺԶл任3ǲлɹĹؼ.гѭкܴĲ,,ѭл任ȻΪл任оص.
ģ(unimodular)任һ෶Χܹѭ任,ȼڶѭռһʽΪ1ģ󣩵ķԱ任,ͨΪ˷еĲԶоһЩѭ任(б(skewing)(interchanging)(reversal)).ģ任бѭռά,,Ϊ1Ĺ淶ѭģ任ǹ淶ѭ,任дʽԽΪ.Щʺѭ任,ģ任ֳΪѭл任оص46.
ģ任ڱ֤任ȷԵͬʱʹѭл.,ʹģ任ѭԶл,ζԸشѭԶҳʹѭлǡģ任.еĴԶлûʵһԶлģ任,Ϊ޷ԶѭԶʹ֮лģ任3.ýгƻ7ṩѭռͼӻߣ8ݶѭķ,ʹѰǡܶѭлģ任ҲǺѵ.о㷨ĿǶԸشѭԶҳʹѭлǡģ任.
Լ򵥵Ķѭ,U.Banerjee㷨˵θԴѭеĿѭؾ,ѰҺϷڲ㲢лģ任4.ĶԶѭڲ㲢лѭڲ㲢л,ĶԶѭ㲢л޷ֱӴѭ㲢л.һȷʹشѭ㲢лģ任㷨,ؾ֪ʱǶѭл.
,ѭĳʱ,D'Hollanderĵֺķܹһ㲢ѭ,ѹڲ㴮ѭص,һ㲢лѭ5.Xue˶ԷȫǶѭ任ΪȫǶѭռֱģ任ķ6,ĵѭģлַͬһ.
ĵ1ڽһģл任,֤Ϸģ任֪ؾĶѭǴڵ.֤ȫǹ,ѵóϷģ㷨.һĶѭʵ˵лģ任㷨.
1 Ѱѭлģ
ŵռı任,ѭĿѭؾҲһ任,Щѭ任ʹĿѭл.ؾ֪ѭ,ѰҺϷĲл任һַ:ʹڲѭеwavefrontͲʹѭеpartition.Banerjeeķ4ݶѭ㲢лģ㷽ڶѭ,n2ѭ.D'Hollanderķ5ֱnѭ,nѭ,Ҳܷе㲢.ֵ̽nѭģл㷨һɲѭģ任,ʹn-rank(D)ѭһܹл,rank(D)-1ڲѭҲܲл.ص֤nάռ,ֻҪmؾǳ:
.nmؾDrank(D)n,ͿҵһϷб任ģU,ʹUD=0DTT,Drank(D)mĺϷؾΪ.
.DΪȾ,ҳһģ任U,ʹóѭ**,ڲѭɲл.
DΪȿ,ʽD1,ͿԽD'Hollanderĵֺķ,ͨһ㲢ѭ,ʹڲ㴮ѭصǽյģ5.,ǵķڲ㲢л֮ǰ,rank(D)=mңD1,D'HollanderķܵĲлѭ(Dѭ),Ȼٶڲѭл,õn-rank(D)+1ѭһѭrank(D)-1еڲѭ.
1.1 ʹѭл
ѭл任뱣֤ԭռ,ڿѭصѭִеִ˳,༴ҪĺϷ.
1(Ϸľ). nάؾdΪϷ(valid),ǰֵ0:0nd.ؾDǺϷ,ÿd1,...,dmǺϷ.
1(һϷı任Ҫ). nnģU,Ϸnm׾D,D=UDҲǺϷľ,ҽUǾ,ҶԽϵԪض1.
֤:()ΪDǺϷ,d110,d120,...,d1m0;ΪUģ,ҶԽϵԪض1.di=Udi,d1i=d1i0.d1i0,diΪϷ.d1i=0,d1i=0,d2i=u21*d1i+d2i=d2i,d2i0,diΪϷ.d2i=0,d2i=0,d3i=u31*d1i+u32*d2i+d3i=d3i0,...,d1i=d2i=...=dk-1,i=0,d1i=d2i=...=dk-1,i=0,dk,,...,,d1i=d2i=...=dn,i=0,,һk,ʹdki0.,diϷ.
()(1) j1,u1j0,ȡd=...,0,dj=1,0...T,d1=u1j0,dϷd䲻Ϸ;u1j0,ȡd=d1=1,...,0,dj=-u11u1j-1,0,...,0T,d1=u11-u11u1j*u1j-u1j0,dϷd䲻Ϸ.u12=...=u1n=0,....jk,u1j=...=uk-1j=0,ukj0,ȡd=...,0,dk=1,0...T,d1=ukj0,dϷd䲻Ϸ;u(k-1)j0,ȡd=...0,dk=1,-ukkuk(j-1),0...T,d1=ukk-ukku1j*ukj-ukj0,dϷd䲻Ϸ.uk(k+1)=...=ukn=0.Uһ.(2) ΪU,ukk0.ukk0,ȡd=...0,dk=1,0...T,d= ...,0,dk=ukk0,...T,dϷd䲻Ϸ,UԽԪش0.ΪUģ,Խߵĳ˻ʽ1,ЩԽԪض1.
1֪,3ֻģ任,ԽԪزȫ0,,,ǲܱ֤кϷؾ任ȻϷ.ֻб任ܱ֤任ĺϷ.ô,ĳؾD,rank(D)n,ǷпҵϷģ任U,ʹUD=0DTT,Drank(D)mĺϷΪ?Ķ˿϶Ļش.
1(ϷԪģ). nάռ,ֻҪmؾǳ,nmľDs=rank(D)n,һһϷб任ģU,ʹUD=0DTT,Drank(D)mĺϷΪ.

֤(㷨1):,nάؾкŵD=d1,...,dmݱʾΪİD=e1,...,enT,ÿeimά.¼Ĺؼ.ѰU,ʹUDΪ0,...,0,en-s+1,...,enT Ĳ:


(1) (ʼ) s=rank(D),t=1,z=0,E0={},E1={e1},E2={e2,...,en},T=0,UU={}
/* t¼Ѿ޹e,z¼ѱ任Ϊ0ĸ,T¼мģ任 */
(2) IF z=n-s GOTO (4).
(3) For E0={e1=0,...,ez=0},E1={ez+1,...,ez+t},E2={ez+t+1,...,en},DΪϷؾ.
IF rank(E1+{ez+t+1})=t+1 THEN
E1=E1+{ez+t+1},E2=E2-{ez+t+1}
t=t+1
GOTO (2)
ELSE
ez+t+1ez+1,...,ez+t,ڷa1,...,at,at+1,at+10,gcd(a1,...,at,at+1)=1
a1ez+1+...+atez+t=at+1ez+t+1.(1)

/* Щϵͨ·:DsubΪDtӾ(E1tmάѡȡ޹صt,DincΪez+t+1ӦЩеtά.at+1=det(Dsub)0,a1,...,at=at+1DincDsub-1,ɴ˵õϵٷֱԼ,Ӷ֤gcd(a1,...,at,at+1)=1 */
WHILE at+11 DO /* շת */
FOR i=1,...,t,
bi=ai/at+1(2)
ai=ai mod at+1.(3)
 ENDFOR 
/*at+1ai0,i=1,...,t */ (4)
T=T+1


/*ez+t+1=-b1ez+1-...-btez+t+ez+t+1.(5)

1,DǺϷ,ǺϷ */
T=T+1,
/* iΪat-i0СǸ,
at-i+1=...=at=0.(6)

DǺϷ,ǺϷ:
ΪDǺϷ,ez+t-i,ez+t+1Ϸ,jʹd1j=...=dz+t-i-1,j=0,dz+t-i,j0dz+t+1,j0,ʽ(1)(4)(6)֪dz+t+1,j=az+t-i*dz+t-i,j/az+t+10,ì */
/* Ϊʹʽ(1),ϵ */
a1=-a1,...,at-i-1=-at-i-1,at-i=at+1,at+1=at-i.
/* ʽ(2)(5)֪,ʽ(1)µa1,...,at,at+1ez+t+1,ez+1,...,ez+tԳ,Ϊgcd(a1,...,at,at+1)=1,ʴѭһֹ */
ENDWHILE
/* Ԫ */
/* 1,DǺϷ,ǺϷ*/
/* û0 */
/* Ϊez+t+1=0,DǺϷ,ǺϷ,ҲǺϷ */
E0=E0+{0},E2=E2-{ez+t-1},z=z+1.
ENDIF
ENDFOR
(4) U=UTUT-1...U1Ϊģ,UT,UT-1,...,U1UU.
1. ڵռά(mn),ģ任ʹn-mѭл.
㷨Uļֻ漰б任,.
2. UǸݶ1Ըd1,...,dmĺϷģ任,ֻҪԭռкϷľddj1,...,djsΪųɵsάӿռ,ڱ任µռUdԾǺϷ,Ҳn-s㲢л(Udǰn-sΪ0).
֤:Ϊdԭdj1,...,djsųɵsάӿռ,Դһϵзȫʵ(֤Ϊ)a1,...,as,ʹd=a1dj1+...+asdjs.Ud=U(a1dj1+...+asdjs)=a1Udj1+...+asUdjs.Ϊdj1,...,djsǰn-sΪ0,Udǰn-sΪ0.
2. 㷨1õģ任㲢ģ任,ģ任ɲлѭ.
֤:жn-rank(D)пɱ任Ϊ0,rank(UD)rank(D),ģ任ı,ì.
1.2 ʹڲѭл
3. nάռ,ֻҪmؾǳ,nmľDs=rank(D)=n,һһϷб任ģU,ʹUDnmĺϷ,оĵ1Ԫش0(UDԪش0).
֤(㷨2):һϵзǸu1,...,un-1,,UT=Ϊ.k=1,,d1j=...=d(n-2)j=0,d(n-1)j0},...,k=n-1,
㷨1,ǶDģU1任õU1D=0TDTT,DΪs=rank(D),ڸ㷨2DõUs,U2U1Dɽһڲѭл.
1.3 ѭռ߽
nѭռIΪ{(i1,...,in)ZnL1i1U1,L2(i1)i2U2(i1),...,Ln(i1,...,in-1)inUn(i1,...,in-1)}任ĵռJΪ{(j1,...,jn)ZnLL1j1UU1,LL2(j1)j2UU2(j1),...,LLn(j1,...,jn-1)jnUUn(j1,...,jn-1)}.ھѭʹԱ߽ʽ,,ԽIռ߽ʾΪAibʽ,Aһ2nnϵ,bһ2n1ϵ:,k=1,...,n.Ϊi=U-1j,,Jռб߽ΪAU-1jb,ֻҪFourier-MotzkinͶӰԪ㷨9ݾͿԼLLkUUkԱʽ.ԭѭ߽bгѭű,ͨűʽԿӦF-M㷨ѭı߽.
2 ѭռģ任Ӧʵ
дѭؾ,㷨1ģ,ʹѭ㲢л,ΪõD=ȿ,D=1,ԲҪٸD'Hollanderһpartition.ʹ㷨2õģ,ʹѭڲ㲢л,Ӷģļ.F-M㷨ѭ߽ʽ,ģ任.㷨Զ,ԲԶл任ʵ.
DO i1=1,100
DO i2=i1,100
DO i3=i1+i2,200
a(i1+1,i2+3,i3+2)=...
...=a(i1,i2+1,i3+5)+a(i1+1,i2,i3)
ENDDO
ENDDO
ENDDO
DOALL j1=17,1700
DO j2=max((2-j1)/3,(-3*j1-400)/11), 
min(-5,(200-j1)/3,(700-j1)/2ݣ(500-5*j1)/16)
DOALL j3=max(1,j1+3*j2-100,(j1+2*j2-200)/5),
min(100,(-j2)/5, (j1+3*j2)/2)
i1=j3
i2=j1+3*j2-j3
i3=j1+2*j2-5*j3
a(i1+1,i2+3,i3+2)=...
...=a(i1,i2+1,i3+5)+a(i1+1,i2,i3)
ENDDOALL
ENDDO
ENDDOALL
3  
ؾΪ֪nάѭ,ڲ㲢лģл任,֤㲢лҪĺϷģǴڵ,Ҹ˼ʹѭлĺϷģ㷨.һ㷨ڷȫǶѭͷǳؾѭģ任.㷨Զлʵ.
*оõȻѧ𡢹863߿ƼĿ𡢹ʵǼƻ͹ҽίʿ.
**ʵn-rank(D)+1ѭrank(D)=0򲻴ҪһлĴѭ
ͨѶϵ:һ,Ϻ 200433,ѧдо
߼顡һ,1972,ʿ,ҪоΪд,ܼ.
갱,1965,,ҪоΪл.
ʩ,1971,,ҪоΪд.
촫,1943,,ʿʦ,ҪоΪд.
ߵλѧдоϺ 200433
ο
1 Wolfe M. Optimizing supercompilers for supercomputers Ph.D. Thesis. University of Illinois, UIUCDCS-R-82-1105, 1982
2 Banerjee U. Dependence Analysis for Supercomputing. Norwell, MA: Kluwer Academic Publishers Group, 1988
3 촫,갱,ͮ.Զлϵͳ.ѧ,1996,7(3):180186
(Zhu Chuan-qi, Zang Bin-yu, Chen Tong. The automatic parallelizing compiler AFT. Journal of Software, 1996,7(3):180186)
4 Banerjee U. Unimodular transformations of doubleloops. In: Advances in Languages and Compilers for Parallel Processing. Cambridge, MA: MIT Press, 1991. 192219
5 D'Hollander E H. Partitioning and labeling of loops by unimodular transformations. IEEE Transactions on Parallel & Distributed Systems, 1992,3(4):465476
6 Xue Jin-ling. Unimodular transformations of non-perfectly nested loops. International Journal of Parallel Computing, 1997,22(12):16211645
7 Yu Yi-jun, Wang Qi, Zhu Chuan-qi. The design of a parallel programming environment for FPT. In: D'Hollander E H et al eds. Proceedings of the Topic in Knowledge and Information Technology. Communication & Congnition, 1996. 6980
8 Wang Qi, Yu Yi-jun, D'Hollander E H. Visualizing the iteration space in PEFPT. In: Hertzberger B, Sloot P eds. Proceedings of the High Performance Computing and Network International Conference and Exhibition. Springer-Verlag KG, 1997. 908915
9 Williams H P. Fourier-Motzkin elimination to integer programming problems. Journal of Combinatorial Theory(A), 1976,(21):118123
1997-12-29յԭ,1998-03-23յ޸ĸ
