指令安腾处理器

计算机研究与发展!
""#$%%%&$'()!
*#$$&$+++!
,-.
/01234/5*/670891:9;9319@94/76928AA('):(BB"(C%,'%%+收稿日期:'%%BD%ED$B;修回日期:'%%CD%CD$'基金项目:国家"八六三"高技术研究发展计划软件重大专项基金项目('%%AFF$G''%%)非线性规律访存操作的数据预取技术吴佳骏$,'冯晓兵$张兆庆$$(中国科学院计算技术研究所北京$%%%E%)'(中国科学院研究生院北京$%%%A))(HII#JG=32NG=3/QJ2N$$(!
"#$%$&$'()*(+,&$%"-.
'/0"(1(-2,*0%"'#'3/45'+2()6/%'"/'#,7'%8%"-$%%%E%)'(9:45&4$';"%4S3838=383192/24J29313KR08PS0;J2N71/5J4J2N898=92PS0;J2N8=9;971/5J4J2NJ25/1638J/2,8=99>8/3/2;81J>971/5J4J2N89;81J>9J89138J@9J;7085/1H31>,H=JI0;88=9>3837195983837195986383719598971/5J4J2N技术,提出了新的信息收集类型;81J>9J89138J@9,更精确地反映程序执行时访存指令的实际行为,并结合别名分析的结果调整对同一安腾处理器上加入了数据预取指令[/]#本文基于0,123-41562.
2+7技术,提出新的信息收集类型0,123-2,-18,29-,更精确地反映程序执行时访存指令的实际行为,使得程序整体性能提高了:#$;-行的数据预取,扩大了数据预取范围,使得程序整体性能提高!
#@-,"&/DE@路组相连的G"=8=>-,!
#&AE的!
"路组相连的G$=8=>-,!
HE内存,操作系统为I-3B8,G2+JKL398+=-3M-19-1"#!
#编译器是选用*L/F开放源码编译系统NI'[;]#我们使用基准测试程序M(O'":::进行了比较测试,M(O'":::是一组P51,18+和'的工业基准测试包,我们使用它的!
"个整数测试例子#!
"#相关工作编译器通过获取程序代码的循环信息进行数据预取操作的插入["],主要是依据循环变量下标来计算程序将要访问的地址然后对它进行预取#在编译器NI'的循环优化里就采用了这种传统的方式,静态分析循环插入数据预取指令#但是我们发现有些程序循环并不是依靠下标变量进行访存,例如M4-=":::里面的测试例子Q=6其中存在大量依靠指针链进行访存的循环,在安腾"上运行这个程序时发现它F#:"8"!
"/F系统上实现了基于41562.
-的0,123-41-6-,=>#文献[!
]在*+,-.
公司的安腾编译器上实现了41562.
2+7制导的0,123-41-6-,=>,并且得到了不错的性能提升,其中Q=6的加速比达到了!
#&#本文在文献[!
,@]基础上改进了基于41562.
2+7的数据预取技术,使得编译器性能得到进一步提高##$%&'()(*+信息指导下的数据预取#"!
,-%(.
/信息的收集"#!
#!
0,123-41562.
2+7插装优化编译器决定哪些.
583要去做插装时最简单高效的方法就是只对在.
554里面的.
583指令进行插装#当.
583指令都在同一个基本块时可以依据.
583指令地址信息将一部分.
583指令看成等价#其中分为两种情况:!
)对于.
583指令的地址只相差一个常数;")G583指令的地址变量存在别名关系#对于基本块内上述两种情况的.
583指令我们认为它们是等价的,因为它们的0,123-的距离都是相同的,可以只从一个.
583指令的0,123-信息得到块内其他.
583指令的0,123-数据#所以只需选择有代表性的.
583做41562.
2+7,这样就可以减少41562.
2+7的执行开销#"#!
#"0,123-信息分类对每一个做了41562.
2+7的.
583,程序运行时可获得它们的41562.
2+7信息#文献[!
]中统计了两种信息0,123-98.
J-和0,123-3266-1-+=-,但是我们在对收集的0,123-信息进行分析时发现0,123-3266-1-+=-不能满足数据预取指令插入的需要#因为0,123-3266-1-+=-只是进行连续两次0,123-98.
J-的比较,而插入预取指令通常提前一次以上的迭代,那么41562.
2+7收集的信息必须统计更大范围的0,123-98.
J-波动情况#为了收集这些信息我们提出了新的41562.
2+7信息类型0,123-2,-18,29-#0,123-98.
J-收集的是同一.
583指令的两次连续执行间地址的距离信息#0,123-2,-18,29-收集到的是连续0,123-98.
J-之间的差值为零的最长距离次数,通过这个数字我们可以看出大范围0,123-的波动情/&$计算机研究与发展"::;,FF(")况!
根据经验数据预取时迭代距离很少超过"#,所以我们设定统计的$%&'(%$)&最大距离为"#,如果*%'$+&)(,-&连续稳定次数超过"#,我们也把它统计在$%&'(%$)&为"#的计数器上!
依靠*%'$+&)(,-&和*%'$+&$%&'(%$)&两者结合,可以进一步确定*%'$+&序列是否适合做.
'&/&%01,因为光是简单的*%'$+&信息不够精确!
下面将用一个例子来展示这种情况!
图2中有两个*%'$+&序列!
和",这两个序列的地址步长统计信息都是一样的!
最高步长是3次数为4!
在!
序列中*%'$+&+$//&'&50&为零的次数是#占了所有*%'$+&+$//&'&50&的#67,而序列"中*%'$+&+$//&'&50&值零只占了367!
如果仅参考*%'$+&+$//&'&50&信息,编译器就有可能做出!
比"更适合预取的判断!
但是这个结论仅在迭代预取距离为"时有效,当迭代距离等于2时,!
序列只有"67的预取会命中,相反"序列可以达到867的命中率,而迭代预取距离大于2时!
的预取全部会失效!
编译器在遇见上面例子中情况时就可以通过收集到的*%'$+&$%&'(%$)&知道,如果!
位于小循环需要迭代距离大于2时并不适合做数据预取,而"可以适用于比!
更大变化范围的迭代预取!
9%'$+&*&:-&50&!
3,3,#,#,3,3,3,#,#,3,39%'$+&+$//&'&50&6,2,6,;2,6,6,2,6,;2,69%'$+&$%&'(%$)&",6,",6,",2,6,",6,"#$%["]+#('[2],+#('["]'(*>$-,,同时!
"#+5:+#('[+]!
#$#!
-&'()也必须大于'(*>$-,,这里的:是前面对,=(+指令计算的预取迭代次数!
第"个条件保证预取的开销小于0(01&C$**所造成的性能损失,第2个条件是要保证数据预取都是在连续有效的迭代中进行!
'(*>$-,5!
+6*#('+6*#'$('>(!
,!
@(@$'4-!
#(634,@(@$'4-!
#(6345/=17@+**$('>(!
,$/&+'*#,+*#!
63("A!
B(*+.
(,123!
3>(@+**$('>(!
,$/&+'*#,+*#!
63(#A!
B(*+.
($%&!
2)+E5(C$0*%'$+&(G9B),=(+:一个,=(+有多个出现频率比较高的非零*%'$+&(比如说至少有一个在267以上),并且迭代距离!
"#+5:+#('[+]!
#$#!
-&'()的比例也非常高(比如它占的概率至少要在467以上)!
这种情况下单一的静态数据预取就不能兼顾几种不同的数据预取距离,必须通过插入指令在程4>8吴佳骏等:非线性规律访存操作的数据预取技术序执行时动态地计算数据预取距离!
例如一个"#$%指令它的&'()%*值+,,-,,+.
.
有一个的出现概率都至少为+/0,并且!
1-!
"#!
$%&[!
]!
$'$()*&%+出现概率为2/0,那么我们就可以判定这个"#$%为%34$5)6&'()%*"#$%!
我们通常设定+.
0作为&'()%*值的标准,-.
$/&%0/')1,把7.
0作为!
1-!
"#!
$%&[!
]!
$'$()*&%+的标准,-.
!
$%&$/&%0/')1!
+!
+!
8对冗余数据预取的调整另外在做静态数据预取插入时要考虑的一个问题就是去掉多余的数据预取!
这里分两种情况!
第1种是本身每次预取距离都在一个6$69*行内的,对于这种情况就直接不对它进行预取!
另外一种是同一个基本块里面的"#$%,对于这些"#$%首先要找出步长变化的基本规律都相同的"#$%把它们放到一个集合内,判定的标准就是它们的距离是否为常量!
这里引入别名分析的结果来判定这些"#$%之间的地址距离大小,如果它们的距离小于一个6$69*行的大小,那么就对它的数据预取距离进行调整加大数据预取范围!
这样可以增加数据预取指令效率,提高数据6$69*的命中率!
具体算法如图8所示::);!
8(*=*'69%)&'$46*!
图8数据预取距离调节算法)=(2(3/%433%00-(5%6!
7%(')1'8,39&'8,1!
**)){!
!
@A%;*)='9*'B#"#$%)4&'(A6')#4&$66*&&'9*&$5*6$69*")4*5(:1!
0C')1'8!
1!
0"5(:1!
0')1'8!
1!
0:5(:1!
0;5!
71!
0C')1'8!
1!
0#5!
71!
0')1'8!
1!
0:5!
71!
0;!
!
(*6#(%'9*5$D)5A5$4%5)4)5A5%)&'$46*&)=($E&(8&%*%$3/1!
0$(73%;')1'8!
1!
0;1!
**)#3(3/%)!
7%0!
>(*=*'69)&"*&&'9$4'9*>(*=*(*46*#4*#('9*6A((*4'#>>(*=*'69*D6**%*%7)'*($'#(&,'9*4%*6(*$&*$6$69*")4*%)&'$46*#4>(*=*(*46*>(*=*'69%)&'$46*,#'9*(B)&*,)46(*$&*$6$69*")4*%)&'$46*#4>(*=*(*46*#4*8&%*%$3/1!
0$(73%FC3(3/%)!
7%0!
'971(&C*!
&0$=()".
5(:1!
0:5!
71!
0;!
!
$%KA&''9*>(*=*'69%)&'$46*'#$L#)%$66*&&'9*&$5*6$69*")4*'9$''9*>(*=*(*46*"#$%)4&'(A6')#4&$66*&&B9)"*($E&(8&%*%$3/1!
0$(73%;>'971(&)#3(3/%)!
7%0!
(*=*'69指令插入!
对于--.
8&%*%$3/所用到的距离是在编译时计算出来:1!
0$(73%C@M$'80$&!
1%!
@的值是由前面的算法计算出来的迭代距离!
计算实际预取距离后下一步就是插入指令,设"#$%的地址寄存器为&1,那么就在"#$%前面插入8&%*%$3/(1!
0$(73%G&1)!
这样就完成了对NNJ做>(*=*'69的工作!
对于ONJ类型的"#$%要做的工作就要多一些,因为它的预取距离要通过程序运行时动态地计算得到!
对ONJ型"#$%的>(*=*'69指令插入过程如下:1)插入一条5#L*指令在"#$%指令之前,用来保存这次"#$%的地址信息;+)在"#$%指令前插入一条减法指令!
用上一次5#L*指令所保存的地址值减去这一次"#$%的地址值,就可以得到&'()%*值;8)插入8&%*%$3/((11&%00G@M0$&!
1%)指令在"#$%指令的前面!
实际程序中用简单位移来替代乘法以减少PQR的运算开销!
!
实验结果通常>(#=)")4;会使得程序的运行产生很大的开销!
本文使用采样技术来减少>(#=)")4;带来的额外程序执行时间!
采样频率会直接影响>(#=)")4;执行开销和最终生成程序代码的性能!
>(#=)")4;的开销和最终代码性能是一对矛盾关系!
低采样频率可以减少>(#=)")4;的开销,但是会使得>(#=)")4;收集到的信息不够精确影响最终程序性能!
为了选取合适的采样频率我们测试了不同频率下的>(#=)")4;开销和对最终程序性能的影响,测试结果如图,和图/所示!
图,表示的是>(#=)")4;时程序的执行时间与无>(#=)")4;时执行时间之比!
在没有使用采样技术时程序的>(#=)")4;执行时间平均是原来的,倍,通过采样技术显著地降低了>(#=)")4;执行开销!
但是由于程序运行时调用>(#=)")4;插装函数本身的开销,导致了在采样值大于1-以后执行时间并没有随着采样值的增加而显著减少!
图/是采样后最终生成程序与无采样时的执行时间之比!
从图中可以看出,由于采样导致的信息精确性减少,使得总体上程序的最终执行时间变长!
大多情况下采样率高的程序性能也会好于采样率低的,但是少部分例子低采样率性能反而比高采样率的性能要好,比如>*("E5S,这主要是由于>(#=)")4;时程序的输入集与最终程序输入集的差异所导致!
从上面两个图中和考虑采样7/8计算机研究与发展+.
.
2,,,(+)值为!
"时对程序性能影响比较小,而且#$%&'(')*执行开销相对于不做采样减少较大+所以采样值!
"对于最终程序性能和#$%&'(')*开销是一个很好的平衡点,在大多情况下已经可以满足实际应用中对编译器性能的需求+,'*+"-.
$&%$/0)1.
%&2-345556.
76$.
78(6+图"2-34555性能测试结果,'*+9:;.
6.
76$.
78(6%&#$%&'(')*%:;.
#.
$&%$/0)1.
%&.
&&.
16@70/#(.
采样后程序执行时间对比图"为基于#$%&'(')*的数据预取和传统静态分析程序插入数据预取指令的性能对比+测试按A种方式进行+图中!
"表示76$'=.
#$.
&.
61;,#$表示#$%&'(')*收集到的76$'=.
'6.
$06'DG的性能提升+2$0&@循环预取优化没有效果,76$'=.
优化反而降低了!
+4HG的性能+这里的性能下降主要是因为做#$%&'(')*时程序的输入集和测试时输入集的程序访存行为不一致所造成的+所以76$'=.
优化的#$%&'(')*信息的准确度非常重要,如果没有精确的访存信息反而可能降低程序性能+-0$7.
$,I%(&和/1&在76$'=.
优化下得到了大幅的性能提升,#0$7.
$为H+D!
G,6I%(&为A+>>G,/1&为AA+HAG+但是/1&在执行循环预取时性能反而下降了4+D5G+这主要是因为循环预取优化不能正确分析指针访存行为,而在/1&中大量循环通过指针方式访存,所以循环预取优化造成性能下降+其他例子中76$'=.
优化也得到了不同程度的性能提升,基于#$%&'(')*数据预取优化时这!
4个例子平均性能得到H+>9G的提升+而循环数据预取优化平均仅获得了5+!
!
G的性能提高+76$'=.
'6.
$06'D吴佳骏等:非线性规律访存操作的数据预取技术!
结论!
"#$%&%'(和!
")$)*+,都是当前比较热门的编译技术-我们在.
/0上实现的基于!
"#$%&%'(的!
")$)*+,中,提出新的信息收集类型,更精确地反映程序执行时访存指令的实际行为-并且结合别名分析的结果调整对同一+1+,)行的数据预取,得到比普通数据预取更好的预取性能,扩展了基于软件自动向导的!
")$)*+,研究领域-借助使用!
"#$%&%'(技术去找出静态分析无法得到的2*"%3)信息,我们扩大了可以进行!
")$)*+,的程序范围-编译器生成的代码性能明显得到了提升,例如4+$的加速比达到了5-67,!
1"2)"的加速比达到了5-89-基于!
"#$%&%'(的!
")$)*+,比传统的循环优化静态分析数据预取有更好的性能和效率-参考文献[5]:;)"#$")(;&1"2*"%3)!
1**)"'2%'%"")(;&1"!
"#("1421'3%*2;2)%'+#4!
%&)"!
")$)*+,%'([0]-@"#("144%'(A1'(;1()B)2%('1'3C4!
&)4)'*1*%#'D88D,E)"&%',F)"41',D88D[D]B1>%301&&1,1',G)'G)'')3,H&&1'@#"*)"$%)&3-I#$*J1")!
")$)*+,%'([0]-K,)L*,C'*'&0#'$#'H"+,%*)+*;"1&I;!
!
#"*$#"@"#("144%'(A1'(;1()21'3.
!
)"1*%'(I2*)42,I1'*10&1"1,01&%$#"'%1,5MM5[N]O)1'PA#;!
E1)",K%)'PQ;0,)'-=$$)+*%>),1"3J1")PR12)331*1!
")$)*+,%'($#",%(,P!
)"$#"41'+)!
"#+)22#"2[O]-C===K"1'2#'0#4!
;*)"2,5MMS,LL(S):78MT7DN[L]B#;(O#2)!
,,B%"UF";'J1&3-@")$)*+,%'(;2%'(V1"U#>!
")3%+*#"2[0]-K,)DL*,H'';1&C'*'&I4!
#'0#4!
;*)"H"+,%*)+*;"),B)'>)",0#&#"13#,5MM6[S]H4%"/#*,,H'3")12V#2,#>#2,F;"%'31"II#,%-B)!
)'3)'+)R12)3!
")$)*+,%'($#"&%'U)331*12*";+*;")2[0]-K,)9*,C'*'&0#'$#'H"+,%*)+*;"1&I;!
!
#"*$#"@"#("144%'(A1'(;1()21'3.
!
)"1*%'(I2*)42,I1'O#2),01&%$#"'%1,5MM9[7]C'*)&0#"!
-C'*)&!
C*1'%;4KV@"#+)22#"W1"3J1")B)>)&#!
)"'2V1';1&[.
A]-,**!
:!
!
3)>)&#!
)"X%'*)&X+#4!
3)2%('!
%1P7L!
41';1&2X,*4,D888[6]C'2*%*;*)#$0#4!
;*%'(K)+,'#&#(,0,%')2)H+13)4#$I+%)'+)2-.
/0D-5-.
!
)'")2)1"+,+#4!
%&)"R12)3#'CHP7L[.
A]-,**!
:!
!
%!
$P#"+-2#;"+)$#"()-')*!
")134)P")&)12)PD-5-,*4,D88S(%'0,%')2))(中国科学院计算技术研究所-基于CH7L开放源代码编译器[.
A]-,**!
:!
!
%!
$P#"+-2#;"+)$#"()-')*!
")134)P")&)12)PD-5-,*4,D88S)[9]0,%PG);'(A;U,/#R)"*V;*,,W1"%2,@1*%&,!
"#$-@"#$%&)P(;%3)3!
#2*P&%'U2*"%3)!
")$)*+,%'([0]-K,)57*,C'*'&0#'$#'I;!
)"+#4!
;*%'(,Y)J%2#"#$*,)C'2*%*;*)#$0#4!
;*%'(K)+,'#&#(,*,)0,%')2)H+13)4#$I+%)'+)2-W%241%'")2)1"+,%'*)")2*2%'+&;3)+#4!
%&)"*)+,'%+1&1'3")&1*%#'*##&2-冯晓兵,5M7M年生,研究员,博士生导师,主要研究方向为编译技术及相关工具($[R"%+*-1+-+')-/0&(+/0&-1%(+,R#"'%'5MN9-F"13;1*)$"#4@)U%'(\'%>)"2%*-@"#$)22#"1'3@,-B-2;!
)">%2#"*,)#$C'2*%*;*)#$0#4!
;*%'(K)+,'#&#(,*,)0,%')2)H+13)4#$I+%)'+)2-W%241%'")2)1"+,%'*)")2*2%'+&;3)+#4!
%&)"*)+,'%+1&1'3")&1*%#'*##&2-张兆庆,5MN9年生,研究员,博士生导师,主要研究方向为编译技术及相关工具(Z]Z,1'("%+*-1+-+')-2*3*&4506&57+4-#(8K,%2!
"#^)+*%22;!
!
#"*)3R*,)0,%')2)97N%4!
#"*1'*2#$*J1")C*)42W%(,@)"$#"41'+)0#4!
%&)"I2*)4(D88LHH5_DD88)1'3%*%2R12)3#'1'#!
)'")2)1"+,+#4!
%&)".
/0D-5-.
/0%23)>)&#!
)3R*,)+##!
)"1*%#'#$*,)C'2*%*;*)#$0#4!
;*%'(*)+,'#&#(,0,%')2)H+13)4#$I+%)'+)21'3C'*)&C'+,J,%+,%2R12)3#'C'*)&'2CHP7L-H**,)!
)1U#!
*%4%Z1*%#'+#4!
%&1*%#'#!
*%#'.
/0D-5%2#'&S!
)"+)'*&#J)"*,1'C'*)&'2!
"#3;+*+#4!
%&)"=006-8#'C*1'%;4PD22*)4-:,)'1'1&Z%'(0@\D888CYK*)2*")2;&*J)$#;'3*,1*1++)22%'(4)4#"#++;!
%)2NN-N'#$*,)";'*%4),2#()**%'("%3#$4)4#"1++)22#>)",)13R)+#4)21>)"%4!
#"*1'*J#"U$#"%4!
"#>%'(!
"#("14'2!
)"$#"41'+)-B1*1!
")$)*+,%21+#44#'*)+,'%];);2)3*#)&%4%'1*)4)4#"1++)22#>)",)13,R;*R3)!
)'3%'(#'2*1*%+1'1&2%2*,)+#4!
%&)"+1',1"3&+#"")+*&!
")$)*+,31*1*,1*1")'#'&%')1"1++)22)3-E!
"#$%&%'(*)+,'%];)2#')+1'()**,)")(;&1*%#'RJ,%+,*,)!
"#("141++)22)24)4#",1'3*,)!
"#$%&%'(%'$#J%&&(;%3)*,)+#4!
%&)"*#1++;"1*)&%'2)"*!
")$)*+,%'2*";+*%#'2-E12)3#'2*"%3)!
"#$%&%'(*)+,'%];),*,%2!
1!
)"!
"#!
#2)21')J%'$#*!
)'14)32*"%3)%*)"1*%>)J,%+,%24#")1++;"1*)*,1''#"41&!
"#$%&%'(-K#()*,)"J%*,*,)1&%12%'$#*#13^;2**,)31*1!
")$)*+,$#"*,)214)+1+,)&%'),*,)+#4!
%&)"()*21R)**)"!
)"$#"41'+)*,1'*,)'#"41&31*1!
")$)*+,-K,)0@\D8885DCYK+12)2()*9-SL'!
)"$#"41'+)%4!
"#>)4)'*1'34+$()*266-96'!
)"$#"41'+)%'+")12)#'C*1'%;4PD22*)42#'*,)1>)"1()-87N计算机研究与发展D886,LL(D)