ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.101-409



һֶ֧ѭˮļĴṹ
ݺ첨־
ժҪĴṹˮ㷨Ĺؼ֮һ.Ϊֶ֧ѭˮ,һӱļĴṹ빲ԾʽˮĴ.Чؽѭˮµ,ͬκͿεļĴԼ⣻Чѭд,ָ߳ж.3ַ䷽ʽɹʹãĴˮĴͼĴ鷽ʽ.ˮĴʽȷġһѭεļĴṩ򵥶Ч֧.Ĵ䷽ʽ˶ѭˮʱڲȷ.ԾΪṩ˿ݴ.ʵ,ּĴѽṹ䷽ʽʮЧ.
ؼʡָ,Ĵ,ˮĴ,أˮ.
ͼšTP302
A Novel Register File Structure Supporting for Software Pipelining of Nested Loops
RONG Hong-boTANG Zhi-zhong
(Department of Computer Science and Technology Tsinghua University Beijing100084)
AbstractThe structure and allocation of the register file is a key factor affecting the performance of software pipelining.To support software pipelining of nested loops,a novel register file,partly-shared leaping pipeline register file,is presented and its allocation is discussed.The register file effectively addresses the special problems in software pipelining nested loops,i.e.,intra- and inter-level register renaming,and iteration discontinuity.Three allocation styles are designed for flexible application:single,pipeline and groupe register styles.Pipeline registers effectively supports intra-level register renaming with deterministic lifetime.A variable,which generally has deterministic lifetime,may have non-deterministic lifetime in software pipelining nested loops.Group registers address such a problem.To make a paused iteration continue execution again,a leaping operation provides quick data transmission between registers.The engineering practice has proved the efficiency of the structure and its allocation method.
Key wordsInstruction-Level parallelism,register file,pipeline register,data dependence,software pipelining.
ָILPinstruction level parallelismǵǰϵоȵ.VLIWϵṹµˮѧǵྫ.ԴĽǶȿ,һˮ㷨Ҫ⣺1 ĳʱ̽ܲ2 ĳʱ̽Ĵ.ͨ,㷨ԹܲҪ,ԼĴṹһҪר,Ա㻥,ӶЧʵ㷨.ĴṹֱӰ쵽,,ˮ㷨Ĺؼ֮һ.
Ŀǰ,жˮ㷨13,ҪԵѭ.Զѭ,һֻڲѭˮ,ѭִ.ILSPinterlaced inner and outer loop software pipelining㷨4,5ݲѭִзʽ,Ƚϳɹؽ˶ѭˮ.̽Ĵṹ.
ILSP㷨һӱļĴṹ빲ԾʽˮĴ.ԸЧʵֹܲfunction unitFU֮ͨ.㷨ѭءڲѭصĻ,ɼĴѭд.ڲ,ֻҪдؼ.Ӷָ߳ж.
ڼĴķ㷨йϵ,ȻعһILSP㷨,ȻеļĴ.
1 ILSP㷨ļ򵥻ع
ͳֱ,ڵ͵Ĺ̺Ϳѧ,󲿷ʱ䶼ڲѭϣ6.,ǰĸˮ㷨ڶڲѭˮ.,Ƿ,Ǻ.
ͼ1е߶αʾд.ڲJѭˮ,ѭIIinitiation intervalIIΪ2,ÿִһJѭͼ1bʾ.Iѭˮ,IIΪ1,ÿһִһJѭ.IIС,JѭִҲ̣ͼ1cʾ.

Fig.1Comparison between algorithms
ͼ1㷨Ƚ
ע⵽ILSPǴIѭʼˮ,ȻҵJѭظģʽ.,ȴѭˮ,ڷڲѭظģʽ,תڲѭˮִڲѭ,תˮ.ڡĹ,ֱִ.
 ,һѭ,һҪڲѭʼˮ,ǿѡһѲοʼˮ,һ㽻ˮķ.ѡ׼.ļٶ㿪ʼˮ.ǡ㡱ָ.
2 ݼĴṹ
Ŀǰ,ҪݼĴṹ¼.
1 ȫֹĴѣ79.мĴйܲڴ湲.Ӳṹ,ÿĴ롢˿ںܶ,չ.Աֱ֧ȽϺ.
2 ֲĴѣ8.FUֻܷڱFUľֲĴ,ͨ洢ͨ.Ӳṹ.
3 Ĵͨ10.ھֲĴѵĻ,ڸFUľֲĴ֮ṩͨ.
4 ˮĴѣ3,11.ÿFUоֲĴ˳ųһ,Ϊֱˮ.FUĴֱˮ֮佨ͨ,Ϊˮƽˮ.Ĵһ.ˮƽˮҪFU֮ͨ,ֱˮڼĴ.
5 빲Ĵѣ8.ַΪддȫֲֶͶȫдֲ.ȫֹĴѺ;ֲĴѵһ.Աֱ֧ȽϺ,ӲԸ.
ۺ˸ֽṹŵ,빲ԾʽˮĴ.Ƕȫдֲ,ҸFUľֲĴ֯ˮ,Ĵ֮ݴ͵Ĺ.
ͼ2ʾ,ÿܲFUһԼľֲĴˮ,FUļĴˮγĴ.ˮΪRi,0Ri,1...Ri,n,i=0,1,...,m.ˮʽ֯Ĵ,Լ򵥡Ȼؽͬѭ֮ļĴ,ɸЧ.

Fig.2Partly-Shared leaping pipeline register file
ͼ2빲ԾʽˮĴ
빲ĺǸFUԴĴеκһĴ,ֻдڱܲľֲĴ.,ӲӶȽСЧ֧ŻԼFUͨ.
ԾĺǼĴеһĴκһĴֱӴ.ʹˮĴֻˮдݵĹ.Ϊ˽ѭִʱĶ,FUݴṩ֧.
3 Ĵ
Ĵ֮,ݱںλõĲͬ,ѵļĴΪ3ࣨ˵üĴ3ַ䷽ʽ
1 Ĵ.ڴųСڵѭIIı.ѭִйв䣻СڵIIı,ӦĴݲᱻһѭݳ.,Ƿ1Ĵ.䷽кܶ1,Ĳ.
2 ˮĴ.ڴIIҾ1ѭεı.
ĳFUһˮ,ΪñǰļĴ,ΪˮĴ.ˮĴͬһ߼,ȴжĴ.ĴĸˮĴĳ.
ˮĴΪRi,jRi,j+1...Ri,j+l-1,l䳤.涨ˮĴ3ֿò. д.ֻ1ĴRi,jд,Ri,jΪβĴ. .ԴRi,j,Ri,j+1,...,Ri,j+l-1еκһ. ˮ.Ri,j+k=Ri,j+k-1,k=l-1,l-2,...,1,Ҳǰһ,ͷRi,j+l-1ݽ.
3 Ĵ.ڳ1ѭεı.
Щѭ,ڲѭõıڲѭ,ѭõı.Ƕѭˮ.
4 ˮĴķ
ͨˮ㷨,ڲѭǲе,Ҫڲѭд.ILSP,ѭǲе,²ͬѭڲѭҲ,,ҪѭĶдأͬѭڲѭ֮أ.ˮĴķ䷽ʽ,ʵͨӲмĴЩ.ˮĴֻھһѭεı,,ֻԵѭΪýԴ⵽ڵĸѭ.
4.1ص
ˮ,IIб,ܱ֤ѭ嶨ıֵᱻһѭͬһֵ.
ָһʱ̼ȥĶʱ.һָж,һָõı,ڲһ,Ϊ0.
ͼ3aвִʱΪ1.ڱT1,T2,T3ڷֱΪ1,0,0,ˮõĽII=2.T1ԼII.
Ϊ˼СII,ͼ3dʾ,Դвs1:T1䣽T1,ͼͼ3(e).ʱ,бT1,T1,T2,T3Ϊ0,һã,ˮII=1,Чһ.
ΪT1T1ĳFUֲˮϵڼĴ,ô,s1:T1䣽T1ˮ.Աͼ3(b)ͼ3(e),Կs2s0дر.
4.2ˮĴĳ
ˮĴĳΪl,
l=۱/II+1
1
IIָֻдص,ˮ.
ͨԴедضõ.д(OPiOPj,d),dΪiteration difference or iteration distance,ʾXĲOPiĳAֵ,X+dĲOPjAãдȷAΪ
tj+d*II-ti-delay(OPi)
2
titjֱʾOPiOPjͬһѭеʱ,delay(OPi)ָOPiִʱ.гAйصд,ֱ,ȡ,ΪA.

Fig.3Eliminating anti-dependency
ͼ3д
ͼ3еıT1Ϊ.ֻдص,ˮIIΪ1.Դͼ3aʾедأs0s1,0,s0s2,0,ݹʽ(2),T1ڷֱΪ0,1.ȡ,T1Ϊ1,T1,ٸ1,ͻᱻĵ.ɹʽ(1),ӦT1ˮĴΪ1/1+1=2.
T1iʾI=iʱs0T1ĸֵ,ˮĴΪRy,zRy,z+1,I=1ʱ,T11дRy,zͼ4aʾ.I=2ʱ,ִˮ,T11һĴRy,z+1,ٽT12дRy,zͼ4bʾ.ͬ,I=3ʱ,ִˮ,T12һĴRy,z+1,ٽT13дRy,z,ע⣬ʱT11Ѿ,Աˣͼ4cʾ.

Fig.4The effect of a pipeline register
ͼ4ˮĴ
,ڱδǰ,ˮĴһֱ,ֱڽ.
4.3ˮĴѰַ
һ,Դ,ڱAд(OPiOPj,d),ˮĴβĴΪRy,z,OPiʵļĴΪRy,zOPjʵļĴΪRy,z+k,

3
ti,tjOPi,OPjͬһѭеʱ̣delay(OPi)OPiִʱ.
ɴʱ,ÿԱиֵĲ֮Ҫˮ.
,ͼ3еıT1,Դͼ3aʾедأs0s1,0ȷs0еT1ӦʵļĴΪRy,zs1еT1ӦʵļĴҲǣɣs0s2,0ȷs2еT1ӦʵļĴΪ.ˮĵȼ۳ͼ5aʾ,ɴͼ5bʾ.ͼ3 ͼ4ͼ5,ȷԲѷ.

Fig.5Pipelined register addressing and code geneation
ͼ5ˮĴ˳Ѱַ
5 Ĵķ
ILSPһ̰㷨.ֻҪڲѭظģʽûг,ͻһѭ.,ڿѭ,,ñڵڼѭйأڸֵܳ˯.
ͼ6ʾ,Aһѭ.I=1,2,3ʱ,AΪ2.Ҳ˵,Aڸֵ,ٹ2,ͻᱻһ.I=4,5ʱ,Aڱòȷ.ͼԲȦI=4,5ʱеĲ.I=4Ϊ,ѭִֻ˲s0,s1֮,ͱֹͣ,Ϊʱڲѭظģʽ,潫תڲѭˮרִI=1,2,3ʱڲѭ.ڴ˹,I=4ʱǸA,˯״̬.ֱI=1,2,3ڲѭһXYʱ,ܼI=4ʱ.ʱ,I=4ʱǸAѹ,õ.

Fig.6Nondeterministec sleeping period of a variable
ͼ6Ĳ˯
ڲһWHILEѭ,.,ȷAʱ.,I=4ʱ,Aǲȷ.
ΪAˮĴĻ,ʽ(1),ҪȵõA.ǿɱ,ȷ.ʱ,޷ˮĴĳ.Ϊһ,ҪΪAĴ.
5.1Ĵķ䡢Ѱַ
ʵ,ѭĿ.,ɱصؼٶȫֵ,ΪĴ,Խ.
һѭA,ΪAһĴRf(i),z,Rf(i+1),z,...,Rf(i+e-1),z.eǼĴ,Ҳͬʱ򿪵ѭĸ亯f(k)ָkѭеAӦļĴĵ1±ꣻzǵ2±.fһӲ.
eʽȷ

4
ѭָѭвĸ,ڲǶѭĲΪILSP㷨ĳһѭڲвһĲ,ǷǶѭ.ͼ6ʾ,FORѭ5s0,s1,s2,s3,s4ڲWHILEѭ3s2,s3,s4,,Ϊ5.

ĴΪ5,˵,ͬʱ5ѭ.
ĴѰַʮּ򵥣ˮͼ6bʾебAһͳһġ١Ĵ,R1,漴.Ĵֻһ±,ԳΪ١Ĵ.ʵ,Rf(k),1,kѭ,һƼĴΪѭƼĴ飩ٱ.Ҳ˵,ÿѭĲ֪Լĸ.,ȻѭĴͬ,,Ӳӳ,I=1,2,3,4,5ʱ,Aֱӳ䵽˲ͬļĴRf(1),1,Rf(2),1,Rf(3),1,Rf(4),1,Rf(5),1.庯fΪf(1)=0,f(2)=1,f(3)=2,f(4)=4,f(5)=3,Aֱӳ䵽R0,1,R1,1,R2,1,R4,1,R3,1.
,ͼ6b,ͬIѭеAӳ䵽ͬļĴ.һIѭǰ,һӳ.ҪǱڻᷢȷ,ȫȷȥ,ΪͬѭAụา.ʵ,Ĵ鷽ʽ÷һ鵥ĴķʵּĴ.Ϊͳһ,ʹ˼ټĴӳ.
5.2ĴˮĴıȽ
ĴˮĴ߼϶һĴ,ȴĴ.Ĵͨ÷,ԴˮĴĹ.,ҪӲֵ亯f(k),ԼѭƼĴѭ.ӲѭƼĴ鶼Ҫ̬.
ˮĴԼ򵥡Ȼд,ҪӲ֧.ڱȷ.
5.3ӲӳILSPĿ
ILSPĿƻҪһѭƼĴ顢һϵͳضջˮѭװſտڲѭĶ.ѭ֮ǰ,ɱӲṩЩϢ,һѭ,ӲÿϢԶѭִ,ͬ.,ѭʱ䣬˵.
ӳͼ7ʾ.VLIWnܲ,ô,ͬʱִеѭĸn.,ӳĳȶΪn.һ,nȡ32Ѿ㹻.ӼټĴĴַӳһ򵥵Ĳ,ͼ7ʾ.

Fig.7The hardware mapping table and the loop control register file
ͼ7ӲӳͿƼĴ
6 Ծ
ILSP㷨£ġҪĴеĴܽݴ,ͳˮĴ,ھֲˮд.
ͼ6ʾ,3ѭI=1,2,3ڲwhileѭͬʱִ.I=1ʱǸwhileѭΪXYֹͣ,ô,I=1ʱѭѾ.ʱ,ע⵽I=4Ǹѭִֻs0s1,ڲwhileѭδִ.,ӦڲѭĹܲ,ִ.,s0ıAλһܲľֲĴ,¶A,ΪǵļĴдֲ.,뽫AǸܲľֲĴĹܲһֲĴ,Ծ.òڶʱ.
Ծּ֧ĴĿݴ.ͬʱ,ѭƼĴе,ʹѭ.
Ծɶ,£(1) ڶǸʱڵĩβ,ź,ʹFUʱж,ȴڣ(2) ݴǴRu,vRx,y,ô,֪ͨFUxȽRu,vֵ,ȻдRx,yע⵽ĴǶȫ,дֲģ(3) ѭƼĴĲ,FUת״̬.Ϲ̹ռ.
7 ʵ
һָϵṹ,Żϵṹģϵͳ.ĴѵĴСΪ3299FU,ÿFU32ֲĴ.ֱ𰴣1 ȫֹĴѣĴ䷽ʽILSP㷨2ͬʱԵĴˮĴͼĴ䷽ʽILSP㷨.ͨʵһЩ͵Ķѭ,õһЩҪ,ѡ1.
Table 1Partial experimental results
1ʵ

ProgramTotal loop levelsNumber of the
operations in the
outer loopNumber of the
operations in the
inner loopCyclesCyclesCyclesSpeedup
Inner product
(100100)2231433 7308 0312004.20
Fibonacci sequence
(100100)328101 152 685338 0312003.4
Matrix sum
(100100)2231734 4408 2992004.15
Matrix mulplification10
(100100)332142 339 478649 8552003.60
Fandemon matrix11
(100100)2321616 9367 2472004.38
Flower12
(11000)336172 196835462.63

˵:(1)  ȫֹĴʽСԾʱʱ
(Cycles using a global shared regiser file and without the leaping operation);
(2)  3ּĴ䷽ʽСԾʱʱ
(Cycles using the three register allocation styles and with the leaping operation);
(3)  ԾͶ̬ռʱ
(Cycles used by leaping operations and dynamic refreshing).
ٳ,ѭ,,ڲ,ʱ,޼ٱ,
ڻ,Შ,ӷ,˷,ɾ,ˮɻ.
ӱпԿ,ð빲ԾʽˮĴ,ILSP㷨ļٱԼΪ3.29.Ҫԭǣ1 ӲˮĴͼĴ飩д,ԼĴʱʽݴԼ벻ͳһ鷳,ӶСѭʹ볤ȣ2 ԾӲṩʱĿݴԼһϵѭƼĴĸ,ʹ迼Ƕ.,Ҷ벹֮νٶȺܿ.
עÿִһѭҪһԾͶ̬,ÿռ2,ѭ2.
8 빲ԾʽˮĴѺȫֹĴѵıȽ
빲ԾʽˮĴǶȫֹĴѵļ.
ܲĲ,ʹĴѵ֯ΪһҪ.ȫֹĴ,ѵĿչԽܵ.ΪҪÿÿܲԼĴִеһд,˿ںд˿ڵĿܶ,ͶдٶȽܵӰ.
,ȫֹļĴѻΪԶĲ,չҪõö.ಿ,ÿֹģС.һÿֵļĴɶ,չԾͽһ.Ϊж೤,ĴĴٶǲӰ,ǰ빲ԾʽˮĴҪݴͷʽ.
֮,빲ԾʽˮĴǶȫֹĴѽл,֯Ϊ.ڱİ,ʵݴȡֲ,ٸ֮ݴ.
ԾӲӳȷʵӲӶ.,ּ򵥵Ļ,ӶȺܵ.,Ƚ϶,빲ԾʽˮĴѵĸӶҪȫֹĴѵ͵ö࣬,Զѭȵ֧ҲҪã1.
9 
㽻ˮĴ,ҪͬκͿεļĴ⣬Լ.ĶЩ,˾ձļĴṹͷ䷽.ӹ̵ʵʽ,ЩʮЧ.
оõȻѧ(No.69773028).ݺ첨,1972,ʿ,ҪоΪб,ϵṹ.־,1946 ,ڣʿʦ,ҪоΪ㷨б뼼,ϵṹ.
ͨѶϵ:ݺ첨,100084,廪ѧѧ뼼ϵ
ߵλݺ첨(廪ѧѧ뼼ϵ100084)
־(廪ѧѧ뼼ϵ100084)
ο
1Yu T,Tang Z Z,Zhang C H et al.Control mechanism for software pipelining on nested loop.In:Regina S S ed.Proceedings of the Conference on Advances in Parallel and Distributed Computing.Los Alamitos:IEEE Computer Society Press,1997.345350
2Luo Jun,Tang Zhi-zhong,Zhang Chi-hong et al.Algorithm to data allocation in software pipelining.Journal of Software,1998,9(1):7479)
(޾,־,ų.ˮеһݷ㷨.ѧ,1998,9(1):7479)
3Rau B R,Fisher J A.Instruction-level parallel processing:History,overview and perspctive.Journal of Supercomputing,1993,7(1/2):950
4Hwang K.Advanced Computer Architecture:Parallelism,Salability,Programmability.New York:McGraw-Hill,1993.457496
5Lam M.Software pipelining:an efficient scheduling technique for VLIW architectures.SIGPLAN Notices,1988,23(7):318328
6Duesterwald E,Gupta R,Soffa M L.Register pipelining:an integrated approach to register allocation for scalar and subscripted variables.In:Kastens U,Pfahler P eds.Proceedings of the Compiler Construction:4th International Conference CC'92.New York:Springer-Verlag,1992.192206
7Hoogerbrugge J,Corporaal H.Register file port requirements of transport triggered architectures.Professional Engineering,1994,7(21):191195
8Tang Zhi-zhong,Wang Lei,Qian Jiang.Software pipelining on program with complicated loops.Journal of Software,1996,7(7):422427
(־,,Ǯ.ѭˮ.ѧ,1996,7(7):422427)
9NewBurn C J,Huang A S,Shen J P et al.Balancing fine-and medium-grained parallelism in scheduling loops for the XIMD architecture.Architectures and Compilation Techniques for Fine and Medium Grain Parallelism (A-23).North Holland:Elsevier Science Publishers,1993.3952
10Su B G,Wang J,Tang Z Z et al.URPR-1:a single-chip vliw architecture.Microprocessing and Microprogramming,1993,39(1):2541
11Wen Yu-hong.The research and design of VLIW optimizing compiler based on GURPR global software pipelining algorithm M S.Thesis.Tsinghua University,1991
(ں.GURPR*ȫˮ㷨VLIWŻоƣ˶ʿѧλģ.廪ѧ,1991)
1998-12-31յԭ,1999-04-02յ޸ĸ
