基于頻率時(shí)效感知的混合內(nèi)存寫冷熱頁面調(diào)度

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

（1.中國(guó)科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027；2.銅陵職業(yè)技術(shù)學(xué)院 信息工程系，安徽 銅陵 244061；3.銅陵有色金屬集團(tuán)公司，安徽 銅陵 244000；4.中國(guó)安全生產(chǎn)科學(xué)研究院，北京 100012）

0 引言

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

1 相關(guān)研究

1.1 混合內(nèi)存架構(gòu)

針對(duì)PCM 和DRAM 的特點(diǎn)，目前的研究集中在將PCM 和DRAM 二者的優(yōu)點(diǎn)結(jié)合。在混合內(nèi)存[2-5]結(jié)構(gòu)上的使用，分為同級(jí)混合內(nèi)存和層次混合內(nèi)存，如圖1所示。

圖1 同級(jí)混合和層次混合內(nèi)存結(jié)構(gòu)框圖Fig.1 Peer and hierarchical hybrid memory structure

1）同級(jí)混合內(nèi)存[6]（圖1a）利用PCM 字節(jié)尋址的特點(diǎn)，內(nèi)存由PCM 和DRAM 兩部分構(gòu)成，并當(dāng)作一個(gè)整體統(tǒng)一編址。訪問時(shí)，根據(jù)頁面特點(diǎn)，將頁面分別放入PCM 或DRAM。2）層次混合內(nèi)存[7]（圖1b）。其將DRAM 作為PCM 的緩存，先訪問DRAM，如DRAM 沒有命中，再訪問PCM，通過DRAM 的寫無限性緩沖PCM 的寫有限性。

1.2 已有混合內(nèi)存冷熱頁的判定

由于PCM 的寫耐久性有一定的次數(shù)限制，讀寫不均衡，寫時(shí)間較長(zhǎng)，所以在混合內(nèi)存緩沖區(qū)管理調(diào)度策略的設(shè)計(jì)中，通常要達(dá)到2 個(gè)目標(biāo)：1）減少PCM 的寫次數(shù)，延長(zhǎng)PCM 的使用年限；2）提高訪問時(shí)緩沖區(qū)頁面的命中率，從而減少頁面調(diào)度時(shí)資源的消耗及同時(shí)產(chǎn)生的PCM 寫操作。

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

以上算法都涉及頁面冷熱頁的判定。LRUWPAM 中給每個(gè)頁面設(shè)置權(quán)值，當(dāng)頁面是“讀請(qǐng)求”時(shí)，權(quán)值增加，當(dāng)是“寫請(qǐng)求”時(shí)，權(quán)值減少，通過權(quán)值和閥值的比較判定頁面的讀寫熱頁類型。CLOCK-DWF 通過每個(gè)頁面寫次數(shù)來判斷“寫熱頁”和“寫冷頁”。其它幾種算法也都通過次數(shù)來判斷頁面的冷熱。

2 頻率時(shí)效感知頁面劃分

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

1）頁面訪問有局部性

存儲(chǔ)系統(tǒng)負(fù)載訪問有局部性[13]的特點(diǎn)，即寫操作聚集在若干頁面上。在某一時(shí)間段內(nèi)，若干頁面訪問次數(shù)很多，比較密集，其它頁面沒有訪問或者零星訪問。

2）“寫熱頁”和“寫冷頁”和頁面調(diào)用的時(shí)段有關(guān)頁面調(diào)用的階段性

某些頁面寫入后，可能很長(zhǎng)時(shí)間不再調(diào)用，也可能階段性爆發(fā)，并且在較近時(shí)段發(fā)生過寫操作頁面為“寫熱頁”的概率比較大，即局部爆發(fā)和爆發(fā)的間隔時(shí)段有關(guān)。

針對(duì)上述問題，本文提出根據(jù)先前訪問的頻率距離現(xiàn)在訪問的間隔、當(dāng)前局部爆發(fā)訪問的特點(diǎn)，將頁面的局部寫頻率和上次的高頻訪問和最近高頻訪問的時(shí)間間隔來計(jì)算權(quán)值，并根據(jù)權(quán)值對(duì)頁面“寫”冷熱進(jìn)行劃分，即頻率時(shí)效寫頁面劃分。

2.1 模型定義

頁面寫訪問的局部爆發(fā)性、訪問頻率和最近寫訪問間隔對(duì)頁面寫的冷熱有著直接影響。根據(jù)這一特點(diǎn)，本文通過寫訪問頻率和最近寫訪問間隔、頻率時(shí)效（frequency time interval，F(xiàn)TI）進(jìn)行計(jì)算，預(yù)測(cè)頁面的冷熱度。首先引入如下幾個(gè)概念。

局部寫訪問統(tǒng)計(jì)器（local write access statistics，LWAS）。如圖2所示，該統(tǒng)計(jì)器為長(zhǎng)度為20 的隊(duì)列，按照寫訪問的時(shí)間順序，記錄最近發(fā)生的20 次寫請(qǐng)求訪問，并不重復(fù)統(tǒng)計(jì)最近每個(gè)頁面的訪問次數(shù)，計(jì)算得到局部寫訪問頻率的值為Pn。

圖2 局部寫訪問統(tǒng)計(jì)器Fig.2 Local write access statistics

頻率時(shí)效頁面寫冷熱權(quán)值計(jì)算公式為

式中：W1為當(dāng)前頁面上一次寫訪問時(shí)的權(quán)值；W2為出現(xiàn)最近頁面寫請(qǐng)求時(shí)計(jì)算的權(quán)值；WDist為上一次最近的權(quán)值除以這個(gè)頁面的最近寫距離。C取值時(shí)，先假定為0.4～0.6 的區(qū)間，然后經(jīng)過實(shí)驗(yàn)數(shù)據(jù)測(cè)定，取0.5 比較合適。當(dāng)頁面沒有出現(xiàn)過，W1沒有值時(shí)，取默認(rèn)值0.45，WDist取默認(rèn)值1。

高頻訪問頁容器（high frequency access page container，HFAC）。該容器為一鏈表，由局部寫訪問統(tǒng)計(jì)器中Pn≥2 的頁面按照時(shí)間次序組成，每個(gè)節(jié)點(diǎn)由頁面序號(hào)和權(quán)值構(gòu)成，權(quán)值根據(jù)式（1）得到。當(dāng)LWAS 中出現(xiàn)大于兩次的頁面時(shí)，將頁面放入HFAC，如果HFAC 中出現(xiàn)過這個(gè)頁面，在記錄值后，將其從前面鏈表中刪除。

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

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

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

2.2 冷熱頁調(diào)度

DRAM 和PCM 按照4:1 的比例進(jìn)行配置，DRAM 存儲(chǔ)的頁面?zhèn)€數(shù)為DSize，PCM 存儲(chǔ)的頁面?zhèn)€數(shù)為PSize。

頻率時(shí)效頁面寫冷熱度權(quán)值計(jì)算過程如下：

當(dāng)出現(xiàn)頁面寫訪問請(qǐng)示時(shí)，將頁面序號(hào)放入局部寫訪問統(tǒng)計(jì)器頭部；

統(tǒng)計(jì)局部寫訪問統(tǒng)計(jì)器，如果出現(xiàn)Pn≥2的頁面，讀取高頻訪問頁容器中各項(xiàng)，尋找是否存在此頁面；

如果高頻訪問頁容器有該頁面，根據(jù)式（1）計(jì)算頁面權(quán)值，放入高頻訪問頁容器頭部，刪除先前的節(jié)點(diǎn)；如果沒有該頁面，計(jì)算權(quán)值放入高頻訪問頁容器。

在混合內(nèi)存中，由于PCM 的寫次數(shù)限定性，寫頁面存放以DRAM 為優(yōu)先，以頻率時(shí)效的CLOCK算法（frequency time interval CLOCK，F(xiàn)TI-CLOCK）來實(shí)現(xiàn)頁面的調(diào)度。出現(xiàn)寫請(qǐng)求時(shí)，進(jìn)行局部寫訪問頻率統(tǒng)計(jì)并按式（1）計(jì)算權(quán)值，將權(quán)值插入HFAC。如果出現(xiàn)Pn≥2 寫請(qǐng)求時(shí)，調(diào)度原則如下：

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

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

將HFAC 中權(quán)值最小，且在DRAM 中的頁面，與頁面置換。

2.3 算法過程

頻率時(shí)效頁面寫冷熱權(quán)值計(jì)算過程如算法1 所示，其中輸入為W1、WDist和Pn，輸出為計(jì)算的權(quán)值W2。

算法1頻率時(shí)效頁面寫冷熱權(quán)值計(jì)算

頻率時(shí)效的CLOCK（FTI-CLOCK）調(diào)度過程如算法2 所示，在Pn≥2 的頁面寫請(qǐng)求時(shí)，執(zhí)行算法進(jìn)行頁面調(diào)度。

算法2FTI-CLOCK 頁面調(diào)度

3 實(shí)驗(yàn)仿真及分析

3.1 實(shí)驗(yàn)方法

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

具體實(shí)驗(yàn)數(shù)據(jù)集[16]測(cè)試參數(shù)見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental data set

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

3.2 存儲(chǔ)空間變化的PCM 寫次數(shù)

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

圖3 存儲(chǔ)空間變化的不同調(diào)度PCM 寫次數(shù)Fig.3 Different scheduling PCM write times with storage space changing

通過數(shù)據(jù)集在4 種調(diào)度策略下的PCM 寫次數(shù)的數(shù)據(jù)顯示，如圖3中a～e 圖所示：

1）隨著混合內(nèi)存空間容量的增大，各數(shù)據(jù)集在4 種調(diào)度策略的寫次數(shù)都下降。實(shí)驗(yàn)結(jié)果顯示當(dāng)存儲(chǔ)空間增大時(shí)，可以顯著減少PCM 的寫次數(shù)；

2）合成數(shù)據(jù)集中讀寫的比例，對(duì)PCM 寫的次數(shù)影響較大，實(shí)驗(yàn)結(jié)果表明當(dāng)寫比例增大時(shí)，PCM寫的次數(shù)明顯增大；

3）數(shù)據(jù)的局部操作性對(duì)PCM 的寫次數(shù)有影響，但不是很大；

4）實(shí)驗(yàn)結(jié)果顯示，頻率時(shí)效的FTI-CLOCK 調(diào)度算法，可以有效減少PCM 的寫次數(shù)。

3.3 固定存儲(chǔ)空間的PCM 寫次數(shù)

當(dāng)存儲(chǔ)空間固定為2 GB，DRAM:PCM 為4:1，實(shí)驗(yàn)數(shù)據(jù)集在FTI-CLOCK 頁面調(diào)度、CLOCK、CLOCK-DWF 和D-CLOCK 情況下，PCM 寫次數(shù)的實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 存儲(chǔ)空間固定的不同調(diào)度PCM 寫次數(shù)Fig.4 Different scheduling PCM write times with fixed storage space

通過分析實(shí)驗(yàn)得出的數(shù)據(jù)可知，當(dāng)存儲(chǔ)空間、比例一定時(shí)：CLOCK 算法沒有對(duì)混合存儲(chǔ)空間進(jìn)行區(qū)分，進(jìn)行無區(qū)別的讀寫操作，PCM 的寫次數(shù)較多；CLOCK-DWF 操作，僅根據(jù)頁面的讀寫請(qǐng)求，就對(duì)頁面的冷熱進(jìn)行劃分，并將讀頁面置換進(jìn)PCM，頁面劃分較為簡(jiǎn)單，造成寫PCM 寫次數(shù)還是比較高；D-CLOCK 根據(jù)當(dāng)前頁面的寫次數(shù)和平均寫次數(shù)比較來劃分頁面的冷熱，降低了PCM 寫次數(shù)，但沒有考慮頁面寫的局部爆發(fā)和時(shí)間間隔；FTI-CLOCK 考慮了頁面的局部爆發(fā)寫特點(diǎn)，并將局部寫頻率和寫的時(shí)間間隔相結(jié)合，在4 個(gè)算法的寫操作中，寫次數(shù)最低。實(shí)驗(yàn)證明，頻率時(shí)效的FTI-CLOCK 調(diào)度能夠有效減少PCM 寫次數(shù)，明顯地優(yōu)化PCM 寫，提高PCM 的使用時(shí)長(zhǎng)。

4 結(jié)論

作為新一代存儲(chǔ)材料，PCM 有著許多優(yōu)點(diǎn)，有著較高的存儲(chǔ)密度，并且低能耗，已經(jīng)進(jìn)入工程應(yīng)用階段，但如何解決PCM 的寫耐久性是一個(gè)急需解決的問題，多年來，許多研究人員給出了多種解決方案。本文通過分析內(nèi)存頁面寫的局部性和時(shí)效性，提出了新公式將二者結(jié)合在一起，通過計(jì)算權(quán)值的形式來區(qū)分頁面的冷熱。

1）通過局部訪問統(tǒng)計(jì)器對(duì)局部密集寫訪問的頻率進(jìn)行了統(tǒng)計(jì)；

2）將最近時(shí)間的高頻寫請(qǐng)求，上次密集寫和這次訪問的時(shí)間間隔統(tǒng)一到一個(gè)計(jì)算公式中，并根據(jù)頻率和時(shí)效計(jì)算權(quán)值；

3）在考慮局部密集寫訪問和頻率時(shí)效權(quán)值的基礎(chǔ)上，實(shí)現(xiàn)寫頁面的調(diào)度，實(shí)驗(yàn)結(jié)果表明，該方法可以有效降低PCM 的寫次數(shù)；

4）本文只是從比較小的數(shù)據(jù)出發(fā)來實(shí)現(xiàn)頻率時(shí)效的寫冷熱頁面調(diào)度，但對(duì)大數(shù)據(jù)環(huán)境下，如何通過局部寫訪問和時(shí)效性來進(jìn)行頁面的調(diào)度，是下一步研究的方向。