资源描述：
《基于复用距离的cache失效率分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第!&卷第1期小型微型计算机系统ZG.[!&JG/1!""%年1月3*J*Y3*AMXWLWB53WW-O/!""%基于复用距离的!"!#$失效率分析付雄，张昱，陈意云（中国科学技术大学计算机科学与技术系，安徽合肥!(""!&）5$678.：9:;<7+=!:>,?/-@:/?+摘要：复用距离已经成为程序?7?<-行为的一种重要度量标准，但高复杂度和可能的内存溢出问题使得其难以应用/本文在引入最大?7?<-大小的基础上提出一种受限的复用距离分析方法/该方法有效地避免了一般复用距离分析可能导致的内存溢出问题，同时使得复用距离分析达到线性时间复杂度/文章通过对一系列整数
2、和浮点程序的实验说明基于该复用距离分析的?7?<-失效率分析的可行性和正确性/关键词：复用距离；A7?<-失效率；局部性中图分类号：BC(00文献标识码：D文章编号：0"""$0!!"（!""%）"1$0&&&$"#%$&’$()’*"+!$,"’$-."!#$/)’’%"*$0+"12’)’EF28G+=，HIDJKL:，AI5JL8$9:+（!"#$%&’"(&)*+)’#,&"%-./"(."$(01".2()3)45，6(/7"%8/&5)*-./"(."$(01".2()3)45)*+2/($，9"*"/!(""!&，+2/($）03’*4"!*：M-:>
3、-@8>,7+?-<7>N-?G6-7+86OGP,7+,6-,P8?GQOPG=P76?7?<-N-<7R8GP，N:,<8=>8N.-6-6GP9GR-P$Q.GTOPGN.-667U-8,>:>8+=@8QQ8?:.,/AG+>8@-P8+=67S?7?<->8;-，,<8>O7O-P8+,PG@:?->7.868,-@P-:>-@8>,7+?-7+7.9>8>6-,6-,OG>>8N.-6-6GP9GR-PQ.GTOPGN.-68++GP67.P-:>-@8>,7+?-7+7.9>8>，7,
4、,<->76-,86-,<8>6-,?G6O.-S8,9GQP-:>-@8>,7+?-7+7.9>8>@-?P-7>-,G.8+-7P/5SO-P86-+,>QPG6>G6-8+,-=-P7+@Q.G7,8+=$OG8+,OPG=P76>>Q-7>8N.-7+@?GPP-?,,<7,?7?<-68>>P7,-8>7+7.9;-@N9,<8>P-:>-@8>,7+?-7+7.9>8>/5$2674-’：P-:>-@8>,7+?-；?7?<-68>>P7,-；.G?7.8,98引言和3都与程序及其输入相关；当3比较大，如达到上亿时，很容易导
5、致系统物理内存甚至(!位地址空间溢出/计算机ACF速度的高速增长和内存速度的缓慢增长使本文通过引入最大?7?<-大小（37SA7?<-W8;-），提出了得ACF和内存之间的速度差距越来越大，这导致内存系统成一种受限的复用距离分析方法/该方法有效地弥补了其他复为性能上的瓶颈/现代计算机体系结构中广泛采用?7?<-来用距离分析的不足，其主要特点有：降低这种影响，但是?7?<-不能命中时形成的?7?<-失效会引（0）使分析所需的空间只与最大?7?<-大小相关，不再随起较长时间的内存存取/实际中?7?<-能否有效地利用取决程序或者其输入的改变而改变，有效地避免了可能导致的内
6、于程序局部性（4G?7.8,9）和数据的复用模式［0］/随着?7?<-层存溢出问题；次数目的增加和自适应能力的增强，如何模型化程序局部性（!）将分析的时间复杂度降低到与访问数据的次数J成并分析?7?<-失效率成为研究的热点，这对开发高性能应用线性关系；程序、现代优化编译器以及高性能计算机系统都有着重要意（(）当被访问数据的复用距离局限在某给定区间时，可义［0，!］/以通过调整最大?7?<-大小尽快完成复用距离分析/复用距离（M-:>-V8>,7+?-）是局部性的度量标准之一［!］，本文的组织如下：第!节介绍受限的复用距离分析方法；但复用距离分析具有较高的时空代价，这
7、制约了其应用［0，(］第(节介绍用复用距离分析?7?<-失效率；第’节介绍实验及/一些研究者采用区间树（*+,-PR7.BP--）［(］、伸展树（WO.79结果分析；第#节和第%节分别介绍相关工作、结论及未来工BP--）［0］等数据结构来提高分析的性能/目前在精确分析程序作/数据的复用距离的各种算法中，最好的时间和空间复杂度分［0］9受限的复用距离分析别为X（J.G=3）和X（3），其中J和3分别为访问数据的次数和访问数据集的大小/分析的复杂度仍然很高，并且J9:8定义收稿日期：!""#$"%$!&基金项目：国家自然科学基金项目（%"’&("%)）资助；*+,-
