仇　徑，羅嘉蕙，項曉燕，陳志堅

(1.浙江大學超大規(guī)模集成電路設計研究所，浙江杭州310027; 2.復旦大學專用集成電路與系統(tǒng)國家重點實驗室，上海201203)

?

基于熱點行搜索的低功耗數(shù)據(jù)高速緩存

仇徑1，羅嘉蕙1，項曉燕2，陳志堅1

(1.浙江大學超大規(guī)模集成電路設計研究所，浙江杭州310027; 2.復旦大學專用集成電路與系統(tǒng)國家重點實驗室，上海201203)

摘要：針對數(shù)據(jù)高速緩存短時間內(nèi)頻繁訪問連續(xù)區(qū)段的特征，該文提出了一種基于熱點硬件自搜索和歷史訪問軌跡的數(shù)據(jù)高速緩存低功耗方法.該方法通過動態(tài)搜索熱點片段，緩存目標熱點行在高速緩存中的位置信息，過濾標簽存儲器和冗余數(shù)據(jù)存儲器的訪問.運行EEMBC測試基準的實驗結(jié)果表明，與基于MRU(Most Recently Used)的路預測方法相比，該方法Cache的動態(tài)功耗可降低30.77%，性能提升26.21%.

關鍵詞：低功耗;過濾訪問;熱點行搜索

1　引言

高速緩存(Cache)普遍應用于嵌入式處理器中，用以解決存儲墻的問題.隨著Cache容量和組相連度的不斷提升，Cache的功耗增加明顯.據(jù)統(tǒng)計，Cache功耗已經(jīng)達到了嵌入式處理器總功耗的20%～60%［1，2］，降低數(shù)據(jù)Cache功耗對降低整個處理器功耗有重要意義［3］.

在降低數(shù)據(jù)Cache功耗方面，目前主流方法包括路預測訪問方法和路過濾訪問方法兩種.文獻［4］中路預測訪問方法根據(jù)MRU表從組內(nèi)多路數(shù)據(jù)中猜測選擇一路數(shù)據(jù)，投機完成Cache數(shù)據(jù)訪問.如果預測錯誤，則在下一個周期內(nèi)完成剩余候選塊的標識比較和數(shù)據(jù)訪問，會明顯增加Cache的訪問時間.為了提高傳統(tǒng)路預測Cache預測的準確率，文獻［5］提出一種通過引入最小預測位的路預測訪問方法，進一步提高路預測算法的預測率.但這些方法只能針對特定的應用增加預測準確率，無法普遍適用.因此，文獻［6］提出一種基于行為模式預測的訪問方法，該方法根據(jù)訪問Cache的歷史信息，通過預測器判定當前指令是否適合采用路預測技術以及適用的路預測方法類型.上述所有路預測方法的缺陷在于無法避免標簽路的訪問，且一旦預測錯誤，需要額外訪問Cache，造成性能和功耗損失.

基于路過濾的方法，與路預測方法的本質(zhì)區(qū)別在于，路過濾并非投機訪問，而是根據(jù)過濾算法排除冗余的Cache訪問，減少功耗.文獻［7］提出了過濾Cache的方案，當CPU讀取數(shù)據(jù)時，首先訪問過濾Cache，若缺失，則訪問主Cache.該方案在過濾失效時會導致較長的訪問延時.為解決這個問題，文獻［8］提出了熱點Cache方案，僅在熱點程序中訪問熱點Cache，其他程序訪問主Cache.熱點Cache減少了過濾Cache方法的訪問延時，但仍需額外的Cache邏輯，增加靜態(tài)功耗.文獻［9］提出了一種基于多元信息的路過濾訪問方法，不增加額外的Cache邏輯，但只能過濾34.3%無效Cache的訪問.為提高過濾效率，文獻［10］通過標志預訪問來提前過濾后續(xù)指令的冗余訪問操作，文獻［11］通過使用鄰行信息鏈接歷史訪問表，獲取指令的路信息，可過濾96%的指令Cache冗余訪問.但由于數(shù)據(jù)Cache的不確定性和不連續(xù)性，上述方法無法進行針對性的過濾訪問;文獻［12］利用過濾Cache和L1 Cache訪問延時的不同使用字選擇和標簽提前比較的方式來避免冗余數(shù)據(jù)路訪問，但對于大多數(shù)標簽路和數(shù)據(jù)路同時訪問的數(shù)據(jù)Cache，該方法無效.

為滿足數(shù)據(jù)Cache功耗和性能的雙重要求，本文提出了一種熱點自搜索的數(shù)據(jù)Cache訪問方法.本文的主要內(nèi)容包括:(1)研究數(shù)據(jù)Cache訪問規(guī)律，發(fā)現(xiàn)熱點行數(shù)目平均僅占數(shù)據(jù)Cache的訪問次數(shù)的0.4%，卻為程序提供了80.4%的數(shù)據(jù)，并有短時間內(nèi)被頻繁訪問的規(guī)律.(2)針對Cache訪問熱點集中的規(guī)律，提出一種熱點自搜索數(shù)據(jù)Cache的低功耗訪問方法.通過追蹤程序熱點行，自動緩存熱點程序訪問的路選擇信息，高效過濾冗余存儲器訪問.(3)進一步，為同時優(yōu)化數(shù)據(jù)Cache的性能和時序，復合使用空間信息和時間信息索引歷史軌跡，提升索引效率.(4)通過對EEMBC測試程序的測試，基于本方法的Cache與基于MRU的路預測方法的Cache相比動態(tài)功耗降低30.77%，性能提升26.21%.

2　數(shù)據(jù)Cache訪問規(guī)律研究

高速緩存的訪問是以路為單位進行的.通過對主流嵌入式測試基準程序EEMBC的分析，發(fā)現(xiàn)程序所訪問數(shù)據(jù)高速緩存行數(shù)目與存儲載入指令的數(shù)目的比例小于2%(如表1)，程序數(shù)據(jù)訪問具有良好的空間局部性，其中熱點緩存行(定義同文獻［8］)數(shù)目小于20%(如圖1(a))，說明高速緩存行的訪問空間集中在少數(shù)熱點緩存行.通過實時監(jiān)測發(fā)現(xiàn)，每百條連續(xù)的存儲載入指令平均訪問的緩存行數(shù)目少于10行(如圖1(b))，熱點緩存行在短時間內(nèi)被頻繁訪問，Cache訪問的時空局部性明顯.

表1　訪問數(shù)據(jù)高速緩存行數(shù)目與存儲載入指令的數(shù)目的比例

3　過濾訪問方法

基于數(shù)據(jù)Cache熱點訪問集中的特點，本文提出了一種硬件自搜索熱點行，從而低功耗訪問數(shù)據(jù)Cache的方法.該方法的核心思想是:(1)自動緩存存儲載入指令的訪問地址以及路選擇信息，使用緩存的信息過濾后續(xù)相同行的Cache訪問操作，避免標簽路以及冗余數(shù)據(jù)路訪問;(2)利于訪問頻度閾值判定方法，主動跟蹤程序，判定所訪問數(shù)據(jù)是否屬于熱點程序，并自動搜索熱點程序后續(xù)鄰近行的路選擇信息;(3)Cache的過濾與訪問操作串行完成，失敗的過濾操作正常訪問數(shù)據(jù)Cache，避免性能和功耗損失;(4)使用時空復合高效索引，過濾操作不增加額外延時.具體實現(xiàn)方式描述如下:

過濾操作通過歷史軌跡單元實現(xiàn)，該單元記錄熱點存儲載入指令所在高速緩存行的地址和路選擇信息.當后續(xù)存儲載入指令執(zhí)行時，首先與歷史軌跡單元所記錄的地址進行匹配，若地址匹配，則根據(jù)記錄的路選擇信息，僅訪問所記錄的Cache數(shù)據(jù)路，過濾其他組相連的Cache數(shù)據(jù)路和標簽路的訪問，省略標簽比較過程;若沒有匹配，則將其訪問地址更新存入歷史軌跡單元，正常訪問數(shù)據(jù)Cache，待訪問結(jié)束后將此次訪問的路選擇信息更新回歷史軌跡單元(如圖2).

熱點自搜索操作通過熱點追蹤單元(如圖3)實現(xiàn).熱點追蹤單元主動監(jiān)視歷史軌跡單元中所有行的訪問狀態(tài)，當某行數(shù)據(jù)被訪問時，熱點追蹤單元會提升該行的熱度值，并按越早訪問熱度值越低的原則降低其他行的熱度值.熱度值超過熱點閾值時，熱點追蹤單元會將該行標示為熱點行.被標示的熱點行，熱點追蹤單元會主動訪問數(shù)據(jù)Cache，提取其相鄰行的路選擇信息，緩存在歷史軌跡單元中.當相鄰行數(shù)據(jù)被訪問時，直接使用歷史軌跡單元中的信息過濾標簽路和冗余數(shù)據(jù)路的訪問，并主動觸發(fā)下一相鄰行信息的緩存.當熱度值低于冷卻閾值時，該行被取消熱點行標記，停止預緩存相鄰路的信息.熱點的相鄰行在歷史軌跡單元中使用熱點行的信息進行索引，不耗費冗余資源.

使用存儲載入指令的物理地址索引歷史軌跡單元理論上可以獲得最高的索引效率.但由于存儲載入指令的物理地址需經(jīng)過基址和偏移量運算，通過內(nèi)存管理單元轉(zhuǎn)換虛實地址獲得，難以保證過濾操作在Cache訪問之前完成.本文使用低位虛擬地址進行索引，避免全地址計算和虛實地址轉(zhuǎn)換引入的關鍵路徑.但若僅引入低位地址等空間信息索引，缺乏時間信息，會導致特定程序的索引效率低，具體表現(xiàn)為:當不同程序段的存儲載入指令的低位地址相同出現(xiàn)疊名時，歷史軌跡單元記錄的信息會在疊名的兩條指令中反復抖動.為了降低該損失，索引機制須同時引入時間信息和空間信息進行索引.本文提出利用時間信息(PC、PID)和空間信息(地址)的哈希索引算法，使用高位PC拼接低位地址和PID的方式索引歷史軌跡單元.使用這種時空復合索引的機制可以大幅減少索引歷史軌跡單元所需延時，索引效率和使用存儲載入指令的物理地址的傳統(tǒng)索引方式相差僅為3%.

實現(xiàn)硬件電路如圖4所示.

4　實驗探究

實驗平臺使用CK807效能優(yōu)先嵌入式處理器.該處理器使用自主研發(fā)的C-SKY 16/32位混編RISC指令集，支持指令雙發(fā)亂序執(zhí)行，數(shù)據(jù)Cache大小16KB，四路組相連，每路數(shù)據(jù)256bit，采用LRU替換策略，在tsmc65lp工藝實測頻率達到666MHz.實驗部分基于EEMBC測試基準的典型程序，在實現(xiàn)基于熱點行搜索的低功耗數(shù)據(jù)高速緩存的基礎上，進一步搜索了歷史軌跡單元的深度對過濾效率的影響.

實驗結(jié)果表明深度為4的歷史軌跡單元命中比例在77%左右;深度為8時則大幅提升至86%;深度為16時進一步提升為93%;但由于熱點行訪問的時空局部性明顯，深度為32的歷史軌跡單元命中比例提升不明顯，僅提升1%至94%左右(如圖5).

根據(jù)文獻［13］的結(jié)論，Cache的動態(tài)訪問功耗同比于訪問的位寬和次數(shù)之積.實驗平臺的Cache為四路組相連結(jié)構(gòu)，每次訪問64位數(shù)據(jù)路，88位標簽路，單次過濾成功可減少81%的動態(tài)訪問功耗.針對EEMBC測試程序，深度不同的歷史軌跡單元平均可以減少58%到73%的動態(tài)訪問功耗(如圖6).

為了達到頻率要求(tsmc65lp工藝達到600MHZ以上)，Cache命中的載入指令通常需經(jīng)過地址準備、Cache訪問、數(shù)據(jù)選擇三個時鐘周期.過濾成功時，數(shù)據(jù)選擇的過程可省略，載入指令可在兩個周期內(nèi)完成，后續(xù)數(shù)據(jù)依賴的程序能夠更早獲得操作數(shù)，提速程序運行.該過濾方法針對CK807這個CPU可以提升6.2%的處理器性能(如圖7).

在EEMBC測試程序中，使用深度為16的歷史軌跡單元，熱點閾值設置為4時，熱點行預取的效能最高.其中被自動標識為熱點行的程序占比為22.93%，平均84.83%的數(shù)據(jù)通過熱點行以及其預取的相鄰行實現(xiàn)數(shù)據(jù)Cache的過濾訪問.與不使用熱點自搜索的方法相比，提升了歷史軌跡單元39.97%的命中率(如圖8(a)).本文還提出了空間時間信息復合索引機制.實驗表明，PC信息的引入可以很好的離散索引信息，提升歷史軌跡單元的索引效率(如圖8(b)).

為了降低硬件的實現(xiàn)復雜度和歷史軌跡單元本身的能耗開銷，針對EEMBC基準測試程序，選擇深度為16的歷史軌跡單元能最好地實現(xiàn)數(shù)據(jù)Cache的過濾訪問.在資源相當?shù)那闆r下，與MRU算法［4］和與字選擇方法［12］本文的方法可以提升過濾準確率，且不會造成性能損失.實驗表明數(shù)據(jù)Cache的動態(tài)功耗可降低30.77%(與MRU相比)5.1%(與字選擇相比)，性能提升26.21%(與MRU相比)11.88%(與字選擇相比)(如圖9).

5　總結(jié)

本文提出了一種基于熱點行搜索的數(shù)據(jù)Cache過濾訪問方法.自動搜索熱點程序，緩存熱點行路選擇信息，使用時空信息復合索引被緩存信息，過濾數(shù)據(jù)Cache的訪問.實驗表明，在成本略微增加的前提下，與傳統(tǒng)Cache訪問方法相比，實際動態(tài)訪問功耗降低70.1%，性能提升6.2%;與基于MRU的路預測方法相比，動態(tài)功耗降低30.77%，性能提升26.21%;與基于字選擇的路過濾方法相比，動態(tài)功耗降低5.1%，性能提升11.8%.

參考文獻

［1］Zang W，Gordon-Ross A.A survey on cache tuning from a power/energy perspective［J］.ACM Computing Surveys(CSUR)，2013，45(3): 32.

［2］ZHENG Z，Zhiying W，Li S.Region-based way-partitioning on L1 data cache for low power［J］.IEICE Transactions on Information and Systems，2013，96(11): 2466 -2469.

［3］Xiangyun Z，Lianfeng Z，Dong B.Research on the low power design method for the embedded multi-core processor［A］.2013 Fourth International Conference on Digital Manufacturing and Automation(ICDMA)［C］.IEEE，2013.1141 -1144.

［4］Inoue K，Ishihara T，Murakami K.Way-predicting set-associative cache for high performance and low energy consumption［A］.Proceedings of the 1999 International Symposium on Low Power Electronics and Design［C］.ACM，1999.273 -275.

［5］Chen H C.Design of a low-power way-predicting cache using valid-bit pre-decision strategy［J］.Journal of the Chinese Institute of Engineers，2008，31(5): 805 -814.

［6］Ye J，Ding H，Hu Y，et al.A behavior-based adaptive access-mode for low-power set-associative caches in embedded systems［J］.Journal of Information Processing，2012，20(1): 26 -36.

［7］Kin J，Gupta M，Mangione-Smith W H.The filter cache: an energy efficient memory structure［A］.Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture［C］.IEEE Computer Society，1997.184 -193.

［8］Yang C L，Lee C H.HotSpot cache: joint temporal and spatial locality exploitation for i-cache energy reduction［A］.Proceedings of the 2004 International Symposium on Low Power Electronics and Design［C］.IEEE，2004.114 -119.

［9］Fan L，Wang S，Zheng Y，et al.Low power cache architectures with hybrid approach of filtering unnecessary way accesses［A］.Proceedings of the 2013 International Workshop on Programming Models and Applications for Multicores and Manycores［C］.ACM，2013.93 -99.

［10］張宇弘，王界兵，嚴曉浪，等.標志預訪問和組選擇歷史相結(jié)合的低功耗指令cache［J］.電子學報，2004，32(8): 1286 -1289.Zhang Y，Wang J.Pre-visiting tag and keeping way history to reduce power in instruction cache［J］.Acta Electronica Sinica，2004，32(8): 1286 -1289.(in Chinese)

［11］項曉燕，陳志堅，孟建熠，等.基于鄰行鏈接訪問的低功耗指令高速緩存［J］.浙江大學學報(工學版)，2013，7: 011.Xiang X，Chen Z.Low power instruction cache based on adjacent line linking access［J］.Journal of Zhejiang University(Engineering Science)，2013，7: 011.(in Chinese)

［12］Choi J H，Kwak J W，Jhang S T，et al.Data filter cache with word selection cache for low power embedded processor［A］.Proceedings of the 2013 Research in Adaptive and Convergent Systems［C］.ACM，2013.422 -427.

［13］Kamble M B，Ghose K.Analytical energy dissipation models for low power caches［A］.Proceedings of International Symposium on Low Power Electronics and Design［C］.IEEE，1997.143 -148.

仇徑男，1988年出生于江西省，2010年獲浙江大學電氣工程學院學士學位.現(xiàn)為浙江大學超大規(guī)模集成電路設計研究所博士研究生，主要研究方向為低功耗處理器設計與研究.E-mail: qiujing@ vlsi.zju.edu.cn

羅嘉蕙1989年出生于湖南省，2012年獲浙江大學電氣工程學院學士學位.現(xiàn)為浙江大學超大規(guī)模集成電路設計研究所博士研究生，主要研究方向為處理器體系結(jié)構(gòu)設計與研究.

Low Power Data Cache Based on Hotspot Initiative Search

QIU Jing1，LUO Jia-hui1，XIANG Xiao-yan2，CHEN Zhi-jian1
(1.Institute of VLSI Design，Zhejiang University，Hangzhou，Zhejiang 310027，China; 2.State Key Laboratory of ASIC＆System，F(xiàn)udan University，Shanghai 201203，China)

Abstract:On account of the characteristics that the data cache will be frequently accessed in a short period of time，this paper proposes a low power data cache access methods based on hotspot initiative search and historical access trace.The method will automatically judge hot process，dynamically buffer the target hotspot location information to filter tag and redundant data memory access.Running EEMBC benchmark results show that compared with MRU prediction method(Most Recently Used)this approach can reduce 30.77%dynamic access power，and get 26.21%performance improvement.

Key words:low power; filter access; hotspot initiative search

作者簡介

收稿日期:2014-05-06;修回日期: 2015-02-17;責任編輯:李勇鋒

DOI:電子學報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.016

中圖分類號：TP 302.2; TN 47

文獻標識碼：A

文章編號：0372-2112(2016)01-0110-05