張 震，付印金，胡谷雨

(1.陸軍工程大學(xué) 指揮控制工程學(xué)院，南京 210007； 2.73610部隊(duì)，南京 210007)(*通信作者電子郵箱yinjinfu@gmail.com)

0 引言

隨著信息技術(shù)的高速發(fā)展，大數(shù)據(jù)所催生的內(nèi)存計(jì)算和處理器核數(shù)的不斷增加對(duì)內(nèi)存的速度、容量、功耗和可靠性的需求都達(dá)到前所未有的新高度。在過(guò)去數(shù)十年期間，動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(Dynamic Random Access Memory, DRAM)作為主要主存儲(chǔ)器被廣泛應(yīng)用在移動(dòng)終端和大規(guī)模計(jì)算系統(tǒng)中。然而，現(xiàn)代計(jì)算機(jī)系統(tǒng)對(duì)大容量、低功耗、擴(kuò)展性強(qiáng)的高性能內(nèi)存的需求不斷增加，高靜態(tài)功耗、容量提升達(dá)到上限、擴(kuò)展性有限的DRAM面臨著眾多新型存儲(chǔ)技術(shù)的挑戰(zhàn)。

新型非易失性存儲(chǔ)器(NonVolatile Memory, NVM)的出現(xiàn)為打破這些限制提供契機(jī)，相變存儲(chǔ)器(Phase Change Memory, PCM)被視為最有希望替代DRAM成為下一代的主存儲(chǔ)器。PCM具有非易失性、低靜態(tài)功耗、擴(kuò)展性強(qiáng)等特性，但同時(shí)PCM單個(gè)存儲(chǔ)單元的寫(xiě)壽命有限，訪(fǎng)問(wèn)性能也遜色于DRAM[1]，因此，PCM還無(wú)法完全取代DRAM單獨(dú)作為主存使用。

為了解決PCM訪(fǎng)問(wèn)時(shí)延以及耐受性?xún)煞矫娴膯?wèn)題，研究者從存儲(chǔ)層次結(jié)構(gòu)方面提出兩種基于PCM和DRAM的混合存儲(chǔ)架構(gòu)。第一種使用DRAM和PCM共同作為主存，通過(guò)數(shù)據(jù)分配以及數(shù)據(jù)遷移技術(shù)發(fā)揮DRAM的讀寫(xiě)優(yōu)勢(shì)，同時(shí)減少PCM的寫(xiě)操作次數(shù)[2-4]；第二種架構(gòu)使用DRAM作為PCM的緩存來(lái)掩蓋PCM I/O性能以及寫(xiě)耐受性的不足[5-7]。兩種架構(gòu)各有優(yōu)勢(shì)，相比之下第二種架構(gòu)更適合解決PCM寫(xiě)壽命受限的問(wèn)題。

如何減少PCM寫(xiě)次數(shù)以及更好地均勻化寫(xiě)操作分布是設(shè)計(jì)高效磨損均衡算法必須考慮的兩個(gè)因素。已有研究者提出使用DRAM緩存技術(shù)來(lái)減少PCM的寫(xiě)操作次數(shù)[4]，同時(shí)通過(guò)數(shù)據(jù)交換[2]和移位技術(shù)[5,8]來(lái)實(shí)現(xiàn)數(shù)據(jù)塊內(nèi)部和不同數(shù)據(jù)塊之間的磨損均衡。前者將修改頻繁的數(shù)據(jù)塊緩存在DRAM，把修改較少或者訪(fǎng)問(wèn)不頻繁的數(shù)據(jù)塊淘汰至PCM，能夠一定程度上減少寫(xiě)訪(fǎng)問(wèn)密集型應(yīng)用對(duì)某些存儲(chǔ)單元的磨損次數(shù)。數(shù)據(jù)移位和交換技術(shù)通過(guò)改變邏輯地址到物理地址映射關(guān)系的方式，將磨損嚴(yán)重的存儲(chǔ)單元的寫(xiě)操作均勻到磨損較輕的存儲(chǔ)單元，實(shí)現(xiàn)不同粒度下的寫(xiě)操作均勻分布。

現(xiàn)有的基于PCM的磨損均衡算法能夠一定程度上延長(zhǎng)PCM的寫(xiě)壽命，但是依然存在以下幾點(diǎn)問(wèn)題。1)已有的以DRAM作為緩存減少PCM寫(xiě)次數(shù)的設(shè)計(jì)方法只關(guān)注如何優(yōu)化臟數(shù)據(jù)頁(yè)的淘汰策略，并不能利用數(shù)據(jù)塊的讀寫(xiě)傾向性避免PCM上不必要的寫(xiě)操作；2)采用確定性映射機(jī)制的靜態(tài)磨損均衡策略不能有效處理惡意訪(fǎng)問(wèn)攻擊情況下的寫(xiě)操作均勻分布，替換頁(yè)的選擇缺乏隨機(jī)性的保護(hù)；3)以單個(gè)頁(yè)面為粒度的磨損均衡操作在空間局部性較強(qiáng)的應(yīng)用場(chǎng)景中效率低下。

針對(duì)上述問(wèn)題，本文提出一種在新型DRAM緩存+DRAM/PCM混合主存架構(gòu)下基于布隆過(guò)濾器(Bloom Filter, BF)的兩層動(dòng)態(tài)磨損均衡策略:第一層在新型混合存儲(chǔ)架構(gòu)下通過(guò)最近最少使用(Least Recently Used, LRU)和帶有時(shí)間變化的最不經(jīng)常使用(Least Frequenctly Used with Aging, LFU-Aging)相結(jié)合的緩存算法減少PCM寫(xiě)操作;第二層則是在PCM內(nèi)部實(shí)現(xiàn)寫(xiě)操作均勻分布的組間磨損均衡算法。本文工作主要包括：

1)設(shè)計(jì)一種全新的混合存儲(chǔ)架構(gòu)，使用DRAM作為cache，PCM和DRAM統(tǒng)一編址共同作為主存。DRAM cache在LRU和LFU-Aging的兩級(jí)緩存策略的基礎(chǔ)上對(duì)每個(gè)數(shù)據(jù)塊的讀寫(xiě)信息進(jìn)行統(tǒng)計(jì)，當(dāng)緩存寫(xiě)滿(mǎn)時(shí)根據(jù)數(shù)據(jù)塊的讀寫(xiě)傾向性寫(xiě)回到相應(yīng)的主存介質(zhì)。其中，DRAM存儲(chǔ)被淘汰的修改較為頻繁的數(shù)據(jù)塊，PCM存儲(chǔ)修改較少的干凈數(shù)據(jù)塊，減少PCM寫(xiě)操作的同時(shí)通過(guò)讀寫(xiě)熱度區(qū)分避免臟數(shù)據(jù)塊被寫(xiě)回到PCM。

2)基于BF實(shí)現(xiàn)低空間開(kāi)銷(xiāo)、高查詢(xún)速度的磨損均衡算法。不同于傳統(tǒng)的動(dòng)態(tài)磨損均衡算法中每個(gè)數(shù)據(jù)塊對(duì)應(yīng)一個(gè)計(jì)數(shù)器來(lái)跟蹤寫(xiě)次數(shù)，本文利用BF技術(shù)將所有數(shù)據(jù)塊的寫(xiě)操作情況映射到一個(gè)開(kāi)銷(xiāo)更小的計(jì)數(shù)器數(shù)組當(dāng)中，并且通過(guò)判斷數(shù)據(jù)塊所映射的計(jì)數(shù)器數(shù)值大小判斷磨損情況。同時(shí)，BF有助于更快地查找需要進(jìn)行磨損均衡的數(shù)據(jù)塊以及選擇替換對(duì)象。

3)針對(duì)現(xiàn)有算法在處理強(qiáng)空間局部性的數(shù)據(jù)集時(shí)出現(xiàn)的性能瓶頸，設(shè)計(jì)一種組間磨損均衡策略。算法以每128 MB的連續(xù)地址空間為一個(gè)分組，當(dāng)記錄分組寫(xiě)次數(shù)的BF計(jì)數(shù)器的數(shù)值超過(guò)閾值時(shí)進(jìn)行組間磨損均衡，實(shí)現(xiàn)不同分組之間的寫(xiě)操作均勻分布。

1 相關(guān)工作

PCM的每個(gè)單元只能承受107～109次[9]的寫(xiě)操作，特別是在連續(xù)寫(xiě)的情況下，存儲(chǔ)單元的耐受性將受到嚴(yán)重制約。研究者從存儲(chǔ)系統(tǒng)的體系結(jié)構(gòu)、緩存優(yōu)化策略、數(shù)據(jù)遷移等方面對(duì)如何提高PCM耐受性作出了廣泛且深入的研究。提升PCM寫(xiě)壽命最直接的方式就是減少對(duì)存儲(chǔ)單元的寫(xiě)操作次數(shù)，而磨損均衡處理策略是延長(zhǎng)存儲(chǔ)器使用壽命的另一個(gè)重要方法。現(xiàn)有的磨損均衡策略可以分為兩個(gè)方向：減少寫(xiě)操作以及均勻化寫(xiě)操作分布。

1.1 DRAM緩存技術(shù)

DRAM作為PCM緩存的二級(jí)主存系統(tǒng)模型是混合主存研究的一個(gè)重要方向，這種架構(gòu)一方面為系統(tǒng)提供大容量的存儲(chǔ)空間，另一方面可以解決由PCM本身讀寫(xiě)延遲以及寫(xiě)壽命缺陷帶來(lái)的系統(tǒng)性能下降問(wèn)題。使用DRAM作為PCM緩存的方式能夠?qū)⑿薷念l繁的數(shù)據(jù)盡可能保存在DRAM中，減少這部分?jǐn)?shù)據(jù)對(duì)主存造成的頻繁寫(xiě)傷害，同時(shí)可以掩蓋PCM寫(xiě)性能的不足。

Park等[4]提出臟數(shù)據(jù)保持策略，將修改頻繁的臟數(shù)據(jù)在DRAM中保留更長(zhǎng)的時(shí)間；Qureshi等[5]提出Lazy-Write的寫(xiě)操作策略，當(dāng)頁(yè)面被逐出DRAM且該頁(yè)被修改過(guò)時(shí)才寫(xiě)入PCM；Ferreira等[7]針對(duì)PCM讀寫(xiě)不均衡的特性，通過(guò)對(duì)頁(yè)面設(shè)定優(yōu)先級(jí)的方式把低功耗和低時(shí)延讀操作集中的頁(yè)面寫(xiě)回到PCM來(lái)減少主存的寫(xiě)數(shù)量；Mladenov等[10]根據(jù)空間局部性原理以及改進(jìn)的Lazy-Write算法將DRAM中最早處理過(guò)的請(qǐng)求數(shù)據(jù)寫(xiě)回PCM，再將新數(shù)據(jù)寫(xiě)入DRAM中。

現(xiàn)有的DRAM緩存技術(shù)通過(guò)優(yōu)化緩存策略能夠有效減少修改頻繁的數(shù)據(jù)對(duì)PCM造成的寫(xiě)傷害，但被寫(xiě)回的臟數(shù)據(jù)仍然會(huì)增加PCM寫(xiě)操作數(shù)量，同時(shí)這部分?jǐn)?shù)據(jù)所表現(xiàn)出來(lái)的寫(xiě)傾向性會(huì)在將來(lái)增加PCM磨損均衡操作的負(fù)擔(dān)。此外，不同算法在緩存大小的設(shè)置、何時(shí)將數(shù)據(jù)寫(xiě)回到PCM、替換頁(yè)的選擇等方面不盡相同，這些問(wèn)題也將影響PCM耐久性提升的效果。

1.2 均勻化寫(xiě)操作分布技術(shù)

根據(jù)是否記錄數(shù)據(jù)的訪(fǎng)問(wèn)熱度，已有的均勻?qū)懖僮鞣植嫉哪p均衡算法可以分為動(dòng)態(tài)和靜態(tài)兩類(lèi)。動(dòng)態(tài)磨損均衡策略跟蹤數(shù)據(jù)的寫(xiě)頻率，當(dāng)數(shù)據(jù)塊的寫(xiě)次數(shù)超過(guò)設(shè)定的閾值時(shí)選擇磨損情況良好的數(shù)據(jù)塊作為替換對(duì)象，以此來(lái)均衡不同數(shù)據(jù)塊之間的寫(xiě)次數(shù)；靜態(tài)磨損均衡策略通過(guò)周期性地變換邏輯地址到物理地址的映射關(guān)系來(lái)實(shí)現(xiàn)局部或者全局的寫(xiě)操作均勻分布。

Dhiman等[2]設(shè)計(jì)了一種軟硬件結(jié)合的混合內(nèi)存系統(tǒng)—PDRAM，通過(guò)記賬(book keeping)硬件技術(shù)來(lái)存儲(chǔ)PCM頁(yè)面粒度的寫(xiě)操作頻率，同時(shí)利用軟件手段維護(hù)PCM的寫(xiě)訪(fǎng)問(wèn)次數(shù)表；Park等[11]提出一種基于segment的數(shù)據(jù)交換策略PFFS，一旦寫(xiě)操作次數(shù)最大的分塊與最少的分塊之間的寫(xiě)次數(shù)差距超過(guò)一定的閾值就進(jìn)行數(shù)據(jù)交換操作；Zhou等[12]通過(guò)限制數(shù)據(jù)段被頻繁選中進(jìn)行數(shù)據(jù)交換來(lái)避免某一個(gè)段被過(guò)多寫(xiě)訪(fǎng)問(wèn)；Park等[13]提出多級(jí)數(shù)據(jù)交換技術(shù)動(dòng)態(tài)地平衡不同頁(yè)面之間的寫(xiě)次數(shù)；Dong等[14]通過(guò)監(jiān)測(cè)寫(xiě)數(shù)據(jù)流量以及存儲(chǔ)單元承受寫(xiě)操作的情況來(lái)控制損耗均衡的力度，當(dāng)數(shù)據(jù)更新分布較為均勻時(shí)提高數(shù)據(jù)交換的門(mén)檻，當(dāng)寫(xiě)請(qǐng)求訪(fǎng)問(wèn)集中在少數(shù)存儲(chǔ)塊時(shí)降低數(shù)據(jù)交換的條件來(lái)觸發(fā)更多的損耗均衡操作；Yun等[15]提出基于BF的磨損均衡算法，利用BF的特性判斷數(shù)據(jù)塊的冷熱情況進(jìn)行數(shù)據(jù)交換。

靜態(tài)磨損均衡策略的優(yōu)勢(shì)在于使用有限的空間記錄寫(xiě)訪(fǎng)問(wèn)信息，但是周期性的數(shù)據(jù)移位(data shifting)操作在寫(xiě)請(qǐng)求本身分布較為均勻的應(yīng)用場(chǎng)景下會(huì)增加不必要的寫(xiě)操作，同時(shí)確定的地址映射機(jī)制不能應(yīng)對(duì)特殊數(shù)據(jù)流的惡意攻擊。動(dòng)態(tài)磨損均衡策略主要針對(duì)頁(yè)間的數(shù)據(jù)交換(data swapping)操作，該類(lèi)方法需要通過(guò)一定的空間開(kāi)銷(xiāo)記錄數(shù)據(jù)塊的磨損情況，能夠更加準(zhǔn)確地定位到需要執(zhí)行磨損均衡的數(shù)據(jù)塊，同時(shí)使得PCM達(dá)到更長(zhǎng)的使用壽命。如何降低記錄寫(xiě)次數(shù)的空間開(kāi)銷(xiāo)、有效避免惡意攻擊、以怎樣的粒度進(jìn)行數(shù)據(jù)交換和移位都是在設(shè)計(jì)磨損均衡算法時(shí)必須考慮的因素。

2 新型混合存儲(chǔ)架構(gòu)

圖1(a)、(b)是兩種常見(jiàn)的混合存儲(chǔ)架構(gòu)，為了解決PCM寫(xiě)耐受性的問(wèn)題，前者利用DRAM作為緩存，將修改頻繁的數(shù)據(jù)緩存在DRAM中以減少對(duì)主存的寫(xiě)操作數(shù)量，而后者使用DRAM和PCM共同作為主存，通過(guò)預(yù)測(cè)數(shù)據(jù)的讀寫(xiě)傾向性進(jìn)行頁(yè)面遷移操作，將寫(xiě)頻繁的頁(yè)面保存在DRAM來(lái)提高PCM的使用壽命。DRAM緩存策略的主要目標(biāo)是減少PCM上的寫(xiě)操作，為此，許多已有的研究工作都是利用局部性原理將頻繁更新的數(shù)據(jù)緩存在DRAM，淘汰最近一段時(shí)間沒(méi)有被頻繁修改的數(shù)據(jù)至PCM。但是，基于傳統(tǒng)的LRU、LFU等緩存算法，淘汰至PCM的臟數(shù)據(jù)頁(yè)仍然會(huì)帶來(lái)冗余的寫(xiě)操作。同時(shí)，PCM和DRAM混合主存架構(gòu)下的頁(yè)面遷移策略能夠?qū)崿F(xiàn)讀寫(xiě)熱度不同的數(shù)據(jù)存儲(chǔ)在不同存儲(chǔ)介質(zhì)當(dāng)中，但是遷移操作本身所帶來(lái)的額外寫(xiě)操作也會(huì)在一定程度上磨損PCM的存儲(chǔ)單元。

圖1 基于DRAM和PCM的混合主存存儲(chǔ)架構(gòu)

針對(duì)現(xiàn)有的兩種主要混合存儲(chǔ)架構(gòu)在改進(jìn)PCM耐受性方面的不足，本文提出一種DRAM緩存+DRAM/PCM混合主存的新型存儲(chǔ)架構(gòu)，并在此基礎(chǔ)上設(shè)計(jì)了一種基于LRU和LFU-Aging改進(jìn)的兩級(jí)緩存算法。本文將從兩個(gè)方面說(shuō)明這種策略的優(yōu)勢(shì)：

1)新型存儲(chǔ)架構(gòu)。使用DRAM作為緩存能夠有效延長(zhǎng)PCM的使用壽命，但是相比DRAM，PCM相對(duì)較低的讀寫(xiě)性能和更新數(shù)據(jù)時(shí)的高能耗成為限制其獨(dú)立作為主存的重要障礙。結(jié)合現(xiàn)有的兩種主流的存儲(chǔ)架構(gòu)(如圖1(c)所示)，本文設(shè)計(jì)了一種一小塊DRAM作為緩存、PCM和DRAM共同作為主存的新型混合存儲(chǔ)架構(gòu)。該架構(gòu)一方面利用緩存技術(shù)解決了PCM寫(xiě)壽命受限的問(wèn)題，另一方面PCM和DRAM的混合主存能夠充分發(fā)揮DRAM的寫(xiě)訪(fǎng)問(wèn)性能(存儲(chǔ)寫(xiě)傾向性數(shù)據(jù))以及PCM的低靜態(tài)功耗(響應(yīng)讀傾向性數(shù)據(jù))，在保證系統(tǒng)性能的同時(shí)降低了能耗開(kāi)銷(xiāo)。

2)新型緩存策略。時(shí)間局部性和訪(fǎng)問(wèn)頻率是設(shè)計(jì)緩存策略時(shí)需要考慮的兩個(gè)重要方面，新型存儲(chǔ)架構(gòu)下的DRAM緩存策略在同時(shí)參考時(shí)間局部性和訪(fǎng)問(wèn)頻率的基礎(chǔ)上，充分考慮數(shù)據(jù)的讀寫(xiě)傾向性，將沒(méi)有修改過(guò)的讀傾向性數(shù)據(jù)淘汰至PCM，而更新頻繁的熱寫(xiě)數(shù)據(jù)被寫(xiě)回到DRAM。本文設(shè)計(jì)了一種基于LRU和LFU-Aging的雙層緩存策略(如圖2所示)：第一層通過(guò)LRU管理所有的臟數(shù)據(jù)塊以及未經(jīng)修改的干凈數(shù)據(jù)塊，根據(jù)時(shí)間局部性原理淘汰第一層中最近最少使用的冷數(shù)據(jù)塊至相應(yīng)的第二層LFU-Aging隊(duì)列；第二層結(jié)合時(shí)間局部性和訪(fǎng)問(wèn)頻率分別管理一個(gè)臟塊LFU-Aging隊(duì)列和一個(gè)干凈塊LFU-Aging隊(duì)列，如果從第一層淘汰下來(lái)的冷數(shù)據(jù)塊是修改過(guò)的，該數(shù)據(jù)頁(yè)進(jìn)入臟數(shù)據(jù)塊隊(duì)列，否則進(jìn)入干凈數(shù)據(jù)塊隊(duì)列。當(dāng)需要淘汰數(shù)據(jù)時(shí)，將隊(duì)列中處于LFU位置的數(shù)據(jù)塊刪除，即臟塊寫(xiě)回到DRAM，干凈數(shù)據(jù)塊寫(xiě)回到PCM。傳統(tǒng)的緩存策略通過(guò)長(zhǎng)時(shí)間緩存更新頻繁的數(shù)據(jù)來(lái)保護(hù)PCM，但是被寫(xiě)回的臟數(shù)據(jù)仍然更有可能在未來(lái)表現(xiàn)出寫(xiě)頻繁趨勢(shì)，該策略能夠?qū)⒉煌x寫(xiě)熱度的數(shù)據(jù)分別寫(xiě)回到DRAM和PCM，使PCM盡可能存儲(chǔ)發(fā)生修改可能性更小的讀傾向性數(shù)據(jù)，進(jìn)一步減少PCM冗余寫(xiě)操作。此外，基于LRU和LFU-Aging改進(jìn)的緩存算法在考慮訪(fǎng)問(wèn)頻率的基礎(chǔ)上，利用時(shí)間局部性避免了緩存污染，且易于實(shí)現(xiàn)、擁有高命中率。

3 基于BF的磨損均衡算法

通過(guò)新型混合存儲(chǔ)架構(gòu)下的基于LRU和LFU-Aging的緩存替換算法，本文能夠在緩存被頻繁訪(fǎng)問(wèn)數(shù)據(jù)的基礎(chǔ)上，利用數(shù)據(jù)的讀寫(xiě)傾向性將干凈數(shù)據(jù)寫(xiě)回到PCM，進(jìn)一步減少了PCM上的寫(xiě)操作。而在PCM主存中，本文在Partial Bloom Filter結(jié)構(gòu)基礎(chǔ)上針對(duì)強(qiáng)空間局部性的應(yīng)用實(shí)現(xiàn)了低空間開(kāi)銷(xiāo)、高查詢(xún)速度的組間磨損均衡算法。

3.1 基本思想

均勻化寫(xiě)操作分布是提高PCM耐受性的另一個(gè)重要研究方向，現(xiàn)有的磨損均衡操作根據(jù)數(shù)據(jù)交換或者數(shù)據(jù)移位的粒度可以分為組間和組內(nèi)兩大類(lèi)：組間磨損均衡以一個(gè)分組(通常選取一個(gè)頁(yè)面作為一個(gè)分組)為基本操作單位，能夠?qū)崿F(xiàn)寫(xiě)操作次數(shù)多的分組和寫(xiě)操作次數(shù)少的分組之間的磨損均衡；而組內(nèi)磨損均衡則保證分組內(nèi)部更細(xì)粒度的寫(xiě)操作單元(例如line)均勻化寫(xiě)操作分布。傳統(tǒng)的以頁(yè)面為粒度的數(shù)據(jù)交換磨損均衡操作在某些頁(yè)面寫(xiě)操作次數(shù)突出的情況下效果良好，但是對(duì)于連續(xù)訪(fǎng)問(wèn)一段連續(xù)地址空間或者空間局部性較強(qiáng)的寫(xiě)訪(fǎng)問(wèn)模式，以單個(gè)頁(yè)面為單位的磨損均衡將不再那么有效。

圖2 基于LRU和LFU-Aging的新型緩存策略

Bloom Filter是一種擁有高空間和時(shí)間效率的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。Counting Bloom Filter將標(biāo)準(zhǔn)Bloom Filter位數(shù)組的每一位擴(kuò)展為一個(gè)計(jì)數(shù)器(Counter)，通過(guò)k個(gè)不同的hash函數(shù)將元素投影到k個(gè)不同的計(jì)數(shù)器，插入元素時(shí)對(duì)應(yīng)的計(jì)數(shù)器加1，刪除元素時(shí)減1。在Counting Bloom Filter基礎(chǔ)之上演變而來(lái)的Partial Bloom Filter將位數(shù)組等分成k個(gè)區(qū)域，每個(gè)哈希函數(shù)只映射到其中一個(gè)區(qū)域，對(duì)應(yīng)的哈希函數(shù)映射范圍都是{0,1， …,m/k-1}。

基于Bloom Filter的思想，本文設(shè)計(jì)了一種針對(duì)強(qiáng)空間局部性數(shù)據(jù)流的組間磨損均衡策略。每個(gè)分組大小為128 MB，包含32 768個(gè)page，利用Partial Bloom Filter記錄每個(gè)分組的寫(xiě)操作次數(shù)，當(dāng)某個(gè)分組的寫(xiě)操作次數(shù)超過(guò)一定的閾值，則將該分組與寫(xiě)次數(shù)最少的分組進(jìn)行數(shù)據(jù)交換。在分組之間進(jìn)行數(shù)據(jù)交換時(shí)，將兩個(gè)分組中一一對(duì)應(yīng)的頁(yè)面進(jìn)行地址映射的變換(如圖3 Segment swap)，實(shí)現(xiàn)分組之間的寫(xiě)操作均勻分布。

圖3 基于Partial Bloom Filter的組間磨損均衡策略

3.2 組間磨損均衡

相比靜態(tài)磨損均衡策略，動(dòng)態(tài)磨損均衡對(duì)內(nèi)存中每個(gè)分組的寫(xiě)操作次數(shù)進(jìn)行跟蹤，把磨損相對(duì)嚴(yán)重的分組中的寫(xiě)操作均勻到寫(xiě)操作次數(shù)較少的分組，這種依據(jù)全局寫(xiě)訪(fǎng)問(wèn)信息、沒(méi)有確定性映射機(jī)制的重定位方式需要額外的映射表記錄邏輯地址到物理地址的映射關(guān)系。傳統(tǒng)的動(dòng)態(tài)磨損均衡算法中每個(gè)分組對(duì)應(yīng)一個(gè)計(jì)數(shù)器記錄寫(xiě)次數(shù)，為了減少計(jì)數(shù)器帶來(lái)的空間開(kāi)銷(xiāo)，同時(shí)提高查詢(xún)效率，本文基于Partial Bloom Filter實(shí)現(xiàn)了低空間開(kāi)銷(xiāo)、高查詢(xún)速度的組間磨損均衡算法。

由于很多應(yīng)用程序會(huì)連續(xù)訪(fǎng)問(wèn)一段連續(xù)的地址空間，同時(shí)寫(xiě)操作表現(xiàn)出明顯的空間局部性，一個(gè)頁(yè)面被修改，相鄰地址的數(shù)據(jù)頁(yè)也會(huì)被修改，因此寫(xiě)操作的增加往往呈現(xiàn)一定的局部性，基于單個(gè)頁(yè)面的磨損均衡操作不再那么高效。組間磨損均衡算法以每128 MB連續(xù)地址空間作為一個(gè)分組，利用Partial Bloom Filter的思想通過(guò)一個(gè)計(jì)數(shù)器記錄分組所有頁(yè)面的寫(xiě)操作情況，當(dāng)分組中的頁(yè)面響應(yīng)寫(xiě)請(qǐng)求，計(jì)數(shù)器的數(shù)值加1，響應(yīng)讀請(qǐng)求時(shí)計(jì)數(shù)器數(shù)值不變化。當(dāng)某個(gè)分組的寫(xiě)操作次數(shù)超過(guò)一定的閾值，找到寫(xiě)操作次數(shù)最少的分組并進(jìn)行地址映射的變換。在進(jìn)行組間數(shù)據(jù)交換時(shí)，定義寫(xiě)操作次數(shù)超過(guò)閾值的分組為A，寫(xiě)操作次數(shù)最少的分組為B，如果分組A中的頁(yè)面i再次響應(yīng)寫(xiě)請(qǐng)求，那么在分組B中找到對(duì)應(yīng)的頁(yè)面i，改變這兩個(gè)頁(yè)面之間的地址映射關(guān)系，即把頁(yè)面Ai的邏輯地址映射到頁(yè)面Bi的物理地址，將頁(yè)面Bi的邏輯地址映射到頁(yè)面Ai的物理地址，從而達(dá)到分組之間磨損均衡的目的。

這種組間磨損均衡算法具有如下幾點(diǎn)優(yōu)勢(shì)：

1)降低記錄寫(xiě)操作歷史信息所帶來(lái)的開(kāi)銷(xiāo)。每128 MB連續(xù)地址下的寫(xiě)操作被映射到1個(gè)計(jì)數(shù)器，相比傳統(tǒng)的動(dòng)態(tài)磨損均衡策略中每一個(gè)頁(yè)面對(duì)應(yīng)一個(gè)寫(xiě)操作計(jì)數(shù)器，算法利用Partial Bloom Filter極大地減少了計(jì)數(shù)器數(shù)量，從而降低了因統(tǒng)計(jì)寫(xiě)操作歷史信息所帶來(lái)的空間開(kāi)銷(xiāo)。

2)在寫(xiě)訪(fǎng)問(wèn)空間局部性較強(qiáng)的應(yīng)用中，能夠有效判斷分組的磨損情況。當(dāng)幾個(gè)連續(xù)的頁(yè)面響應(yīng)寫(xiě)請(qǐng)求時(shí)，這些頁(yè)面所在分組的寫(xiě)操作計(jì)數(shù)器會(huì)迅速增加，且寫(xiě)訪(fǎng)問(wèn)的局部性越強(qiáng)，分組之間的寫(xiě)操作次數(shù)差異越明顯，將超過(guò)寫(xiě)操作閾值分組的邏輯地址重映射到寫(xiě)操作次數(shù)小的分組將會(huì)起到很好的均衡效果。

4 性能評(píng)估

對(duì)于PCM耐受性的缺陷，本文從減少寫(xiě)操作數(shù)量和均勻化寫(xiě)操作分布兩個(gè)方向?qū)崿F(xiàn)了PCM寫(xiě)壽命的提高?；贒RAM cache+PCM/DRAM混合主存的新型存儲(chǔ)架構(gòu)能夠?qū)?shù)據(jù)流讀寫(xiě)傾向性進(jìn)行劃分，減少對(duì)PCM存儲(chǔ)介質(zhì)不必要的寫(xiě)操作，基于Bloom Filter的組間磨損均衡策略能夠?qū)崿F(xiàn)分組之間的寫(xiě)操作均勻分布。本章從實(shí)驗(yàn)環(huán)境的設(shè)置以及新型存儲(chǔ)架構(gòu)下的磨損均衡算法對(duì)于減少PCM寫(xiě)操作、均勻化寫(xiě)操作分布的實(shí)驗(yàn)效果這兩方面進(jìn)行闡述和分析。

4.1 測(cè)試環(huán)境

由于目前還沒(méi)有真實(shí)的混合內(nèi)存物理器件，對(duì)于混合內(nèi)存的研究工作都是基于模擬器平臺(tái)進(jìn)行仿真，本文使用基于GEM5和NVMain搭建的混合模擬器(如圖4所示)來(lái)測(cè)試算法的有效性。GEM5是由M5和GEMS緊耦合而成的全系統(tǒng)模擬器，而NVMain是一個(gè)在內(nèi)存結(jié)構(gòu)層面模擬新型非易失性存儲(chǔ)器件的局部硬件模擬器，兩者結(jié)合不僅可以支持構(gòu)建混合存儲(chǔ)體系結(jié)構(gòu)，而且能夠更準(zhǔn)確地模擬各種非易失性存儲(chǔ)設(shè)備的性能。

圖4 GEM5+NVMaim混合存儲(chǔ)架構(gòu)

實(shí)驗(yàn)中仿真實(shí)現(xiàn)了DRAM cache+PCM/DRAM混合主存的存儲(chǔ)架構(gòu)，在主存這一層級(jí)對(duì)兩種存儲(chǔ)介質(zhì)進(jìn)行統(tǒng)一編址，channel0為DRAM，其余地址空間被PCM占據(jù)。對(duì)于從DRAM cache淘汰至混合主存的數(shù)據(jù)塊，根據(jù)其在緩存中表現(xiàn)出來(lái)的讀寫(xiě)傾向性被寫(xiě)回到相應(yīng)的主存設(shè)備，即修改頻繁的數(shù)據(jù)被寫(xiě)回到DRAM，修改較少的靜態(tài)數(shù)據(jù)寫(xiě)回到PCM。

GEM5模擬器中Alpha處理器架構(gòu)提供四種可選擇的CPU類(lèi)型以及三級(jí)緩存的設(shè)置。本實(shí)驗(yàn)將CPU類(lèi)型指定為T(mén)iming類(lèi)型，即根據(jù)時(shí)序模型模擬相應(yīng)的訪(fǎng)問(wèn)，設(shè)置兩級(jí)緩存，包括64 KB的一級(jí)指令緩存、32 KB一級(jí)數(shù)據(jù)緩存以及2 MB二級(jí)緩存。對(duì)于主存，實(shí)驗(yàn)配置4個(gè)channel，其中channel0為傳統(tǒng)的DDR3 SDRAM，channel1～3為PCM，主存大小設(shè)置為4 GB，而針對(duì)強(qiáng)空間局部性應(yīng)用場(chǎng)景所設(shè)計(jì)的組間磨損均衡的實(shí)現(xiàn)以128 MB大小的Subarray作為基本操作單位。參數(shù)配置如表1所示。

表1 測(cè)試環(huán)境及參數(shù)配置

實(shí)驗(yàn)選取SPLASH-2測(cè)試集中的FFT、LU、RADIX作為基本測(cè)試程序，每個(gè)測(cè)試程序的大小、讀寫(xiě)比例不盡相同，磨損均衡算法在不同測(cè)試程序下因數(shù)據(jù)流的空間局部性不同而產(chǎn)生實(shí)驗(yàn)效果上的差異。

4.2 性能分析

本文提出的兩層磨損均衡算法分別從緩存數(shù)據(jù)寫(xiě)回時(shí)減少PCM上寫(xiě)操作數(shù)量以及PCM存儲(chǔ)設(shè)備內(nèi)部上的寫(xiě)操作均勻分布這兩方面實(shí)現(xiàn)了PCM寫(xiě)壽命的延長(zhǎng)，實(shí)驗(yàn)測(cè)試結(jié)果將對(duì)寫(xiě)操作數(shù)量的減少以及均勻分布情況進(jìn)行分析與對(duì)比。

4.2.1 寫(xiě)操作次數(shù)減少情況

在傳統(tǒng)的使用DRAM緩存減少PCM主存寫(xiě)操作次數(shù)方式的基礎(chǔ)上，本文提出一種DRAM cache+DRAM/PCM混合內(nèi)存的新型存儲(chǔ)架構(gòu)。該架構(gòu)能夠從兩方面減少主存中PCM存儲(chǔ)介質(zhì)的寫(xiě)操作數(shù)量：一方面使修改頻繁的數(shù)據(jù)盡可能保存在DRAM cache中，避免了主存頻繁的存取訪(fǎng)問(wèn)；另一方面通過(guò)LRU和LFU-Aging相結(jié)合的緩存策略區(qū)分?jǐn)?shù)據(jù)塊的讀寫(xiě)訪(fǎng)問(wèn)趨勢(shì)，使得寫(xiě)訪(fǎng)問(wèn)頻繁的數(shù)據(jù)寫(xiě)回到DRAM，讀訪(fǎng)問(wèn)頻繁的數(shù)據(jù)保存在PCM，進(jìn)一步減少了PCM存儲(chǔ)介質(zhì)的寫(xiě)操作數(shù)量。

實(shí)驗(yàn)從混合存儲(chǔ)架構(gòu)中DRAM cache上減少的寫(xiě)回請(qǐng)求次數(shù)以及LRU+LFU-Aging緩存策略對(duì)于混合主存命中率的影響這兩方面來(lái)衡量新型混合存儲(chǔ)架構(gòu)以及緩存策略的優(yōu)劣性。從表2可以看出，相比傳統(tǒng)的LRU緩存策略，本文所提出的緩存策略能夠有效判斷數(shù)據(jù)流的讀寫(xiě)傾向性，使得從cache寫(xiě)回PCM上寫(xiě)請(qǐng)求的數(shù)量減少達(dá)到13.4%～38.6%。同時(shí)，針對(duì)DRAM cache設(shè)計(jì)的基于LRU+LFU-Aging的緩存策略在不同測(cè)試程序下的讀寫(xiě)緩存命中率和傳統(tǒng)的LRU相當(dāng)(如表2所示)，增加讀寫(xiě)傾向性的判斷并未造成命中率的下降。

表2 新型混合存儲(chǔ)架構(gòu)下緩存策略的性能對(duì)比

4.2.2 寫(xiě)操作均勻分布情況

對(duì)于寫(xiě)訪(fǎng)問(wèn)局部性較強(qiáng)的數(shù)據(jù)流，往往會(huì)呈現(xiàn)出內(nèi)存中某一個(gè)連續(xù)區(qū)域內(nèi)的寫(xiě)次數(shù)明顯多于其他區(qū)域，針對(duì)該問(wèn)題本文設(shè)計(jì)了一種基于Bloom Filter的組間寫(xiě)操作均勻分布策略。如圖5(a)所示，從左至右分別是測(cè)試集Barnes、Radix和Ocean，在沒(méi)有磨損均衡策略的情況下測(cè)試集的寫(xiě)操作分布呈現(xiàn)出明顯的空間局部性，某些分組的寫(xiě)次數(shù)遠(yuǎn)遠(yuǎn)高于其他分組，值得注意的是，這些寫(xiě)次數(shù)突出的分組往往集中在某一個(gè)channel中，這種情況往往會(huì)加速存儲(chǔ)介質(zhì)的損壞。本文利用Partial Bloom Filter結(jié)構(gòu)記錄每個(gè)分組的磨損情況并依據(jù)分組寫(xiě)次數(shù)計(jì)數(shù)情況執(zhí)行組間磨損均衡，從統(tǒng)計(jì)數(shù)據(jù)可以發(fā)現(xiàn)，90%分組的寫(xiě)次數(shù)都能集中在平均寫(xiě)次數(shù)的20%浮動(dòng)范圍之內(nèi)(如圖5(b)所示)。值得注意的是，Ocean 測(cè)試集原先的寫(xiě)操作分布相對(duì)均勻，這種情況下的均勻化寫(xiě)操作分布的效果相比強(qiáng)空間局部性測(cè)試集下的實(shí)現(xiàn)效果稍有遜色。

圖5 以128 MB為分組大小時(shí)磨損均衡前后寫(xiě)操作分布情況對(duì)比

本文設(shè)計(jì)的組間磨損均衡策略以128 MB為一個(gè)分組，當(dāng)分組的寫(xiě)次數(shù)超過(guò)某一閾值，觸發(fā)組間磨損均衡。這種粗粒度的觸發(fā)條件對(duì)于分組內(nèi)部頁(yè)面的寫(xiě)次數(shù)缺乏一定的監(jiān)控，會(huì)出現(xiàn)分組寫(xiě)次數(shù)尚未超過(guò)閾值，但是分組內(nèi)某一頁(yè)面已經(jīng)被過(guò)多“磨損”的情況。以更細(xì)粒度的分組作為寫(xiě)訪(fǎng)問(wèn)歷史信息統(tǒng)計(jì)的基本單位往往能夠取得更好的磨損均衡效果，同時(shí)以更大的幾率避免分組內(nèi)部某一存儲(chǔ)單元被提前損壞，例如以一個(gè)頁(yè)面作為一個(gè)獨(dú)立分組，統(tǒng)計(jì)每一個(gè)頁(yè)面的寫(xiě)信息，但是這樣也會(huì)帶來(lái)空間開(kāi)銷(xiāo)增大和數(shù)據(jù)遷移造成的額外寫(xiě)操作問(wèn)題。如圖6所示，以測(cè)試集Barnes為例，如果以64 MB為一個(gè)分組，可以將90%以上的寫(xiě)操作均勻分布在平均值10%的浮動(dòng)范圍內(nèi)，但是冗余寫(xiě)操作的比例也相應(yīng)地從2.35%提高至4.1%。

圖6 以64 MB為分組大小時(shí)磨損均衡前后寫(xiě)操作分布情況

5 結(jié)語(yǔ)

相變存儲(chǔ)器的發(fā)展成熟打破了傳統(tǒng)存儲(chǔ)架構(gòu)中以DRAM作為主存設(shè)備所面臨的高能耗、易失性等瓶頸，為了解決PCM寫(xiě)壽命受限的問(wèn)題，本文從減少寫(xiě)次數(shù)和均勻化寫(xiě)操作分布兩個(gè)方向有效地延長(zhǎng)PCM的使用壽命。本文提出DRAM cache+DRAM/PCM的混合存儲(chǔ)結(jié)構(gòu)，通過(guò)LRU和LFU-Aging相結(jié)合的緩存策略將讀寫(xiě)熱度不同的數(shù)據(jù)分別存儲(chǔ)在DRAM或PCM中，避免頻繁修改數(shù)據(jù)對(duì)PCM所造成的不必要的寫(xiě)操作負(fù)擔(dān)。同時(shí)，針對(duì)訪(fǎng)問(wèn)局部性較強(qiáng)的應(yīng)用，本文設(shè)計(jì)一種組間磨損均衡策略，通過(guò)Bloom Filter結(jié)構(gòu)以較低空間代價(jià)實(shí)現(xiàn)PCM中所有分組的寫(xiě)次數(shù)記錄，從而實(shí)現(xiàn)了寫(xiě)操作的均勻化分布。實(shí)驗(yàn)結(jié)果表明，在新型混合存儲(chǔ)架構(gòu)下減少PCM寫(xiě)操作達(dá)13.4%～38.6%，并且針對(duì)強(qiáng)空間局部性的訪(fǎng)問(wèn)模式，能夠有效均勻分組之間的寫(xiě)操作分布，90%以上的分組的寫(xiě)次數(shù)能夠浮動(dòng)在平均寫(xiě)次數(shù)±20%之內(nèi)。