ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



һʱָ·
־ҡ ֡ų졡ղ
ժҪһֲӲϵʱָ·SHRTDsoftware/hardware run-time disambiguation.Ϊӳʱȷڴʼ̲,SHRTDĹܵԪִNOP.Ϊ֤ӳٲִ˳һ,ʱȷִNOPйܵԪ˳NOPĿ.SHRTDڲ,ͬʱĴռ,ҲصĴ.·Чؽָ,ΪǱڵָмṩ˿.
ؼʡָ,ָ,ָ,ʱ,ʱ.
ͼšTP338
A New Run-Time Pointer Aliasing Disambiguation Method
TANG Zhi-zhong1 QIAO Lin1 ZHANG Chi-hong1 SU Bo-gong2
1(Department of Computer Science and TechnologyTsinghua UniversityBeijing100084)
2(Department of Computer ScienceWilliam Paterson UniversityUSA)
AbstractIn this paper, a new run-time pointer aliasing disambiguation method, called SHRTD (software/hardware run-time disambiguation), which combines hardware and software techniques is presented. During run time, the SHRTD method lets function units execute NOPs to implement the postponement of the incorrect memory load operation and its successive operations. To guarantee the consistency of the execution sequence of all postponed operations, the order of function units which executes NOPs and the number of NOPs must be determined during compiler time. The SHRTD can be used for irreversible code, and it has very limited compensation code space and no serious rerollability problem. The SHRTD method solves pointer aliasing problem efficiently and makes it possible to obtain potential instruction-level parallel speedup.
Key wordsInstruction-level parallelism, very-long instruction word, pointer aliasing, run-time checking, run-time compensation.
ǰĳָ֣very-long instruction word,VLIWþ̬Ⱥˮķָԣinstruction-level parallelism,ILP1.ַľǴڴʵԣambiguous dependence,ʹܹ龲̬,Ҳܹܺõشָpointer aliasing.Ϊ˽ָ,ԻøߵǱָд,ף2ʱԣrun-time disambiguation,RTDķʱ飨run-time checkʱrun-time compensation.ַӦˮʱ,ʱȻȷڴ,ֻʺЩ2.ʱ鷽Ȼκδ,ڴԣrerollability.ַͬȱǴصĴռ,ȫˮпܵ¾޴Ĳռ俪.
һµĻӲϵʱ鷽SHRTD.SHRTDĻ˼ǣ1Ϊӳʱȷڴʼ̲,ܵԪִNOPִв룻2Ϊ֤ӳٲִ˳һ,ʱȷִNOPйܵԪ˳NOPĿ.
1 SHRTDӲṹ
һָмϵͳҪ󲿷ɣóϵṹĵͲVLIWϵṹ8ԪPEĶദ.ͼ1һ򻯵PEϵṹSHRTDӲֻ֧.ϵṹ7ܵԪ2ALU2˷2ڴʶ˿ں1֧ѭƵԪBRLC.VLIWܹ1ʱд42ڴʲ4֧.SHRTDӲָֻ֧洢һ洢ӳٲָһָָ洢ѡĶ·ѡϺһSHRTD WORDֻ洢Ŀָ.

ͼ1PEϵṹ
2ض붨
ļ裺еĲֻռ1ʱڣеPEһһڴƬÿPEֻһڴڴдBRLCԪ,ÿBRLCԪͬʱ4֧.
1(). op1op2ǳе,֮ĲĿ1ΪĲ,Ϊdis(op1, op2).
2(ž). op1op2ǳѰŵ,ԭʼдвop1ڲop2֮ǰ.ź֮VLIWĿΪN,İž

3벹. op1op2ֱǳѰŵSTORELOAD,ǵİžd(op1,op2)0.⵽ַͻʱ벹һЩղӳٲȷLOAD̲,ǳЩĿղĿΪ벹code compensation measure.
Ȼ,op1op2ڲͬڴ˿,ӦĴ벹=|d(op1,op2)|+1.
4ڰž䰲ž룩. һΪnѭеĲop1op2,op(k)1op(j)2ֱʾop1op2ĵkκ͵jε,1jn,1kn.jk,ưžd(op(k)1,op(j)2)Ϊ䰲ž룻j=k,ưžd(op(k)1,op(j)2)Ϊڰž.ǵop1op2ѭ岻ͬڰžͬ,ʿɽڰžΪdinn(op1,op2).
ѭˮ㷨ѭǰȷѭII,ѭĵ1֮䰲ž.һȷѭII,¶.
1. ѭII.op(k)1op(j)2ֱѭѰŵLOADSTORE,ǵڰžΪdinn(op1,op2),䰲žd(op(k)1,op(j)2)<0,j<k.op(k)1op(j)2ڲͬڴ˿,һεҪSHRTDp=.
֤ΪгÿIIһѭ,ڲop(j)1op(j)2֮乲˴ѭ.ע⵽ʱѭ,ӶֻҪЩѭĲop(k)1֮ǰӦSHRTD,жϲop(k)1op(j)2j+1kj+ǷԼ,p=ΪһεҪSHRTDĿ.
2. ѭII.op(k)1op(j)2ֱѭѰŵLOADSTORE,SHRTD⵽ַͻʱ,ӦĴ벹
=d(op(k)1,op(j)2)+1=dinn(op1,op2)-(k-j)II+1.
֤ΪԴԵop(k)1op(j)2,=d(op(k)1,op(j)2)+1Ϊ벹.op(j)1Ϊt,op(j)2Ϊt+dinn(op1,op2),op(k)1Ϊt+(k-j)II,ʲop(k)1op(j)2䰲ž
d(op(k)1,op(j)2)=(t+(k-j)II)-(t+dinn(op1,op2))=(k-j)II-dinn(op1,op2).
Ȼop(k)1op(j)2֮ǰ,ȻǸֵ.SHRTD⵽ʱ,op(k)1Ѿǰִ|(k-j)II-dinn(op1,op2)|ʱ,ȡop(j)2ִǰ.Ϊ֤ȷִ,op(k)1֮ǰ(k-j)II-dinn(op1,op2)+1ղ,ӶӦĴ벹=d(op(k)1,op(j)2)+1=dinn(op1,op2)-(k-j)II+1.
3SHRTDԭ
1ͱ2˵ˮʹSHRTD,ԭʼĳͼ2ʾ,RTD֮ĳͼ3ʾ.1޵ַͻˮ,źָŵϱűʾòĴε.
1ѭʵ޵ַͻʱˮ
CLKALU1ALU2MUL1MUL2MEM1MEM2BRLC0BRLC1BRLC2
1op(1)1
2op(2)1op(1)5SHRTD(op(2)5,op(1)8)
3op(1)6op(3)1op(2)5SHRTD(op(3)5,op(1)8)SHRTD(op(3)5,op(2)8)
4op(2)6op(1)7op(4)1op(3)5SHRTD(op(4)5,op(1)8)SHRTD(op(4)5,op(2)8)SHRTD(op(4)5,op(3)8)
5op(3)6op(2)7op(5)1op(4)5op(1)8SHRTD(op(5)5,op(2)8)SHRTD(op(5)5,op(3)8)SHRTD(op(5)5,op(4)8)
6op(4)6op(3)7op(6)1op(1)9op(5)5op(2)8SHRTD(op(6)5,op(3)8)SHRTD(op(6)5,op(4)8)SHRTD(op(6)5,op(5)8)
7op(5)6op(4)7op(7)1op(2)9op(6)5op(3)8SHRTD(op(7)5,op(4)8)SHRTD(op(7)5,op(5)8)SHRTD(op(7)5,op(6)8)
8op(6)6op(5)7op(8)1op(3)9op(7)5op(4)8SHRTD(op(8)5,op(5)8)SHRTD(op(8)5,op(6)8)SHRTD(op(8)5,op(7)8)
9op(7)6op(6)7op(9)1op(4)9op(8)5op(5)8SHRTD(op(9)5,op(6)8)SHRTD(op(9)5,op(7)8)SHRTD(op(9)5,op(8)8)


2ѭʵSHRTD(op(6)5,op(4)8)⵽op(6)5op(4)8ַͻ
CLKALU1ALU2MUL1MUL2MEM1MEM2BRLC0BRLC1BRLC2
6op(4)6op(3)7op(6)1op(1)9op(5)5op(2)8SHRTD(op(6)5,op(3)8)SHRTD(op(6)5,op(4)8)SHRTD(op(6)5,op(5)8)
7op(5)6op(4)7NOPop(2)9NOPop(3)8SHRTD(op(7)5,op(4)8)SHRTD(op(7)5,op(5)8)SHRTD(op(7)5,op(6)8)
8NOPop(5)7NOPop(3)9NOPop(4)8SHRTD(op(8)5,op(5)8)SHRTD(op(8)5,op(6)8)SHRTD(op(8)5,op(7)8)
9NOPNOPop(7)1NOPop(6)5NOP NOP NOP NOP
10op(6)6NOPop(8)1NOPop(7)5NOP NOP NOP NOP
11op(7)6op(6)7op(9)1op(4)9op(8)5op(5)8SHRTD(op(9)5,op(6)8)SHRTD(op(9)5,op(7)8)SHRTD(op(9)5,op(8)8)


ͼ2ԭʼѭ롡ͼ3SHRTDĴ
ʱ1ʱ5ѭװ׶Σʱ6֮ѭˮ׶.ѭˮ׶,ÿVLIWָʵִе6ѭ,иڲͬѭ,һѭֻҪһʱ.ѭԶԶѭڵĲʱ,ѭװſչ̿ԺԲ,Ӷ޵ַͻʱ,ĲмٱԼΪ6.
ΪѭII=1,dinn(op5,op8)=3,ӶҪSHRTDp=3.ЩSHRTDֱжϽŵLOADǷǰ3εSTOREѭڴַͻ,ǷΪ1,23.SHRTD(op(6)5,op(4)8)⵽op(6)5op(4)8ַͻʱʱΪ6,һЩղ,ӦĴ벹=dinn(op1,op2)-(k-j)II+1=2.
ʱ,op(6)5op(4)8ѭΪ2,op(6)5op(4)8֮,2ʾ.Ϊ䰲žd(op(6)5,op(4)8)=-1,ԹܵԪNOP,ЩNOPӳ˵6εLOADִ̲.ʱڵӳ,ִ˳ʱ11ص״̬,̲κδԵ.
4SHRTDĲмٱȷ
3. ѭΪII=1,ѭĴдܳΪl=6,ѭΪnop1op2ֱѭѰŵLOADSTORE,䰲ždinn(op1,op2)=d=3,ĳηj3Ϊ3,j2Ϊ2,j1Ϊ1ĵַͻĲгٱ.mεַͻƽмٱ
֤ɶ2֪,ΪxĵַͻʱĴ벹x=d-x+1,1xd,ĳηj3Ϊ3,j2Ϊ2,j1Ϊ1ĵַͻ,ܵĴ벹=3j1+2j2+j3.
ִиóʱ,ܵʱΪ6n,ִʱװſս׶ηֱҪ5ʱ,ûм⵽ַͻʱ,ˮ׶Ҫn-2ʱ.ʱ⵽ַͻ,ܵĲִΪ(n-2)+25+(3j1+2j2+j3)=n+3j1+2j2+j3+8,ӶʱĲгٱһεĹ,һεַͻƽ벹(3+2+1)=2,Ӷmεַͻƽмٱȡ
j1=0,j2=0,j3=0ʱ,κεַͻ,ٱȵnʱļS=6j1=n,j2=0,j3=0ʱ,ȫַͻΪ1,S=1.5j1=0,j2=n,j3=0ʱ,ȫַͻΪ2,S=2j1=0,j2=0,j3=nʱ,ȫַͻΪ3,S=3.ǵԡѭڵвǲɲе,ļٱȻ.
ʹͬķԷ⵽ַͻʱָˮ.
5  
ӱ,SHRTDЧؽָ,ʹʵֵʱͬЧ.SHRTDڴ滺Ӳ֧Ϲ,ԼӿַȽϵٶ.
SHRTD3ƣ(1) Ϊʱ鷽ûд,رʺκβ룻(2) ΪκSHRTDֻҪһSHRTDָ,Ĵռ䲢(3) ڴ.
SHRTDҪرӲ֧֣(1) һСΪDWָ,WVLIWָĿ,Ddmax+1,,dmaxǴгеֵ(2) һ·ѡMUX,MUXĿVLIWֵָĲĿ(3) SHRTDָSHRTD WORDĴ.
оؿδǶѭˮȫ3ʹSHRTD.
оõȻѧ.־,1946,,ʿʦ,ҪоΪϵṹ,㷨,б뼼.,1972,ʿ,ҪоΪб뼼,Petri,гʽ.ų,1964,,ҪоΪ㷨,б뼼.ղ,1938,,ҪоΪˮ㷨,б뼼.
ͨѶϵ:־,100084,廪ѧѧ뼼ϵ
ߵλ־ҡ ֡ų(廪ѧѧ뼼ϵ  100084)ղ(William Patersonѧѧϵ)
ο
1Rau B R,Fisher A.Instruction-level parallel processing:history,overview, and perspective. The Journal of Supercomputing, 1993,7(1):950
2Nicolau A.Run-Time disambiguation: coping with statically unpredictable dependencies. IEEE Transactions on Computers, 1989,38(5):663678
3־,ų,.ˮȫһˮµԷ.ѧ,1998,21():201206
(Tang Zhi-zhong, Zhang Chi-hong, Qiao Lin. Pipelining safe methoda new way to support data dependence analysis for software pipelining. Chinese Journal of Computers, 1998,21(supplement):201206)
1998-05-11յԭ 
1998-09-01յ޸ĸ
