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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 研究背景和動機

2.1 研究背景

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

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

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

2) 強化學(xué)習(xí)

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

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

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

2.2 研究動機

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

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

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

3 系統(tǒng)結(jié)構(gòu)

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

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

(1)

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

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

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

圖3給出了混合緩存系統(tǒng)的整體組織架構(gòu).該架構(gòu)由混合緩存和分配預(yù)測器組成.與其他混合緩存架構(gòu)類似，每個高速緩存集分為SRAM區(qū)域和STT-RAM區(qū)域.數(shù)據(jù)區(qū)域由SRAM和STT-RAM組成，標(biāo)簽區(qū)域僅由SRAM構(gòu)成[21-22].分配預(yù)測器存儲開銷小，需頻繁讀寫，因此也由SRAM構(gòu)成.

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

Fig.3 Architecture of RLHC圖3 RLHC架構(gòu)

在設(shè)計混合緩存分配策略時，關(guān)鍵的問題有：

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

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

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

將在下一部分詳細(xì)描述解決方法.

4 系統(tǒng)設(shè)計與實現(xiàn)

本節(jié)詳細(xì)地介紹基于強化學(xué)習(xí)的混合緩存分配策略設(shè)計整體實現(xiàn)方法.整個設(shè)計中主要從緩存行的分類、緩存的狀態(tài)信息收集、分配策略設(shè)計和死區(qū)預(yù)測這4個方面進(jìn)行介紹.

4.1 緩存行的分類

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

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

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

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

4.2 緩存的狀態(tài)信息收集

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

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

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

Fig.5 Structure of prediction table entry圖5 預(yù)測表entry結(jié)構(gòu)

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

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

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的次數(shù)；Et_r:讀一次Tag所需的能量；Nt_w:寫Tag的次數(shù)；Et_w:寫一次Tag所需的能量；Nsram_r:讀SRAM的次數(shù)；Esram_r:讀一次SRAM所需的能量；Nsram_w:寫SRAM的次數(shù)；Esram_w:寫一次SRAM所需的能量；Nstt-ram_r:讀STT-RAM的次數(shù)；Estt-ram_r:讀一次STT-RAM所需的能量；Nstt-ram_w:寫STT-RAM的次數(shù)；Estt-ram_w:寫一次STT-RAM所需的能量；Ndram_r:讀DRAM的次數(shù)；Edram_r:讀一次DRAM所需的能量;Ndram_w:寫DRAM的次數(shù)；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 緩存分配策略設(shè)計

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

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

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

算法1.SRAM與STT-RAM權(quán)重計算.

輸入：SRAM能量sram_energy、STT-RAM能量stt-ram_energy、學(xué)習(xí)率λ、折扣率d、SRAM權(quán)重Wsram、STT-RAM權(quán)重Wstt-ram；

輸出：更新后的SRAM權(quán)重和STT-RAM權(quán)重.

①tRO or WO or RW；

②rdt；

③ ifratio×sram_energy>stt-ram_energythen

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

STT-RAM權(quán)重*/

⑤ else then

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

權(quán)重*/

⑦ end if

⑧WsramWsram/(Wsram+Wstt-ram)；

⑨Wstt-ram1-Wsram.

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

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

Table 5 Access Statistics of Cache Set A表5 緩存集合A的訪問統(tǒng)計

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.

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

4.4 緩存死區(qū)預(yù)測

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

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

4.5 小 結(jié)

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

5 實驗分析與結(jié)果

5.1 模擬器配置

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

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

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

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

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

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

5.2 工作負(fù)載

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

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

Table 8 Qualitative Summary of Key Characteristics of PARSEC 3.0[36]
表8 PARSEC3.0關(guān)鍵特征的定性總結(jié)[36]

ProgramApplicationDomainParallelGranularityWorkingSetblackscholesFinancial AnalysiscoarsesmallbodytrackComputer VisionmediummediumcannealEngineeringfineunboundeddedupEnterprise StoragemediumunboundedfacesimAnimationcoarselargeferretSimilarity SearchmediumunboundedfluidanimateAnimationfinelargefreqmineData MiningmediumunboundedstreamclusterData MiningmediummediumswaptionsFinancial AnalysiscoarsemediumvipsMedia Processingcoarsemediumx264Media Processingcoarsemedium

5.3 單核上L2能耗

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

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

Fig.8 L2 STT-RAM writes under single-core system圖8 在單核系統(tǒng)下L2 STT-RAM寫入次數(shù)

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

5.4 單核上L2性能

圖9、圖10分別顯示了不同策略在單核系統(tǒng)下L2的AMAT和IPC.與STT-RAM基線和PHC相比，我們的策略分別將L2的AMAT降低了2.2%和1.3%.同時，與STT-RAM基線和PHC相比，我們的策略將系統(tǒng)性能分別提高了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 在單核系統(tǒng)下L2 AMAT

Fig.10 L2 IPC under single-core system圖10 在單核系統(tǒng)下L2 IPC

5.5 多核上L2能耗

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

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

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

Fig.13 L2 AMAT under quad-core system圖13 在四核系統(tǒng)下L2 AMAT

Fig.12 L2 STT-RAM writes under quad-core system圖12 在四核系統(tǒng)下L2 STT-RAM寫入次數(shù)

5.6 多核上L2性能

圖13、圖14分別顯示了不同策略在四核系統(tǒng)下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 在四核系統(tǒng)下L2 IPC

6 總 結(jié)

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