基于路訪問軌跡的指令高速緩存低功耗策略*

冷 冰，嚴曉浪，孟建熠，葛海通

（浙江大學超大規模集成電路設計研究所，浙江杭州 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．