ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



ʱָ巽ļٱȷ
  ־ ų ղ
ժҪ Ӳϵʱָ巽SHRTD(software/hardware run-time disambiguation)ڲ,ͬʱ,Ĵռܵ,صĴ.ϸSHRTDָмٱ,˷ַͻĲмٱƽмٱԼַͻʲмٱ.ۼٱȶָб뼼оҪʵ.
ؼ ָ,ָ,ָ,,ٱ.
ͼ TP302
Analyzing Speedups of a Run-Time Pointer Aliasing Disambiguation Method
QIAO Lin1 TANG Zhi-zhong1 ZHANG Chi-hong1 SU Bo-gong2
1(Department of Computer Science and Technology Tsinghua University Beijing 100084)
2(Department of Computer Science William Paterson University USA)
Abstract A new run-time pointer aliasing disambiguation method, SHRTD, combined with software and hardware techniques, can be used for irreversible code and has very limited compensation code space and no serious rerollability problem. In this paper, instruction-level parallel speedups of the SHRTD method are analyzed in detail. Speedups and mean speedups where address conflicts occurred and speedups where address conflicts will occur according to their probabilities are given. Three theoretical speedups introduced in this paper are very useful for studying and evaluating instruction-level parallel compiling techniques.
Key words Instruction-level parallelism, very-long instruction word, pointer aliasing, ambiguous dependence, speedup.
ǰĳָ(very-long instruction word,VLIW)þ̬Ⱥˮķָ(instruction-level parallelism,ILP)[1].ַľǴڴʵ(ambiguous dependence).ʹܹ龲̬,Ҳܹܺõشָ(pointer aliasing).ΪָԻøߵָдٱ,[2]ʱ(run-time disambiguation,RTD)ķ,ʱ(run-time check)ʱ(run-time compensation).ַӦˮʱ,ʱȻȷڴ,ֻʺЩ[2];ʱ鷽Ȼκδ,ڴ(rerollability).ַͬȱǴصĴռ,ȫˮпܵ¾޴Ĳռ俪.
,[3]һֻӲϵʱ鷽SHRTD(software/hardware run-time disambiguation).SHRTDĻ˼:(1) ڼ⵽ڴַͻʱ,ΪӳٲȷLOAD̲,ܵԪLOAD֮ǰNOP;(2) Ϊ֤ӳٲִ˳һ,ʱȷִNOPйܵԪ˳NOPĿ.
SHRTD3:(1) Ϊʱ鷽ûд,رʺκβ;(2) ΪκSHRTDֻҪһSHRTDָ,Ĵռ䲢;(3) ڴ.Ȼ,ĶSHRTDķ,ֻԾӸ˷,ûв۷.[3]Ļ϶SHRTDչо,SHRTD۷,ó˷ַͻʲмٱȺͷַͻĲмٱƽмٱȵֵ.ĵĽָб뼼оҪʵ.
1SHRTD
SHRTD:(1) еĲֻռһʱ;(2) еPEһһڴƬ,ÿPEֻ1ڴԪ1ڴдԪ4ѭƵԪ.
1.1 Ӳṹ
һָмϵͳҪóϵṹĵͲVLIWϵṹ8Ԫ(PE)Ķദ󲿷.ÿPE11ܵԪ,2ALU2˷2ڴʶ˿ں4ѭƵԪ.VLIWܹһʱд42ڴʲ4֧.SHRTDӲֻ֧:(1) ָ洢һСΪDWĴ洢ӳٲָ,WVLIWָĿ,D=dmax+1,,dmaxǴгеֵ;(2) һָָ洢ѡĶ·ѡMUX,MUXĿVLIWֵָĲĿ;(3)SHRTDָSHRTD WORDֻĴ.
1.2 ضͶ
ضͶ,йض֤[3].
1(ž). op1op2ǳѰŵ,ԭʼдвop1ڲop2֮ǰ.ź֮VLIWĿΪN,İž
 (1)
2(벹). op1op2ֱǳѰŵSTORELOAD,ǵİžd(op1,op2)<0.⵽ַͻʱ벹һЩղӳٲȷLOAD̲,ǳЩĿղĿΪ벹(code compensation measure).
1. op1op2ڲͬڴ˿,ӦĴ벹=|d(op1,op2)|+1.
һѭ,еÿһڲͬĵ϶һλ,ͬһڲͬϵİλǲͬ.,Ƕڰž䰲žĸ,ڲͬϵľ尲Ϣ.
3(ڰž䰲ž). һΪnѭеĲop1op2,op1(k)op2(j)ֱʾop1op2ĵkκ͵jε,1j n,1 k n.j k,ưžd(op1(k),op2(j))Ϊ䰲ž;j= k,ưžd(op1(k),op2(j))Ϊڰž.ǵop1op2ѭ岻ͬڰžͬ,ʿɽڰžΪdinn(op1,op2).
ѭˮ㷨ѭǰȷѭI,ѭĵ1֮䰲ž.һȷѭI,¶.
2. ѭI.op1(k)op2(j)ֱѭѰŵLOADSTORE,ǵڰžΪdinn(op1,op2),䰲žd(op1(k),op2(j))< 0,j< k.op1(k)op2(j)ڲͬڴ˿,һεҪSHRTD.
3. ѭI.op1(k)op2(j)ֱѭѰŵLOADSTORE,SHRTD⵽ַͻʱ,ӦĴ벹
|d(op1(k),op2(j))|+1=dinn(op1,op2)-(k-j)I+1. (2)
2SHRTDĲмٱȷ
ڴSHRTDĲмٱ.Ϊ벢ִʱвȷ,ҪȷطմĸӶȺʹռСǷǳѵ,,ʹøSHRTDĲмٱ.
4. ѭΪI=1,ѭĴдܳΪl,ѭΪn.op1op2ֱѭѰŵLOADSTORE,䰲ždinn(op1,op2)d,ĳηjdΪd, jd- 1Ϊd- 1,, j1Ϊ1ĵַͻĲгٱ
. (3)
һεĹ,һεַͻƽ벹
, (4)
mεַͻƽмٱ
. (5)
֤:ɶ3֪,ΪxĵַͻʱĴ벹x=d-x+1,1xd,ĳηjdΪd, jd- 1Ϊd- 1,, j1Ϊ1ĵַͻ,ܵĴ벹.ִиóʱ,ܵʱΪln,ִʱװſս׶ηֱҪl-1ʱ,ûм⵽ַͻʱ,ˮ׶Ҫn-2ʱ.ʱ⵽ַͻ,ܵĲִΪ 
,
ʱĲгٱ
.
һεĹ,һεַͻƽ벹
,
mεַͻƽмٱ
. 
1:ĳѭĳl=6,LOADSTOREİžd=3.һεַͻƽ벹,mεַͻƽ벹.
j10,j2=0,j3=0ʱ,κεַͻ,ѭĲмٱȵnʱļ;j1n,j2=0,j3=0ʱ,ȫַͻΪ1,ٱȵnʱļ;j10,j2=n,j3=0ʱ,ȫַͻΪ2,ٱȵnʱļ;j10,j2=0,j3=nʱ,ȫַͻΪ3,ٱȵnʱļ.Щ[3]ķһ.
5. ڲַͬͻĸ¼໥,ͬһεϲͬĵַͻĸ¼,һѭзΪdĵַͻΪpd,Ϊd- 1ĵַͻΪpd- 1,,Ϊ1ĵַͻΪp1,ͬ4,mεַͻĴ벹mĸʵĺ,
 (6)
 
 (7)
ʱĲмٱΪ
 (8)
֤:ע⵽ĳjdΪd, jd- 1Ϊd- 1,, j1Ϊ1ĵַͻĸΪ
 (9)
mεַͻĸ
 (10)
mεַͻĴ벹

p(m)Ȼmĸʵĺ.,mεַͻĲмٱΪ
. 
ͬĵַͻʱ,ĲмٱȲͬ.ΪڳִǰƲмٱȵһֶ,ʵĲмٱSp(m)ζſõĲмٱ,ǺSHRTDЧԵҪ.2ʾ˶4Ͷ5֮Ĺϵ.
2:ʹ1Ĳ.ݶ5,mεַͻʱƽ벹

һεвͬĵַͻΪȸ¼,p=q=r,
,
 

ͬʹö4õĽԼ[3]ķһ.
1.
 (11)
֤:,

6. ͬ5,ַͻƽ벹
 (12)
ַͻƽмٱ
. (13)
ַͻƽмٱȵnʱ
 (14)
֤:ǵPmʵǿַܷܲͻһnBernoulliʵ,,
.
Ӷַͻܴ벹

1,ַͻƽ벹

ַͻƽмٱΪ.ַͻƽмٱȵnʱ. 
˽й,ǺSHRTDƽܵҪ.ַͻΪ0ʱ,ֵȻΪl.
3 
[3]SHRTDӲϵʱָ巽SHRTD,ڲ,ͬʱ,Ĵռ,صĴ.
ڴ˻϶SHRTDչо,ϸSHRTDָмٱ,۷.ĵõķַͻʲмٱȺͷַͻĲмٱƽмٱȵֵָб뼼оҪʵ.
עͣоõȻѧ
߼飺֣1972ʿҪоΪб뼼Petriг
ʽ
־ң1946ڣҪоΪϵṹ㷨б
뼼
ų죺1964ڣҪоΪ㷨б뼼
ղ1938ڣʿʦҪоΪˮ㷨б뼼

ߵλ֡־ҡų:廪ѧѧ뼼ϵ  100084
ղWilliam Patersonѧѧϵ 
ο
1Rau B R, Fisher A. Instruction-level parallel processing: history, overview, and 
perspective. 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־,,ų.һʱָ·.ѧ,1999,10
(7):685~689
(Tang Zhi-zhong, Qiao Lin, Zhang Chi-hong et al. A new run-time pointer aliasing
disambiguation method. Journal of Software, 1999,10(7):685689)
ոڣ1998-06-22޸ڣ1998-11-06
