冷 冰，嚴(yán)曉浪，孟建熠，葛海通

（浙江大學(xué)超大規(guī)模集成電路設(shè)計研究所，浙江杭州 310027）

0 引言

現(xiàn)代嵌入式處理器通常采用組相聯(lián)指令高速緩存來降低沖突訪問缺失（conflict miss）［1，2］，但是組相聯(lián)高速緩存同時引起了冗余的訪問功耗。研究表明，指令高速緩存功耗已成為處理器總功耗的主要組成部分之一，如StrongArm SA110中指令高速緩存的功耗占總功耗的25%［2］。在高速緩存實(shí)現(xiàn)中為了減少訪問延時，對標(biāo)志存儲器和數(shù)據(jù)存儲器的訪問是并行的，而其中的命中檢測和對無關(guān)路的冗余訪問導(dǎo)致了大量額外的功耗。

為了降低組相聯(lián)指令高速緩存的功耗，學(xué)術(shù)界目前已提出許多的方法。Filter Cache［3］和 Hotspot Cache［4］主要通過在處理器和一級高速緩存之間增加一個較小的零級緩存來達(dá)到低功耗和低命中延時的目的，但由于其零級采用的是較小的直接映射結(jié)構(gòu)，對程序的局部性有較強(qiáng)的依賴，缺失率較高，而且一旦缺失需要繼續(xù)訪問一級緩存，增大總訪問延時的同時也增加了存儲訪問的功耗。路預(yù)測（way-prediction）技術(shù)［5，6］通過收集運(yùn)行時緩存訪問信息，預(yù)測將要訪問的高速緩存路，從而避免無關(guān)路的訪問;但預(yù)測失敗會導(dǎo)致額外的標(biāo)志存儲和數(shù)據(jù)存儲的并行訪問，增加總訪問延時和訪問功耗;即使預(yù)測正確，由于路預(yù)測方法的投機(jī)執(zhí)行本質(zhì)，仍然需要通過訪問標(biāo)志存儲器對預(yù)測的結(jié)果進(jìn)行檢查，從而增加一定的功耗。路記憶策略［7］主要利用記錄的路訪問歷史，在高速緩存中為每條指令保存相關(guān)的鏈接信息，其避免命中檢測和無關(guān)路訪問的效果較好;但是由于其記錄的粒度精細(xì)到指令，需要為高速緩存中每條指令字預(yù)設(shè)跳轉(zhuǎn)信息位，而普通指令并不需要該位，因此會造成大量的硬件浪費(fèi);同時當(dāng)高速緩存行替換發(fā)生時，路訪問歷史信息會全部丟失，頻繁重建鏈接記錄會增加冗余數(shù)據(jù)的訪問，歷史信息利用效率較低。

本文提出了一種基于路訪問軌跡信息的指令高速緩存低功耗策略。該方法基于指令高速緩存和轉(zhuǎn)移目標(biāo)緩存等現(xiàn)有硬件結(jié)構(gòu)，兼顧軌跡信息精確性的同時采用硬件代價較小、精確到緩存行的大粒度策略。通過指令高速緩存行中記錄的跨行訪問的路軌跡信息來避免跨行連續(xù)訪問中不必要的命中檢測與無關(guān)路訪問。利用轉(zhuǎn)移目標(biāo)緩存（branch target buffer，BTB）中記錄的轉(zhuǎn)移目標(biāo)路軌跡信息來消除非連續(xù)訪問中不必要的命中檢測無關(guān)路訪問。進(jìn)一步提出了不同的路訪問軌跡信息的維護(hù)策略，研究降低該方法對路軌跡記錄維護(hù)的影響，提高路訪問軌跡信息的利用效率，降低信息重建的頻度，達(dá)到較為理想的低功耗效果。

1 基于路訪問軌跡信息的低功耗策略

由于程序指令存儲的連續(xù)性本質(zhì)，處理器在取指時對指令高速緩存訪問的連續(xù)性十分顯著，通常訪問分為3種:1）順序指令流引起的高速緩存行內(nèi)連續(xù)訪問;2）順序指令流引起的高速緩存跨行連續(xù)訪問;3）轉(zhuǎn)移指令引起的非連續(xù)訪問;此外還存在其他的特殊非連續(xù)訪問，如指令異常、硬件中斷等。行內(nèi)連續(xù)訪問最為簡單，每次訪問的指令高速緩存路與上一次訪問相同，命中檢測和無關(guān)路的訪問均可避免;跨行訪問與轉(zhuǎn)移非連續(xù)訪問的情況稍為復(fù)雜，因?yàn)樾袃?nèi)訪問可保證本次高速緩存訪問命中，而跨行訪問與轉(zhuǎn)移非連續(xù)訪問還存在高速緩存缺失的情況，對此需要考慮新的路訪問軌跡信息的建立與維護(hù)。

與路預(yù)測的投機(jī)策略不同，路軌跡信息可以保證路軌跡信息的正確，徹底避免后續(xù)的正確性檢查所引起的標(biāo)志存儲器訪問。為了記錄跨行訪問的路訪問軌跡，高速緩存行需要增加跨行連續(xù)訪問路指針SWP及其有效位SWPV，如圖1。SWP它記錄了連續(xù)指令流中需要訪問的后繼高速緩存行當(dāng)前所在的路。若是首次訪問該后繼緩存行，路訪問軌跡尚未建立，則采用傳統(tǒng)的標(biāo)志、數(shù)據(jù)存儲器并行訪問的方式得到該緩存行所在路，然后為其前驅(qū)緩存行建立路軌跡信息。SWPV表明該路軌跡記錄有否有效，如果該位有效，則保證連續(xù)指令流中的下一個高速緩存行命中，SWP指向該行所在的路。轉(zhuǎn)移非連續(xù)訪問路軌跡的記錄則需要改進(jìn)現(xiàn)有的轉(zhuǎn)移目標(biāo)緩存。轉(zhuǎn)移目標(biāo)緩存利用轉(zhuǎn)移指令的轉(zhuǎn)移歷史記錄，在轉(zhuǎn)移指令的目標(biāo)地址計算結(jié)果得到之前訪問指令高速緩存以加速處理器取指。由于轉(zhuǎn)移目標(biāo)緩存中的有效表項(xiàng)可一一對應(yīng)近期的轉(zhuǎn)移指令，可以在其中類似地增加轉(zhuǎn)移訪問路指針TWP及其有效位TWPV，如圖1。TWP指向該轉(zhuǎn)移指令的轉(zhuǎn)移目標(biāo)所在的指令高速緩存路。對于一個N路組相聯(lián)的高速緩存來說，SWP和TWP均只需log2N位即可。一旦路軌跡信息被建立，指令高速緩存的訪問即可簡化為對單一路緩存行的訪問，從而大大減少標(biāo)志位與無關(guān)數(shù)據(jù)路的訪問。

圖1 跨行訪問路指針和轉(zhuǎn)移訪問路指針Fig 1 SWP and TWP pointer

2 路訪問軌跡信息的維護(hù)

指令高速緩存發(fā)生了行更新和替換時需要清除現(xiàn)有的路軌跡信息。如果某緩存行B被替換，則需清除其前驅(qū)緩存行A的跨行連續(xù)訪問路指針SWP，但此時不能定位緩存行A所在的路。如圖2，跨行連續(xù)訪問路指針SWP的維護(hù)一般有2種策略:1）清除緩存行A所在高速緩存組中所有路緩存行的SWP;2）由于緩存行A和緩存行B在指令流中連續(xù)，因此，緩存行A的標(biāo)志位可由緩存行B的標(biāo)志位計算得到，然后在組內(nèi)進(jìn)行標(biāo)志位比較，若找到緩存行A，則清除其SWP;策略1比較簡單，但會同時清除組內(nèi)其他路的路軌跡信息，影響路軌跡記錄的利用效率;策略2同樣不會增加信息位，但前驅(qū)索引的計算較為復(fù)雜，同時檢查前驅(qū)行所在組內(nèi)的所有標(biāo)志為的操作較慢而且會引起額外的功耗，另外，其訪問可能會與標(biāo)志存儲器其他的訪問請求產(chǎn)生競爭。為了準(zhǔn)確定位前驅(qū)緩存行，現(xiàn)提出第3種策略，如圖2，在高速緩存行中添加前驅(qū)指針PWP及其有效位PWPV記錄其前驅(qū)行的路信息，替換發(fā)生時可以根據(jù)緩存行B的前驅(qū)指針找到前驅(qū)行A并清除其SWP。

在緩存行B被替換時，轉(zhuǎn)移目標(biāo)緩存中所有以緩存行B中指令為目標(biāo)的轉(zhuǎn)移訪問路指針TWP也需要被清除，而此時同樣沒有其位置信息。如圖2，轉(zhuǎn)移訪問路指針TWP的維護(hù)一般有2種策略:1）清除轉(zhuǎn)移目標(biāo)緩存中的所有TWP指針;2）在高速緩存行中添加行轉(zhuǎn)移前驅(qū)狀態(tài)位ttf。ttf為0表示本緩存行尚無轉(zhuǎn)移前驅(qū);ttf為1表示本緩存行存在轉(zhuǎn)移前驅(qū);緩存行被替換時可根據(jù)狀態(tài)位ttf來決定是否清除所有TWP。策略1中TWP指針的誤清除率較高;策略2通過增加一個信息位，可在一定程度上降低TWP的誤清除率。為了進(jìn)一步減少誤清除率，如圖2，可以在策略2的基礎(chǔ)上添加轉(zhuǎn)移前驅(qū)指針bttp轉(zhuǎn)移前驅(qū)狀態(tài)位ttf增加到兩位得到策略3:ttf為0表示本行尚無轉(zhuǎn)移前驅(qū);ttf為1表示本緩存行有一個轉(zhuǎn)移前驅(qū)，bttp指針指向其在轉(zhuǎn)移目標(biāo)緩存中的位置，發(fā)生替換時可直接定位TWP;ttf為2表示本緩存行存在一個以上的轉(zhuǎn)移前驅(qū)，發(fā)生替換時需清除所有TWP。相似地，可以擴(kuò)展策略3得到策略4，即記錄2個或2個以上的轉(zhuǎn)移前驅(qū)的位置信息。

當(dāng)轉(zhuǎn)移目標(biāo)緩存中的表項(xiàng)發(fā)生了更新或替換時，需要同時清除其TWP指針。在上述提出的第3種和第4種TWP維護(hù)策略中，因?yàn)闆]有轉(zhuǎn)移目標(biāo)緩存行的高速緩存索引，所以，無法更新其所在高速緩存行的行轉(zhuǎn)移前驅(qū)狀態(tài)及其指針，而不準(zhǔn)確的行轉(zhuǎn)移前驅(qū)狀態(tài)會在該高速緩存行被替換時導(dǎo)致對應(yīng)TWP指針的誤清除。對此可以為轉(zhuǎn)移目標(biāo)緩存表項(xiàng)添加其轉(zhuǎn)移目標(biāo)高速緩存行的索引信息tip，如圖2。表項(xiàng)替換或更新發(fā)生時根據(jù)tip清除相應(yīng)的轉(zhuǎn)移目標(biāo)行的行轉(zhuǎn)移前驅(qū)信息，降低誤清除率。

圖2 不同的SWP，TWP維護(hù)策略的Cache，BTB結(jié)構(gòu)Fig 2 Different Cache and BTB entry configurations of maintenance strategies of SWP and TWP

3 實(shí)驗(yàn)結(jié)果與分析

以高性能嵌入式處理器CK510［8］模擬器軟件為平臺，實(shí)現(xiàn)了本文所述的路軌跡指令高速緩存和轉(zhuǎn)移目標(biāo)緩存。實(shí)驗(yàn)采用Motorola的嵌入式測試基準(zhǔn)Powerstone［9］，對比了傳統(tǒng)指令高速緩存和路軌跡指令高速緩存的標(biāo)志位與數(shù)據(jù)存儲器訪問次數(shù)，同時分析了不同路軌跡信息維護(hù)策略對于訪問次數(shù)的影響，其中采用了不同SWP，TWP維護(hù)策略的方案分別標(biāo)記為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路組相聯(lián)的1k和2k指令高速緩存，緩存行寬度為16字節(jié)即8條指令的配置下，相對于傳統(tǒng)指令高速緩存，332-cache路軌跡指令高速緩存的訪問次數(shù)相對值如表1所示。

表1 332-cache的訪問次數(shù)相對值Tab 1 Relative value of access times of 332-cache

結(jié)果顯示:1k的332-cache對標(biāo)志位存儲器和數(shù)據(jù)存儲器的平均訪問次數(shù)分別降低到傳統(tǒng)指令高速緩存的5．10%和 28．83%，2k的 332-cache則降低到 3．60% 和27．70%?？梢钥闯?對于較大的高速緩存來說緩存行缺失率較低，所以，路軌跡信息的重建概率較低、使用效率較高，因此，可以得到更好的低功耗效果。

相對于132-cache，332-cache可以降低由于緩存行替換引起的SWP清除，從而提高SWP的利用率。在4路組相聯(lián)的1k指令高速緩存的配置下，根據(jù)SWP進(jìn)行的低功耗跨行訪問占全部跨行訪問的比例如表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程序相對較大，指令高速緩存缺失率較高。結(jié)果顯示332-cache的前驅(qū)指令策略可以更準(zhǔn)確地定位需要清除SWP的緩存行前驅(qū)，避免了誤清除，得到了更高的SWP信息利用效率。

相對于 311-cache，321-cache，331-cache 和 332-cache 可以降低由于緩存行替換引起的TWP清除，而相對于331-cache，332-cache可以降低由于緩存行替換和轉(zhuǎn)移前驅(qū)狀態(tài)不準(zhǔn)確引起的TWP清除，從而提高了TWP的利用率。在4路組相聯(lián)的1k指令高速緩存的配置下，根據(jù)TWP進(jìn)行的低功耗跨行訪問占全部跨行訪問的比例如表3所示。

表 3 311-cache，321-cache，331-cache 和 332-cache的低功耗轉(zhuǎn)移訪問比例Tab 3 Low power consumption transfer access proportion of 311-cache，321-cache，331-cache and 332-cache

結(jié)果顯示，321-cache策略相對與311-cache的提高較少，其原因在于程序中大量部分緩存行都存在轉(zhuǎn)移前驅(qū)，雖然有轉(zhuǎn)移前驅(qū)狀態(tài)位的輔助，但緩存行缺失時總是指示該行存在轉(zhuǎn)移前驅(qū)，因此，對TWP利用效率仍然較低。331-cache相對于311-cache的提高相對明顯，由于記錄了一個轉(zhuǎn)移前驅(qū)的位置信息，緩存行缺失時能夠準(zhǔn)確定位轉(zhuǎn)移前驅(qū)，避免其他TWP的誤清除，因此，對TWP利用效率有了明顯提高。332-cache相對于331-cache的提高較低，由于程序中轉(zhuǎn)移指令總數(shù)較少，轉(zhuǎn)移目標(biāo)緩存很少有替換發(fā)生，而且轉(zhuǎn)移目標(biāo)緩存表項(xiàng)被替換后其對應(yīng)的高速緩存行也被替換的情況較少。

4 結(jié)束語

本文通過分析指令高速緩存的連續(xù)訪問特性，提出了一種基于改進(jìn)的高速緩存和轉(zhuǎn)移目標(biāo)緩存建立路訪問軌跡信息的指令高速緩存低功耗方法，有效地消除了組相聯(lián)指令高速緩存中無關(guān)標(biāo)志位和數(shù)據(jù)的訪問。同時提出和分析了多種路軌跡信息的維護(hù)策略，有效地減少了簡單維護(hù)策略造成的路軌跡信息重建，提高了路軌跡信息利用效率，從而提升了其低功耗效果。

［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］ 孟建熠，黃 凱，嚴(yán)曉浪，等．應(yīng)用與SoC功能驗(yàn)證的快速處理器仿真模型［J］．浙江大學(xué)學(xué)報:工學(xué)版，2009，43（3）:401－405．