基于頻率時效感知的混合內存寫冷熱頁面調度

劉 兵，汪令輝，張 濤，陳友良

（1.中國科技大學 計算機科學與技術學院，安徽 合肥 230027；2.銅陵職業技術學院 信息工程系，安徽 銅陵 244061；3.銅陵有色金屬集團公司，安徽 銅陵 244000；4.中國安全生產科學研究院，北京 100012）

0 引言

隨著大數據技術、人工智能和工業互聯網等技術的發展，需處理的數據量越來越多，對內存的節能、存儲密度、隨機寫、高并發性隨機讀和實時處理分析等都提出了更高的要求。當前主要的內存技術是DRAM（dynamic random access memory），要通過不斷地刷電來保持數據，能源的消耗比較大。另外，DRAM 的存儲集成也已經接近極限。非易失性存儲（non-volatile memory，NVM）技術為解決這一問題提供了一種新方法，其中以相變存儲器（phase change memory，PCM）[1]性能最為突出，其作為近些年存儲技術發展的熱點技術，有著廣泛的應用前景。PCM 相對于DRAM 的優點是存儲密度較大、功耗低；缺點是寫入的速度比DRAM慢、寫的次數有限。因此，減少PCM 的寫操作，提高其寫耐久性，是許多研究者探討的問題。

1 相關研究

1.1 混合內存架構

針對PCM 和DRAM 的特點，目前的研究集中在將PCM 和DRAM 二者的優點結合。在混合內存[2-5]結構上的使用，分為同級混合內存和層次混合內存，如圖1所示。

圖1 同級混合和層次混合內存結構框圖Fig.1 Peer and hierarchical hybrid memory structure

1）同級混合內存[6]（圖1a）利用PCM 字節尋址的特點，內存由PCM 和DRAM 兩部分構成，并當作一個整體統一編址。訪問時，根據頁面特點，將頁面分別放入PCM 或DRAM。2）層次混合內存[7]（圖1b）。其將DRAM 作為PCM 的緩存，先訪問DRAM，如DRAM 沒有命中，再訪問PCM，通過DRAM 的寫無限性緩沖PCM 的寫有限性。

1.2 已有混合內存冷熱頁的判定

由于PCM 的寫耐久性有一定的次數限制，讀寫不均衡，寫時間較長，所以在混合內存緩沖區管理調度策略的設計中，通常要達到2 個目標：1）減少PCM 的寫次數，延長PCM 的使用年限；2）提高訪問時緩沖區頁面的命中率，從而減少頁面調度時資源的消耗及同時產生的PCM 寫操作。

Seok H.等[8-9]提出以“最近最少使用”（least recently used，LRU）算法為基礎的LRU-WPAM（LRU with prediction and migration）算法，增加了一個頁面的讀寫預測，根據判斷緩沖區頁面是否命中。當未命中時，用最近最少使用頁面置換；命中時，根據讀寫請求修改頁面權值，再判斷權值是否達到閥值。判斷頁面是讀傾向高的頁面（“讀熱頁”），還是寫傾向高的頁面（“寫熱頁”），如果頁面達到閥值，將“讀熱頁”移動移動進PCM，將“寫熱頁”移動進DRAM。Lee S.等[10]提出CLOCK-DWF 算法，將DRAM 和PCM 各組成一個環狀隊列，當空間充足時，把讀請求頁面存入混合內存的PCM 中，寫請求頁面放入混合內存的DRAM 中。當DRAM 空間不足時，進行冷熱頁的調度，將寫冷頁調度進入PCM，PCM的空間不足時，使用CLOCK 算法調度頁面。類似的還有Chen K.M.等[11]提出的MHR-LRU（maintainhit-ratio LRU），劉兵等[12]提出的FWLRU（favors write LRU）策略等。

以上算法都涉及頁面冷熱頁的判定。LRUWPAM 中給每個頁面設置權值，當頁面是“讀請求”時，權值增加，當是“寫請求”時，權值減少，通過權值和閥值的比較判定頁面的讀寫熱頁類型。CLOCK-DWF 通過每個頁面寫次數來判斷“寫熱頁”和“寫冷頁”。其它幾種算法也都通過次數來判斷頁面的冷熱。

2 頻率時效感知頁面劃分

在PCM 的讀寫操作中，根據PCM 的特性，讀操作和DRAM 中的操作區別不大，寫操作的使用對于PCM 的揚長避短有決定性的作用。如果能準確及時地預測出“寫冷頁”和“寫熱頁”，既可利用PCM 的低能耗、存儲密度大的特點，又可避免寫操作有限的缺點，從而提高PCM 的寫耐久性，同時提高頁面的命中率。但已有的冷熱頁面預測或者判定方法，忽略了如下幾個方面的問題：

1）頁面訪問有局部性

存儲系統負載訪問有局部性[13]的特點，即寫操作聚集在若干頁面上。在某一時間段內，若干頁面訪問次數很多，比較密集，其它頁面沒有訪問或者零星訪問。

2）“寫熱頁”和“寫冷頁”和頁面調用的時段有關頁面調用的階段性

某些頁面寫入后，可能很長時間不再調用，也可能階段性爆發，并且在較近時段發生過寫操作頁面為“寫熱頁”的概率比較大，即局部爆發和爆發的間隔時段有關。

針對上述問題，本文提出根據先前訪問的頻率距離現在訪問的間隔、當前局部爆發訪問的特點，將頁面的局部寫頻率和上次的高頻訪問和最近高頻訪問的時間間隔來計算權值，并根據權值對頁面“寫”冷熱進行劃分，即頻率時效寫頁面劃分。

2.1 模型定義

頁面寫訪問的局部爆發性、訪問頻率和最近寫訪問間隔對頁面寫的冷熱有著直接影響。根據這一特點，本文通過寫訪問頻率和最近寫訪問間隔、頻率時效（frequency time interval，FTI）進行計算，預測頁面的冷熱度。首先引入如下幾個概念。

局部寫訪問統計器（local write access statistics，LWAS）。如圖2所示，該統計器為長度為20 的隊列，按照寫訪問的時間順序，記錄最近發生的20 次寫請求訪問，并不重復統計最近每個頁面的訪問次數，計算得到局部寫訪問頻率的值為Pn。

圖2 局部寫訪問統計器Fig.2 Local write access statistics

頻率時效頁面寫冷熱權值計算公式為

式中：W1為當前頁面上一次寫訪問時的權值；W2為出現最近頁面寫請求時計算的權值；WDist為上一次最近的權值除以這個頁面的最近寫距離。C取值時，先假定為0.4～0.6 的區間，然后經過實驗數據測定，取0.5 比較合適。當頁面沒有出現過，W1沒有值時，取默認值0.45，WDist取默認值1。

高頻訪問頁容器（high frequency access page container，HFAC）。該容器為一鏈表，由局部寫訪問統計器中Pn≥2 的頁面按照時間次序組成，每個節點由頁面序號和權值構成，權值根據式（1）得到。當LWAS 中出現大于兩次的頁面時，將頁面放入HFAC，如果HFAC 中出現過這個頁面，在記錄值后，將其從前面鏈表中刪除。

混合內存CLOCK 鏈表（hybrid memory CLOCK）。DRAM 和PCM 混合內存頁面整體鏈表，按CLOCK 算法處理。

CLOCK-DRAM。將DRAM 中頁面按CLOCK算法組織并處理頁面。

CLOCK-PCM。將PCM 中頁面按CLOCK 算法組織并處理頁面。

2.2 冷熱頁調度

DRAM 和PCM 按照4:1 的比例進行配置，DRAM 存儲的頁面個數為DSize，PCM 存儲的頁面個數為PSize。

頻率時效頁面寫冷熱度權值計算過程如下：

當出現頁面寫訪問請示時，將頁面序號放入局部寫訪問統計器頭部；

統計局部寫訪問統計器，如果出現Pn≥2的頁面，讀取高頻訪問頁容器中各項，尋找是否存在此頁面；

如果高頻訪問頁容器有該頁面，根據式（1）計算頁面權值，放入高頻訪問頁容器頭部，刪除先前的節點；如果沒有該頁面，計算權值放入高頻訪問頁容器。

在混合內存中，由于PCM 的寫次數限定性，寫頁面存放以DRAM 為優先，以頻率時效的CLOCK算法（frequency time interval CLOCK，FTI-CLOCK）來實現頁面的調度。出現寫請求時，進行局部寫訪問頻率統計并按式（1）計算權值，將權值插入HFAC。如果出現Pn≥2 寫請求時，調度原則如下：

如果頁面在CLOCK-DRAM 中，執行操作，如果頁面在CLOCK-PCM 中或者未命中，查找DRAM中是否存在空閑空間；

如果存在空閑空間，將頁面調入DRAM，如果沒有空閑空間，比較CLOCK-DRAM 和HFAC，查找CLOCK-DRAM 不在HFAC 中的頁面，如果存在，按照CLOCK 算法將頁面轉換進PCM 或者淘汰，如果沒有，瀏覽HFAC；

將HFAC 中權值最小，且在DRAM 中的頁面，與頁面置換。

2.3 算法過程

頻率時效頁面寫冷熱權值計算過程如算法1 所示，其中輸入為W1、WDist和Pn，輸出為計算的權值W2。

算法1頻率時效頁面寫冷熱權值計算

頻率時效的CLOCK（FTI-CLOCK）調度過程如算法2 所示，在Pn≥2 的頁面寫請求時，執行算法進行頁面調度。

算法2FTI-CLOCK 頁面調度

3 實驗仿真及分析

3.1 實驗方法

為了模仿混合內存環境，通過在ubuntu 18.04 系統上架設仿真模擬器GEM5[14]+NVMain[15]來實現DRAM 和PCM 混合內存實驗環境。GEM5 是GEMS和M5 結合的全系統模擬器，它有ISA 和多種CPU模型，本實驗用它來模仿整個系統，NVMain 是循環級的內存模擬器，本實驗用它來模仿PCM，從而實現DRAM+PCM 的實驗環境。實驗時采用系統級仿真模式SE，每個頁面設為4 kB 大小，延遲數據：PCM 參照F.Bedeschi 等的研究[16]，DRAM 參照Micron 的測試[17]。

具體實驗數據集[16]測試參數見表1。

表1 實驗數據集Table 1 Experimental data set

本實驗數據集由兩部分構成：真實數據和合成數據。真實數據采集于安徽省蕪湖市某天貓網站某段時間的交易記錄，數據集經過去噪處理，有356 733 次讀和115 790 次寫；合成數據通過開源軟件DiskSim獲得，通過它對磁盤的模擬讀寫操作來獲取比例不同的局部性讀寫操作數據集，表1中的數據集中Locality（局部性），如“80%/20%”，表示在20%的局部空間上發生的80%的讀寫操作。

3.2 存儲空間變化的PCM 寫次數

將數據集Trace9151、Trace8987、Trace3377、Trace1899 和OLTP 在頻率時效下的FTI-CLOCK 頁面調度和CLOCK、CLOCK-DWF 和D-CLOCK 的頁面調度進行比較。圖3給出了5 組數據集在4 種不同頁面調度下的PCM 寫次數統計，本次實驗中內存頁面逐漸增大，DRAM 和PCM 按照4:1 統一修改的比例進行配置。

圖3 存儲空間變化的不同調度PCM 寫次數Fig.3 Different scheduling PCM write times with storage space changing

通過數據集在4 種調度策略下的PCM 寫次數的數據顯示，如圖3中a～e 圖所示：

1）隨著混合內存空間容量的增大，各數據集在4 種調度策略的寫次數都下降。實驗結果顯示當存儲空間增大時，可以顯著減少PCM 的寫次數；

2）合成數據集中讀寫的比例，對PCM 寫的次數影響較大，實驗結果表明當寫比例增大時，PCM寫的次數明顯增大；

3）數據的局部操作性對PCM 的寫次數有影響，但不是很大；

4）實驗結果顯示，頻率時效的FTI-CLOCK 調度算法，可以有效減少PCM 的寫次數。

3.3 固定存儲空間的PCM 寫次數

當存儲空間固定為2 GB，DRAM:PCM 為4:1，實驗數據集在FTI-CLOCK 頁面調度、CLOCK、CLOCK-DWF 和D-CLOCK 情況下，PCM 寫次數的實驗結果如圖4所示。

圖4 存儲空間固定的不同調度PCM 寫次數Fig.4 Different scheduling PCM write times with fixed storage space

通過分析實驗得出的數據可知，當存儲空間、比例一定時：CLOCK 算法沒有對混合存儲空間進行區分，進行無區別的讀寫操作，PCM 的寫次數較多；CLOCK-DWF 操作，僅根據頁面的讀寫請求，就對頁面的冷熱進行劃分，并將讀頁面置換進PCM，頁面劃分較為簡單，造成寫PCM 寫次數還是比較高；D-CLOCK 根據當前頁面的寫次數和平均寫次數比較來劃分頁面的冷熱，降低了PCM 寫次數，但沒有考慮頁面寫的局部爆發和時間間隔；FTI-CLOCK 考慮了頁面的局部爆發寫特點，并將局部寫頻率和寫的時間間隔相結合，在4 個算法的寫操作中，寫次數最低。實驗證明，頻率時效的FTI-CLOCK 調度能夠有效減少PCM 寫次數，明顯地優化PCM 寫，提高PCM 的使用時長。

4 結論

作為新一代存儲材料，PCM 有著許多優點，有著較高的存儲密度，并且低能耗，已經進入工程應用階段，但如何解決PCM 的寫耐久性是一個急需解決的問題，多年來，許多研究人員給出了多種解決方案。本文通過分析內存頁面寫的局部性和時效性，提出了新公式將二者結合在一起，通過計算權值的形式來區分頁面的冷熱。

1）通過局部訪問統計器對局部密集寫訪問的頻率進行了統計；

2）將最近時間的高頻寫請求，上次密集寫和這次訪問的時間間隔統一到一個計算公式中，并根據頻率和時效計算權值；

3）在考慮局部密集寫訪問和頻率時效權值的基礎上，實現寫頁面的調度，實驗結果表明，該方法可以有效降低PCM 的寫次數；

4）本文只是從比較小的數據出發來實現頻率時效的寫冷熱頁面調度，但對大數據環境下，如何通過局部寫訪問和時效性來進行頁面的調度，是下一步研究的方向。