何愛華，岳麗華，吳章玲，郭有強.蚌埠學院 計算機科學與技術系，安徽 蚌埠 33030.中國科學技術大學 計算機科學與技術學院，合肥 3007

?

PCM混合主存系統(tǒng)的寫感知主存管理算法*

何愛華1,2+，岳麗華2，吳章玲2，郭有強1
1.蚌埠學院 計算機科學與技術系，安徽 蚌埠 233030
2.中國科學技術大學 計算機科學與技術學院，合肥 230027

HE Aihua,YUE Lihua,WU Zhangling,et al.Write-aware memory management in PCM-based hybrid memory systems.Journal of Frontiers of Computer Science and Technology,2016,10(6)：799-810.

摘要：相變存儲器（phase change memory，PCM）憑借字節(jié)可尋址，讀取速度快（納秒級），高存儲密度，低能耗等優(yōu)點，在目前基于DRAM（dynamic random access memory）的主存擴展達到瓶頸的情形下，已經(jīng)成為最具前途的主存存儲介質(zhì)之一，但是PCM有高寫延遲，壽命有限等缺陷，因此出現(xiàn)了DRAM/PCM混合主存架構(gòu)。提出了一種以減少PCM寫和保持命中率為目標的混合主存管理算法——寫感知的CLOCK算法（CLOCK with a write-aware strategy，CLOCKW）。已有研究主要基于寫臨近信息（recency of writes，RW）來預測頁面寫熱度，CLOCKW引入內(nèi)在寫距離（inter-write-distance，IWD）概念，并結(jié)合寫臨近信息來預測頁面寫熱度，從而把寫密集頁面放置在DRAM。此外，CLOCKW通過記錄有限的歷史寫操作信息，將新置換進的頁面放在合適的存儲介質(zhì)，避免不必要的頁面遷移。最后，基于CLOCK算法的CLOCKW滿足虛擬主存管理的低代價要求。實驗顯示，CLOCKW在保持命中率前提下，可以有效減少PCM寫次數(shù)。

關鍵詞：相變存儲器；混合主存；寫感知；主存管理

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0799-12

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

信息爆炸時代產(chǎn)生的海量數(shù)據(jù)，對數(shù)據(jù)處理和數(shù)據(jù)分析技術帶來了挑戰(zhàn)，其中首當其沖的是大數(shù)據(jù)存儲技術的挑戰(zhàn)。為了克服數(shù)據(jù)存取過程中DRAM（dynamic random access memory）和二級存儲之間的I/O瓶頸，主張配置大容量DRAM的全新分布式內(nèi)存計算平臺Spark[1]成為熱門話題。但是單節(jié)點上基于DRAM的主存擴展已經(jīng)達到瓶頸，限制了高效數(shù)據(jù)處理與分析技術的發(fā)展[2]。以相變存儲器（phase change memory，PCM）為代表的新型非易失存儲器，憑借接近DRAM的讀速度和支持字節(jié)可尋址的特性，以及存儲密度高，非易失，能耗低等優(yōu)點，一度被期望代替DRAM成為新的主存存儲介質(zhì)（如圖1（a）所示）[3]。但是PCM的寫延遲高，壽命有限等固有缺陷，使PCM完全代替DRAM作為主存的方案不可行。因此，基于DRAM/PCM的混合主存模型成為當前的一個研究熱點[4-8]。目前主流的混合主存模型有兩種：一種是僅PCM的物理地址對操作系統(tǒng)可見，而DRAM作為PCM的緩存，類似于L1、L2片上緩存，其地址空間對操作系統(tǒng)不可見（如圖1（b）所示）；另一種是DRAM和PCM的物理地址空間都對操作系統(tǒng)可見，操作系統(tǒng)可以對兩種存儲介質(zhì)統(tǒng)一編址（如圖1（c）所示）。對于圖1（b）所示結(jié)構(gòu)，整個主存架構(gòu)存儲層次比其他兩種主存架構(gòu)多一層，CPU訪問主存數(shù)據(jù)需要多一層的映射機制轉(zhuǎn)換。另外，CPU訪問數(shù)據(jù)都需要經(jīng)過DRAM緩沖，而CPU上運行程序的多樣性和訪問數(shù)據(jù)的大規(guī)模性，將會導致DRAM與PCM之間數(shù)據(jù)交互增多，頻繁的DRAM數(shù)據(jù)置換和PCM數(shù)據(jù)讀寫將極大影響系統(tǒng)的整體性能。因此本文聚焦于基于圖1（c）架構(gòu)的主存管理研究[9]。

目前基于PCM的混合主存管理技術，主要是針對PCM的讀寫不均衡和寫壽命有限的特性，對傳統(tǒng)面向DRAM的CLOCK、LRU（least recently used）算法進行改進，以減少PCM寫為目標，將寫操作集中在DRAM。LRU-WPAM（LRU with prediction and migration）[10]通過預測頁面讀寫傾向性，將讀傾向頁遷移到PCM，寫傾向頁遷移到DRAM來減少PCM寫操作。CLOCK-DWF（CLOCK with dirty bits and write frequency）[11]通過頁面遷移策略，致力于用DRAM服務所有發(fā)生在PCM的寫請求。但是這兩種算法在頁面遷移時都會將一個頁面替換出主存，造成命中率下降。主存讀寫速度比二級存儲高多個數(shù)量級，因此命中率下降會嚴重影響算法整體性能。在頁缺失情況下，從二級存儲讀一個頁面到PCM主存時，也會造成PCM寫操作，因此D-CLOCK（dual-CLOCK）[12]必要時替換DRAM的頁來限制PCM上發(fā)生頁缺失的次數(shù)，從而減少PCM的寫次數(shù)，這也是以降低命中率為代價。MHR-LRU（maintain-hit-ratio LRU）[13]和APP-LRU（access pattern prediction based LRU）[14]以保證命中率為首要目標，但是只有在頁缺失情況下才會觸發(fā)頁面遷移操作，不能及時將寫傾向頁遷移到DRAM，性能提升有限。

Fig.1　Architectures of PCM-based memory systems圖1　基于PCM的主存系統(tǒng)架構(gòu)圖

LRU算法造成頻繁的鏈表移動以及需要較多的硬件支持，因此并沒有應用到操作系統(tǒng)的虛擬主存管理中，而是廣泛應用于類似于數(shù)據(jù)庫系統(tǒng)緩沖區(qū)管理的場景。近似于LRU但是代價更低的CLOCK算法成為虛擬主存管理的主流算法[15-16]。因此，本文提出一種基于CLOCK的混合主存管理算法——寫感知的CLOCK算法（CLOCK with a write-aware strategy，CLOCKW）。CLOCKW保留了原CLOCK的數(shù)據(jù)結(jié)構(gòu)以及頁面替換算法，因此可以保持和CLOCK相同的命中率。此外，CLOCKW以減少PCM寫為目標，關注頁面寫熱度預測，以便及時將寫熱度高的頁面存儲到DRAM。CLOCKW借鑒LIRS（low inter reference recency set）[17]的IRR（inter-reference recency）思想，引入了內(nèi)在寫距離（inter-write-distance，IWD）概念，并結(jié)合頁面寫臨近信息（recency of writes，RW）來定義頁面寫熱度，用于決策是否將頁面存儲于DRAM來減少PCM寫次數(shù)。同時，當頁面被替換出主存時，CLOCKW并不立即丟棄該頁寫信息，而是繼續(xù)保留一段時間，用于未來該頁重新被載入主存時衡量頁面寫熱度，從而將該頁存儲在合適的存儲介質(zhì)上，避免將來不必要的頁面遷移。為了滿足虛擬主存管理的低代價需求，CLOCKW只保留限定數(shù)目的當前寫和歷史寫信息。因此，CLOCKW不僅有媲美于CLOCK的命中率，而且能有效預測頁面寫熱度，從而將熱寫頁存儲到DRAM上減少PCM上的寫次數(shù)，還可以實際應用于混合主存系統(tǒng)的虛擬主存管理。

2　相關工作

國內(nèi)PCM存儲器上的研究開展得較早，取得的成果也較多。PCM存儲器研究工作的主要機構(gòu)有上海微系統(tǒng)與信息技術研究所、華中科技大學、國防科技大學、中國科學技術大學、清華大學等，它們主要致力于國產(chǎn)PCM芯片[18]、PCM存儲單元糾錯機制[19]、緩沖區(qū)管理[12-14]等方面的研究。

由于混合存儲系統(tǒng)中不同介質(zhì)的訪問速度不同，且PCM寫壽命有限，傳統(tǒng)的面向DRAM主存系統(tǒng)的頁面置換算法已不再適用。

LRU-WPAM[10]在原LRU算法的基礎上，分別增加了DRAM讀鏈表、寫鏈表和PCM讀鏈表、寫鏈表，用于監(jiān)控主存中每個頁的讀寫請求，并以此為基礎將讀傾向頁遷移到PCM、寫傾向頁遷移到DRAM。MHR-LRU[13]和APP-LRU[14]都是在頁缺失時進行頁面遷移操作。MHR-LRU使用DRAM寫鏈表——DWL（DRAM write-aware LRU）記錄DRAM頁的寫操作信息，當DRAM頁面被寫時，被寫頁被置于DWL鏈表頭部，因此位于DWL鏈表尾部的頁面被認為是寫最冷的頁面。如果寫一個新頁面觸發(fā)頁面置換，而置換出的頁面在PCM，MHR-LRU將DRAM中寫最冷的頁遷移到PCM剛置換出的空間，同時將新頁面存儲于DRAM以服務于新頁面上寫請求。APPLRU記錄了部分被替換出頁的讀寫信息作為訪問歷史信息，并結(jié)合頁面當前訪問信息衡量頁面讀寫傾向性。當頁缺失時，可根據(jù)新頁面的訪問歷史信息選擇合適的存儲介質(zhì)。

CLOCK-DWF[11]分別用一個改進的CLOCK鏈表和通用CLOCK鏈表管理DRAM和PCM中的頁面。CLOCKW-DWF所有寫請求都會在DRAM執(zhí)行，當一個新頁面或PCM頁面寫命中時，都會將頁面載入DRAM，若此時DRAM沒有空閑頁面，CLOCK-DWF會根據(jù)DRAM頁面的最近被寫操作命中的情況和寫頻率判斷頁面寫冷熱，從而將DRAM寫最冷的頁面遷移到PCM。如果PCM沒有空閑空間存放從DRAM遷移出的頁面，會調(diào)用CLOCK算法將一個PCM頁替換出主存，引起命中率下降。D-CLOCK[12]采用與CLOCK-DWF相同的策略處理寫請求，即所有寫請求都會在DRAM執(zhí)行。但是D-CLOCK使用全局CLOCK鏈表管理DRAM和PCM頁面，用于頁面置換時選擇替換出的頁面，同時維護一個額外鏈表監(jiān)控DRAM上頁面RW和寫頻率，用于區(qū)分寫熱度高（熱寫）頁和寫熱度低（冷寫）頁。此外，DCLOCK并不是嚴格遵從CLOCK算法選擇替換頁，必要時替換DRAM的頁來限制PCM上發(fā)生頁缺失的次數(shù)，因為即使讀一個頁到PCM也會產(chǎn)生一次PCM寫，而強制替換DRAM頁可能會降低命中率。

綜上所述，LRU-WPAM和APP-LRU算法的數(shù)據(jù)劃分方法為讀寫傾向性劃分，致力于將讀傾向的頁面存儲到PCM上，寫傾向的頁面存儲到DRAM上。前者在頁面遷移時可能將一個頁面換出緩沖區(qū)，引起命中率下降；而后者雖然能保證命中率，但頁面替換時才可能觸發(fā)頁面遷移操作，不能將讀寫傾向性發(fā)生變化的頁面及時遷移到合適的存儲介質(zhì)上。MHR-LRU、CLOCK-DWF和D-CLOCK則是根據(jù)訪問冷熱進行數(shù)據(jù)劃分。MHR-LRU只有DRAM到PCM的單向遷移，當PCM頁面發(fā)生頻繁更新時，無法將其遷移到DRAM上進一步減少PCM上的寫操作。而CLOCK-DWF和D-CLOCK在兩種存儲介質(zhì)之間執(zhí)行數(shù)據(jù)遷移時，會將數(shù)據(jù)換出主存空間，存在命中率下降的問題。本文提出的CLOCKW算法對數(shù)據(jù)進行寫冷熱劃分，將熱寫頁存儲到DRAM上，冷寫頁存儲到PCM上，既能保證算法命中率，也能通過DRAM與PCM之間的頁面遷移有效減少對PCM的寫操作次數(shù)。

3　CLOCKW概述

3.1基本思路

基于PCM混合主存系統(tǒng)的主存管理算法關鍵在于準確預測熱寫頁，并將其存儲到DRAM上，以發(fā)揮DRAM寫帶寬高的優(yōu)勢。此外，應避免將冷寫頁誤分類為熱寫頁，導致DRAM資源浪費和不必要的遷移操作。

已有研究主要借鑒LRU算法，用RW預測頁面寫熱度，但是LRU算法無法有效應對局部性較弱的訪問模式，如數(shù)據(jù)掃描、訪問間隔大于緩沖區(qū)大小的循環(huán)數(shù)據(jù)訪問。LIRS算法提出IRR概念來解決LRU算法的缺陷[17]，該算法定義IRR為頁最近兩次訪問期間被訪問的其他頁的個數(shù)，并用IRR定義頁面訪問熱度，即IRR越小，頁面越熱。CLOCKW借鑒LIRS思想，引入內(nèi)在寫距離概念，定義如下：

定義1（內(nèi)在寫距離，IWD）頁p的IWD指p在倒數(shù)第二次寫和最近一次寫的間隔內(nèi)被寫的其他頁的數(shù)量。如果頁p只被寫過一次或從未被寫過，則p 的IWD為無窮大。

定義2（寫臨近信息，RW）頁p的RW指的是該頁最近一次被寫以后，其他被寫訪問過的頁面數(shù)。

直觀地理解，IWD越小的頁面，寫熱度越高。但是如果一個IWD很小的頁面很長時間沒有被寫，將該頁面繼續(xù)歸類為熱寫頁是不合適的。因此，CLOCKW綜合RW和IWD對熱寫頁和冷寫頁進行分類。

假設熱寫頁里p1的RW最大（記為RWmax），即p1是熱寫頁里最近最久沒被寫過的頁。當一個RW比RWmax小但是IWD很大的冷寫頁 p2被再次寫時，p2的IWD被更新，此時將p2轉(zhuǎn)換為熱寫頁，p1轉(zhuǎn)換為冷寫頁。因為即使p1當前的IWD比 p2的新IWD小，但是p1未來更新的新IWD必然比RWmax大，而p2的新IWD比RWmax?。╬2被再次訪問前的RW比RWmax?。?，所以可以認為 p2的寫熱度比 p1的寫熱度高。因此CLOCKW只需追蹤RW比RWmax小的頁的寫信息即可有效檢測熱寫頁。

CLOCKW的設計思路如下：

（1）CLOCKW設定熱寫頁數(shù)目的上限為DRAM可容納的頁數(shù)目。當一個寫請求命中位于PCM上的頁時，如果CLOCKW保留了該頁的寫歷史信息，則認為該頁是熱寫頁。因此，CLOCKW將該熱寫頁遷移至DRAM，同時將DRAM一個冷寫頁遷移至PCM。

（2）為了保證命中率，CLOCKW采用CLOCK的頁替換算法，但是當一個頁被替換出主存時，該頁寫信息被繼續(xù)保留一段時間。當讀一個新頁觸發(fā)頁面置換時，根據(jù)歷史信息判定該頁是熱寫頁還是冷寫頁，進而決定該頁是存儲到DRAM還是PCM，避免后來不必要的頁面遷移操作。

（3）當寫一個新頁觸發(fā)頁面置換，并且置換出的頁面在PCM時，如果CLOCKW保留了新頁的寫歷史信息，則按（1）處理。但如果CLOCKW未保留該頁寫歷史信息，盡管該頁是冷寫頁，仍將該頁載入DRAM，同時將DRAM里冷寫頁遷移至PCM。因為將新頁載入PCM和寫新頁會造成兩次PCM寫，將該頁載入DRAM可將這兩次PCM寫集中于DRAM，而遷移只造成一次PCM寫。

3.2基本結(jié)構(gòu)

CLOCKW的結(jié)構(gòu)如圖2所示。全局CLOCK鏈表采用原CLOCK的數(shù)據(jù)結(jié)構(gòu)和頁面替換算法來管理所有主存頁面，以保證CLOCKW的命中率和CLOCK的相同。寫CLOCK鏈表記錄了DRAM頁、PCM頁的寫信息，以及部分被替換出主存的頁歷史寫信息。DRAM冷寫頁鏈表存放寫CLOCK鏈表中未記錄寫信息的DRAM頁，這些DRAM頁在相當長一段時間內(nèi)未被寫過。如果所有DRAM頁都在寫CLOCK鏈表有對應寫信息，則DRAM冷寫頁鏈表為空。

Fig.2　Structure of CLOCKW圖2　CLOCKW結(jié)構(gòu)圖

設DRAM容量為nd頁，PCM容量為np頁，主存總?cè)萘繛閚頁（n=nd+np）。寫CLOCK鏈表根據(jù)所記錄頁的寫信息，把頁分為熱寫頁和冷寫頁。CLOCKW的目標是將所有熱寫頁存儲到DRAM以減少PCM寫，因此設置熱寫頁數(shù)目的上限為nd。HANDhot指向RW最大（即RWmax）的熱寫頁，類似于LIRS算法，將最近最久未訪問的熱頁置于LRU棧底，CLOCKW指定HANDhot指向的熱寫頁為寫CLOCK鏈表尾部，而HANDhot逆時針方向所指的第一個頁自然成為寫CLOCK鏈表頭部。當熱寫頁數(shù)目超過上限時，順時針轉(zhuǎn)動HANDhot，將指向的熱寫頁變?yōu)槔鋵戫?。HANDcold總是指向順時針方向離寫CLOCK鏈表尾部（HANDhot）最近的冷寫頁，即RW最大的冷寫頁。CLOCKW限定寫CLOCK鏈表節(jié)點總數(shù)（包括歷史頁寫信息和當前在主存中的頁寫信息）上限為2n，如果節(jié)點總數(shù)超過2n，則移動HANDcold將指向的冷寫頁從寫CLOCK鏈表移除。從寫CLOCK鏈表移除的DRAM頁會插入到DRAM冷寫頁鏈表頭部。

CLOCK算法引入訪問位來近似LRU的棧操作，CLOCKW與CLOCK類似。當一個頁被寫時，如果寫CLOCK鏈表保留了該頁寫信息，將該頁寫訪問位置1。HANDhot掃過寫訪問位為1的熱寫頁時，不會將該熱寫頁變?yōu)槔鋵戫?，而是將寫訪問位置0，繼續(xù)尋找下一個熱寫頁。HANDcold掃過寫訪問位為1的冷寫頁時，由于該頁最近又被寫過，HANDcold并不會將該頁移除，而是引入冷標志位，將該頁冷標志位置1。引入冷標志位概念后，HANDcold應指向順時針方向離HANDhot最近且冷標志位未被置1的冷寫頁。

HANDcold掃過熱寫頁時，直接略過該頁，但是HANDhot掃過冷寫頁時，所做工作和HANDcold掃過該頁一樣，即將寫訪問位為0的冷寫頁移除，寫訪問位為1的頁面的冷標志位置1。這是因為HANDhot指向的熱寫頁為寫CLOCK鏈表尾部，該熱寫頁代表RW最大（RWmax）的熱寫頁，而CLOCKW只需追蹤RW比RWmax小的頁的寫信息，當HANDhot定位在新的熱寫頁時，RW比新的熱寫頁大的寫信息無需再保留。

DRAMcold總是指向離HANDcold順時針方向最近的寫訪問位為0的DRAM冷寫頁或者訪問位為1且冷標志位為1的DRAM冷寫頁。如果沒有這兩種類型的DRAM冷寫頁，則DRAMcold為空。

3.3頁請求處理策略

當一個頁請求到達時，主存系統(tǒng)會面臨頁請求命中和未命中兩種情形，在介紹這兩種情形下的處理方法之前，首先介紹一個輔助算法——DRAM冷寫頁查找算法。該算法查找DRAM上的冷寫頁，優(yōu)先從DRAM冷寫頁鏈表查找，接著查看DRAMcold指針是否指向一個DRAM冷寫頁，若找到存儲在DRAM上的冷寫頁，則直接返回（算法1第1～4行）。如果都沒找到，CLOCKW嘗試把一個寫訪問位為1且冷標志位為0的冷寫頁變熱，這可能會導致熱寫頁數(shù)目超過上限，從而觸發(fā)HANDhot順時針轉(zhuǎn)動把相對較冷的熱寫頁轉(zhuǎn)換為冷寫頁（算法1第5～20行）。CLOKCW致力于將熱寫頁置于DRAM，因此變冷的熱寫頁很大概率會在DRAM上（變冷的頁也有可能不在主存中，因為CLOCKW保留了原CLOCK的頁面替換算法，一個熱寫頁可能因其他頁的頻繁讀請求被替換出主存），當變冷的頁面不在DRAM上面時，算法返回空指針，否則返回變冷的DRAM頁面，如算法1第18～20行所示。若臨時指針掃描一圈都未找到寫訪問位為1且冷標志位為0的DRAM冷寫頁，可斷定所有熱寫頁都是DRAM頁，此時轉(zhuǎn)動HANDhot將寫熱度最低的DRAM熱寫頁變冷，如算法1第21～23行所示。

算法1 DRAM冷寫頁查找算法

輸出：存儲在DRAM上的冷寫頁或空。

1.If（DRAM冷寫頁鏈表不為空）then

2.return位于DRAM冷寫頁鏈表尾部的頁；

3.else if（DRAMcold指針不為空）then

4.return DRAMcold指針指向的頁并將DRAMcold指向順時針方向下一個DRAM冷寫頁；

5.else//DRAMcold為空

6.啟動臨時指針p，從HANDcold開始順時針掃描

7.if（p是熱寫頁或?qū)懺L問位為0的冷寫頁）then

8.p指向順時針方向的下一個頁面；

9.else if（p是寫訪問位和冷標志位都為1的冷寫頁）then

10.將該頁移到寫CLOCK鏈表頭部；

11.p的寫訪問位和冷標志位置為0；

12.else if（p是寫訪問位為1且冷標志位為0的冷寫頁）then

13.將該頁轉(zhuǎn)為熱寫頁；寫訪問位置為0；

14.移動該頁到寫CLOCK鏈表頭部；

15.if（熱寫頁數(shù)目未超過上限）then

16.return NULL；

17.else

18.轉(zhuǎn)動HANDhot將一個熱寫頁p轉(zhuǎn)為冷寫頁；

19.If（p為DRAM頁）then返回p；

20.else return NULL；

21.轉(zhuǎn)動HANDhot將一個熱寫頁p轉(zhuǎn)為冷寫頁；

22.if（p為DRAM頁）then returnp；

23.else return NULL；

算法2給出了CLOCKW在頁請求命中時的處理策略。只有寫一個PCM頁并且寫CLOCK鏈表中保留了該頁寫信息時，才可能發(fā)生頁面遷移，如第3～7行所示。因為此時該PCM頁被認為是熱寫頁，應將該頁面與一個DRAM冷寫頁交換。當一個PCM頁被認定為熱寫頁時，算法1將調(diào)用DRAM冷寫頁查找算法嘗試尋找一個DRAM冷寫頁，并將該冷寫頁與被命中的PCM頁進行交換（第5～7行）。否則，若寫CLOCK鏈表中未發(fā)現(xiàn)被寫訪問命中的頁寫信息，則認為該頁為冷寫頁，無需進行交換操作，但它的寫訪問信息將被加入到寫CLOCK鏈表中，如第8～12行所示。但若訪問請求類型為讀操作，則除了置位頁面的訪問位以外，沒有任何其他操作。

算法2頁請求命中處理算法

輸入：請求頁p，訪問類型op。

輸出：請求頁的主存地址。

1.將全局CLOCK鏈表中頁p的訪問位置1；

2.If（op為寫請求）then

3.if（寫CLOCK鏈表保留了頁p寫信息）then

4.將寫CLOCK鏈表中頁p寫訪問位置1；

5.if（p在PCM）then

6.if（調(diào)用DRAM冷寫頁查找算法找到一個DRAM冷寫頁q）then

7.將q遷移至PCM；將頁p載入DRAM；

8.else//寫CLOCK鏈表未發(fā)現(xiàn)頁p寫信息

9.將頁p的寫信息加入到鏈表頭部；

10.設置頁p為冷寫頁；初始化寫訪問位和冷標志位為0；

11.if（鏈表保留的寫信息達到上限）then

12.轉(zhuǎn)動HANDcold移除部分冷寫頁信息；

13.返回頁p在DRAM或PCM的主存地址；

算法3給出了CLOCKW在頁請求未命中時的處理策略。該算法首先根據(jù)傳統(tǒng)CLOCK頁面替換規(guī)則從全局CLOCK鏈表中選取頁面換出主存（第1行），當一個缺失頁準備從磁盤載入主存時，CLOCKW根據(jù)該頁的寫歷史信息和訪問類型選擇合適的存儲介質(zhì)。若頁請求類型為讀且被訪問頁在寫CLOCK鏈表顯示為熱寫頁，則嘗試為其分配一個DRAM上的存儲空間，此時若換出頁在PCM上，將觸發(fā)遷移操作從DRAM遷移一個冷寫頁到PCM上，如第3～10行所示。但是正如3.1節(jié)設計思路所提到的，如果寫一個新頁觸發(fā)頁面置換，并且置換出的頁面在PCM時，CLOCKW總是將DRAM一個冷寫頁遷移至PCM，同時將新頁載入DRAM（第21～25行所示）。此外，還需向?qū)慍LOCK鏈表更新或添加被訪問頁的寫信息，以便將來對其進行寫冷熱判斷，具體細節(jié)如第14～20行所示。最后算法更新全局CLOCK鏈表信息，用于執(zhí)行頁面替換策略（第26行）。

算法3頁請求未命中處理算法

輸入：請求頁p，訪問類型op。

輸出：請求頁的主存地址。

1.根據(jù)全局CLOCK鏈表的訪問信息，利用CLOCK的頁面替換算法，選擇一個頁q替換出主存；

2.If（op是讀操作）then

3.if（寫CLOCK鏈表保留了頁p的寫信息，并顯示p是熱寫頁）then

4.if（頁q在DRAM）then

5.將頁p載入DRAM；

6.else//頁q在PCM

7.if（調(diào)用DRAM冷寫頁查找算法找到一個DRAM冷寫頁c）then

8.將頁c遷移至q所在位置；將頁p載入DRAM

9.else//嘗試尋找DRAM冷寫頁失敗

10.將頁p載入到頁q的位置；

11.else//頁p是冷寫頁

12.將頁p載入到頁q的位置；

13.else//op是寫操作

14.if（寫CLOCK鏈表保留頁p寫信息）then

15.將寫CLOCK鏈表中頁p寫訪問位置1；

16.else//寫CLOCK鏈表未發(fā)現(xiàn)頁p寫信息

17.將頁p的寫信息加入到鏈表頭部；

18.設置頁p為冷寫頁；初始化寫訪問位和冷標志位為0

19.if（鏈表保留的寫信息達到上限）then

20.轉(zhuǎn)動HANDcold移除部分冷寫頁信息;

21.if（頁q在DRAM）then

22.將頁p載入DRAM；

23.else//頁q在PCM

24.調(diào)用DRAM冷寫頁查找算法直到找到一個DRAM冷寫頁c為止；

25.將頁c遷移至q所在位置；將頁p載入DRAM；

26.將頁p加入全局CLOCK鏈表；設置訪問位為1；

27.返回頁p在DRAM或PCM的主存地址；

總體來說，相比于CLOCK算法，CLOCKW中每個頁需要4 bit表示頁寫信息和訪問信息，原CLOCK算法只需要1 bit表示其訪問信息，空間復雜度增長并不是很大，若原CLOCK算法的空間復雜度為S(n)，則CLOCKW算法的空間復雜度為S(4n)。CLOCKW算法最好情況下，每次讀寫操作都不會觸發(fā)遷移操作，只有對全局CLOCK鏈表的掃描執(zhí)行頁面替換操作，這種情形下CLOCKW算法退化成CLOCK算法，其算法時間復雜度與原CLOCK算法相同；相反，若每次寫請求均會觸發(fā)遷移操作，遷移操作將會對寫CLOCK鏈表進行掃描，而寫CLOCK鏈表的長度是全局CLOCK鏈表的兩倍，因此CLOCKW算法最壞情形下的時間復雜度是原CLOCK算法的3倍。最后，當頁面被寫命中時，只需更新對應頁面的位信息，而位信息置位可由底層硬件實現(xiàn)，只有可能觸發(fā)頁面遷移時才會有部分鏈表操作，這些操作將大大減少PCM上的寫操作，但PCM寫延遲是DRAM的幾倍，因此總體上來說，并不會影響系統(tǒng)的整體性能。

4　實驗與分析

本文實驗與傳統(tǒng)CLOCK算法和基于CLOCK算法設計的CLOCK-DWF[6]、D-CLOCK[7]進行對比。

4.1實驗設置

由于PCM目前還沒有商業(yè)化產(chǎn)品，本文采用仿真實驗來測試算法的有效性，實驗中仿真實現(xiàn)了DRAM與PCM的同級主存架構(gòu)，采用統(tǒng)一編址模式，DRAM占據(jù)低端地址空間，而PCM使用高端地址空間，即算法可以通過頁面地址判斷出該頁是屬于DRAM還是PCM；在為新頁分配空間時，指定需要存儲在DRAM上還是PCM上，系統(tǒng)根據(jù)分配的頁面地址空間判斷是否符合分配需求，若不符合則可能觸發(fā)遷移操作。實驗中，主存頁幀大小為4 KB，主存空間大小設定從1 000個頁幀到3 000個頁幀。PCM的存儲密度被認為可以達到DRAM的4倍，因此DRAM與PCM總是維持1∶4的空間大小比例。

實驗中使用了5種類型的測試數(shù)據(jù)集，如表1所示。其中一個是OLTP數(shù)據(jù)集，即由Gerhard Weikum提供的真實的銀行系統(tǒng)交易處理數(shù)據(jù)集，該數(shù)據(jù)集對CODASYL數(shù)據(jù)庫進行了470 677次頁面讀和136 713次頁面寫，曾被用于文獻[20-21]的實驗測試。另外4個是人工生成的Zipf訪問序列[22]。對于有N個不同頁面的Zipf數(shù)據(jù)集，頁面i被訪問的概率滿足式（1）：

Table 1　Parameters of Zipf and OLTP traces表1 Zipf與OLTP數(shù)據(jù)集參數(shù)

4.2合成數(shù)據(jù)集實驗評估

4.2.1頁面缺失

圖3顯示了系統(tǒng)運行Zipf合成數(shù)據(jù)集時，CLOCKW與其他3個對比算法的頁面缺失數(shù)隨著主存空間大小變化的實驗結(jié)果。

從圖3中可以看出，各個算法的頁面缺失隨著主存空間增加而減少，CLOCKW頁面缺失數(shù)與傳統(tǒng)CLOCK算法相同。實驗數(shù)據(jù)顯示，D-CLOCK的頁面缺失數(shù)雖然在多數(shù)情況下與CLOCK相近，但在某些情形下會略高于CLOCK，這是由于D-CLOCK為防止從二級存儲器讀入的頁被頻繁寫入PCM，會從DRAM上強制替換出一個頁面用于存儲新讀入的頁面，這種做法可能會將一個熱度較高的頁面替換出主存。而CLOCK-DWF雖然在Zipf1955和Zipf4655數(shù)據(jù)集下頁缺失數(shù)與其他3個算法相似，但在數(shù)據(jù)訪問比較集中的情況下（如Zipf4682和Zipf1982），頁面缺失數(shù)較其他3種算法多。這是因為CLOCK-DWF在從DRAM遷移頁面到PCM且PCM沒有空閑空間時，會調(diào)用CLOCK算法將PCM頁替換出主存，從而增加頁面缺失。

Fig.3　Page fault counts on Zipf traces圖3　Zipf系列數(shù)據(jù)集頁面缺失數(shù)

4.2.2PCM寫次數(shù)

在基于PCM的混合主存系統(tǒng)中的主存管理算法，除了要保證命中率以外，減少PCM上的寫次數(shù)也是一個重要的設計目標。圖4描述了隨著主存空間變化，4種算法對PCM主存的寫操作數(shù)，包括從磁盤寫入PCM和從DRAM遷移到PCM引起的寫，以及數(shù)據(jù)集對PCM的寫請求。

從圖4中可以明顯看出，雖然數(shù)據(jù)集不同，但隨著主存空間容量變大，DRAM空間也相應增加，能容納更多的寫頁面，4種算法對PCM的寫次數(shù)有著相似的變化趨勢——呈遞減趨勢。圖4同時也顯示，CLOCKW對PCM的寫操作次數(shù)僅是CLOCK算法的55%～66%，而相比于CLOCKW，D-CLOCK和CLOCKDWF會引起更多PCM寫。

這是因為在D-CLOCK和CLOCK-DWF中，每一次PCM上的寫命中都會觸發(fā)一次頁面遷移，這會引起大量的頁面遷移操作，而CLOCKW是根據(jù)對命中的PCM頁面的冷熱判斷來決定是否需要遷移到DRAM，從而減少了某些不必要的頁面遷移。

4.3OLTP數(shù)據(jù)集實驗評估

本節(jié)介紹OLTP數(shù)據(jù)集在4種算法上的運行結(jié)果。圖5（a）和圖5（b）分別描述了實驗在PCM上的寫次數(shù)和頁面缺失數(shù)對比。

從圖5（a）可以看出，CLOCKW的PCM寫次數(shù)高于D-CLOCK。實驗顯示，D-CLOCK的PCM寫次數(shù)僅是CLOCK的78%～81%，而CLOCKW比D-CLOCK大約多10%的PCM寫。這是由于OLTP數(shù)據(jù)集具有較多的不同訪問頁面，缺失率高，同時該數(shù)據(jù)集含有大量的讀請求，CLOCKW不會將讀未命中的頁面強制放入DRAM上存儲，但D-CLOCK會以降低命中率為代價，強制替換出DRAM的頁，使得從二級存儲器新讀入的頁被存儲到DRAM上，從而限制新進頁寫入到PCM上的次數(shù)，以減少PCM的寫次數(shù)。當目標存儲器上沒有空閑的存儲空間時，D-CLOCK和CLOCKDWF均會采取強制頁替換策略，因此D-CLOCK和CLOCK-DWF在運行OLTP數(shù)據(jù)集時，頁缺失數(shù)明顯高于CLOCK和CLOCKW算法，如圖5（b）所示。由于主存與二級存儲器之間的訪問延遲相差多個數(shù)量級，以大量頁面缺失來換取PCM寫次數(shù)的減少將嚴重影響系統(tǒng)數(shù)據(jù)訪問的性能。

Fig.4　PCM write counts on Zipf traces圖4　Zipf系列數(shù)據(jù)集PCM寫次數(shù)

Fig.5　Page fault counts and PCM write counts on OLTP trace圖5　OLTP數(shù)據(jù)集頁面缺失數(shù)和PCM寫次數(shù)

5　結(jié)論

本文提出了一種基于CLOCK的混合主存管理算法——寫感知CLOCK算法CLOCKW。CLOCKW采用傳統(tǒng)的CLOCK算法替換策略，以保證與CLOCK相同的命中率。同時，CLOCKW引入了“內(nèi)在寫距離”概念，并結(jié)合頁面寫臨近信息來定義和預測頁面寫熱度，從而能及時將寫熱度高的頁面放置于DRAM上，減少對PCM的寫。當頁面被替換出主存時，CLOCKW會保留頁面歷史寫信息用于未來該頁重新被載入主存時衡量頁面寫熱度，從而將該頁放置在合適的存儲介質(zhì)上，減少不必要的頁面遷移。實驗結(jié)果表明，本文算法在不同數(shù)據(jù)集下都能保證與CLOCK相同的命中率，同時又能較為準確地預測頁面的寫冷熱，通過DRAM與PCM之間的頁面遷移，有效減少PCM的寫次數(shù)。

References:

[1]Apache Spark.Spark overview and programming guide [EB/OL].[2016-02-19].http://spark.apache.org/.

[2]Wu Zhangling,Jin Peiquan,Yue Lihua,et al.A survey on PCM-based big data storage and management[J].Journal of Computer Research and Development,2015,52(2):343-361.

[3]Seong N H,Woo D H,Lee H S.Security refresh:prevent malicious wear-out and increase durability for phase-change memory with dynamically randomized address mapping[C]// Proceedings of the 37th International Symposium on Computer Architecture,Saint-Malo,France,Jun 19-23,2010. New York,USA:ACM,2010:383-394.

[4]Seok H,Park Y,Park K H.Migration based page caching algorithm for a hybrid main memory of DRAM and PRAM[C]// Proceedings of the 26th Annual ACM Symposium on Applied Computing,Taichung,China,Mar.21-24,2011.New York,USA:ACM,2011:595-599.

[5]Shin D J,Park S K,Kim S M,et al.Adaptive page grouping for energy efficiency in hybrid PRAM-DRAM main memory[C]//Proceedings of the 2012 ACM Research in Applied Computation Symposium,San Antonio,USA,Oct 23-26, 2012.New York,USA:ACM,2012:395-402.

[6]Qureshi M K,Srinivasan V,Rivers J A.Scalable high performance main memory system using phase-change memory technology[C]//Proceedings of the 36th Annual International Symposium on Computer Architecture,Austin,USA,Jun 20-24,2009.New York,USA:ACM,2009:24-33.

[7]Park H,Yoo S,Lee S.Power management of hybrid dram/ pram-based main memory[C]//Proceedings of the 48th ACM/ EDAC/IEEE Design Automation Conference,San Diego, USA,Jun 5-9,2011.New York,USA:ACM,2011:59-64.

[8]Condit J,Nightingale E B,Frost C,et al.Better I/O through byte-addressable,persistent memory[C]//Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles,Big Sky Resort,USA,Oct 11-14,2009.New York,USA:ACM,2009:133-146.

[9]Chen Shimin,Gibbons P B,Nath S.Rethinking database algorithms for phase change memory[C]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research,Asilomar,USA,Jan 9-12,2011:21-31.

[10]Seok H,Park Y,Park K W,et al.Efficient page caching algorithm with prediction and migration for a hybrid main memory[J].ACM SIGAPP Applied Computing Review, 2011,11(4):38-48.

[11]Lee S,Bahn H,Noh S H.CLOCK-DWF:a write historyaware page replacement algorithm for hybrid PCM and DRAM memory architectures[J].IEEE Transactions on Computers,2014,63(9):2187-2200.

[12]Chen Kaimeng,Jin Peiquan,Yue Lihua.Efficient buffer management for PCM-enhanced hybrid memory architecture[C]//LNCS 9313:Proceedings of the 17th Web Technologies and Applications,Guangzhou,China,Sep 18-20,2015. Berlin,Heidelberg:Springer,2015:29-40.

[13]Chen Kaimeng,Jin Peiquan,Yue Lihua.A novel page replacement algorithm for the hybrid memory architecture involving PCM and DRAM[C]//LNCS 8707:Proceedings of the 11th IFIP International Conference on Network and Parallel Computing,Ilan,China,Sep 18-20,2014.Berlin, Heidelberg:Springer,2014:108-119.

[14]Wu Zhangling,Jin Peiquan,Yang Chengcheng,et al.APPLRU:a new page replacement method for PCM/DRAM-based hybrid memory systems[C]//LNCS 8707:Proceedings of the 11th IFIP International Conference on Network and Parallel Computing,Ilan,China,Sep 18-20,2014.Berlin, Heidelberg:Springer,2014:84-95.

[15]Friedman M B.Windows NT page replacement policies[C]// Proceedings of the 25th International Computer Measurement Group Conference,Reno,USA,Dec 5-10,1999:234-244.

[16]Jiang Song,Chen Feng,Zhang Xiaodong.CLOCK-Pro:an effective improvement of the CLOCK replacement[C]// Proceedings of the Annual Conference on USENIX Annual Technical Conference,Anaheim,USA,Apr 10-15,2005.Berkeley,USA:USENIXAssociation,2005:323-336.

[17]Jiang Song,Zhang Xiaodong.LIRS:an efficient low inter-reference recency set replacement policy to improve buffer cache performance[J].ACM SIGMETRICS Performance Evaluation Review,2002,30(1):31-42.

[18]Cai Daolin,Chen Houpeng,Wang Qian,et al.An 8 Mb phase change random access memory based on 0.13 μm technology[J].Research&Progress of Solid State Electronics,2011,31(6):601-605.

[19]Fan Jie,Jiang Song,Shu Jiwu,et al.Aegis:partitioning data block for efficient recovery of stuck-at-faults in phase change memory[C]//Proceedings of the 46th Annual IEEE/ ACM International Symposium on Microarchitecture,Davis, USA,Dec 7-11,2013.NewYork,USA:ACM,2013:433-444.

[20]Jin Peiquan,Ou Yi,H?rder T,et al.AD-LRU:an efficient buffer replacement algorithm for flash-based databases[J]. Data&Knowledge Engineering,2012,72:83-102.

[21]O?neil E,O?neil P,Weikum G.The LRU-K page replacement algorithm for database disk buffering[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data,Washington,USA,May 25-28,1993. New York,USA:ACM,1993:297-306.

[22]Knuth D.Sorting and searching[M]//TheArt of Computer Programming:Volume 3.Massachusetts:Addison-Wesley,1973.

附中文參考文獻：

[2]吳章玲,金培權(quán),岳麗華,等.基于PCM的大數(shù)據(jù)存儲與管理研究綜述[J].計算機研究與發(fā)展,2015,52(2):343-361.

[18]蔡道林,陳后鵬,王倩,等.基于0.13 μm工藝的8 Mb相變存儲器[J].固體電子學研究與進展,2011,31(6):601-605.

HE Aihua was born in 1975.She received the M.S.degree from Anhui University in 2008.Now she is a teacher at Bengbu University,and visiting scholar at University of Science and Technology of China.Her research interests include hybrid memory management and flash-based databases.

何愛華（1975—），女，2008年于安徽大學獲得碩士學位，現(xiàn)為蚌埠學院教師，中國科學技術大學訪問學者，主要研究領域為混合存儲管理，閃存數(shù)據(jù)庫。

YUE Lihua was born in 1952.She received the M.S.degree from University of Science and Technology of China in 1991.Now she is a professor and Ph.D.supervisor at University of Science and Technology of China.Her research interests include database system and application,information integration and real time database.

岳麗華（1952—），女，1991年于中國科學技術大學獲得碩士學位，現(xiàn)為中國科學技術大學教授、博士生導師，主要研究領域為數(shù)據(jù)庫系統(tǒng)及運用，信息集成，實時數(shù)據(jù)庫。

WU Zhangling was born in 1988.She is a Ph.D.candidate at University of Science and Technology of China.Her research interests include hybrid memory management,flash-based databases and new database architecture.

吳章玲（1988—），女，中國科學技術大學計算機科學與技術學院博士研究生，主要研究領域為混合存儲管理,閃存數(shù)據(jù)庫，新型數(shù)據(jù)庫架構(gòu)。

GUO Youqiang was born in 1966.He received the M.S.degree from Hefei University of Technology in 2006.Now he is a professor and M.S.supervisor at Bengbu University.His research interests include data mining,information integration,algorithm design and optimization.

郭有強（1966—），男，2006年于合肥工業(yè)大學獲得碩士學位，現(xiàn)為蚌埠學院教授、碩士生導師，主要研究領域為數(shù)據(jù)挖掘，信息集成，算法設計及優(yōu)化。

*The National Natural Science Foundation of China under Grant No.61472376(國家自然科學基金);the Key Projects of Domestic and Foreign Research and Training of Outstanding Young and Middle Aged Backbone Talents in Universities under Grant No. gxfxZD2016269(高校優(yōu)秀中青年骨干人才國內(nèi)外訪學研修重點項目).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡優(yōu)先出版:2016-04-21,http://www.cnki.net/kcms/detail/11.5602.TP.20160421.1451.002.html

+Corresponding author:E-mail:flyhah@163.com

文獻標志碼：A

中圖分類號：TP316.1

doi:10.3778/j.issn.1673-9418.1603007

Write-Aware Memory Management in PCM-Based Hybrid Memory Systems?

HEAihua1,2+,YUE Lihua2,WU Zhangling2,GUO Youqiang1
1.Department of Computer Science and Technology,Bengbu University,Bengbu,Anhui 233030,China
2.School of Computer Science and Technology,University of Science and Technology of China,Hefei 230027,China

Abstract:Phase change memory(PCM)has been increasingly viewed as an attractive technology to incorporate into the memory hierarchy since the scalability of DRAM(dynamic random access memory)is approaching its limit.Although PCM has higher density and lower idle power consumption than DRAM while exhibiting byte-addressability and read latencies in the nanosecond range,it has poor write performance and limited endurance.Therefore,researchers have proposed hybrid memory systems involving both PCM and DRAM.This paper presents CLOCKW(CLOCK with a write-aware strategy),a novel hybrid memory management scheme that is designed to not only minimize writes to PCM,but also maintain a high hit ratio.The purpose of CLOCKW is trying to make write-intensive pages resident in DRAM.Particularly,differing from previous studies,which use RW(recency of writes)to estimate future access patterns,this paper introduces the concept of IWD(inter-write-distance),and combines it with RW to estimate hotness of future writes.In addition,by additionally keeping a record of a limited number of replaced pages’write references and placing the newly reached page in an appropriate storage medium when page fault occurs,unnecessary migrationsbetween DRAM and PCM can be avoided.More importantly,CLOCKW is based on the CLOCK scheme,and its running cost is affordable for virtual memory management.The evaluation shows that CLOCKW can efficiently reduce PCM writes without degrading the hit ratio.

Key words:phase change memory;hybrid memory;write-aware;buffer management