改進(jìn)的偏向?qū)懻{(diào)度的混合內(nèi)存緩沖區(qū)調(diào)度策略

劉 兵 ，汪令輝，張 銳，崔 瑩，段 峰

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

隨著大數(shù)據(jù)、人工智能等技術(shù)的發(fā)展，數(shù)據(jù)的處理量越來(lái)越大，這對(duì)計(jì)算機(jī)的主存儲(chǔ)器提出了越來(lái)越高的要求。當(dāng)前，以動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器（dynamic random access memory，DRAM）為主的主存儲(chǔ)技術(shù)也面臨著較大的挑戰(zhàn)，主要面臨的問(wèn)題為DRAM 存儲(chǔ)集成已達(dá)極限，且能耗也是一個(gè)重要問(wèn)題。人們從軟件和硬件等方面提出了多種方式，希望彌補(bǔ)這一缺點(diǎn)，比如通過(guò)非易失存儲(chǔ)（non-volatile memory，NVM）來(lái)解決這一問(wèn)題。非易失存儲(chǔ)具有較高的集成度、非易失、低能耗、字節(jié)尋址等特點(diǎn)。非易失存儲(chǔ)器有電阻隨機(jī)存儲(chǔ)器ReRAM[1]、自旋磁存儲(chǔ)器[2]、相變存儲(chǔ)器[3]（phase change memory，PCM）等。其中，PCM 具有良好的可擴(kuò)展性，有望成為新一代的主流技術(shù)。

1 研究背景和相關(guān)工作

1.1 PCM的相關(guān)特性

相變存儲(chǔ)器是一種硫族化合物，分為晶體狀態(tài)和非晶體狀態(tài)。它具有寫的不對(duì)稱性，PCM寫1（SET）的時(shí)候，要施加一個(gè)時(shí)間長(zhǎng)、電壓低的電脈沖，溫度在結(jié)晶點(diǎn)以上、融化點(diǎn)以下，導(dǎo)致其結(jié)晶，物質(zhì)從非晶態(tài)到晶態(tài)轉(zhuǎn)化。PCM寫0（RESET）的時(shí)候，要施加一個(gè)電壓高、時(shí)間短的電脈沖，當(dāng)溫度上升到溶點(diǎn)后，再經(jīng)過(guò)一個(gè)淬火（降溫速率大于109 K/s）的過(guò)程，物質(zhì)從晶態(tài)到非晶態(tài)轉(zhuǎn)化。

相變存儲(chǔ)器在晶態(tài)和非晶態(tài)時(shí)，其阻抗是不同的，當(dāng)施加一個(gè)電壓時(shí)，對(duì)應(yīng)的電流不同，從而可以判斷為0或1。PCM讀的過(guò)程中，電流通過(guò)時(shí)產(chǎn)生的熱量很小，不會(huì)引起晶態(tài)的變化。

PCM和DRAM 相比較，具有存儲(chǔ)密度大和無(wú)空閑功耗的優(yōu)點(diǎn)。DRAM的工藝制程是PCM的4倍，所以在相同的芯片面積下，PCM可以增加更大的容量；DRAM 空閑時(shí)，需要通過(guò)不斷地刷電來(lái)保持?jǐn)?shù)據(jù)，而PCM為非易失性存儲(chǔ)設(shè)備，不需要刷電。

PCM和DRAM 相比較，也有它自身的缺點(diǎn)，主要如下：

1）PCM的讀操作時(shí)間是DRAM的2倍，功耗相差不大；

2）PCM的寫操作時(shí)間是DRAM的10倍，PCM寫功耗比DRAM 大；

3）PCM的寫次數(shù)為108～1 012，DRAM幾乎無(wú)限，寫次數(shù)為大于1 015。

1.2 PCM在內(nèi)存中的應(yīng)用

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

目前，針對(duì)PCM的特性，許多研究者嘗試結(jié)合二者的優(yōu)點(diǎn)，提出了混合內(nèi)存[4-9]的概念?；旌蟽?nèi)容的主要架構(gòu)方式包括層次架構(gòu)和平行架構(gòu)兩種。

1）層次架構(gòu)。該方式下，DRAM 作為PCM的緩存，所有的請(qǐng)求都先訪問(wèn)DRAM，當(dāng)請(qǐng)求沒(méi)有選中是時(shí)，再訪問(wèn)PCM。這種架構(gòu)方式的優(yōu)點(diǎn)是利用DRAM 彌補(bǔ)PCM的寫不足，同時(shí)利用PCM 增加存儲(chǔ)密度，利用其非易失性存儲(chǔ)特點(diǎn)，減少空閑能耗。

2）平行架構(gòu)。該方式中PCM和DRAM的同一層混合使用，整個(gè)內(nèi)存由兩者共同組成，統(tǒng)一編址，數(shù)據(jù)只放在PCM或者DRAM中的一個(gè)中，如將寫傾向較高的頁(yè)面放在DRAM中，將讀傾向較高的頁(yè)面放在PCM中。

在層次架構(gòu)下，當(dāng)出現(xiàn)對(duì)內(nèi)存需要較大的調(diào)用時(shí)，會(huì)增大DRAM和PCM 交換的工作量，系統(tǒng)效率較大下降，并且會(huì)增大PCM的磨損。平行架構(gòu)中，根據(jù)PCM 也是字節(jié)尋址的特點(diǎn)，將DRAM和PCM統(tǒng)一地址空間，但由于二者的讀寫等特性不一樣，為了降低能耗并延長(zhǎng)PCM的使用時(shí)間，緩沖區(qū)的管理算法就顯得尤為重要。

1.2.2 平行架構(gòu)緩沖區(qū)管理算法

已有關(guān)于混合內(nèi)存的緩沖區(qū)管理算法主要有LRU-WPAM（least recently used with prediction and migration）[10-11]和CLOCK-DWF（clock with dirty bit and write frequency）[12]。其中，CLOCK-DWF算法對(duì)CLOCK 算法進(jìn)行了改進(jìn)，通過(guò)記錄每個(gè)頁(yè)面的寫次數(shù)來(lái)判斷讀傾向和寫傾向，從而調(diào)度寫傾向在DRAM中，讀傾向在PCM中；LRU-WPAM算法以最近最少使用（LRU）算法為基礎(chǔ)，增加了一個(gè)頁(yè)面讀寫預(yù)測(cè)機(jī)制，從而進(jìn)行頁(yè)面的調(diào)度。

在LRU-WPAM的緩沖區(qū)管理中，當(dāng)緩沖區(qū)頁(yè)面未命中時(shí)，與LRU算法一樣，選擇緩沖區(qū)最近最少使用的頁(yè)面進(jìn)行置換；當(dāng)緩沖區(qū)中頁(yè)面命中時(shí)，首先根據(jù)讀寫請(qǐng)求修改頁(yè)面權(quán)值，然后判斷是否達(dá)到閥值，并根據(jù)權(quán)值決定是否將頁(yè)面移動(dòng)到PCM或者DRAM中，如果目標(biāo)存儲(chǔ)器上沒(méi)有空閑空間，在DRAM中選擇讀子隊(duì)列尾部頁(yè)面釋放，在PCM上選擇寫子隊(duì)列尾部頁(yè)面釋放。

在CLOCK-DWF的緩沖區(qū)管理中，首先，將DRAM和PCM分別組成一個(gè)環(huán)狀隊(duì)列；然后，根據(jù)數(shù)據(jù)訪問(wèn)時(shí)的讀寫類型，將寫請(qǐng)求的頁(yè)面存放在DRAM中，讀請(qǐng)求頁(yè)面存放在PCM中。當(dāng)DRAM空閑空間不足時(shí)，將“寫”冷頁(yè)寫入PCM，當(dāng)PCM空閑空間不足時(shí)，用CLOCK頁(yè)面調(diào)度的算法對(duì)頁(yè)面進(jìn)行調(diào)度。

2 FWLRU混合內(nèi)存緩沖區(qū)調(diào)度策略

在上述算法的混合內(nèi)存管理中，根據(jù)“寫”熱頁(yè)和“讀”熱頁(yè)的判斷，調(diào)度頁(yè)面在PCM或者DRAM中存儲(chǔ)。如果所在頁(yè)面當(dāng)前存儲(chǔ)和判斷的結(jié)果不一致，則需要進(jìn)行PCM和DRAM的頁(yè)面遷移。根據(jù)以上調(diào)度算法，主要會(huì)造成以下幾個(gè)問(wèn)題：

1）頻繁地在PCM和DRAM中進(jìn)行頁(yè)面遷移，要消耗大量的系統(tǒng)資源。同時(shí)，當(dāng)PCM和DRAM中的空閑空間不足時(shí)，需要從二者中選擇頁(yè)面進(jìn)行釋放，釋放的頁(yè)面可能就是即將訪問(wèn)的頁(yè)面，這樣就會(huì)將緩沖區(qū)原先命中的訪問(wèn)變成沒(méi)有命中，造成緩沖區(qū)命中率下降。

2）將“讀”熱頁(yè)從DRAM中遷入PCM，遷移寫入時(shí)實(shí)際上增加了PCM的寫，與減少PCM寫的初衷不一致。

3）當(dāng)頁(yè)面的訪問(wèn)是讀傾向較多的時(shí)候，按照LRU-WPAM、CLOCK-DWF算法的要求，都要遷移進(jìn)入PCM，這樣反而造成PCM寫的增加。

另外，根據(jù)A.R.Alameldeen 等的研究[13-15]，內(nèi)存數(shù)據(jù)訪問(wèn)具有明顯的局部性，局部數(shù)據(jù)的訪問(wèn)達(dá)到40%以上，有些情況下甚至超過(guò)60%。

針對(duì)以上情況，本文提出一種偏向?qū)懻{(diào)度緩沖區(qū)調(diào)度策略（favors write least recently used，F(xiàn)WLRU）的混合內(nèi)存緩沖區(qū)調(diào)度策略，主要進(jìn)行了以下兩個(gè)方面的優(yōu)化：

1）只進(jìn)行“寫”熱頁(yè)的調(diào)度，而不進(jìn)行“讀”熱頁(yè)的調(diào)度?；旌蟽?nèi)存的主要目的是充分利用PCM的高存儲(chǔ)密度和低能耗這兩個(gè)優(yōu)點(diǎn)來(lái)優(yōu)化內(nèi)存，避免PCM讀寫不均衡、寫有限等缺點(diǎn)。DRAM和PCM在讀上區(qū)別并不大，如果強(qiáng)制將所有大于權(quán)值的讀傾向頁(yè)移動(dòng)進(jìn)入PCM，將增加PCM的寫操作，特別是如果讀操作較多時(shí)，寫的次數(shù)將更多。但是如果不進(jìn)行讀頁(yè)面的調(diào)度，對(duì)系統(tǒng)性能將沒(méi)有什么影響。所以在FWLRU算法中只考慮將“寫”熱頁(yè)調(diào)度進(jìn)入DRAM，而不進(jìn)行“讀”熱頁(yè)的調(diào)度。

2）“寫”熱頁(yè)采取PCM和DRAM頁(yè)面互換的原則進(jìn)行遷移。在將“寫”熱頁(yè)從PCM 置換到DRAM 過(guò)程中，當(dāng)DRAM 空間不夠時(shí)，如果采取淘汰策略，有可能淘汰的頁(yè)面就是下一次就要訪問(wèn)的頁(yè)面，這樣就把將要訪問(wèn)的頁(yè)面淘汰掉了，從而把原本命中的操作變成了不命中，降低了命中率。而FWLRU算法中，不進(jìn)行頁(yè)面的淘汰，只是將PCM頁(yè)面的DRAM中的頁(yè)面采取互換原則，以此避免淘汰可能將要被訪問(wèn)的頁(yè)面，提高頁(yè)面的命中率。

2.1 訪問(wèn)行為記錄

FWLRU混合內(nèi)存緩沖區(qū)調(diào)度策略中使用了3個(gè)LRU隊(duì)列：DRAM讀隊(duì)列（DR）、DRAM寫隊(duì)列（DW）、PCM寫隊(duì)列（PW）。

LRU隊(duì)列在緩沖區(qū)中按照訪問(wèn)時(shí)間組成隊(duì)列，其中，最近訪問(wèn)位于隊(duì)列首部，最長(zhǎng)時(shí)間訪問(wèn)位于隊(duì)列尾部。DR隊(duì)列記錄DRAM中頁(yè)面的讀操作，DW隊(duì)列記錄DRAM中的寫操作，PW 隊(duì)列記錄PCM中的寫操作，都按照最近訪問(wèn)原則從前至后排列。

2.2 PCM中“寫”熱頁(yè)和DRAM中頁(yè)面的互換

FWLRU 偏向?qū)懻{(diào)度的緩沖區(qū)調(diào)度策略中，當(dāng)緩沖區(qū)塊命中時(shí)，修改頁(yè)面的權(quán)值，如果是“讀”命中，權(quán)值增加；如果是“寫”命中，權(quán)值減少。將權(quán)值和“讀寫熱頁(yè)判定標(biāo)準(zhǔn)”閥值進(jìn)行比較，若頁(yè)面權(quán)值小于閥值，則說(shuō)明是一個(gè)“寫”熱頁(yè)。根據(jù)緩沖區(qū)和內(nèi)存空間的物理地址（internal memory address）映射，查看這個(gè)頁(yè)面的物理地址是在DRAM中還是在PCM中，如果在PCM中，要進(jìn)行PCM和DRAM 空間頁(yè)面的互換，同時(shí)將頁(yè)面加在LRU隊(duì)列首部。和“讀寫熱頁(yè)判定標(biāo)準(zhǔn)”閥值比較，如果大于閥值，則說(shuō)明是一個(gè)“讀”熱頁(yè)，不進(jìn)行操作。

同時(shí)，根據(jù)讀寫操作，如果是寫，那么根據(jù)物理地址的映射，加入到DW或者PW 隊(duì)列的頭部；如果是DRAM讀寫，那么加入到隊(duì)列的頭部，并修改頁(yè)面的權(quán)值。

“寫”熱頁(yè)將執(zhí)行頁(yè)面從PCM寫入DRAM，如果DRAM 空間有空閑，那么直接寫入；如果DRAM空間已滿，那么將DR隊(duì)列尾部頁(yè)面和“寫”熱頁(yè)互換，如圖1所示。頁(yè)面互換時(shí)，不進(jìn)行DRAM頁(yè)面的淘汰，這樣可以避免將有可能即將訪問(wèn)的頁(yè)面淘汰掉，把頁(yè)面原本的命中操作變成不命中操作，從而降低緩沖區(qū)的頁(yè)面命中率。

圖1 PCM寫熱頁(yè)與DRAM中DR隊(duì)列尾部頁(yè)面互換Fig.1 Exchange of PCM hot page and DR queue tail page in DRAM

2.3 調(diào)度流程

算法1 描述了混合內(nèi)存緩沖區(qū)調(diào)度策略的調(diào)度流程。算法中IMAddr（internal memory address）為頁(yè)面從緩沖區(qū)映射到內(nèi)存的物理地址，物理地址根據(jù)字節(jié)地址范圍劃分為DRAM和PCM 區(qū)域。頁(yè)面如果判定是“寫”熱頁(yè)，且IMAddr在PCM中時(shí)，執(zhí)行2.2所述頁(yè)面互換工作。緩沖區(qū)頁(yè)面訪問(wèn)類型為“讀”時(shí)，修改頁(yè)面權(quán)值加1，同時(shí)將頁(yè)面序列加入到LRU和DR隊(duì)列頭部。

算法1 混合內(nèi)存緩沖區(qū)調(diào)度策略流程

算法完成后，返回IMAddr值。

3 實(shí)驗(yàn)結(jié)果及分析

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

本實(shí)驗(yàn)采用在ubuntu 18.04系統(tǒng)上架設(shè)GEM5[16]模擬器仿真，同時(shí)安裝NVMain[17-18]模擬相變存儲(chǔ)器，從而實(shí)現(xiàn)DRAM和PCM 混合實(shí)驗(yàn)環(huán)境。系統(tǒng)采用SE（系統(tǒng)調(diào)用）模式，PCM的延遲數(shù)據(jù)參照F.Bedeschi的研究[19]，DRAM的延遲參照Micron的測(cè)試[20]。每個(gè)頁(yè)面大小設(shè)定為固定值4 kB，DRAM和PCM的比例采取固定配置形式，按照1∶4 配置，整體存儲(chǔ)空間按照實(shí)驗(yàn)需要進(jìn)行增大或減少。

本實(shí)驗(yàn)選用的數(shù)據(jù)集由真實(shí)數(shù)據(jù)和合成數(shù)據(jù)兩部分構(gòu)成，其中真實(shí)數(shù)據(jù)出自于安徽蕪湖某電商網(wǎng)站交易系統(tǒng)的某日交易記錄，該數(shù)據(jù)集對(duì)數(shù)據(jù)庫(kù)進(jìn)行了356 733次讀和115 790次寫操作；合成數(shù)據(jù)來(lái)自開(kāi)源軟件DiskSim，版本為4.0。DiskSim 進(jìn)行磁盤讀寫模擬，同時(shí)改變配置參數(shù)，設(shè)置局部性讀寫不同的比例來(lái)得到系列數(shù)據(jù)集，挑選其中具有代表性的4個(gè)數(shù)據(jù)組參與混合內(nèi)存實(shí)驗(yàn)。局部性（Locality）中“80%/20%”，指80%的數(shù)據(jù)發(fā)生在20%的空間上。具體實(shí)驗(yàn)數(shù)據(jù)集測(cè)試參數(shù)見(jiàn)表1。

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

3.2 頁(yè)面命中率

將FWLRU混合內(nèi)存緩沖區(qū)調(diào)度策略和LRU、LRU-WPAM、CLOCK-DWF在模擬器上進(jìn)行了頁(yè)面命中率檢測(cè)。圖2給出了5組測(cè)試數(shù)據(jù)集在內(nèi)存頁(yè)面逐漸增大的情況下，4種不同的緩沖區(qū)調(diào)度下頁(yè)面未命中的數(shù)量。

圖2 不同調(diào)度策略下的命中率實(shí)驗(yàn)結(jié)果Fig.2 Experiment results of hit rate under different scheduling

分析圖2所示實(shí)驗(yàn)結(jié)果數(shù)據(jù)，可得出以下結(jié)果：

1）從圖2a至2e的5組類型數(shù)據(jù)的實(shí)驗(yàn)情況看，隨著內(nèi)存容量逐漸增大，頁(yè)面未命中的數(shù)量明顯減小?？梢?jiàn)內(nèi)存容量的大小對(duì)命中率有著直接的影響，容量越大，命中率越高。

2）從命中率情況看，F(xiàn)WLRU算法的命中率比LRU-WPAM和CLOCK-DWF的要高，接近LRU算法的。這和FWLRU算法中不進(jìn)行頁(yè)面的淘汰有關(guān)，只是將“寫”熱頁(yè)從PCM到DRAM的互換，防止了將即將訪問(wèn)的頁(yè)面淘汰而造成的命中率下降。

通過(guò)實(shí)驗(yàn)結(jié)果對(duì)比可以看出，相對(duì)于LRUWPAM和CLOCK-DWF算法，F(xiàn)WLRU算法提高了頁(yè)面的命中率。

3.3 PCM寫次數(shù)

設(shè)定內(nèi)存空間大小固定為1GB（DRAM 與PCM的比值為1∶4）的情況下，對(duì)PCM在FWLRU、LRU、LRU-WPAM、CLOCK-DWF 4種策略下的寫總次數(shù)進(jìn)行實(shí)驗(yàn)?zāi)M，結(jié)果如圖3所示。

圖3 不同調(diào)度策略下的PCM寫次數(shù)實(shí)驗(yàn)結(jié)果Fig.3 Experiment results of PCM write times under different scheduling

通過(guò)圖3所示實(shí)驗(yàn)數(shù)據(jù)可以看出，LRU 由于不考慮兩種存儲(chǔ)介質(zhì)的不同，沒(méi)有進(jìn)行“寫”熱頁(yè)和“讀”熱頁(yè)的調(diào)度，所以PCM寫的次數(shù)最多；LRU-WPAM和CLOCK-DWF 考慮了PCM和DRAM 這兩種存儲(chǔ)介質(zhì)，并進(jìn)行了將“寫”熱頁(yè)存放在DRAM、“讀”熱頁(yè)存放在PCM上，導(dǎo)致PCM寫的數(shù)量有所降低，但將“讀”熱頁(yè)集中到PCM上，移動(dòng)的過(guò)程也增加了PCM的寫，并且對(duì)讀比例大的頁(yè)面進(jìn)行訪問(wèn)，反而有可能加大PCM的寫。FWLRU 考慮讀操作上DRAM和PCM的區(qū)別不大，故不進(jìn)行“讀”熱頁(yè)的移動(dòng)，只將“寫”熱頁(yè)互換到DRAM中，所以PCM寫的次數(shù)比LRU-WPAM和CLOCK-DWF的有所降低。實(shí)驗(yàn)結(jié)果證明，F(xiàn)WLRU 對(duì)PCM 進(jìn)行了優(yōu)化，寫的次數(shù)減少。

4 結(jié)論

非易失性存儲(chǔ)材料PCM 是解決DRAM的存儲(chǔ)密度和降低能耗的好材料，但是PCM 具有讀寫不對(duì)稱和寫有限等缺點(diǎn)，許多研究者提出以多種混合內(nèi)存的緩沖區(qū)調(diào)度策略來(lái)解決這一問(wèn)題。本文在混合內(nèi)存架構(gòu)的基礎(chǔ)上，提出了一種偏向?qū)懻{(diào)度的混合內(nèi)存緩沖區(qū)調(diào)度策略。

1）只將“寫”熱頁(yè)從PCM 置換進(jìn)DRAM，沒(méi)有將“讀”熱頁(yè)寫入PCM，避免了調(diào)度過(guò)程中或者頻繁調(diào)度中對(duì)PCM的寫，特別是讀偏向較多的頁(yè)面；

2）PCM和DRAM 采取頁(yè)面互換的形式，不從DRAM中淘汰頁(yè)面，避免了將可能即將訪問(wèn)的頁(yè)面淘汰，將命中操作變成沒(méi)有命中操作的情況，提高了頁(yè)面訪問(wèn)的命中率。

3）本文從緩沖區(qū)調(diào)度入手來(lái)解決PCM讀寫不對(duì)稱、寫有限等問(wèn)題。但是冷熱頁(yè)的劃分還是采取簡(jiǎn)單的權(quán)值計(jì)數(shù)方式，這種冷熱頁(yè)劃分方式是否過(guò)于簡(jiǎn)單還有待考證；而且沒(méi)有對(duì)PCM的磨寫均衡進(jìn)行考慮，這是下一步研究的方向。