基于路访问轨迹的指令高速缓存低功耗策略*

冷 冰，严晓浪，孟建熠，葛海通

（浙江大学超大规模集成电路设计研究所，浙江杭州 310027）

0 引言

现代嵌入式处理器通常采用组相联指令高速缓存来降低冲突访问缺失（conflict miss）［1，2］，但是组相联高速缓存同时引起了冗余的访问功耗。研究表明，指令高速缓存功耗已成为处理器总功耗的主要组成部分之一，如StrongArm SA110中指令高速缓存的功耗占总功耗的25%［2］。在高速缓存实现中为了减少访问延时，对标志存储器和数据存储器的访问是并行的，而其中的命中检测和对无关路的冗余访问导致了大量额外的功耗。

为了降低组相联指令高速缓存的功耗，学术界目前已提出许多的方法。Filter Cache［3］和 Hotspot Cache［4］主要通过在处理器和一级高速缓存之间增加一个较小的零级缓存来达到低功耗和低命中延时的目的，但由于其零级采用的是较小的直接映射结构，对程序的局部性有较强的依赖，缺失率较高，而且一旦缺失需要继续访问一级缓存，增大总访问延时的同时也增加了存储访问的功耗。路预测（way-prediction）技术［5，6］通过收集运行时缓存访问信息，预测将要访问的高速缓存路，从而避免无关路的访问;但预测失败会导致额外的标志存储和数据存储的并行访问，增加总访问延时和访问功耗;即使预测正确，由于路预测方法的投机执行本质，仍然需要通过访问标志存储器对预测的结果进行检查，从而增加一定的功耗。路记忆策略［7］主要利用记录的路访问历史，在高速缓存中为每条指令保存相关的链接信息，其避免命中检测和无关路访问的效果较好;但是由于其记录的粒度精细到指令，需要为高速缓存中每条指令字预设跳转信息位，而普通指令并不需要该位，因此会造成大量的硬件浪费;同时当高速缓存行替换发生时，路访问历史信息会全部丢失，频繁重建链接记录会增加冗余数据的访问，历史信息利用效率较低。

本文提出了一种基于路访问轨迹信息的指令高速缓存低功耗策略。该方法基于指令高速缓存和转移目标缓存等现有硬件结构，兼顾轨迹信息精确性的同时采用硬件代价较小、精确到缓存行的大粒度策略。通过指令高速缓存行中记录的跨行访问的路轨迹信息来避免跨行连续访问中不必要的命中检测与无关路访问。利用转移目标缓存（branch target buffer，BTB）中记录的转移目标路轨迹信息来消除非连续访问中不必要的命中检测无关路访问。进一步提出了不同的路访问轨迹信息的维护策略，研究降低该方法对路轨迹记录维护的影响，提高路访问轨迹信息的利用效率，降低信息重建的频度，达到较为理想的低功耗效果。

1 基于路访问轨迹信息的低功耗策略

由于程序指令存储的连续性本质，处理器在取指时对指令高速缓存访问的连续性十分显著，通常访问分为3种:1）顺序指令流引起的高速缓存行内连续访问;2）顺序指令流引起的高速缓存跨行连续访问;3）转移指令引起的非连续访问;此外还存在其他的特殊非连续访问，如指令异常、硬件中断等。行内连续访问最为简单，每次访问的指令高速缓存路与上一次访问相同，命中检测和无关路的访问均可避免;跨行访问与转移非连续访问的情况稍为复杂，因为行内访问可保证本次高速缓存访问命中，而跨行访问与转移非连续访问还存在高速缓存缺失的情况，对此需要考虑新的路访问轨迹信息的建立与维护。

与路预测的投机策略不同，路轨迹信息可以保证路轨迹信息的正确，彻底避免后续的正确性检查所引起的标志存储器访问。为了记录跨行访问的路访问轨迹，高速缓存行需要增加跨行连续访问路指针SWP及其有效位SWPV，如图1。SWP它记录了连续指令流中需要访问的后继高速缓存行当前所在的路。若是首次访问该后继缓存行，路访问轨迹尚未建立，则采用传统的标志、数据存储器并行访问的方式得到该缓存行所在路，然后为其前驱缓存行建立路轨迹信息。SWPV表明该路轨迹记录有否有效，如果该位有效，则保证连续指令流中的下一个高速缓存行命中，SWP指向该行所在的路。转移非连续访问路轨迹的记录则需要改进现有的转移目标缓存。转移目标缓存利用转移指令的转移历史记录，在转移指令的目标地址计算结果得到之前访问指令高速缓存以加速处理器取指。由于转移目标缓存中的有效表项可一一对应近期的转移指令，可以在其中类似地增加转移访问路指针TWP及其有效位TWPV，如图1。TWP指向该转移指令的转移目标所在的指令高速缓存路。对于一个N路组相联的高速缓存来说，SWP和TWP均只需log2N位即可。一旦路轨迹信息被建立，指令高速缓存的访问即可简化为对单一路缓存行的访问，从而大大减少标志位与无关数据路的访问。

图1 跨行访问路指针和转移访问路指针Fig 1 SWP and TWP pointer

2 路访问轨迹信息的维护

指令高速缓存发生了行更新和替换时需要清除现有的路轨迹信息。如果某缓存行B被替换，则需清除其前驱缓存行A的跨行连续访问路指针SWP，但此时不能定位缓存行A所在的路。如图2，跨行连续访问路指针SWP的维护一般有2种策略:1）清除缓存行A所在高速缓存组中所有路缓存行的SWP;2）由于缓存行A和缓存行B在指令流中连续，因此，缓存行A的标志位可由缓存行B的标志位计算得到，然后在组内进行标志位比较，若找到缓存行A，则清除其SWP;策略1比较简单，但会同时清除组内其他路的路轨迹信息，影响路轨迹记录的利用效率;策略2同样不会增加信息位，但前驱索引的计算较为复杂，同时检查前驱行所在组内的所有标志为的操作较慢而且会引起额外的功耗，另外，其访问可能会与标志存储器其他的访问请求产生竞争。为了准确定位前驱缓存行，现提出第3种策略，如图2，在高速缓存行中添加前驱指针PWP及其有效位PWPV记录其前驱行的路信息，替换发生时可以根据缓存行B的前驱指针找到前驱行A并清除其SWP。

在缓存行B被替换时，转移目标缓存中所有以缓存行B中指令为目标的转移访问路指针TWP也需要被清除，而此时同样没有其位置信息。如图2，转移访问路指针TWP的维护一般有2种策略:1）清除转移目标缓存中的所有TWP指针;2）在高速缓存行中添加行转移前驱状态位ttf。ttf为0表示本缓存行尚无转移前驱;ttf为1表示本缓存行存在转移前驱;缓存行被替换时可根据状态位ttf来决定是否清除所有TWP。策略1中TWP指针的误清除率较高;策略2通过增加一个信息位，可在一定程度上降低TWP的误清除率。为了进一步减少误清除率，如图2，可以在策略2的基础上添加转移前驱指针bttp转移前驱状态位ttf增加到两位得到策略3:ttf为0表示本行尚无转移前驱;ttf为1表示本缓存行有一个转移前驱，bttp指针指向其在转移目标缓存中的位置，发生替换时可直接定位TWP;ttf为2表示本缓存行存在一个以上的转移前驱，发生替换时需清除所有TWP。相似地，可以扩展策略3得到策略4，即记录2个或2个以上的转移前驱的位置信息。

当转移目标缓存中的表项发生了更新或替换时，需要同时清除其TWP指针。在上述提出的第3种和第4种TWP维护策略中，因为没有转移目标缓存行的高速缓存索引，所以，无法更新其所在高速缓存行的行转移前驱状态及其指针，而不准确的行转移前驱状态会在该高速缓存行被替换时导致对应TWP指针的误清除。对此可以为转移目标缓存表项添加其转移目标高速缓存行的索引信息tip，如图2。表项替换或更新发生时根据tip清除相应的转移目标行的行转移前驱信息，降低误清除率。

图2 不同的SWP，TWP维护策略的Cache，BTB结构Fig 2 Different Cache and BTB entry configurations of maintenance strategies of SWP and TWP

3 实验结果与分析

以高性能嵌入式处理器CK510［8］模拟器软件为平台，实现了本文所述的路轨迹指令高速缓存和转移目标缓存。实验采用Motorola的嵌入式测试基准Powerstone［9］，对比了传统指令高速缓存和路轨迹指令高速缓存的标志位与数据存储器访问次数，同时分析了不同路轨迹信息维护策略对于访问次数的影响，其中采用了不同SWP，TWP维护策略的方案分别标记为132-cache（SWP策略1，TWP策略3带TIP），311-cache（SWP 策略 3，TWP 策略 1 不带 TIP），321-cache（SWP策略3，TWP策略2不带TIP），331-cache（SWP策略3，TWP策略3不带TIP），332-cache（SWP策略3，TWP策略3带TIP）。

在4路组相联的1k和2k指令高速缓存，缓存行宽度为16字节即8条指令的配置下，相对于传统指令高速缓存，332-cache路轨迹指令高速缓存的访问次数相对值如表1所示。

表1 332-cache的访问次数相对值Tab 1 Relative value of access times of 332-cache

结果显示:1k的332-cache对标志位存储器和数据存储器的平均访问次数分别降低到传统指令高速缓存的5．10%和 28．83%，2k的 332-cache则降低到 3．60% 和27．70%。可以看出:对于较大的高速缓存来说缓存行缺失率较低，所以，路轨迹信息的重建概率较低、使用效率较高，因此，可以得到更好的低功耗效果。

相对于132-cache，332-cache可以降低由于缓存行替换引起的SWP清除，从而提高SWP的利用率。在4路组相联的1k指令高速缓存的配置下，根据SWP进行的低功耗跨行访问占全部跨行访问的比例如表2所示。

表2 132-cache，332-cache的低功耗跨行访问比例Tab 2 Low power consumption inter-line access proportion of 132-cache and 332-cache

adpcm，des，fir，pocsag，qurt程序相对较大，指令高速缓存缺失率较高。结果显示332-cache的前驱指令策略可以更准确地定位需要清除SWP的缓存行前驱，避免了误清除，得到了更高的SWP信息利用效率。

相对于 311-cache，321-cache，331-cache 和 332-cache 可以降低由于缓存行替换引起的TWP清除，而相对于331-cache，332-cache可以降低由于缓存行替换和转移前驱状态不准确引起的TWP清除，从而提高了TWP的利用率。在4路组相联的1k指令高速缓存的配置下，根据TWP进行的低功耗跨行访问占全部跨行访问的比例如表3所示。

表 3 311-cache，321-cache，331-cache 和 332-cache的低功耗转移访问比例Tab 3 Low power consumption transfer access proportion of 311-cache，321-cache，331-cache and 332-cache

结果显示，321-cache策略相对与311-cache的提高较少，其原因在于程序中大量部分缓存行都存在转移前驱，虽然有转移前驱状态位的辅助，但缓存行缺失时总是指示该行存在转移前驱，因此，对TWP利用效率仍然较低。331-cache相对于311-cache的提高相对明显，由于记录了一个转移前驱的位置信息，缓存行缺失时能够准确定位转移前驱，避免其他TWP的误清除，因此，对TWP利用效率有了明显提高。332-cache相对于331-cache的提高较低，由于程序中转移指令总数较少，转移目标缓存很少有替换发生，而且转移目标缓存表项被替换后其对应的高速缓存行也被替换的情况较少。

4 结束语

本文通过分析指令高速缓存的连续访问特性，提出了一种基于改进的高速缓存和转移目标缓存建立路访问轨迹信息的指令高速缓存低功耗方法，有效地消除了组相联指令高速缓存中无关标志位和数据的访问。同时提出和分析了多种路轨迹信息的维护策略，有效地减少了简单维护策略造成的路轨迹信息重建，提高了路轨迹信息利用效率，从而提升了其低功耗效果。

［1］ Muller M．The ARM600 processor and FPA［C］∥Hot Chip 4 Symposium on Performance Chips，Memorial Auditorium，Stanford，1992．

［2］ Montanaro J，Witek R T，Anne K，et al．A 160 MHz 32-b 0．5W CMOS RISC microprocessor［C］∥The 42nd IEEE International Solid-State Circuits Conference，ISSCC 1996．Austin，TX，1996:214 －215，447．

［3］ Kin J，Munish G，Mangione-Smith W H，et al．The filter cache:An energy efficient memory structure［C］∥Proceedings of the 30th Annual IEEE/ACM International Symposium on Micro-architecture，San Diego，California，USA，1997:184 －193．

［4］ Yang Chia-lin，Lee Chien-hao．HotSpot cache:Joint temporal and spatial locality exploitation for I-cache energy reduction［C］∥Proceedings of the 2004 International Symposium on Low Power Electronics and Design，Newport Beach，California，USA，2004:9－11．

［5］ Inoue K，Ishihara T，Murakami K．Way-predicting set-asociative cache for high performance and low energy consumption［C］∥Proceedings of International Symposium on Low Power Electronics and Design，San Diego，California，USA，1999:273 －276．

［6］ Powell M D，Agarwal A，Vijaykumar T N，et al．Reducing set-associative cache energy via way-prediction and selective direct mapping［C］∥Proceedings of the 34th International Symposium on Micro-architecture，MICRO 34:IEEE，Computer Society Washington D C，USA，2001:54 －65．

［7］ Michael A M，Zhang M，Asanovic K．Way memorization to reduce fetch energy in instruction cache［C］∥Workshop on Complexity-Effective Design，Goteborg，Sweden:IEEE Computer Society，2001．

［8］ C-SKY Microsystems．32-bit high performance and low power embedded processor［DB/OL］．［2003—07—10］．http:∥www．csky．com．

［9］ 孟建熠，黄 凯，严晓浪，等．应用与SoC功能验证的快速处理器仿真模型［J］．浙江大学学报:工学版，2009，43（3）:401－405．