裴頌文 錢藝幻 葉笑春 劉海坤 孔令和

1(上海理工大學光電信息與計算機工程學院 上海 200093)

2(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學院計算技術(shù)研究所) 北京 100190)

3(華中科技大學計算機科學與技術(shù)學院 武漢 430074)

4(上海交通大學計算機科學與工程系 上海 200240)

在大數(shù)據(jù)技術(shù)快速發(fā)展的當下，傳統(tǒng)的隨機動態(tài)存取存儲器(dynamic random access memory, DRAM)逐漸暴露出其局限性，如存儲密度小、帶寬有限、能耗大等[1-3]，揭示了傳統(tǒng)DRAM無法滿足越來越大的內(nèi)存需求.因此，為了解決這一問題，近年來涌現(xiàn)的非易失性存儲器(non-volatile memory, NVM)[4-7]被廣泛關(guān)注，并與DRAM組成異構(gòu)內(nèi)存系統(tǒng)[8-11]，大量研究圍繞非易失性內(nèi)存和異構(gòu)內(nèi)存展開[12-15].NVM擁有比DRAM更大的存儲密度，無靜態(tài)能耗，即不需要反復刷新保存數(shù)據(jù)，從而成為構(gòu)建主存的理想存儲設(shè)備.

然而，與傳統(tǒng)DRAM相比，NVM同樣具有寫操作時延高、耐久性差、寫操作能耗高等缺點.以相位存儲器(phase change memory, PCM)為例，相比簡單的電荷移動，PCM需要更多的能量來改變相變材料(基硫族化合物)內(nèi)部的原子結(jié)構(gòu).另外，PCM的寫入時延大約是DRAM寫入時延的10倍.更詳細的DRAM與部分NVM的特性對比如表1所示.因此，當DRAM和NVM構(gòu)成異構(gòu)內(nèi)存時，應將訪問頻率更高的“熱”內(nèi)存頁存放在DRAM中，而將“冷”內(nèi)存頁存放在NVM中，如此，系統(tǒng)便可以同時兼?zhèn)銷VM和DRAM兩者的性能優(yōu)勢.但這同時又衍生出了新的問題，即如何進行內(nèi)存頁面的放置遷移操作.

近年來，許多相關(guān)研究都試圖解決在NVM和DRAM之間進行內(nèi)存頁遷移的問題，如多級隊列替換算法(multi-queue replacement algorithm, MQRA)[16]、CLOCK-DWF[17]、基于雙向散列鏈表的頁面遷移機制(THMigrator)[18]等.雖然它們在一定程度上優(yōu)化了異構(gòu)內(nèi)存系統(tǒng)帶來的問題，但也造成了冗余的頁面遷移操作，從而降低系統(tǒng)的性能.由于不準確的遷移執(zhí)行參數(shù)與預測機制，進行遷移的頁面實際上可能不夠“熱”，而有些頁面則可能會過早地被遷回NVM，這將導致2種設(shè)備之間頻繁地往返遷移.同時頁面遷移造成的不可避免的操作和資源消耗，例如頁面的重新分配、頁表的更新、帶寬消耗等，都將帶來巨大的系統(tǒng)開銷.因此，不必要的遷移所產(chǎn)生的代價可能反而超過了頁面遷移帶來的收益.此外，NVM的大量數(shù)據(jù)寫入操作也縮短了設(shè)備的使用壽命，并增加了訪問時延.

我們通過實驗觀察到，當應用程序?qū)Ａ繑?shù)據(jù)進行處理時，主存DRAM中被逐出的“冷”頁，可能會在短時間內(nèi)再次變“熱”.在這種情況下，頁面將進行重復的遷移操作，這將會增加NVM的寫入次數(shù)且消耗不必要的系統(tǒng)資源.

定義1.重復遷移.對任意內(nèi)存頁面x和遷移操作序列M=(M1,M2,…,Mi,…,Mn)，若當前執(zhí)行的遷移操作Mi使得x的遷移總次數(shù)n≥2，則遷移操作Mi為x執(zhí)行了一次重復遷移.

定義2.冗余遷移.對任意內(nèi)存頁面x和遷移操作序列M=(M1,M2,…,Mi,…,Mn)，若當前執(zhí)行的遷移操作Mi使得x的遷移總次數(shù)n≥2，且對頁面x的第i次遷移與第i-1次遷移之間的時間間隔t≤σ，則遷移操作Mi為x執(zhí)行了冗余遷移.

其中σ是較小的時間閾值，由不同的內(nèi)存器件和內(nèi)存層次結(jié)構(gòu)的差異而定.

Fig. 1 The percentage of re-migration of CoinMigrator, MQRA and THMigrator圖1 CoinMigrator/MQRA/THMigrator的重復 遷移操作占比

如圖1所示，以CoinMigrator，MQRA，THMigrator為例，對于基準測試bzip2，cactusADM，omnetpp，sjeng，與總的遷移次數(shù)相比，平均有72.50%，66.33%，69.050%，69.11%的遷移操作為重復遷移.此外，由于遷移參數(shù)的主觀人為設(shè)定，一些研究中的頁面“冷”“熱”程度判斷機制可能無法準確判斷并預測一個頁面是否真的“熱”.同時，被判定為“熱”頁的頁面可能不會立即執(zhí)行遷移，由于前一個頁面未完成遷移操作而導致當前頁面需要等待，在這種情況下，在當前頁面完成遷移時，它可能不會再與之前一樣“熱”，并且由于“冷”“熱”判斷標準的不同被對應遷回NVM的頁面可能比遷移到DRAM的頁面更“熱”.這樣的頁面遷移是不必要的，它們不僅會降低系統(tǒng)性能，同時也增加了系統(tǒng)資源的消耗.

為了解決這些問題，本文提出了一種基于DRAM的犧牲Cache(DRAM-based victim Cache, DVC)的異構(gòu)內(nèi)存頁遷移機制(victim Cache for page migration on hybrid main memory system, VC-HMM).當執(zhí)行頁面遷回時，主存DRAM中的“冷”頁將遷移到DVC中，而不是立即寫回PCM.在“冷”頁再次變“冷”之后，遷移控制器將判斷該頁是否為臟頁.由于PCM仍保留原始頁面數(shù)據(jù)，故若頁面不臟，則不需要寫回.VC-HMM還可以根據(jù)遷移收益情況自主地調(diào)整遷移參數(shù)，從而自適應不同的工作負載.本文工作的主要貢獻有3個方面：

1) 提出了一種基于DRAM犧牲Cache的異構(gòu)存儲系統(tǒng)結(jié)構(gòu)來消除冗余遷移.

2) 提出了適用于VC-HMM的基于雙向散列鏈表的頁面遷移機制進行更有效的遷移操作.

3) 提出了在不同工作負載下自適應更新遷移執(zhí)行參數(shù)的方案，實現(xiàn)合理的遷移閾值控制.

實驗結(jié)果表明：與其他遷移策略(CoinMigrator,MQRA,THMigrator)相比，VC-HMM平均減少了至少62.97%的PCM寫操作次數(shù)，22.72%的平均訪問時延，38.37%的重復遷移操作，以及3.40%的系統(tǒng)能耗.

1 相關(guān)工作

由于NVM難以作為DRAM的直接代替，異構(gòu)內(nèi)存系統(tǒng)的提出給內(nèi)存問題提供了解決的方案.而為了兼具NVM與DRAM兩者的性能優(yōu)勢，基于異構(gòu)存儲系統(tǒng)的頁面遷移機制研究顯得尤為重要.本節(jié)將首先介紹一些以往有關(guān)異構(gòu)內(nèi)存頁面遷移機制研究的相關(guān)工作，并分析它們的優(yōu)點與不足.

由于NVM在進行寫操作時具有遠大于DRAM的訪問時延和能量消耗，許多研究著眼于如何減少NVM的寫入操作來提升系統(tǒng)性能.Lee等人[17]提出了Clock-DWF算法將寫請求頻繁的頁面遷移到DRAM中.對于一個進入內(nèi)存的新頁面，當訪問為寫操作時，該頁面將直接載入DRAM中，反之放置于NVM中.對于在NVM中的頁面，一旦被寫請求命中則該頁面將遷移到DRAM中.如果DRAM容量已滿，Clock-DWF則會選擇寫請求命中次數(shù)最少或最長時間沒有被訪問的頁面作為“冷”頁逐出DRAM.該機制考慮到了寫操作對NVM的影響，但遷移的評判標準過于簡單，不能正確地判斷“冷”“熱”度從而增加遷移的次數(shù).Kim等人[19]提出了基于自適應分類(adaptive-classification clock)的遷移機制.通過歷史的訪問模式，每個頁面將被設(shè)定為不同的狀態(tài)來判斷頁面是否為讀/寫密集以及是否執(zhí)行遷移操作，減少了不必要的遷移.

除了以上通過監(jiān)控頁面訪問來執(zhí)行遷移的機制外，使用隊列結(jié)構(gòu)存儲頁面信息的策略也在以往的研究中廣泛使用.Seok等人[20]提出了以4個LRU隊列為基礎(chǔ)的遷移模型.所有的頁面被分為4個類別：NVM寫頻繁頁面、NVM讀頻繁頁面、DRAM寫頻繁頁面以及DRAM讀頻繁頁面，并且根據(jù)最近的訪問時間進行有序排列.根據(jù)過去的訪問信息，模型能夠預測未來訪問的類型，更加準確地進行頁面的遷移，以減少NVM的寫操作.Zhou等人[16]提出了多級隊列遷移機制(MQMigrator)來提高遷移頁面判斷的準確性.多級隊列遷移機制的實現(xiàn)基于3個頁面屬性，即最小生存周期、基于訪問頻率的優(yōu)先級以及訪問時間.每一個頁面都將基于“冷”“熱”度與生存周期來更新節(jié)點信息并移動到對應的隊列中.通過多個LRU隊列的維護，系統(tǒng)能夠更加準確地選擇最“熱”和最“冷”的頁面并且監(jiān)控所有的頁面狀態(tài)，但維護成本和時間復雜度較高.Tan等人[21]提出了一種基于歷史訪問信息的統(tǒng)一“冷”“熱”度計算方式，相較于大部分研究中使用訪問次數(shù)作為“冷”“熱”度度量標準的方法，統(tǒng)一的計算方式能更加公平地表現(xiàn)頁面的訪問狀態(tài).同時，遷移的閾值也能夠根據(jù)每次遷移的收益來進行更新.隨后，Tan等人[22]又進一步提出減少NVM寫入操作的機制.當一個臟頁寫回NVM時，只需要寫回以行大小為單位的數(shù)據(jù)而不用寫回整個頁面.該機制減少了冗余寫回操作的同時延長了部分NVM存儲單元的使用壽命.

除了減少NVM的寫入操作和提高“熱”頁的選擇準確性之外，一些研究也提供了其他的遷移思路.Ryoo等人[23]提出了一種基于粒度感知的遷移機制，遷移頁面的粒度大小將根據(jù)不同工作負載的不同訪問模式進行更新，減少不必要的遷移.為了解決遷移能耗的問題，Zhan等人[24]提出了一種基于能耗感知的遷移機制.該機制將權(quán)衡頁面繼續(xù)留存在NVM中和遷移到DRAM中2種情況的能量代價，為系統(tǒng)節(jié)約不必要的遷移能耗.

在內(nèi)存系統(tǒng)結(jié)構(gòu)的研究中，Guo等人[25]提出了新的內(nèi)存系統(tǒng)結(jié)構(gòu)DR-HBM，減少對NVM的寫入.在該結(jié)構(gòu)中，DRAM被分為2個部分：容量較小的DRAM Cache與容量較大的DRAM主存.Cache僅僅緩存源于NVM的頁面并且按照頁面狀態(tài)的不同，在遷回時不用寫回NVM而暫時保存在DRAM中以便再次訪問.在Cache中第1次未命中的頁面不會立刻執(zhí)行緩存直到再一次被請求.這樣的結(jié)構(gòu)設(shè)計減少了NVM的寫入并且節(jié)約了遷移所占用的帶寬.Islam等人[26]提出了一種即時遷移的策略，通過在內(nèi)存系統(tǒng)中添加新的硬件設(shè)備實現(xiàn)實時的頁面遷移而不需要中斷訪問，為系統(tǒng)減少了訪問的時延.

以上所有的遷移策略都對異構(gòu)內(nèi)存的頁面遷移進行了逐步的優(yōu)化升級，但同時也具有一定的局限性.大多數(shù)的遷移策略只關(guān)注遷移的頁面，很少關(guān)注仍留存在DRAM或在遷移隊列中的頁面.通常在一個遷移過程中，一對“冷”“熱”頁面將會交替遷移，從DRAM中選中的“冷”頁將被NVM中的“熱”頁代替以節(jié)約DRAM的存儲空間，但是由于不公平的“冷”“熱”度評價機制，可能會存在“冷”頁面比“熱”頁面更“熱”的情況，或“冷”頁面被逐出后在短時間內(nèi)再次變“熱”.另外，由于頁面達到遷移條件后可能不會立即執(zhí)行遷移，所以當完成遷移時，當前頁面可能不會與之前一樣“熱”，甚至比在它之后執(zhí)行遷移的頁面更加“冷”.在進行頁面逐出遷回時，從DRAM遷移回NVM的頁面都需要進行寫回操作，但是對于讀頻繁頁面來說，頁面中的數(shù)據(jù)可能并沒有經(jīng)過修改，重新寫回NVM將增加NVM的寫操作且縮短NVM設(shè)備的使用壽命.此外，目前存在的大部分遷移策略沒有關(guān)注分析算法的時間復雜度，這也將產(chǎn)生額外的系統(tǒng)消耗.

為了進一步消除海量大數(shù)據(jù)處理帶來的冗余頁面遷移操作，減少PCM寫入次數(shù)，降低訪問時延并提高系統(tǒng)性能，本文進而通過增加新的設(shè)備并改進以往基于雙向散列鏈表的遷移算法，提出了基于DRAM犧牲Cache的異構(gòu)內(nèi)存頁遷移機制.

2 基于犧牲Cache的異構(gòu)內(nèi)存頁遷移機制

在異構(gòu)內(nèi)存系統(tǒng)中，由于NVM寫入操作表現(xiàn)出的低性能問題，在訪問速度較慢的NVM和訪問速度較快的DRAM之間進行內(nèi)存頁面遷移顯得尤為重要.針對訪問時延較大的PCM，為了消除不必要的遷移操作，減少PCM的寫入并縮短訪問的時延，本文提出了VC-HMM，其中包括3個部分：基于DVC(DRAM-based victim Cache)的異構(gòu)內(nèi)存系統(tǒng)結(jié)構(gòu)、適用于VC-HMM的頁面遷移策略以及遷移條件在不同工作負載下的自適應算法.

2.1 基于DRAM犧牲Cache的異構(gòu)內(nèi)存系統(tǒng)結(jié)構(gòu)

圖2展示了VC-HMM的整體結(jié)構(gòu).與傳統(tǒng)的內(nèi)存結(jié)構(gòu)不同的是在DRAM與PCM之間添加了一個小容量的Cache作為DRAM主存部分的犧牲Cache，犧牲Cache由隨機動態(tài)存儲器DRAM構(gòu)成，并用來存儲從主存DRAM中被逐出的“冷”頁.DVC使用訪問速度較快且頁面替換便利的直接映射.與垂直結(jié)構(gòu)的異構(gòu)內(nèi)存系統(tǒng)中使用的DRAM Cache類似，DVC中的每一頁都有一個1 b的臟頁標志來標記頁面是否被修改.當DRAM逐出頁面時，將根據(jù)頁面的物理地址存儲在Cache對應的塊中.如果存儲時產(chǎn)生沖突，則原本在塊中的頁面將被遷回PCM.由于在Cache中的頁面原本就是從DRAM中淘汰的“冷”頁，所以就算沖突后被直接寫回也能一定程度上降低再次被遷移的概率.

Fig. 2 DRAM-based victim Cache on hybrid main memory architecture圖2 基于DRAM犧牲Cache的異構(gòu)內(nèi)存系統(tǒng)結(jié)構(gòu)

當一個頁面被判斷為“熱”頁時，遷移控制器(migration controller, MigC)將執(zhí)行遷移操作，從PCM遷移的頁面將被拷貝到DRAM的空頁框中，而PCM將繼續(xù)保留此頁的數(shù)據(jù)以便將來的遷回寫入.通過這種方法，讀操作密集的頁面即使經(jīng)歷了遷移和遷回也不必寫回PCM，減少了PCM的寫操作.為了實現(xiàn)PCM中原數(shù)據(jù)的保留，在MigC中添加了用來監(jiān)視遷移頁面狀態(tài)的遷移頁面列表(migrated page list, MPL)用于判斷所請求的頁面的位置.如果所請求的頁面已經(jīng)遷移到DRAM中，則MigC將重映射目的地址使請求進行正確訪問；而如果所請求頁面經(jīng)過二次遷移存在于DVC中，請求將通過原本的目的地址在犧牲Cache中查找.MPL會同時通過記錄遷移的頁面是否進行過寫操作，從而在最后逐出DVC時進行寫回判斷，只有臟頁面需要進行寫回，對于其余的頁面只需要刪除相關(guān)的節(jié)點信息即可.

遷移控制器MigC基于THMigrator進行了改進.在THMigrator遷移機制中，頁面節(jié)點的記錄排序通過雙向散列鏈表來完成.雙向散列鏈表的結(jié)構(gòu)能夠直接快速的訪問每個節(jié)點并完成增刪改查的工作，這大大降低了算法的復雜度，加快了遷移的速度.每當有頁面被訪問時，該頁的相關(guān)信息將被記錄為節(jié)點插入對應表的表頭，當表中頁面再一次被訪問時，該節(jié)點將重新被插入表頭，即按照最近最少使用遞減排序.通過這種排列方式進行頁面搜索時能夠把搜索范圍控制在較小的區(qū)域內(nèi).另外，雙向散列鏈表的結(jié)構(gòu)能夠使使用更加頻繁的頁面更早的執(zhí)行遷移，而不是以達到遷移標準的時間來作為遷移準則，這將減少不必要的遷移次數(shù).例如，頁面A比頁面B先達到遷移閾值進入候選遷移列表(migration candidate list, MCL)，但是頁面A此后再也沒有被訪問到，這時頁面B被頻繁使用，則MCL將把頁面B的記錄節(jié)點放在表頭，從而比頁面A更快地進行遷移.

在VC-HMM中雙向散列鏈表結(jié)構(gòu)依舊被使用在頁面排列中.為了更好地適應DVC的結(jié)構(gòu)，在遷移控制器中設(shè)置了3個雙向散列鏈表：PCM頁面列表(PCM page list, PPL)、候選遷移列表(MCL)以及遷移頁面列表(MPL).PPL記錄在PCM中的頁面訪問情況，PPL與MCL中的節(jié)點結(jié)構(gòu)如表2所示.PPL記錄PCM中頁面的“冷”“熱”程度、頁面編號以及生存周期.內(nèi)存中所有的頁面將根據(jù)其物理地址計算得出一個唯一的頁號作為在表中的索引，MigC能夠根據(jù)頁號直接訪問頁面的信息而不需要遍歷查找.當一個在PCM中的頁面首次被訪問時，MigC將該頁面的信息初始化并插入PPL的表頭，且每次訪問都會將之重新插入表頭.“冷”“熱”程度將根據(jù)訪問的次數(shù)逐次遞增，生存周期也將隨著每一次的訪問被重置.生存周期用于控制一個頁面存在于列表中的時間，如果一個頁面長時間不被訪問，則當生存周期用盡，該頁面節(jié)點將被刪除.當PPL中的頁面達到遷移閾值時，該頁面節(jié)點將被插入遷移候選列表MCL的表頭，MCL將在頁面下一次被訪問時執(zhí)行遷移.當有遷移還未完成時，MCL也能夠?qū)㈨撁姘凑铡袄洹薄盁帷背潭扰判蚴垢盁帷钡捻撁鎯?yōu)先遷移.和PPL相同，在MCL中的頁面也將根據(jù)訪問情況更新節(jié)點信息，并且按順序執(zhí)行遷移.每次有請求進入內(nèi)存時，MigC都將檢查是否有頁面達到遷移閾值或超過生命周期，超過生命周期的頁面將被作為“冷”頁從列表中刪除以減少冗余的遷移操作.

Table 2 Page Node Structure of PPL and MCL表2 PCM頁面列表與候選遷移列表的頁面節(jié)點結(jié)構(gòu)

Fig. 3 Migration framework for VC-HMM圖3 VC-HMM遷移框架

執(zhí)行了遷移而進入DRAM的頁面將被作為新的節(jié)點插入遷移頁面列表(MPL)的表頭，并刪除在MCL中的舊節(jié)點，MPL中的節(jié)點結(jié)構(gòu)如表3所示.MPL在PPL和MCL的基礎(chǔ)上記錄更多的頁面信息幫助遷移機制的實現(xiàn)，1b標簽參數(shù)IsInDRAM記錄了頁面存在的位置，頁面地址的映射被記錄用于請求的正確訪問，另外MPL將記錄頁面在DRAM中的讀寫操作次數(shù)來幫助遷移參數(shù)的動態(tài)自適應.MPL也將隨著頁面的訪問更新節(jié)點從而進行排序.當進行“冷”頁判斷時，MigC將逆序遍歷MPL從而查找需要進行遷移的“冷”頁.

Table 3 Page Node Structure of MPL表3 遷移頁面列表的頁面節(jié)點結(jié)構(gòu)

2.2 頁面遷移與訪問

VC-HMM的遷移框架如圖3所示，具體遷移步驟為：

① MigC判斷所訪問內(nèi)存頁是否存在于某個表中.如果在表中，則更新節(jié)點信息并將該節(jié)點置于表頭；如果不在表中，將頁面節(jié)點初始化并插入PCM頁面列表PPL的表頭.

② 如果所訪問頁面節(jié)點在遷移頁面列表MPL中，則根據(jù)標志位判斷該頁在DRAM還是DVC中，并執(zhí)行地址重映射.如果所訪問頁面節(jié)點在候選遷移列表MCL中，則檢查是否有遷移正在進行，若有遷徙正在執(zhí)行則等待當前遷移完成否則進行遷移操作.如果所訪問頁面節(jié)點在PPL中，則判斷是否達到遷移閾值，若達到遷移閾值則將節(jié)點插入MCL表頭.

③ 在MCL中按順序進行遷移，將該頁復制到DRAM的空頁框中，將該頁在MCL中的節(jié)點信息更新到MPL中并刪除原節(jié)點，初始化新節(jié)點信息并置為表頭.

④ 在MPL中從后往前檢索是否有滿足遷出條件的DRAM頁面，若有滿足遷出條件的DRAM頁面，檢查是否有DRAM到DVC的遷出操作正在進行，若沒有正在進行的遷出操作，則進行遷移操作并更新MPL中對應節(jié)點信息，將對應DRAM頁面重新置為空.若當前有遷移操作正在進行，則等待當前遷移操作結(jié)束.

⑤ 在MPL中從后往前檢索是否有滿足遷出條件的DVC頁面，若有滿足遷出條件的DVC頁面，檢查是否有DVC到PCM的頁面逐出正在進行，若當前有遷移操作正在進行，則等待當前逐出結(jié)束.若沒有正在進行的遷移操作，則通過MPL中該節(jié)點記錄的讀寫情況判斷是否需要寫回PCM中，若不需要寫回PCM中，則直接刪除節(jié)點.最后根據(jù)該頁面在DRAM中的讀寫情況計算遷移收益，若收益為正，則更新遷移參數(shù)使頁面更容易遷入DRAM且頁面的生命周期變長；若收益為負，則更新遷移條件使頁面更難遷入DRAM且頁面的生命周期變短.

⑥ 檢查PPL和MCL是否有超過生命周期的頁面節(jié)點，將之逐出.

遷移流程框圖如圖4所示：

Fig. 4 Process of migration圖4 遷移流程

頁面的“冷”“熱”程度根據(jù)訪問次數(shù)遞增.遷移時，MigC將為遷移的頁面尋找DRAM中的空頁框，如果沒有可用的空頁框，MigC將在MPL中逆序查找并逐出最“冷”的頁面到DVC中.基于DRAM犧牲Cache的內(nèi)存頁遷移機制的偽代碼實現(xiàn)方法如算法1所示:

算法1.內(nèi)存頁面遷移算法.

輸入：當前訪問頁面的頁號pagei、頁面所在內(nèi)存設(shè)備通道編號ChannelNumber.

① 初始化PPL,MCL,MPL,Threshold,currentTime;

②Request(pagei);

③ ifIsLocatedInPPL(pagei) then

④UpdatePPL(pagei);/*更新頁面的“冷”“熱”程度值并重置生命周期*/

⑤MoveToHead(pagei);/*將該頁節(jié)點置為表頭*/

⑥ ifpagei→value>Thresholdthen

/*“冷”“熱”程度值達到閾值則插入候選遷移列表表頭*/

⑦InsertMCL(pagei);

⑧RemovePPL(pagei);

⑨ end if

⑩ end if

/*在候選遷移列表中且沒有超過生命周期則進行遷移*/

/*被訪問頁面位于DRAM中*/

&&!IsLocatedInMPL(pagei) then

與遷移操作僅針對當前所訪問的頁面不同，遷回和逐出操作針對每一個完成遷移的頁面，可能在每一個時鐘周期中發(fā)生.MigC將在遷移判斷操作結(jié)束之后分別查看MPL和MCL列表.在MCL中通過從后往前逆序遍歷查看各頁面節(jié)點是否已超過生命周期，超過生命周期的節(jié)點將被直接刪除.類似地，在MPL中逆序查找需要遷移的DRAM和DVC“冷”頁，并進行遷移和遷回操作，隨后針對遷回PCM的頁面進行遷移收益核算.內(nèi)存頁面逐出的偽代碼實現(xiàn)方法如算法2所示.通過MPL執(zhí)行的逐出判斷將在分別尋找到滿足要求的一個DRAM和DVC頁面后結(jié)束本次遍歷.由于逐出操作面向的對象為“冷”頁，故本算法中僅將生命周期作為判斷“冷”“熱”程度的標準以簡化算法的執(zhí)行.

當所訪問的頁面已經(jīng)完成遷移時，MigC將通過MPL中保存的1 b標志位判斷該頁是在DRAM中還是在DVC中.如果IsInDRAM為true則該頁在DRAM中，MigC將通過MPL記錄的頁面地址映射重新映射請求的目標地址；如果IsInDRAM為false則該頁在DVC中，請求將通過原始目的地址與DVC中的地址進行比對從而執(zhí)行訪問.

算法2.內(nèi)存頁面逐出算法.

輸入：當前訪問頁面的頁號pagej.

① forpagej=rbeginMPL();

pagej≠rendMPL();

++pagejdo /*檢查已遷移頁面是否要逐出*/

② ifpagej→expirationTime>currentTime

then

③ ifpagej→IsInDRAM==true then

④VicfromDRAM(pagej);

⑤ else

⑥Revenue(pagej);

⑦VicfromCache(pagej);

⑧AdjustThreshold();

⑨ end if

⑩ end if

pagej≠rendMCL();

++pagejdo /*檢查候選遷移列表中是否有頁面超出生命周期*/

then

2.3 遷移參數(shù)的自適應調(diào)整

為了使遷移機制能夠自適應不同的工作負載，提高遷移的合理性，MigC將通過遷移收益自主地更新遷移參數(shù).當一個頁面最終被逐出DVC時，MigC將計算這一次遷移的收益.遷移收益:

Rw=Writecount×(Timew_in_pcm-Timew_in_DRAM),

(1)

Rr=Readcount×(Timer_in_pcm-Timer_in_DRAM),

(2)

C=TimeP_D+TimeD_DVC+TimeDVC_P×dirty,

(3)

R=Rw+Rr-C.

(4)

式(1)和式(2)通過MPL記錄的讀寫操作次數(shù)計算頁面遷移到DRAM中和留存在PCM中的讀寫時延收益，Writecount表示遷移后該頁面所收到的寫操作次數(shù)，Timew_in_pcm和Timew_in_DRAM分別表示在PCM和DRAM中進行寫操作所需的時間.同理Readcount，Timer_in_PCM，Timer_in_DRAM表示遷移后該頁面所進行的讀操作次數(shù)以及在PCM和DRAM中進行讀操作所需的時間.

式(3)計算了遷移所需的時間代價，如果頁面最終被逐出時為臟，則dirty=1，反之dirty=0.最終的收益通過式(4)計算，如果R>0則表示遷移收益為正，遷移閾值將自動降低使頁面更容易遷移到DRAM中，在DRAM和DVC中的頁面的生存周期也將被延長；如果R<0則表示遷移收益為負，遷移閾值將自動增加使頁面更不容易達到遷移閾值，在DRAM和DVC中的頁面的生存周期也將被縮短.

本文通過線性增值的方式自適應地調(diào)整遷移參數(shù)，設(shè)置以步長為1進行線性增長.生存周期的增減將應用于下一個周期執(zhí)行遷移頁面節(jié)點信息的初始化中，而不是更新目前遷移表中所有內(nèi)存頁的生存周期.實驗中參數(shù)的初始數(shù)值與THMigrator的模型參數(shù)一致.

例如，當頁面x被認定為“冷”頁面，從而從DVC遷移回PCM時，MigC通過計算得出該頁面x遷移的收益.若收益R為正，則表示當前遷移參數(shù)合理有效，留存于DRAM中的頁面將被大概率訪問.然后，MigC降低遷移閾值，增加其他頁面遷移的機會.在下一次遷移時，提升頁面初始生命周期，增加頁面駐留在DRAM中的時間.

3 實驗與分析

本文采用GEM5[27]和NVMain[28-29]構(gòu)建基于異構(gòu)內(nèi)存的多核處理器模型系統(tǒng),GEM5模擬器是一個用于計算機系統(tǒng)架構(gòu)研究的模塊化平臺.NVMain是一個架構(gòu)級的主存儲器模擬器.本文通過GEM5與NVMain的結(jié)合，設(shè)計了具有DRAM犧牲Cache的水平型結(jié)構(gòu)的異構(gòu)內(nèi)存系統(tǒng)，其中DRAM通道與PCM通道的比例為1∶3，DVC的大小為DRAM的1/16，采用時鐘頻率為2 GHz的TimingSimpleCPU，一級緩存設(shè)置為32 KB，二級緩存設(shè)置為256 KB.詳細配置如表4所示，內(nèi)存結(jié)構(gòu)中的1∶1/16∶3為DRAM容量、DVC容量以及PCM容量的比例.

Table 4 Main Configurations of GEM5 and NVMain表4 GEM5和NVMain模擬器的主要配置

為了對VC-HMM進行全面分析，本文選擇了CoinMigrator、多級隊列替換算法(MQRA)和基于雙向散列鏈表遷移機制(THMigrator)作為參考.CoinMigrator遷移策略為NVMain模擬器自帶的隨機遷移策略，每一次的遷移決策由隨機數(shù)決定.MQMigrator遷移策略為Zhou等人[16]提出的頁面替換算法，遷移使用多個隊列來維護頁面的訪問信息，通過隊列優(yōu)先級進行“冷”“熱”頁面的排序和選擇，但由于隊列數(shù)量多，且不能隨機訪問每個頁面節(jié)點.因此，本文提出的VC-HMM采用雙向散列鏈表結(jié)構(gòu)維護頁面信息的數(shù)據(jù)結(jié)構(gòu)，能實現(xiàn)頁面節(jié)點的隨機訪問而不需要遍歷鏈表，降低了頁面信息維護的復雜度.本文采用了SPECCPU2006[30]中的10個不同的基準應用程序，并將CoinMigrator的數(shù)據(jù)作為對應的標準化數(shù)據(jù).

針對一個內(nèi)存頁的讀寫配置與能耗配置如表5所示，參數(shù)來源于文獻[18]，內(nèi)存頁大小設(shè)置為4 KB.

Table 5 Configuration of the Memory for a 4 KB Memory Page

實驗數(shù)據(jù)通過GEM5和NVMain模擬器自身集成的Trace工具來產(chǎn)生，Trace工具可以以文本的形式輸出程序運行時的日志信息,在程序代碼中通過添加一些關(guān)鍵數(shù)據(jù)的打印操作,使用AddStat方法可以將運行時的數(shù)據(jù)輸出到日志信息中,通過這種輸出日志的跟蹤方法可以獲得讀寫操作的數(shù)量和分布以及遷移內(nèi)存頁的數(shù)量等信息.實驗中用于測試的基準應用均使用了1 000萬條指令的運行.其他遷移參數(shù)的設(shè)置與前期研究[18]的配置一致.

3.1 訪問時延

Fig. 5 Normalized average access latency圖5 歸一化的平均訪問時延

實驗數(shù)據(jù)顯示，通常情況下使用VC-HMM的系統(tǒng)的平均訪問延遲比使用CoinMigrator，MQRA，THMigrator的系統(tǒng)的平均訪問延遲分別低22.72%，31.56%，23.63%，如圖5所示.基準中的每個應用在VC-HMM的使用中都有較好的效果.其中，與Coin-Migrator，MQRA，THMigrator相比，應用sjeng在使用VC-HMM時訪問時延的降低最明顯，分別為53.45%，60.58%，60.47%.圖5中應用omnetpp的訪問時延高于CoinMigrator，這是由于CoinMigrator的隨機概率判斷策略使得遷移不穩(wěn)定，每一次的遷移并不完全一樣.本文經(jīng)過多次的實驗，使數(shù)據(jù)盡可能趨于穩(wěn)定.目前VC-HMM的總體訪問時延相比其他的遷移策略基本上都有明顯降低.即使對于所產(chǎn)生的訪問時延高于CoinMigrator策略，VC-HMM策略的訪問時延也僅高于1.5%.

VC-HMM的主要性能提升源于DRAM犧牲Cache，DVC將更多的頁面保留在讀寫速度較快的DRAM部分.即使一個頁面在遷移參數(shù)不精準的情況下進行遷移，該頁面仍然可以在訪問較快的DRAM中停留更長的時間，而不會由于“冷”“熱”度的快速動態(tài)變化而在PCM和DRAM之間頻繁遷移.這使得更多的請求通過訪問時延較短的DRAM進行訪問，而不是訪問讀寫時延長的PCM.不必要遷移操作的減少也避免了帶寬和其他系統(tǒng)資源的占用.實際上VC-HMM通過使已經(jīng)執(zhí)行的遷移變得更有效而不是單純調(diào)整遷移閾值來消除無效遷移.

3.2 PCM寫操作頻次

通過使用添加了DVC的異構(gòu)內(nèi)存系統(tǒng)，PCM訪問的次數(shù)也有了相應的減少.如圖6所示，使用VC-HMM的系統(tǒng)中，PCM的訪問次數(shù)相比使用CoinMigrator，MQRA，THMigrator的系統(tǒng)平均減少了67.38%，73.26%，62.97%.同時，對PCM的寫操作數(shù)也明顯減少.如圖7所示，相比使用CoinMigrator，MQRA，THMigrator的系統(tǒng)，使用VC-HMM的系統(tǒng)平均減少了81.28%，84.99%，75.89%的PCM寫入次數(shù).

Fig. 6 Normalized PCM access times圖6 歸一化的PCM訪問數(shù)

Fig. 7 Normalized PCM write times圖7 歸一化的PCM寫操作數(shù)

盡管遷移閾值可能不夠精確，且由于遷移參數(shù)的人為制定無法選擇和預測真正最“熱”的頁面進行遷移，但VC-HMM增加了遷移頁留在DRAM部分的時間，使大部分的請求通過DRAM進行訪問，冗余遷移的減少也降低了對PCM的讀寫操作次數(shù)，延長了PCM的使用壽命.原頁面的保留也使得讀頻繁的“冷”頁面在遷移時不需要寫回，進一步降低了PCM被訪問的次數(shù).

3.3 IPC

圖8比較了使用VC-HMM和其他3種算法的系統(tǒng)IPC(平均每個周期完成的指令數(shù)).這4種不同算法所產(chǎn)生的系統(tǒng)IPC差異不顯著，但VC-HMM仍能在一定程度上提高IPC.使用VC-HMM系統(tǒng)的IPC平均比使用CoinMigrator，MQRA，THMigrator的系統(tǒng)的IPC高2.36%，2.88%，4.03%.在所有基準應用中，sjeng的增長率最高，分別為11.36%，12.72%，24.32%，說明sjeng應用的存儲訪問的局部性較高.在這種情況下，所請求的頁面大部分被遷移到DRAM中，大大減少了請求的時間.

Fig. 8 Normalized IPC圖8 歸一化的IPC

然而，即使VC-HMM減少了大量的PCM寫入，使用VC-HMM的系統(tǒng)的IPC也沒有得到顯著的改善.本文分析其中一個原因是由于VC-HMM需要在每次遷移中進行二次遷移.遷移的頁面需要從DRAM到DRAM犧牲Cache進行額外遷移，即使MigC可以自主地調(diào)整遷移參數(shù)，但二次遷移依舊需要額外的時鐘周期來完成.

此外，不同應用程序的寫請求頻次多少、訪存地址的局部性強弱會使得VC-HMM機制下的IPC值發(fā)生變化.寫訪問量較少且局部性較好的應用在使用VC-HMM時能夠得到更好的性能提升.

3.4 冗余遷移操作

圖9比較了使用VC-HMM的系統(tǒng)與使用另外3種算法的系統(tǒng)的重復遷移操作次數(shù)，與使用CoinMigrator，MQRA，THMigrator的系統(tǒng)相比，VC-HMM平均減少了58.80%，52.40%，38.37%的重復遷移操作.其中在基準測試應用calculix和sjeng中，均未檢測到重復的內(nèi)存頁遷移操作.

Fig. 9 Normalized re-migration times圖9 歸一化的重復遷移次數(shù)

由于當前實驗階段難以計算冗余操作中的σ值，本文實驗采用統(tǒng)計重復遷移操作的次數(shù)來量化冗余遷移操作的次數(shù).在cactusADM及omnetpp應用中，VC-HMM的重復遷移次數(shù)高于THMingrator，這是由于VC-HMM擁有遷移閾值和頁面生存周期的自適應策略，對于局部性較差的應用來說，由于VC-HMM相比沒有DVC設(shè)備的策略需要額外的從DRAM到DVC設(shè)備的遷移，這將會導致動態(tài)自適應算法減少頁面在DRAM中的生存周期，從而使得頁面過早遷出，增加了冗余遷移的可能性.同時，DVC的直接映射策略也使得沖突頁面過早地遷回NVM，也增加了冗余遷移的次數(shù).

DVC使得完成遷移的“熱”頁更久地保存在訪問速度較快的DRAM設(shè)備中，且“冷”“熱”頁并不成對進行遷移操作，這阻止了“冷”頁的誤遷回，從而減少了頁面再次變“熱”而導致的冗余遷移問題.在構(gòu)建DVC時，本文使用直接映射策略作為DVC的映射規(guī)則，雖然直接映射策略下的訪問速度較快，但也更加容易引起沖突而加快頁面的遷回，導致部分冗余的遷移操作.由于遷移到DVC的頁面為從主存DRAM中逐出的“冷”頁.因此，雖然存在由于沖突而過早遷回的頁面，但并沒有對系統(tǒng)產(chǎn)生過大的影響.

3.5 系統(tǒng)能耗

Fig. 10 Normalized energy consumption where the capacity of DVC is 1/16 of DRAM圖10 DVC容量為DRAM容量1/16時歸一化的 系統(tǒng)能耗

Fig. 11 Normalized energy consumption where the capacity of DVC is 1/8 of DRAM圖11 DVC容量為DRAM容量1/8時歸一化的 系統(tǒng)能耗

圖10比較了使用VC-HMM的系統(tǒng)與使用另外3種算法的系統(tǒng)的能耗情況.與使用CoinMigrator，MQRA，THMigrator的系統(tǒng)相比，VC-HMM平均減少了2.74%，3.16%，4.29%的系統(tǒng)能耗.由于系統(tǒng)性能的提升，VC-HMM在降低運行時間、提高系統(tǒng)效率的同時減少了能耗.但同時，能耗將根據(jù)使用的DVC的容量大小而改變.圖11對比了DVC容量為DRAM容量的1/8時所產(chǎn)生的能耗.與使用CoinMigrator，MQRA，THMigrator的系統(tǒng)相比，使用比先前增加1倍容量的DVC時，VC-HMM平均增加了24.92%，24.35%，22.97%的系統(tǒng)能耗.VC-HMM在應用hmmer與omnetpp上的能耗大于其他的遷移策略.對于局部性較差的應用來說，遷移的頁面也會較多，從而導致內(nèi)存訪問和靜態(tài)維持數(shù)據(jù)所需的能耗增加，且額外的DRAM到DVC的遷移操作和DVC沖突問題也將增加能耗.此外，DVC容量的增大將減少數(shù)據(jù)沖突的發(fā)生，導致所需保持的數(shù)據(jù)增加，這些數(shù)據(jù)的訪問以及達到生存周期之前的數(shù)據(jù)刷新都將產(chǎn)生大量能耗.

由于DRAM利用電容內(nèi)存儲電荷的多少來存儲數(shù)據(jù)的特性，晶體管漏電使得DRAM需要周期性地充電，且訪問前需要對區(qū)塊進行預充，這將產(chǎn)生不小的系統(tǒng)能耗來維持DRAM的運行.過大的DVC將使得靜態(tài)能耗增加，且得不到合理的使用.另外，由于異構(gòu)內(nèi)存的遷移使得大量的內(nèi)存訪問集中于DRAM，所以DVC的容量大小將不同程度上影響系統(tǒng)能耗.

4 總 結(jié)

本文提出了一種基于DRAM犧牲Cache的異構(gòu)內(nèi)存頁遷移機制VC-HMM，該機制實現(xiàn)了比THMigrator模型更低的訪問延遲，消除了部分無效的遷移操作.此外，VC-HMM在局部性較強的應用中取得了較高的訪存性能.

實驗結(jié)果表明：與使用CoinMigrator、多隊列算法MQRA和基于雙向散列鏈表的遷移機制THMigrator的系統(tǒng)相比，使用VC-HMM的系統(tǒng)的平均訪問延遲降低了22.72%，31.56%，23.63%.同時，VC-HMM相比CoinMigrator,MQRA，THMigrator減少了81.28%，84.99%，75.89%的PCM寫操作，并在一定程度上提升了系統(tǒng)IPC.另外，在減少重復遷移操作方面，VC-HMM平均減少了相比另外3種機制58.80%，52.40%，38.37%的重復遷移操作.在能耗方面，與使用CoinMigrator,MQRA和THMigrator的系統(tǒng)相比，VC-HMM平均減少了2.74%，3.16%，4.29%的系統(tǒng)能耗.未來，我們計劃利用機器學習算法識別和監(jiān)測“熱”頁面，并著力于研究更智能的頁遷移決策，以獲得更高的異構(gòu)內(nèi)存綜合性能.

作者貢獻聲明：裴頌文提出了算法思路和實驗方案；錢藝幻負責完成實驗并撰寫論文；葉笑春提出指導意見并修改論文；劉海坤與孔令和提出指導意見.