一種基于強化學習的混合緩存能耗優化與評價

范 浩 徐光平 薛彥兵 高 贊 張 樺

1(天津理工大學計算機科學與工程學院 天津 300384)2(智能計算及軟件新技術天津市重點實驗室(天津理工大學) 天津 300384)3(天津中德應用技術大學 天津 300350)

靜態隨機訪問存儲器(static random access memory， SRAM)作為緩存廣泛地使用在現有的計算機體系結構中，它極大地緩解了處理器與內存讀寫速度不匹配問題，提高了計算機性能.但是SRAM也存在缺點，它集成度低、密度小、泄漏功率高.為了緩解這些問題，人們研究了許多新型非易失性存儲器(non-volatile memory， NVM).新型非易失性存儲器可實現更高的單元密度、更低的泄漏功率和更低的成本.目前，自旋轉移力矩隨機存取存儲器(spin transfer torque RAM， STT-RAM)有可能成為領先的存儲技術，具有比SRAM更高的單元密度、更低的泄漏功耗.

然而，STT-RAM也存在高寫入能量、高寫入延遲的缺點.特別是，它在寫操作期間會產生磨損，從而限制了可以為每個單元執行的最大寫操作次數.這些缺點限制STT-RAM的使用和性能的發揮.因此許多人在研究如何解決這些問題，從而更好地使用STT-RAM.

目前的研究主要集中在將SRAM和STT-RAM相結合組成混合緩存(SRAM/STT-RAM)，充分利用SRAM和STT-RAM各自的優勢設計優化數據存儲策略.混合緩存結合了SRAM和STT-RAM各自的優點.一方面，由于SRAM的寫入能量和寫入延遲小于STT-RAM的寫入能量和寫入延遲，混合緩存有助于減少STT-RAM的寫入能耗和寫入延遲，從而降低動態能量消耗.另一方面，由于STT-RAM的單元密度大于SRAM和STT-RAM的泄漏功率小于SRAM，在同等面積下混合緩存能提供比SRAM更大的緩存容量和更低的泄漏功率.

在混合緩存中，緩存分為SRAM區域和STT-RAM區域，并且經常寫入的塊(寫密集塊)被分配到SRAM區域以減少STT-RAM區域的寫入次數.以前的策略僅根據操作類型(讀/寫)[1-3]來確定寫密集型數據，將寫密集型數據放入SRAM中，過于簡單且效果差.沒有考慮到SRAM的容量要小于STT-RAM并占混合緩存中很小一部分，過多地將寫密集性數據放入SRAM，可能會增加混合緩存未命中率，降低性能.因此，為不增加混合緩存的未命中率，可以考慮將一部分包含寫操作數據放入STT-RAM中，但是需要控制好界限(確定哪些數據分配到STT-RAM)，因為過多地往STT-RAM寫入數據會增加寫入延遲和寫入能量.因此，在不增加混合緩存的未命中率和減少對STT-RAM寫入次數之間的權衡，是混合緩存設計中的重要挑戰.

本文利用緩存訪問請求的寫入強度(定義見第3節)和重用信息，提出來一種基于能耗的強化學習緩存分配策略，將緩存分配到SRAM區域或者STT-RAM區域中.該分配策略是在不增加混合緩存未命中率的情況下有利于減少STT-RAM的寫入次數，從而有效地降低了緩存系統的能耗.

在設計分配策略前，緩存的數據收集必不可少.首先，通過對緩存行進行分類，將具有相似性質的緩存行聚集在一起.然后，在緩存行集合下收集緩存行的寫入強度信息和重用信息，根據這些信息計算出緩存行集合的能耗.

分配策略就是將緩存行集合中緩存行分配到能耗小的區域(權重大的區域).關鍵思想是使用強化學習對緩存行集合的能耗進行學習，得到該集合分配到SRAM區域或者STT-RAM區域的權重，將集合中的緩存行分配到權重大的區域.實驗評估表明，與單核和四核系統中現有的方法相比，我們所提出的策略分別降低了16.9%和9.7%的能耗.

1 相關工作

目前針對STT-RAM的研究提出各種優化方法[4].主流的優化方法是結合SRAM低寫入能量以及STT-RAM低泄漏功率和大容量的優點提出混合緩存架構.這些研究主要目標是減少STT-RAM寫入次數、降低混合緩存能耗，從而提高混合緩存的性能.

Wu等人[5]提出了一種基于飽和計數器的方法，通過使用每個塊的飽和計數器識別訪問密集型塊，用于檢測和將寫密集型數據遷移到SRAM區域，并將讀密集型數據遷移到非易失性隨機訪問存儲器(non-volatile RAM， NVRAM)區域.他們在每條SRAM高速緩存行中添加了一個粘性位，以使LRU塊可以進行第2次更改以保留在SRAM中，從而避免了過于頻繁的數據遷移.在他們的方法中，飽和閾值被設置為3.Li等人[6]提出了一種基于編譯器輔助的方法識別遷移密集型數據塊，并將遷移密集型數據塊優先選擇分配到混合緩存的SRAM部分，以減少遷移帶來的開銷，提高混合緩存的性能和能效.此外，他們還提出了一種數據分配技術以提高優選緩存的效率.Ahn等人[7]提出來一種基于PC的方法，通過跟蹤傾向于加載寫密集型塊的高速緩存未命中指令，并設計一個新的成本模型來預測未命中緩存塊的寫強度閾值，將成本高于或者等于寫強度閾值的緩存塊放入SRAM區域.在他們的方法中，寫成本閾值可以動態調整，自動適應每個程序.

Peled等人[8]采用了一種特定的強化學習模型，稱為上下文相關的賭博機(contextual bandits)[9-10]，然后將捕獲的編譯器注入的提示獲得的許多軟件屬性和CPU捕獲的一些硬件屬性用于訓練和執行基于上下文相關的賭博機模型的算法，以識別上下文狀態和內存地址之間的高級關系并預測未來的內存訪問.Ipek等人[11]提出了一種基于強化學習的自我優化的內存控制器設計.該設計使用強化學習原理進行操作，克服傳統內存控制器采用固定的、剛性的訪問調度策略來設計平均情況下的應用行為問題.因為基于強化學習的內存控制器會連續不斷地運行，并會根據與系統的相互作用自動調整其DRAM命令調度策略，以優化性能.

上述部分工作提出的策略僅基于寫入強度來區分讀寫密集型，將寫密集型數據分配到SRAM中，將讀密集型數據分配到STT-RAM中.這些策略過于簡單，也不能準確識別寫密集型數據塊.還有部分工作提出的策略是根據編譯時的信息識別寫密集型數據.這些策略過于靜態，也沒有將程序的動態特性進行考慮.先前的大多數工作都只是根據寫入強度來區分緩存讀寫密集型，并預測緩存行分配到的區域(SRAM或STT-RAM).但是僅僅依賴寫入強度，不足以完全區分讀寫密集型數據.而且也沒有考慮混合緩存中SRAM容量與STT-RAM容量的差異，SRAM區域只占混合緩存較小的一部分，其容量較小.因此，需要綜合考慮寫入強度，混合緩存中SRAM和STT-RAM的容量差異對混合緩存能耗和性能造成的影響.目前，強化學習也用來處理現實世界資源分配問題[8，11-12]，使得資源利用最大化.在混合緩存結構下，基于強化學習的數據分配策略可以更準確地區分數據寫入強度，自動調整數據分配區域，更好地優化混合緩存性能.

2 研究背景和動機

2.1 研究背景

1) 新型非易失緩存存儲器

非易失性存儲器具有與傳統易失性存儲器相媲美的性能，但是有著更高的密度和更低的泄漏功率.然而，非易失性存儲器通常在寫入能量以及耐用性方面與傳統易失性存儲器有著較大差距.目前最成熟的NVRAM技術包括相變存儲器(phase change memory, PCM)、阻變存儲器(resistive RAM, ReRAM)和自旋轉移力矩隨機存取存儲器(STT-RAM)等[13].STT-RAM通常被認為是緩存的最佳匹配，因為它具有較低的讀取延遲(接近SRAM的讀取延遲)和預計每個單元實現4×1012次寫入的耐久性[14].為了充分發揮SRAM和STT-RAM的性能，研究員將SRAM與STT-RAM相結合設計一種混合緩存，試圖獲得兩全其美的優勢：SRAM較小的寫入能量和寫入延遲，STT-RAM更高的緩存容量和更低的泄漏功率.

STT-RAM是新一代磁阻隨機存取存儲器(magnetic RAM， MRAM).STT-RAM單元不使用電荷來存儲數據，而是使用磁隧道結(magnetic tunnel junction， MTJ)存儲數據，由2層不同厚度的鐵磁層及一層幾個納米厚的非磁性隔離層組成，通過自旋電流實現信息寫入的.因此，STT-RAM是一種具有接近零泄漏功耗、存儲密度高、讀取速度快的非易失性存儲器.與基于電荷的存儲器(例如SRAM和DRAM)相比，STT-RAM具有更低的泄漏功率和更好的可擴展性.從表1可以看出SRAM和STT-RAM之間讀寫延遲、能耗和密度的差異.

2) 強化學習

強化學習[15-17]是機器學習的一個重要方法，其原理是代理與環境進行交互，以試圖將環境控制到能夠獲得最大回報的最佳狀態.強化學習的任務通常可以描述為Markov決策過程(Markov decision process， MDP)，但是狀態空間、明確的轉移概率和獎勵函數并不是必需的[18].它具有自我管理和在線學習的特性.因此，強化學習是一種新興的解決方案，用于基于統計估計和預期長期效用的最大化來做出決策(例如文獻[16]).多臂賭博機(multi-armed bandit, MAB)[8-10]問題是一種經典的強化學習問題.MAB問題也是一種序列決策問題，這種問題需要在一系列決策中選擇最有利的決策，從而使長期收益最大化.MAB適合解決動態資源分配問題.目前在處理器調度、存儲管理中得到一些研究和應用.

Fig.1 Effect of write intensity on L2 cache圖1 寫入強度對L2緩存的影響

本文使用MAB的變體探索在線強化學習，并將在線強化學習和遺憾最小化引入到混合緩存中設計緩存分配策略.然而，本文使用的理論框架不同于常規在線學習方法，因為在任何給定時間做出的關于決策的反饋是延遲的而不是瞬時的.我們的算法中只維持2個基本動作的概率分布：緩存分配到SRAM區域的概率和分配到STT-RAM區域的概率.因此，我們算法的目標是“學習”系統的每個狀態的“最佳”概率分布，從而達到遺憾最小化.整個算法通過將緩存行分配到能耗較小的區域(SRAM或STT-RAM)，接著通過緩存行的特性進行反饋，使得整個過程遺憾最小，每次緩存行分配都是“最佳”的，從而減少混合緩存的能耗，提升混合緩存性能.

2.2 研究動機

混合緩存設計能充分發揮SRAM和STT-RAM的性能，但是先前的策略[1-2，5，7，19-20]僅僅通過寫入強度區分讀寫密集型數據，將寫密集數據分配到SRAM中、讀密集型數據分配到STT-RAM中.但是在混合緩存中SRAM容量較小，僅基于寫入強度分配數據可能導致SRAM未命中率增加，從而增加混合緩存未命中率，影響混合緩存性能.因此可以增加寫入強度界限，將一部分含寫操作數據分配到STT-RAM中，這樣可以降低SRAM未命中率，不增加混合緩存未命中率甚至可能提高了混合緩存命中率.但若是寫入強度界限過高會過多地增加STT-RAM的寫入次數，從而增加L2寫入能量和寫入延遲.因此混合緩存分配策略設計中重要的挑戰是在不增加混合緩存未命中率的情況下有利于減少STT-RAM的寫入次數.

圖1顯示了在兩級緩存層次結構下從PARSEC 3.0基準ferret獲得的實驗證據.在此圖中，x軸為寫入強度；y軸顯示在以寫入強度等于0時為基準，在不同寫入強度下，L2 Energy，DRAM Energy，L2 Miss Rate的變化.從圖1中可以看出，隨著寫入強度的增加，L2未命中率和DRAM能耗都在降低，而L2能耗卻在增加.這主要是因為將一部分緩存行(有過寫操作的)分配到了STT-RAM中，減少了SRAM的壓力，從而降低了L2未命中率，減少訪問內存的次數，降低了DRAM能耗.然而，這樣卻增加了STT-RAM的寫入次數，從而增加了L2寫入能耗.當寫入強度大于0.45時，L2未命中率基本不再改變.寫入強度繼續增大并不能再降低DRAM能耗和L2未命中率，卻會繼續增加STT-RAM寫入次數，繼而增加L2能耗.這意味著寫入強度影響著混合緩存的未命中率，影響著STT-RAM的寫入次數，影響著混合緩存的能耗.因此需要選擇一個合適的寫入強度，在不增加混合緩存未命中率的情況下有利于減少STT-RAM的寫入次數.

我們設計一種基于能耗以及緩存的寫入強度和緩存重用，使用強化學習的緩存分配策略.通過緩存行的寫入強度信息和重用信息，計算出緩存行集合放入SRAM和STT-RAM所花費的能量，將集合中緩存行分配到所需能量低的區域.這種分配策略在不增加混合緩存未命中率的情況下有利于減少STT-RAM的寫入次數，從而提高混合緩存的性能.

3 系統結構

本文利用緩存訪問請求的寫入強度(讀寫信息)和重用信息，提出強化學習混合緩存(reinforcement learning hybrid cache, RLHC)架構，一種基于能耗和強化學習的緩存分配策略.

首先給出緩存行的寫入強度和重用概念.寫入強度是針對混合緩存提出來的概念，規定了緩存行分配到STT-RAM的界限.緩存分配策略將高寫入強度的緩存行分配到SRAM中、低寫入強度的緩存行分配到STT-RAM中.我們將寫入強度定義為緩存行在指定窗口期(規定的訪問次數)內寫操作數占總操作數的比例.寫操作次數越多，寫入強度越高.寫入強度越高，緩存行分配到SRAM的條件越嚴.如當寫入強度為1時，緩存行在窗口期內全部為寫時才能分配到SRAM區域，其他情況緩存行都會被分配到STT-RAM.這種情況會導致過多的緩存行分配到STT-RAM，STT-RAM寫入次數過多，增加寫入能量和寫入延遲，影響整體性能.正式地，寫入強度定義為

(1)

其中，write_intensiy為寫入強度；write_counts為在窗口期內緩存行的寫操作次數；window_size為窗口期大小，也為緩存行總操作數(緩存行讀操作次數與寫操作次數相加).

重用是預測緩存行在SRAM區域或者STT-RAM區域中命中的可能性.對其分為短、中、長3類.在SRAM區域中命中(短重用)，在STT-RAM中命中(中等重用)或在2個區域中都未命中(長重用).圖2顯示了如何判斷重用.

Fig.2 Reuse judgment logic圖2 重用判斷邏輯

圖3給出了混合緩存系統的整體組織架構.該架構由混合緩存和分配預測器組成.與其他混合緩存架構類似，每個高速緩存集分為SRAM區域和STT-RAM區域.數據區域由SRAM和STT-RAM組成，標簽區域僅由SRAM構成[21-22].分配預測器存儲開銷小，需頻繁讀寫，因此也由SRAM構成.

混合緩存架構的整個思想就是在緩存行未命中時，在分配預測器中查找該緩存行的分配策略，然后將未命中的緩存行分配到合適的位置(SRAM或者STT-RAM).圖3左側為分配預測器，展示了RLHC算法框架.RLHC算法框架可以分為數據收集、反饋和預測部分.首先是數據收集，對未命中緩存行的miss-PC進行Hash得到一個簽名，然后記錄下該緩存行的讀寫信息(讀或者寫操作)和重用信息.接著是反饋，在窗口期結束后通過收集的信息，計算出該緩存行放入SRAM區域和STT-RAM區域的能耗，以及讀寫特性(read-only， RO；write-only， WO；read-write， RW).其中，RO表示緩存行集合中緩存行在窗口期內全為讀操作，WO表示緩存行全為寫操作，RW表示緩存行讀寫操作均有.最后是預測，根據反饋階段得到的SRAM區域和STT-RAM區域的能耗，選擇更新能耗較小區域的權重，利用讀寫特性進行獎勵，使遺憾最小化.最后計算出SRAM區域和STT-RAM區域的權重，緩存行則分配到權重大的區域.我們算法的目標是“學習”系統的每個狀態的“最佳”概率分布.在每次分配緩存行時，將緩存行分配到“最佳”的區域(SRAM或STT-RAM)，從而使整個過程遺憾最小化.從整體設計來看，在混合緩存中應該將緩存行分配到合適的位置，從而減少STT-RAM寫入次數，并且不增加混合緩存未命中率，進而減少混合緩存能耗.本文設計的算法目標是使緩存行分配到“最佳”區域，表現出的特征就是整個混合緩存能耗“最低”，并在不增加混合緩存未命中率的情況下有利于減少STT-RAM的寫入次數.同時基于強化學習的緩存分配策略能根據能耗，自動調整SRAM區域和STT-RAM區域的權重，更好地適應各種工作負載.

Fig.3 Architecture of RLHC圖3 RLHC架構

在設計混合緩存分配策略時，關鍵的問題有：

1) 如何有效地識別緩存的寫入強度？

2) 如何有效地收集所需緩存的信息？

3) 如何將分配策略設計得更加高效？

將在下一部分詳細描述解決方法.

4 系統設計與實現

本節詳細地介紹基于強化學習的混合緩存分配策略設計整體實現方法.整個設計中主要從緩存行的分類、緩存的狀態信息收集、分配策略設計和死區預測這4個方面進行介紹.

4.1 緩存行的分類

當前混合緩存設計的主要挑戰之一是如何在緩存行粒度下判斷其屬性(寫入強度和重用).因為必須通過觀察緩存行的多次訪問才能確定其屬性，然后才能存儲緩存行的屬性，這一過程需要花費足夠長的時間.而且存儲開銷與高速緩存中的緩存行的數量成正比.因此，我們以緩存行為粒度進行學習，會耗時嚴重、存儲開銷大，導致學習成本高.為了解決這個問題，我們對緩存行進行分類，以集合為粒度進行學習.一個集合代表一類緩存行.具體來說，我們為每個緩存行分配一個簽名，并將具有相同簽名的緩存行分類到一個集合中，然后通過收集集合中緩存行的信息來確定整個集合的屬性，從而將集合的屬性應用于該集合中的緩存行.以集合為粒度能加快學習速度并減少元數據存儲.

緩存行集合定義就是具有相同簽名的所有緩存行，因此我們需要對緩存行分配一個簽名.先前的工作已經提出了各種方式生成緩存行簽名，包括指令、指令序列、存儲區域、地址、頁面偏移、首次訪問數據的指令，以及上述的各項的組合[7，22-25].我們選擇導致高速緩存行未被加載到高速緩存中的指令miss-PC作為簽名.先前的工作也證明了miss-PC作為緩存行簽名與寫入強度(Ahn等人[7])和重用(Sembrant等人[24])相關.

圖4顯示了以miss-PC作為簽名對PARSEC 3.0中的3個數據集進行分類的結果.3個數據集代表不同的訪問模式，blackscholes(讀占95%)為讀密集型，facesim(寫占72%)為寫密集型，swaptions(讀占55%)為讀寫均勻型.為方便展示，只統計了這3個數據集在L2中訪問次數前十的集合.集合里基本上只有一種操作，如blackscholes前5個集合都是讀，facesim前4個都是寫.這表明基于miss-PC的簽名能夠有效地識別緩存行寫入強度，我們的分類方法是有效的.

Fig.4 Classification based on miss-PC signature圖4 基于miss-PC簽名的分類

4.2 緩存的狀態信息收集

我們的策略是以集合為學習粒度，需要收集集合中每個緩存行的寫入強度和重用信息，并根據這些信息計算出SRAM區域和STT-RAM區域的能耗，使用強化學習算法進行學習，得出該集合分配到SRAM區域和STT-RAM區域的權重，最后得出該集合的分配策略.我們針對不同的工作負載實驗不同的窗口期大小.我們發現將窗口期大小設置為20時，我們的策略在不同的工作負載下都能取得一個較好的性能，并且緩存行訪問信息的存儲開銷較小.當緩存行集合收集了20次訪問信息便會重置以前收集的信息，重新收集訪問信息.

每次緩存行訪問時收集2條信息：緩存行操作類型信息和重用信息.這些信息都記錄在緩存行對應的集合里.1)緩存行操作類型.記錄緩存行訪問時是讀還是寫.2)重用.記錄緩存行在SRAM區域還是STT-RAM區域命中或者未命中.

收集的數據信息存儲在分配預測表中.該表不僅存放收集的數據，還存放緩存行集合分配策略、死區標簽、權重信息.圖5展示預測表中一個元素的結構.Signature為緩存行miss-PC簽名，當緩存行未命中時，根據miss-PC簽名在表中查找分配策略，然后按照分配策略將緩存行分配到指定區域.先前的研究[7]已經使用12個最低有效位來存儲miss-PC標簽.為了避免存儲完整miss-PC的開銷，我們也使用12個最低有效位，也觀察到與存儲完整的miss-PC具有基本相同的精度(在1%內).History Window記錄該集合中所有緩存行的訪問信息(寫入強度和重用).P代表該集合的分配策略；D為該集合的死區計數器，判斷該集合是否為死區，從而判斷是否需要繞過.Signature為低12 b miss-PC,History Window由6個計數器組成，每個計數器5 b，SRAM Weight和STT-RAM Weight各占4 b，分配策略(P)占2 b和死區飽和計數器(D)占2 b，共54 b/每元素.預測表被設計為LRU緩存，共256個元素，存儲在SRAM中，這導致1.69 KB SRAM緩存.

Fig.5 Structure of prediction table entry圖5 預測表entry結構

能耗計算.根據圖5所示的預測表中的信息計算出能耗.表2顯示了如何結合重用信息計算出SRAM區域能耗.重用確定了需要記錄(統計)的區域.例如一次短讀，SRAM區域記一次SRAM讀；一次中讀，SRAM區域記一次DRAM讀.表3顯示了如何結合重用信息計算出STT-RAM區域能耗.

每種能量類型的能量總和相加就是該區域的能耗.讀寫能量可能不一樣，因此每種能量類型還得區分讀寫.

Power=(Nt_r×Et_r+Nt_w×Et_w)+
(Nsram_r×Esram_r+Nsram_w×Esram_w)+
(Nstt-ram_r×Estt-ram_r+Nstt-ram_w×
Estt-ram_w)+(Ndram_r×Edram_r+
Ndram_w×Edram_w),

(2)

其中，Nt_r:讀Tag的次數；Et_r:讀一次Tag所需的能量；Nt_w:寫Tag的次數；Et_w:寫一次Tag所需的能量；Nsram_r:讀SRAM的次數；Esram_r:讀一次SRAM所需的能量；Nsram_w:寫SRAM的次數；Esram_w:寫一次SRAM所需的能量；Nstt-ram_r:讀STT-RAM的次數；Estt-ram_r:讀一次STT-RAM所需的能量；Nstt-ram_w:寫STT-RAM的次數；Estt-ram_w:寫一次STT-RAM所需的能量；Ndram_r:讀DRAM的次數；Edram_r:讀一次DRAM所需的能量;Ndram_w:寫DRAM的次數；Edram_w:寫一次DRAM所需的能量.

Table 2 Calculation of Energy Consumption of SRAM Under Reuse表2 SRAM在重用下能耗的計算

Table 3 Calculation of Energy Consumption of STT-RAM Under Reuse表3 STT-RAM在重用下能耗的計算

4.3 緩存分配策略設計

在4.2節中講了如何收集訪問信息以及如何計算集合的能耗.我們的分配策略是使用強化學習算法學習，得出該集合分配到SRAM區域和STT-RAM區域的權重，最后得出該集合的分配策略.本節主要講如何使用已有的強化學習算法設計一個分配策略.

本文使用的強化學習算法不同于常規在線學習方法，因為在任何給定時間做出的關于決策質量的反饋是延遲的而不是瞬時的.我們的算法使用在線強化學習和遺憾最小化[26-29]，維持著分配到SRAM區域和STT-RAM區域的概率分布.

我們利用強化學習算法設計的分配策略見算法1.權重開始是相等的，盡管我們可以通過緩存行操作類型(讀寫)來初始化.其中，遺憾(t)可以用緩存行集合的讀寫特性來描述.因為STT-RAM區域大于SRAM區域，我們更傾向于把偏讀的緩存行集合放入STT-RAM區域.緩存行集合的讀寫特性偏讀時遺憾(t)更小.緩存行集合的讀寫特性是根據統計窗口期里的讀寫操作確定的，分別為RO，WO，RW.當RO時t=1，WO時t=2,RW時t=3.其中λ是學習率(最初為0.45)，d是折扣率(最初為0.0051/N，其中N為高速緩存大小)，獎勵值r=dt.ratio是根據集合讀寫特性來定的.當為RO時，緩存行集合中緩存行全為讀，更傾向于放入STT-RAM區域，因此ratio=1.05；當為WO時，緩存行集合中緩存行全為寫，更傾向于放入SRAM區域，因此ratio=0.95；當為RW時，緩存行集合中緩存行有讀有寫，無偏向性，ratio=1.0.

算法1.SRAM與STT-RAM權重計算.

輸入：SRAM能量sram_energy、STT-RAM能量stt-ram_energy、學習率λ、折扣率d、SRAM權重Wsram、STT-RAM權重Wstt-ram；

輸出：更新后的SRAM權重和STT-RAM權重.

①tRO or WO or RW；

②rdt；

③ ifratio×sram_energy>stt-ram_energythen

④Wstt-ramWstt-ram×eλ×r； /*增加

STT-RAM權重*/

⑤ else then

⑥WsramWsram×eλ×r； /*增加SRAM

權重*/

⑦ end if

⑧WsramWsram/(Wsram+Wstt-ram)；

⑨Wstt-ram1-Wsram.

通過一個例子來解釋我們的分配策略.表4和表5中的數據不代表真實數據，只是為了方便計算和演示.表4展示了每次訪問不同區域所需的讀寫能量.表5展示了緩存行集合A的訪問統計,該集合讀寫特性為RW.由表4和表5可以得出SRAM區域和STT-RAM區域的能耗.

Table 4 Reading and Writing Energy in Different Regions表4 不同區域的讀寫能量

Table 5 Access Statistics of Cache Set A表5 緩存集合A的訪問統計

Esram=1×Etag_r+2×Esram_r+
1×Edram_w+1×Edram_r=421,
Estt-ram=1×Etag_r+1×Etag_w+1×
Estt-ram_r+1×Estt-ram_w+1×Edram_r=272.

根據算法2中Wstt-ramWstt-ram×eλ×r(初始權重都為0.5)得出Wstt-ram=0.78；然后歸一化得出SRAM權重為0.39，STT-RAM權重為0.61.因此緩存行集合A中緩存行應該分配到STT-RAM區域.

4.4 緩存死區預測

L2中有部分緩存行只被訪問過一次便不再訪問，這些緩存行占用了L2存儲空間，極大影響了L2性能.已經開發了許多方法來繞過死數據，為實時數據留出更多空間并提高整體命中率[30-33].我們可以使用旁路技術繞過死區，從而減少L2中死區數量，提高L2效率.

我們增加了死區預測，了解緩存集行合是死還是活，并適當地繞過它.因此，我們對緩存行增加一個重用位(1 b)，為緩存行集合增加一個死區計數器(2 b),其初始值為11.每次驅逐緩存行時，判斷緩存行是否重用，如果重用則遞減計數器，否則遞增計數器.當死區計數器飽和(值為11)時，確定緩存行集合已死，在緩存行集合的策略中標記，并繞過緩存行集合的后續數據提取.

4.5 小 結

本節分析了緩存行的分類、緩存的狀態信息收集、分配策略設計和死區預測.圖6顯示了我們整個的分配策略.其中，Default代表緩存行為讀操作則分配到STT-RAM，若為寫操作則分配到SRAM.

5 實驗分析與結果

5.1 模擬器配置

我們使用內部跟蹤驅動模擬器評估RLHC在單核和四核系統下性能.高速緩存層次結構由32 KB，4/8路組關聯專用L1指令/數據高速緩存和每核1 MB，16路組關聯共享L2高速緩存組成，其塊大小為64字節.緩存一致性由MESI協議管理，而不強制包含屬性.混合緩存配置為具有4路SRAM和12路STT-RAM,單核下L2為1 MB，四核下L2為4 MB.

我們提出的混合緩存架構應用于L2高速緩存，并與預測混合緩存(prediction hybrid cache， PHC)[7]的靜態版本進行比較.表6顯示了我們的評估比較的4種策略.除非另有說明，否則所有結果都將歸一化為STT-RAM基線.

Table 6 Evaluated Hybrid Cache Policies表6 評估的混合緩存策略

為了更公平地比較我們的策略和先前的研究結果，這里使用了與先前研究結果[7]相同的SRAM和STT-RAM參數.表7顯示了L2緩存的能量和延遲由CACTI 6.5[34]和NVSim[35]在45nm下建模的得到.

Table 7 Characteristics of L2 Cache表7 L2緩存的特征

在系統結構中，額外的存儲開銷主要由緩存行存儲的12 b miss-PC簽名構成.單核系統存儲開銷包含預測表(1.69 KB)、緩存行存儲的12 b miss-PC簽名(24 KB)和緩存行存儲的一位重用位(2 KB)，總計27.69 KB.緩存行簽名和緩存行重用位的開銷在四核系統中增加了4倍，因為緩存容量增加了4倍，而預測器表的大小保持不變，即總計105.69 KB.總之，我們的策略在單核(四核)系統中引入了2.7%(2.6%)的存儲開銷.

5.2 工作負載

我們使用來自PARSEC3.0[36]的13個基準測試作為單核和多核工作負載.PARSEC3.0是一個由多線程程序組成的基準套件.該套件專注于新興的工作負載，旨在代表芯片多處理器的下一代共享內存程序.PARSEC3.0工作負載以涵蓋不同領域的應用程序，例如計算機視覺、媒體專業處理、計算財務、企業服務器和動畫物理學.表8對PARSEC3.0主要特征進行了定性總結.我們使用Pin[37]在中等輸入大小下為每個PARSEC3.0基準測試生成10億條追蹤指令.

Fig.7 L2 energy breakdown under the single-core system圖7 在單核系統下L2能耗分解

Table 8 Qualitative Summary of Key Characteristics of PARSEC 3.0[36]
表8 PARSEC3.0關鍵特征的定性總結[36]

ProgramApplicationDomainParallelGranularityWorkingSetblackscholesFinancial AnalysiscoarsesmallbodytrackComputer VisionmediummediumcannealEngineeringfineunboundeddedupEnterprise StoragemediumunboundedfacesimAnimationcoarselargeferretSimilarity SearchmediumunboundedfluidanimateAnimationfinelargefreqmineData MiningmediumunboundedstreamclusterData MiningmediummediumswaptionsFinancial AnalysiscoarsemediumvipsMedia Processingcoarsemediumx264Media Processingcoarsemedium

5.3 單核上L2能耗

本節首先評估L2在不同策略下的單核系統能耗，分析這些策略對STT-RAM寫入次數、L2動態能耗和L2性能的影響，并將我們所提出的策略與SRAM基線、STT-RAM基線和PHC策略分別進行比較.

圖7顯示了不同策略在單核系統下L2的能量分解，并與STT-RAM基線進行了對比.其中每條被分解為L2緩存靜態能量消耗、L2緩存動態能量消耗.其中L2緩存動態能量消耗又被分為SRAM寫能量消耗、SRAM讀能量消耗、STT-RAM寫能量消耗和STT-RAM讀能量消耗.如圖7所示，前3個數據集(blackscholes,bodytrack,raytrace)SRAM基線的L2能耗高于其他3條(STT-RAM，PHC，RLHC).這主要是因為這3個數據集在L2訪問主要為讀操作，且讀操作占比均超過95%.再加上STT-RAM在讀性能上略好于SRAM，泄漏功率只有SRAM的15.7%.這些原因導致SRAM基線在這3個數據集下L2能耗過高.其他的10個數據集，SRAM基線L2能耗比STT-RAM基線要低，主要得益于寫操作變多了，STT-RAM寫能量超過SRAM的7倍，導致STT-RAM基線中寫能量過大.混合緩存表現很好，在這些數據集下混合緩存L2能耗基本都小于STT-RAM基線.這是因為混合緩存結合了SRAM和STT-RAM的優點(相比SRAM具有更低的泄漏功率和相比STT-RAM具有更低的寫入延遲和寫入能量).總體而言，與STT-RAM基線相比，我們的策略將L2的能耗降低了28.1%，這得益于減少了STT-RAM的寫入次數，從而降低了STT-RAM的寫入能量.與PHC相比，我們的策略將L2的能耗降低了16.9%.這主要是我們的策略能更好地減少STT-RAM的寫入次數，從而減少寫入能量.

Fig.8 L2 STT-RAM writes under single-core system圖8 在單核系統下L2 STT-RAM寫入次數

圖8顯示了在不同策略下L2中STT-RAM的寫入次數.PHC和RLHC分別減少了19.9%和49.1%的寫入次數.而我們的策略比PHC多減少了29.2%的STT-RAM的寫入次數.因此我們的策略更好地降低了L2能耗.與PHC相比，我們的策略將L2的能耗降低了16.9%，同時我們的策略訪問DRAM的能耗比PHC只高了0.3%.

5.4 單核上L2性能

圖9、圖10分別顯示了不同策略在單核系統下L2的AMAT和IPC.與STT-RAM基線和PHC相比，我們的策略分別將L2的AMAT降低了2.2%和1.3%.同時，與STT-RAM基線和PHC相比，我們的策略將系統性能分別提高了1.9%和1.1%.PHC和RLHC性能好于STT-RAM，是因為混合緩存中有SRAM，降低了STT-RAM寫延遲過高的影響.而PHC和RLHC這兩者的性能都略差于SRAM基線，不超過3%.這是因為混合緩存中STT-RAM寫延遲過高，降低了性能.

Fig.9 L2 AMAT under single-core system圖9 在單核系統下L2 AMAT

Fig.10 L2 IPC under single-core system圖10 在單核系統下L2 IPC

5.5 多核上L2能耗

本節我們評估L2在不同策略下四核系統的能耗.四核配置與單核中的配置類似，只是L2的容量是單核系統下的4倍.

圖11、圖12分別顯示了不同策略在四核系統下L2的能耗分解和STT-RAM的寫入次數，并與STT-RAM基線進行了對比.超過半數的數據集，SRAM基線L2能耗都高于STT-RAM基線.主要是因為在四核系統中，SRAM的泄漏功率是STT-RAM的8.9倍，而且讀取能量是STT-RAM的2.25倍.再加上這些數據集偏向讀，近半數的數據集讀操作占比超過75%.特別是blackscholes(讀操作占98%)，bodytrack(讀操作占95%)，raytrace(讀操作占99%)，x264(讀操作占86%)這4個數據集，SRAM基線的L2能耗遠高于其他3條(STT-RAM,PHC,RLHC).這是因為讀操作太多，SRAM低寫入能量的特性無法發揮.混合緩存表現不錯，在大多數數據集下混合緩存L2能耗要小于STT-RAM基線，在少數數據集下混合緩存L2能耗只是略高于STT-RAM基線.這受益于混合緩存的分配策略減少了STT-RAM的寫入次數.PHC和RLHC分別減少了25.7%和44.3%的寫入次數.而我們的策略比PHC多減少了18.6%的STT-RAM的寫入次數.總體而言，與STT-RAM基線和PHC相比，我們的策略將L2的能耗分別降低了11.9%和9.7%.這比使用單線程應用程序觀察到的效果略小.這主要是在多核情況下，每個核訪問情況不一樣，寫訪問不均勻分布，導致寫入強度很難預測，更難在不增加混合緩存未命中率的情況下減少STT-RAM的寫入次數，從而使得比單核系統下效果有所下降.

Fig.11 L2 energy breakdown under the quad-core system圖11 在四核系統下L2能耗分解

Fig.13 L2 AMAT under quad-core system圖13 在四核系統下L2 AMAT

Fig.12 L2 STT-RAM writes under quad-core system圖12 在四核系統下L2 STT-RAM寫入次數

5.6 多核上L2性能

圖13、圖14分別顯示了不同策略在四核系統下L2的AMAT和IPC.與STT-RAM基線相比，我們的策略將AMAT降低了2%，將IPC提高了2.2%.與PHC相比，我們的策略將AMAT降低了0.7%，將IPC提高了0.8%.

Fig.14 L2 IPC under quad-core system圖14 在四核系統下L2 IPC

6 總 結

本文提出了一種在混合緩存架構上緩存數據的智能分配策略.它的關鍵思想是根據緩存的寫入強度和緩存的重用來計算出在指定窗口期下緩存行分配到SRAM區域和STT-RAM區域的能耗，然后基于能耗使用強化學習來計算出緩存分配到SRAM區域和STT-RAM區域的權重，將緩存分配到權重大的區域.基于緩存的寫入強度和重用信息能更好地計算出緩存放入SRAM區域和STT-RAM區域所花費的能量，使用強化學習能根據當前能耗動態地調整SRAM區域和STT-RAM區域的權重，能自動適應應用程序負載.這2點使我們的分配策略能在不增加混合緩存未命中率的情況下減少STT-RAM的寫入次數，從而提高緩存性能.實驗結果表明，與現有的混合緩存策略相比，我們的策略在單核(四核)系統中實現了16.9%(9.7%)的能量降低.這主要得益于我們的策略更好地減少了STT-RAM的寫入次數.