ѧ
Journal of Software
2000 Vol.11 No.1 P.126-132



VLIWṹϵѭ
ݺ첨־
ժҪǲдĻ.ָ,VLIW(very long instruction word)еʹԷڲͬص.ͬһϵγһ򼯺,ϵ֮Ҳڰϵ.ݴ,һVLIWѭصķ.÷걸,ȥ,Ӷѭȵĸ.¸жͶĳֱҪ,ԼԸӶȵ㷨.ַձ,ΪVLIWˮͶָȵĻ.
ؼʡVLIW(very long instruction word),ѭ,,ѭ,.
ͼšTP338
Eliminate Redundant Loop-Carried Flow Dependences for VLIW Architectures
RONG Hong-boTANG Zhi-zhong
(Department of Computer Science and TechnologyTsinghua UniversityBeijing100084)
AbstractData dependence is the basic guideline and constraint for parallel processing. The structural distinctiveness of VLIW (very long instruction word), i.e., the lockstep property, leads to remarkable uniqueness in its data dependence analysis, as is shown in this paper. Flow dependences with the same iteration distance comprise a linear ordered set, while characteristic flow dependences with different iteration distances may also have inclusion relationship between each other. From such discovery, a novel method is presented to eliminate redundant loop-carried flow dependences for VLIW architectures, so as to facilitate loop scheduling. The method is complete in that it gets rid of all redundancies. The sufficient and necessary preconditions to identify redundancy for single and multiple iteration distances are given, and a linear ordered algorithm is described. The method is generic, and can serve as a foundation for research on VLIW, such as software pipelining and multi-instruction stream scheduling.
Key wordsVLIW (very long instruction word), loop scheduling, data dependence, loop, redundancy.
ǲдĻ.йԷĳɹȻܶ1,2,VLIW(very long instruction word)һضṹĹδ.Ŀǰ,VLIWϽвѭ,ˮ,ʹôͳĻԷ3,4,ȱVLIWרо.Ľ˵,VLIWṹϵ,طڲͬص.
οѭĲVLIWоȵ.ӰѭȵĹؼ,.Ľڵѭʱ,Խ͵ȵĸ.
¼ٶ.
(1) д/ܵԪʽ.VLIWĻ3,4.
(2) һһָ.עٶûпǶڲ,縡,ⲢӰȷ.ͨ,ڲÿղֲ.,OPiOPj,ֱҪTiTj,OPiOPjֱTi1Tj1ղ,ΪOPiһղOPj.
(3) ͬһѭеĲԹ̶λ.һ,ĵĽֱֻͼеǿͨ(ΪС֤ȵءܵص,б֮ǰȷ).һԺо.
һ,һͼDDG(data dependence graph)ж,ÿж.ȷֱÿϵ,ٽ,һ,ǱĵĻ˼.һЩͽ,A,B,A1,A2,...,AnʾأOPiʾһ,iǸòѭе.
1 ж
1. Aһ,ʾOPiOPjдϵ,Ϊd,dǷǸ,A(OPiOPj,d).
d=0ʱ,AΪ,Ϊ.ᵽκ,ĬΪ,d1.
2. A,B,ֻҪA,BȻõ,AB,AB.
3. A,B,AB,BA,A,B,AB.
4. A,B,AB,AB,AB,AB.
. ,,д.
1. (ƽ)A(OPiOPj,d),B(OPiOPj,d),ij=i䣭jʱ,A=B.
֤:֤AB.time(OP)ʾOPִʱ.
ͼ1ʾ,ÿߴһѭ,ϵĵ,϶µ.ͬ,˵.

Fig.1Traslation property
ͼ1ƽ
Aõ,OPjOPiִ֮,
time(OPj)time(OPi)0.(1)
 ʽһһָе,
time(OPi)time(OPi)=i-i,(2)
time(OPj)time(OPj)=j-j.(3)
iji䣭jʱ,ii䣽jj,ʽ(2)ʽ(3)time(OPi)time(OPi)time(OPj)time(OPj),time(OPj)time(OPi)time(OPj)time(OPi).ʽ(1)time(OPj)time(OPi).OPj佫OPiִ֮,BҲõ.,AB.
֤ͬ,BA.AB. 

ڸ,ͼ1дA,B߶ƽе,,Ϊƽ.ƽ˵,VLIW,κһ(OPiOPj,d),д(OPijOP0,d),ȥ,ԼдΪ(ij,d).صʼֹľλòҪ,Ҫǵλ.ж5.
5. A(OPiOPj,d),д(,d),Ц=ij,ΪAֵ.
ƵһҪ.
1. A(a,d),B(b,d),
(1)
֤:ƽ,ԽBƽ,ʹ֮Aʼͬ.ͼ2ʾ,abڴڡںС3ֹϵ,ֱӦAB,ABBA.֤ƽʵ֤,׸.

Fig.2Illustration of theorem 1
ͼ21
ͼ2(a)2(b)ABaݦb
ͼ2(b)ABa=bͼ2(a)ABab

. AB,BA.
֤:ABaݦbbaBA.

ζ,ͬһdϵ,ֵĴС.ͼ3ʾ,Anݦ An-1...ݦA1,AnAn-1...A1.,ֻҪAn,ĶΪɾ.ǳAnΪdϵ.

Fig.3Inclusion between flow dependences with the same iteration distance
ͼ3ͬһϵصİ
6. ĳһd,ΨһӦһֵ,Ϊ(d),ȡֵ£dʱ,(d),,(d)=maxi(i,d)dϵأ.((d),d)Ϊdϵ.
˵,۶.
2 ж
7. A1,A2,...,An,n1,ֻҪǾͿȻһB,A1,A2,...,AnB,A1A2...AnB.
8. A1,A2,...,AnB,n1,A1A2...AnB,ҶһX,A1A2...AnX,BX,ô,BA1,A2,...,An,MaxIncluded(A1,A2,...,An)B.
9. A1,A2,...,An,n1,ͨƽβ,һһB,BA1,BյAnյ,BΪA1,A2,...,AnȻ,ΪNaturalIncluded(A1,A2,...,An)=B.
жʱ,ʹÿֻ,Կܴ.ͼ4ʾ,A,B,CΪͬϵ,A+BNaturalIncluded(A,B)C,Cɾȥ.

Fig.4Redundancy in the case of multiple iteration distances
ͼ4ʱ
غȻؾ:
1. MaxIncluded(A1,A2,...,An)NaturalIncluded(A1,A2,...,An).
2. A1A2+...+AnBMaxIncluded(A1,A2,...,An)B.
12غȻصĶֱӵó.
صķ.
2. A1,A2,...,An,n1,Ai(i,di),i=1,2,...,n,MaxIncluded(A1,A2,...,An)
֤:ͼ5ʾ.ͨƽ,ʹA1,A2,...,Anβ.A1ΪOPk,ֵĶ,յΪOPk1,A2յΪOPk(12),...,AnյΪOPk(12+...n).Ϊ漰n,ÿصյҪͺһ,,AnյҪͺA1n.ô,Anյn1,ڸõ㴦ĲOPk(12+...+n)n+1ġȻA1OPkִеĲ.ȷA1,A2,...,An.

Fig.5Compute Max Included(A1,A2,...An)
ͼ5Max Included(A1,A2,...An)
,MaxIncluded(A1,A2,...,An)ֵkk(1+2+...+n)n+1=(1+2+...+n)+n1
MaxIncluded(A1,A2,...,An)ȻǸAi(i=1,2,...,n)ĺ.

1(Գ). MaxIncluded(A1,A2,...,An)MaxIncluded(Ai1,Ai2,...,Ain),i1,i2,...,in1,2,...,nһ.MaxIncludedĲ˳ν.
2. X(x,d)Y(y,d),ԼһA1,A2,...,An,n0,
(1) xݦyMaxIncluded(X,A1,A2,...,An)MaxIncluded(Y,A1,A2,...,An)
(2) xyMaxIncluded(X,A1,A2,...,An)MaxIncluded(Y,A1,A2,...,An)
(3) xyMaxIncluded(X,A1,A2,...,An)MaxIncluded(Y,A1,A2,...,An).
3. A1,A2,...,AnB1,B2,...,Bn,n1,Aiiϵ,Biiϵһ,i=1,2,...,n,MaxIncluded(A1,A2,...,An)MaxIncluded(B1,B2,...,Bn).
صĻ˼,ҪɽСϵ,һϴϵ.ֻҪЩСϵؼ,ϴϵǸؾ(ͼ4ʾ).
һd,Ѿʱɾֻʣ,Ϊ.2,ҵһЩA1,A2,...,An,ʹMaxIncluded(A1,A2,...,An),ô,ֻҪA1,...,An,Ϳɾ,Ӷdϵضɾ.
,ҪѰҵA1,A2,...,AnΨһ.ΪͬһdԷֽΪd1,d2,...,dn֮,ַֽǲΨһ.ÿһֽd1,d2,...,dnӦһA1,A2,...,An,ӶӦһͬMaxIncluded(A1,A2,...,An).
,ΪжdϵǷȫ,Ҫҵdзֽ,ӶҵеMaxIncluded(A1,A2,...,An).ЩMaxIncludedͬһd,,֮һҲų,Ƕе(MaxIncludedǸMaxIncluded)Ϊdϵ,d.
ʱж.
3. dϵئԼdϵd,ҽdʱ,dϵؿԱɾ.
֤:ؿԱɾ,˵ئѿɱɾ.
(1) .dʱ,ݦdĶ,һĳЩA1,A2,...,An,Ai(i,di),i=1,...,n,di=d,ʹMaxIncluded(A1,A2,...,An).,A1,A2,...,An,ѿɱɾ.
(2) Ҫ.ڦѿɱɾ,ζŴĳЩA1,A2,...,An,ʹA1+A2+...+An,Ai(i,di),i=1,...,n,di=d.2,MaxIncluded(A1,A2,...,An).ɦdĶ,dMaxIncluded(A1,A2,...,An).д,,d.

,ڶ,Ҫĳdϵ,Ҫd.,ƵdĹʽ.
4. d,d=(,d),Ц=max1+1+2,1+1+((dd1))(1,d1)d1ϵ,d1=1,2,...,d1(2,d2)d2ϵ,d1+d2d.
֤:Ȼ,dd.Ҫֵ.
ɦdĶ,(d)=max(MaxIncluded(A1,A2,...,An))Ai(i,di),i=1,...,n,n1,di=d.23˵,A1,A2,...,Anʱ,MaxIncludedֵ,ǿԽһٶA1,A2,...,An.
ɶ2,MaxIncluded(A1,A2,...,An)=(i+1)-1,d.,(MaxIncluded(A1,A2,...,An))=
,(d)=max(11(i+1)-1.
n=2ʱ,(d)=max(1+1)+(2+1)-1=max(1+1)+2.
n2ʱ,(d)=max(1+1)+(MaxIncluded(A2,...,An))=max(1+1)+max((MaxIncluded(A2,...,An)))=max(1+1)+((d-d1)).d1dķֽеһ,dd1,d1ȡֵΧ1,2,...,d1.ע,һݹʽ.
,n,Ц=max1+1+2,1+1+((dd1)).

4˼㦤dĵݹ鷽.Ϊٶ,㷨ݹתΪ.
3  
,Ƕͼϵÿ,ϵأȻЩۺϿ,һϵ.
Pnm=ۦij,n,mϵظֵ.ijiϵһ(ij,i)ֵ.Pĵiм¼iϵ.iϵض릱,ĵiδʱ,ʣλϣ.
n=ۦi,Цi=maxijijʦ,j=1,2,...,m.(i,i)iϵ.ֻе,ɾ,ϵ༴.
n=ۦi.1=,ֵ.
㷨£




㷨ʱͿռ临ӶȶO(mn).
һ.ͼ6ʾ,ѭ6,,ֻʣ1.ɽ㷨ͼ.


Fig.6An example of elininating redundant loop-carried flow dependences
ͼ6ص
4 ʵ
ѡȡ,ʵ1.
Table 1
1

ProgramTotal (intra-block) loop-carried
flow dependencesAfter redundancy
removalRedundancy
rate()
Product5260
Flower4175
Sift5260
Vander10280
Merge13469

ٳ,(ڵ),ɾ,.
,ָռصİٷֱ.ɱпԿ,ƽԼΪ69.Ҫԭÿж,ֻһ.VLIWеɵ.ּVLIWطĻ.ʵڻ,ǽĽνĽƹ㵽һ.
5 
Լѭȵĸ,ȻÿضҪ.ЩҪ,ڼѭȵĸ.VLIWеʵطڲͬص.ݴ,һķ,жͶĳֱҪԼԸӶȵ㷨.
ȻVLIWϵѭΪ㿼ǵ,,еķ̿Կ,ַʵһһ㻯ķ,ѭ,ʿΪVLIWˮͶָȵĻ.һҪۺӦüֵ.ǽоЩӦ.
оõȻѧ(No.69773028)
ݺ첨廪ѧѧ뼼ϵ100084
־ң廪ѧѧ뼼ϵ100084
E-mail: ronghb@mail.cic.tsinghua.edu.cn
ο
1Kai Hwang. Advanced Computer Architecture: Parallelism, Scalability, Programmability. New York: McGraw-Hill, Inc., 1993.457496
2Psarris K, Kong X, Klappholz D. Direction vector I test. IEEE Transactions on Parallel and Distributed Systems, 1993,4(11):12801290
3Rau B R, Fisher J A. Instruction-Level parallel processing: history, over view and perspective. The Journal of Supercomputing, 1993,1(9):950
4Lam M. Software pipelining: an efficient scheduling technique for VLIW machines. SIGPLAN Notices, 1988,23(7):318328
1998-12-01ո
1999-02-01޸
