高 鵬 汪東升 王海霞

1(清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084)2(清華大學(xué)信息技術(shù)研究院 北京 100084)

采用流水化偽隨機編碼算法的相變存儲器壽命延長方法

高 鵬1,2汪東升2王海霞2

1(清華大學(xué)計算機科學(xué)與技術(shù)系 北京 100084)2(清華大學(xué)信息技術(shù)研究院 北京 100084)

(gaopeng1982@gmail.com)

相變存儲器(phase change memory, PCM)是一種頗具前景的新型存儲器件，具有非易失性、靜態(tài)功耗低和存儲密度高的優(yōu)點.然而，該類器件的低寫入壽命是其在實用化中亟待克服的關(guān)鍵問題之一.一般來說，通過每次寫入時僅寫入相異位的策略，可以減少產(chǎn)生的平均寫入量，從而延長PCM的寫入壽命.然而，應(yīng)用這一差異式的寫入策略通常又會以降低讀寫速度為代價.為此，提出了一種兼具高效和快速特點的寫入量減少方法FEBRE(a fast and efficient bit-flipping reduction technique to extend PCM lifetime).該方法在差分寫入階段前，設(shè)計并使用了一種快速的一對多映射，將待寫入的數(shù)據(jù)并行映射為多個編碼向量，從而增加了從其中找到一個與已有數(shù)據(jù)最近的向量的可能性.此外，還提出了一種流水化的偽隨機編碼算法，用以加速一對多映射中的編碼過程，從而降低寫入開銷.實驗表明，與目前領(lǐng)先的PRES(pseudo-random encoding scheme)方法相比，F(xiàn)EBRE方法在寫入操作中，平均減少了5%以上的寫入量，提升了2倍以上的編碼速度；在讀取操作中，減少了45%以上的解碼操作次數(shù).

相變存儲器件；差分寫入；偽隨機編碼算法；編碼方向模式；星型生成規(guī)則

隨著軟硬件技術(shù)的發(fā)展，現(xiàn)代計算機系統(tǒng)對高速、大容量、低功耗的內(nèi)存系統(tǒng)產(chǎn)生了越來越迫切的需求.然而，目前廣泛使用的DRAM(dynamic random access memory)存儲器件,已經(jīng)越來越接近其性能發(fā)展的極限[1]，這是由該技術(shù)自身的漏電功耗和存儲密度所造成的.為了進一步提升存儲系統(tǒng)的性能和容量，同時降低系統(tǒng)功耗，工業(yè)界和學(xué)術(shù)界目前都在積極探索構(gòu)成下一代存儲系統(tǒng)的相關(guān)方案.其中最具代表性的技術(shù)就是相變存儲器(phase change memory, PCM)[1].相比于目前廣泛使用的DRAM器件，PCM器件具有靜態(tài)功耗低、隨機讀寫速度高和容量密度大(4倍于DRAM)等諸多優(yōu)點[1-3]，因此也被視為是構(gòu)建未來存儲系統(tǒng)的重要選擇之一.

然而，PCM技術(shù)也存在一個亟待克服的缺點，即由破壞性的寫入行為所致的較短的寫入壽命(寫入壽命一般被定義為存儲單元的翻轉(zhuǎn)次數(shù)上限.PCM的寫入壽命一般為106～109次，而DRAM器件一般不低于1014次[1-2]).有研究表明[4]，在極端條件下，如不采取任何緩解寫入磨損的措施，一個精心設(shè)計的寫入序列可以在數(shù)分鐘內(nèi)用完一個全新PCM單元的全部寫入壽命，并導(dǎo)致其失去存儲能力而出現(xiàn)故障.因此，延長寫入壽命是PCM技術(shù)得以廣泛使用的前提之一.

差分寫入策略是一種有效的PCM寫入壽命延長方法[5-6].其核心思想在于把待寫入數(shù)據(jù)通過某種編碼算法映射為多個不同的編碼向量，然后從中找出一個和已有數(shù)據(jù)相異位數(shù)最少的向量.通過僅寫入與已存儲數(shù)據(jù)相異的位來完成寫入，該類方法[5-10]可以有效地降低每次寫入時的寫入量.但是，此類方法一般也面臨效率和執(zhí)行速度的矛盾：簡單編碼算法執(zhí)行速度較快，卻難以取得較好的寫入量減少效果；而復(fù)雜的編碼算法通常又會帶來讀寫速度的降低，進而影響系統(tǒng)性能.

為了達到較好的寫入量減少效果，且保持較低的讀寫代價，本文提出了一種快速而高效的差分式寫入量減少方法FEBRE(a fast and efficient bit-flipping reduction technique to extend PCM lifetime).該方法通過將帶寫入的數(shù)據(jù)映射為多個隨機化的編碼向量，提高了從這些編碼向量中找到一個與目標地址已有數(shù)據(jù)更加相似的向量的概率，從而減少了寫入時的差異位數(shù)，最終降低了寫入量.

該方法的核心之處在于其采用了一種新穎的編碼向量并行生成和組織方法，稱為星型生成規(guī)則.該規(guī)則中，多個隨機化分布的編碼向量由一個待寫入的數(shù)據(jù)通過一個并行映射而來.首先，在這一規(guī)則中，待寫入數(shù)據(jù)采用了一對一的直接生成方式產(chǎn)生編碼向量.這一方式消除了之前方法中編碼向量間的重復(fù)問題，從而進一步提升了在編碼向量集合中找到一個與存儲數(shù)據(jù)更近向量的概率，進而降低每次寫入的平均寫入量.其次，星型生成規(guī)則還可以通過減少編碼/解碼的次數(shù)來加快讀寫速度.此外，本文設(shè)計了一種流水化的偽隨機編碼算法，不僅對輸入數(shù)據(jù)保持了較高的隨機化能力，而且加速了編碼向量生成步驟中的編碼速度，緩解了其對讀寫速度帶來的影響.

實驗證明，以上這些創(chuàng)新帶來的優(yōu)勢使得FEBRE方法具有更快的讀寫速度和更好的寫入量減少效果.與目前領(lǐng)先的PRES方法相比，F(xiàn)EBRE方法在寫入操作中平均減少了5%以上的寫入量，提升了2倍以上的編碼速度；在讀取操作中，減少了45%以上的解碼操作次數(shù).

1 相關(guān)工作

在其他條件相同的情況下，對于某個PCM存儲單元而言，越少的寫入量就意味著越長的寫入壽命，這就是差分式寫入方法的基本思想.而以下所述的各方法正是遵循這一思路逐步發(fā)展而來的，其共同點是通過將待寫入的數(shù)據(jù)變換為與已有的數(shù)據(jù)更加相似的形式，從而達到更好的寫入量減少效果.

作為此類方法中最簡單的形式，Data Compare Writing(DCW)[5]方法僅使用待寫入數(shù)據(jù)作為唯一的候選項與已有數(shù)據(jù)進行比較.Flip-N-Write(FNW)[6]在DCW的基礎(chǔ)上，提供了待寫入數(shù)據(jù)和其逐位取反的結(jié)果作為2個候選項，并將兩者中寫入代價較小的那一個用于最終寫入.Min-Shift[7]方法在FNW方法的基礎(chǔ)上，通過對待寫入數(shù)據(jù)添加位移操作，產(chǎn)生了更多的候選數(shù)據(jù)項.總而言之，盡管這些方法帶來的讀寫操作代價較低，但其寫入量減少能力也相對較弱.

一般來說，將一個待寫入數(shù)據(jù)變換為多個隨機化的編碼向量后，可以從中找出一個向量，并使得被選出的向量比待寫入數(shù)據(jù)更接近已有數(shù)據(jù).而且，更多的編碼向量會進一步提高被選出的向量與已有數(shù)據(jù)的相似性，因而也會帶來更好的寫入量減少效果.

基于這一思想，近期該領(lǐng)域的研究在進行數(shù)據(jù)比較前增加了一個顯式的一對多映射的步驟，用以將一個待寫入數(shù)據(jù)編碼為多個編碼結(jié)果，并將其作為待比較的數(shù)據(jù)向量.Flip-Min[8]是該思路的代表方案之一，通過使用Hamming糾錯編碼，F(xiàn)lip-Min中將待寫入數(shù)據(jù)編碼為多個帶有隨機錯誤但又是可被糾錯的編碼向量.而作為最接近本文的研究，PRES(pseudo-random encoding scheme)[9-10]方法中的一對多映射被分割為前后相繼的2個部分：一種數(shù)據(jù)變換策略，用以生成待寫入數(shù)據(jù)的多個帶有不同子數(shù)據(jù)劃分模式的副本；隨后的一對一映射，負責(zé)對劃分后的子數(shù)據(jù)進行編碼，從而將數(shù)據(jù)副本映射為多個不同的隨機化編碼向量.總之，PRES方法提出的隨機化一對多映射使其超過了其他所有同類方法的寫入量減少效果.

盡管PRES方法被認為具有目前最好的寫入量減少效果，但是本文經(jīng)過分析發(fā)現(xiàn)該方法仍然存在2個問題：1)該方法產(chǎn)生的編碼向量集合中存在相當多的重復(fù)元素；2)較慢的編碼算法和編碼向量生成方式.這些問題不僅降低了寫入量減少的效果，而且拖慢了讀寫速度.

2 研究動機

PRES是目前領(lǐng)先的差分式寫入方法，但其也存在一些問題.為了繼承該方法的優(yōu)秀部分，并摒棄其中的不利因素，本節(jié)將首先深入分析PRES方法存在的問題及其成因，以期在其基礎(chǔ)上提出一種更加高效和快速的方法.

2.1 重復(fù)元素起因分析

PRES產(chǎn)生的編碼向量集合中存在大量的重復(fù)元素，這將直接降低其寫入量的減少效果.這是該方法最大的問題，同時也是被其后來研究所忽視的一點.為了探索這一問題的成因，本節(jié)將首先介紹PRES中定義的一些概念，并回顧PRES中生產(chǎn)一個典型編碼向量的過程，以期從中找出問題的根源.

編碼方向模式是PRES引入的一個概念，用于描述一個數(shù)據(jù)是如何被從形式上劃分為多個子數(shù)據(jù)的，以及規(guī)定劃分后的每個子數(shù)據(jù)段中各個位的編碼順序.例如，一個二維矩陣化排列的數(shù)據(jù)可以被劃分為多個行向量的集合，并按照從左到右的方式逐位訪問,而此時的這種劃分和訪問方式就被定義為一種編碼方向模式.

PRES中存在2種編碼向量:1)僅通過一次編碼待寫入數(shù)據(jù)而產(chǎn)生的，稱為一次編碼向量,這部分向量僅占全部向量數(shù)的很少一部分;2)將第1種編碼向量作為輸入，并采用與之不同的編碼方向模式進行再次編碼而產(chǎn)生的，稱為二次編碼向量.但是，在PRES給出的例子中，本文發(fā)現(xiàn)，有一半的二次編碼向量，其內(nèi)容是完全重復(fù)的.盡管這些編碼向量應(yīng)用的是不同的編碼方向模式序列.究其原因，本文認為是由于多次編碼產(chǎn)生方式，以及編碼方向模式之間的可交換性所造成的.

編碼方向模式的可交換性是指在上述的生成二次編碼向量的過程中，某些編碼方向模式的使用順序可以被交換而不影響最終的編碼結(jié)果.為了展示這一結(jié)論，我們首先考慮一個典型的2次編碼過程.即先使用Left-to-Right(LR)模式編碼一個數(shù)據(jù)，然后再使用Top-to-Bottom(TB)模式來編碼第1步產(chǎn)生的結(jié)果.最終產(chǎn)生的二次編碼向量中的任一位可按如下公式計算得出：

(1)

由上述可知，編碼向量集合中的重復(fù)元素問題可以被歸因于編碼方向模式的可交換性和多次編碼的工作方式.而這一點并未被之前的研究所注意到.此外，已有研究也已經(jīng)證明，編碼向量集合的隨機性和寫入量減少是呈正相關(guān)的[8-10].因此，編碼向量集合中的重復(fù)元素會直接降低該集合的隨機性，進而降低了該方法的寫入減少效果.

2.2 讀寫速度分析

PRES存在的另一個問題是讀寫速度緩慢.而本文認為這也是因為其采用了層次式的編碼向量生成和組織方式所造成的.具體而言，PRES中的編碼向量的生成過程如圖1所示：待寫入的數(shù)據(jù)首先被排列為二維矩陣(不改變內(nèi)容)，然后按照水平或垂直方向劃分為多個行向量或列向量.之后，對劃分出的這些向量按照從左到右或從上到下的方向逐位編碼，從而生成一級編碼向量，繼續(xù)重復(fù)這一過程可以形成二級編碼向量.因此，相對于一次生成所有編碼向量的方法，如Flip-Min，這一過程無疑會帶來更多的寫入時間.

Fig. 1 Generating level-1 and level-2 coded vectors in PRES (2 coding direction patterns are used for 4 coded vectors)圖1 PRES方法中一/二級編碼向量的生成方式(采用2個編碼方向模式產(chǎn)生4個編碼向量)

而對于讀取操作，那些經(jīng)過2次編碼而產(chǎn)生的向量同樣需要2次解碼才能得到寫入的數(shù)據(jù)，而且需要2次解碼的向量占據(jù)了整個編碼向量集合的絕大部分.因此，這種方式下的讀取速度也會因此而受到影響.

此外，PRES中所用到的偽隨機編碼算法是一個串行過程，待編碼數(shù)據(jù)的各個位需要依次被編碼.而這又會延長編碼時間，進一步降低寫入速度.以下是該算法的形式化表達

P1=B0+B1；
Pi=Pi-1+Bi；
P0=BL-1+B0.

(2)

B0=PL-1+P0；
B1=P1+B0；
Bi=Pi-1+Pi.

(3)

其中，i=1,2,…,L-1,L為輸入數(shù)據(jù)的長度；Bi表示輸入數(shù)據(jù)的位;Pi表示編碼結(jié)果的位.

盡管式(2)具有較好的數(shù)據(jù)隨機化能力，但其逐位進行編碼的工作方式?jīng)Q定了K位長的數(shù)據(jù)編碼過程至少需要K級加法延遲.這一過程對于長度較長的數(shù)據(jù)而言將耗費更多的時間.

3 FEBRE方法

3.1 基本思想

本文所述的FEBRE方法是建立在PRES方法之上，并針對其缺點進行改進而提出的一種方法.FEBRE的核心思想在于如何構(gòu)造一對多映射，而這也是該方法與其他所有類似方法最大的不同之處.因此，本節(jié)將沿著構(gòu)造一對多映射的順序來介紹FEBRE方法.

在FEBRE方法中，一對多映射被分為了數(shù)據(jù)劃分和子數(shù)據(jù)段編碼2個前后相繼的階段：

階段1. 由星形生成規(guī)則和廣義編碼方向模式共同構(gòu)成，用以將輸入數(shù)據(jù)變形為多種形態(tài)，但保持內(nèi)容不變；

階段2. 由流水化偽隨機編碼算法構(gòu)成，用以將第1階段生成的數(shù)據(jù)變換為多個隨機分布的編碼向量.

在數(shù)據(jù)分劃階段，待寫入的數(shù)據(jù)將首先產(chǎn)生K個副本(K為系統(tǒng)定義的最大副本數(shù)量).然后，為每個數(shù)據(jù)副本配備唯一的一種預(yù)定義的編碼方向模式，并將數(shù)據(jù)副本按照其自己的編碼方向模式劃分為多個子數(shù)據(jù)段.此時各數(shù)據(jù)副本之間的內(nèi)容不變，僅是數(shù)據(jù)劃分方式不同.在這一過程中，為每個數(shù)據(jù)副本指定一個唯一的編碼方向模式的生成規(guī)則，在本文中被稱為星型生成規(guī)則.

與PRES方法不同的是，本文中所用到的編碼方向模式不再局限于水平/垂直等按照自然方向定義的劃分方式上，而是被賦予了更廣泛的含義，即由不同位構(gòu)成的一個排列.因此這樣的編碼方向模式也被稱為廣義編碼方向模式.

在編碼階段中，流水化偽隨機編碼算法將作為一對一映射被應(yīng)用于劃分出的每一個子數(shù)據(jù)段上，從而將原本相同的數(shù)據(jù)副本編碼為不同的數(shù)據(jù),由此產(chǎn)生的編碼向量被稱為候選向量.然后，目標地址上的已有數(shù)據(jù)將與每個候選向量分別進行比較，并選出具有最少相異位的那一個編碼向量，用于最終寫入.此外，產(chǎn)生該向量的編碼方向模式的編號也將被一同記錄，用于讀取時的解碼操作.通過僅翻轉(zhuǎn)目標地址上那些與選出的向量不同的位，差分式寫入最終得以完成.

FEBRE方法的讀取過程相對簡單.當目標地址上的數(shù)據(jù)，及寫入時被記錄的編碼方向模式編號被讀出后，該數(shù)據(jù)將被重新排列為二維矩陣.之后，根據(jù)讀出的編碼方向模式，該數(shù)據(jù)將被劃分為多個子數(shù)據(jù)段.對每個子數(shù)據(jù)段應(yīng)用式(3)所定義的偽隨機解碼算法，即可以得到解碼后的數(shù)據(jù)，該數(shù)據(jù)即為寫入時的原始數(shù)據(jù).

3.2 星形生成規(guī)則

本文提出了一種新的編碼向量集構(gòu)造方法，稱為星型生成規(guī)則,作為交疊使用編碼方向模式的替代.該方法規(guī)定，每個編碼向量必須由唯一的一個編碼方向模式，僅經(jīng)過一次編碼而生成，各編碼方向模式之間不可以重用.圖2給出了使用星型生成規(guī)則生成4個編碼向量的示意圖.如圖2所示，一個待寫入數(shù)首先被復(fù)制多份，然后每個副本根據(jù)某一個選定的編碼方向模式被劃分為多個子數(shù)據(jù)塊的組合，最后每個子數(shù)據(jù)塊進行編碼.而這些被編碼過的數(shù)據(jù)副本無需進一步處理，就直接構(gòu)成了所需的編碼向量集合.

Fig. 2 Generating coded vectors with the star-rule (4 coding direction patterns are used for 4 coded vectors)圖2 星型生成規(guī)則下的編碼向量的生成方式(采用4個編碼方向模式產(chǎn)生4個編碼向量)

星型生成規(guī)則是一個簡單但行之有效的規(guī)則.

1) 應(yīng)用不同編碼方向模式而產(chǎn)生的偽隨機編碼結(jié)果至少會存在一個位的不同，因此編碼結(jié)果集合必然沒有重復(fù)現(xiàn)象.而其直接結(jié)果就是帶來更少的寫入量.

2) 由于每個編碼向量都可以獨立地并行生成，沒有相互依賴，因此編碼速度得以提升，即寫入時間更短.

3) 星型生成規(guī)則中的一次編碼行為也意味著讀取時僅需一次解碼，即讀取時間更少.

顯而易見，星型生成規(guī)則需要更多的編碼方向模式，而這是傳統(tǒng)編碼方向模式(水平、垂直、對角線)所不足以提供的.為了解決這一問題，本文將傳統(tǒng)的編碼方向模式擴展為廣義編碼方向模式.

3.3 廣義編碼方向模式

首先本文定義一個帶有長度參數(shù)的概念：路徑.一個長度為S的路徑是指一個數(shù)據(jù)向量中的S個不同位的一個排列.也就是說，一個路徑指明了哪些位應(yīng)該被視為在同一組中，以及這些位編碼時的訪問順序.在此定義之上，一個廣義編碼方向模式被定義為一組路徑的集合，并且規(guī)定這些路徑定義在同一個數(shù)據(jù)上，且滿足長度相等、互不相交、共同覆蓋數(shù)據(jù)的所有位.圖3給出了一些廣義編碼方向模式的實例，為了簡化描述，此處僅討論那些可以被排列為形如K×K方陣的數(shù)據(jù).2個劃分方式相同，但子數(shù)據(jù)段訪問順序相反的編碼方向模式，例如LR和RL，在此圖中僅列出一個，并為每種模式指定一個編號.如圖3中所示，在每個編碼方向模式中，同色的節(jié)點表示該位置被劃分到了同一個子數(shù)據(jù)段中，而每個節(jié)點的標號表示該子數(shù)據(jù)段進行編碼時的位訪問順序.至此，編碼方向模式的定義從簡單的自然方向被推廣到了數(shù)據(jù)中不同位置元素的排列.而相比于水平/垂直/主副對角線的劃分方式，廣義編碼方向模式更加深刻地反映了編碼方向模式的本質(zhì)，而且其可能的數(shù)量也能夠完全滿足星型生成規(guī)則下對編碼方向模式數(shù)量的需求.

Fig. 3 Examples of the expended coding direction patterns and the index rule圖3 擴展后的編碼方向模式示例及其編號規(guī)則

3.4 流水化偽隨機編碼算法

在劃分階段之后，F(xiàn)EBRE方法將使用流水化偽隨機編碼算法(pipelined pseudo-random encoding algorithm, PPREA)對每個分劃出的子數(shù)據(jù)段進行編碼.通過這一步驟，內(nèi)容相同的數(shù)據(jù)副本將被變換為不同的編碼向量.相比于按照式(2)定義的原始偽隨機編碼算法而言，本文提出的流水化偽隨機編碼算法在保持原始算法較好的隨機化能力基礎(chǔ)上，大幅度提高了執(zhí)行速度.

3.4.1 核心思想

由于偽隨機編碼算法是一個連續(xù)加法的過程，因此，受到超前進位加法的啟發(fā)，本文發(fā)現(xiàn)數(shù)據(jù)中某個位的編碼結(jié)果也可以通過額外的邏輯提前計算得出，而無需在編碼運算中獲得.此外，由式(2)也可得出推論：數(shù)據(jù)中任一子數(shù)據(jù)段的編碼結(jié)果將被該數(shù)據(jù)段的前一位的編碼結(jié)果所唯一確定.

由此，本文構(gòu)造了一種基于分治思想的偽隨機編碼的算法實現(xiàn).其核心思想是：將一個待寫入的數(shù)據(jù)劃分為多個無交疊的子數(shù)據(jù)段后，通過額外邏輯提前計算出這些子數(shù)據(jù)段的前一位的編碼值，然后并行展開所有子數(shù)據(jù)段的編碼過程.

3.4.2 形式化描述

為了形式化地描述和證明該算法，本節(jié)首先定義如下的一些術(shù)語.DK用于表示長度為K位的數(shù)據(jù)向量(從Bit0到BitK-1).假設(shè)DK被平均地分為M個不相交的數(shù)據(jù)段D1,D2,…，DM-1,DM.每個數(shù)據(jù)段包含S個位，S=K是數(shù)據(jù)段Di進行編碼時的輸入，一般是其前一位的編碼結(jié)果，也被稱為該數(shù)據(jù)段的輸入進位.是數(shù)據(jù)段的最后一位的編碼結(jié)果，被稱為該數(shù)據(jù)段的輸出進位(也是下一個數(shù)據(jù)段的輸入進位).規(guī)定數(shù)據(jù)段D1起始于Bit1、終止于BitS，其輸入進位為Bit0(按照編碼規(guī)則，D1的輸入是Bit0而不是Bit0的編碼結(jié)果)，其輸出進位是D2的輸入進位.最后一個數(shù)據(jù)段的輸出進位被回繞定義為Bit0的位置.此外，本文定義輔助函數(shù)Parity()，用來計算并返回從D1到Di-1中的1的奇偶性.定義輔助函數(shù)PREM()用于對輸入進位為的Di數(shù)據(jù)段進行如式(2)所定義的標準偽隨機編碼過程.PPREA的偽代碼如算法1所示.

算法1. PPREA算法偽代碼.

② Fori=1 toM

⑤ End FOR

3.4.3 正確性證明

為了證明算法1提出的算法的正確性，本文首先將提出一個引理，稱為傳播引理，并給出其證明.

傳播引理. 當數(shù)據(jù)段中的某個子數(shù)據(jù)段進行偽隨機編碼時，該數(shù)據(jù)段的輸入進位，該數(shù)據(jù)段中1的奇偶性(假設(shè)奇數(shù)為1，偶數(shù)為0)的異或(XOR)結(jié)果等于該數(shù)據(jù)段的輸出進位.

證明：

3) 考慮S=N+1的情況：

4) 綜上，該引理對所有正整數(shù)N成立.

證畢.

3.4.4 硬件實現(xiàn)

不同分段長度將給PPREA帶來不同的實現(xiàn)代價.因此本節(jié)將討論最優(yōu)的分段長度選擇及其硬件實現(xiàn).

邏輯上，PPREA可以分為超前進位計算和數(shù)據(jù)段內(nèi)編碼2部分.對于一個S位長的子數(shù)據(jù)段而言，需要1+lbK個異或門延遲才能產(chǎn)生輸出進位(作為下一個數(shù)據(jù)段的輸入進位)，需要K-1個異或門延遲完成段內(nèi)編碼.因此，當且僅當1+lbK=K-1時，2部分電路不會出現(xiàn)相互等待的情況，可以充分發(fā)揮電路的并行性.即當子數(shù)據(jù)段長度為4時，達到最優(yōu)分段.

圖4給出了PPREA的最優(yōu)電路實現(xiàn)，包括了4位和K(K>4)位輸入數(shù)據(jù)的情況.虛線框中的電路負責(zé)產(chǎn)生每個數(shù)據(jù)分段的超前輸入進位，其他門電路負責(zé)編碼每個數(shù)據(jù)段內(nèi)的位.為了節(jié)約資源，用于計算最后一個輸入進位的電路在該實現(xiàn)中，也被借用于計算其他的輸入進位.

Fig. 4 The implementation of pipelined pseudo-random encoding algorithm with XOR gate圖4 流水化偽隨機編碼算法的異或門實現(xiàn)

3.4.5 FEBRE方法的讀寫過程

至此，本文已經(jīng)討論了FEBRE方法中的各個組成要素：星型生成規(guī)則、廣義方向模式以及流水化偽隨機編碼算法.為了更好地闡釋FEBRE方法，本節(jié)將展示該方法的一個讀寫用例.如圖5所示，值為0xBC07的數(shù)據(jù)將被寫入一個內(nèi)存位置，其值為0x7126，然后再讀取該位置.系統(tǒng)可用的編碼方向模式如圖3所示，共計16個.系統(tǒng)讀寫字長為16 b.

寫入過程首先產(chǎn)生待寫入數(shù)據(jù)的16份副本;然后，這些副本將根據(jù)如圖3所示的16個可用的編碼方向模式被劃分.在邏輯上，每個副本將被劃分成4個子數(shù)據(jù)段，每個子數(shù)據(jù)段包含4 b.通過對每個子數(shù)據(jù)段應(yīng)用PPREA，就可以得到16個不同的編碼向量.之后，每個編碼向量將會和目標地址已存儲的數(shù)據(jù)0x7126進行比較.其中相異位數(shù)量最少的一個編碼向量0x308E被選出，并寫入那些相異位.同時，產(chǎn)生該向量所用的編碼方向模式的編號0x7也被記錄下來.

讀取過程的第1步是讀出已寫入的數(shù)據(jù)0x308E和它的編號0x7;然后應(yīng)用標號為0x7的編碼方向模式，將0x308E重新劃分為4個子數(shù)據(jù)段.在每個子數(shù)據(jù)段都應(yīng)用了如式(3)所示的解碼算法之后，就得到了最初寫入的數(shù)據(jù)0xBC07.

Fig. 5 Write/Read example for 16 b data圖5 數(shù)據(jù)寫入及讀取過程示例(16 b)

4 性能評估

為了衡量本文提出方法的讀寫性能和寫入量的減少能力，本節(jié)將著重測量以下參數(shù)：PPREA的執(zhí)行速度和其實現(xiàn)代價、編碼向量集合的生成速度，單個編碼向量的解碼速度和每次寫入時的平均寫入量.其中，速度和實現(xiàn)代價方面的測量結(jié)果將會與最為接近本文提出方法的PRES方法的結(jié)果進行對比；而每次寫入時的平均寫入量，作為該類方法最重要的性能參數(shù)，將與PRES,Flip-Min以及經(jīng)典的Flip-N-Write方法進行對比,用以凸顯FEBRE方法的優(yōu)勢.

4.1 測試方案及測試數(shù)據(jù)

除了Flip-N-Write方法，其他算法均難以進行數(shù)學(xué)建模[9]，因此本文將采用蒙特卡洛法進行測試，即：通過使用隨機數(shù)據(jù)模擬對存儲單元的寫入和讀取，來獲得不同方法的寫入時間、讀取時間和實際寫入位數(shù)等參數(shù).具體而言，本文模擬了向一個初始值為0的存儲單元連續(xù)寫入108個隨機產(chǎn)生的數(shù)據(jù)(數(shù)據(jù)長度包括了16 b，32 b，64 b，128 b，256 b，512 b和1 024 b這7種情形)的過程，每次寫入后緊接著進行一次讀取操作.此外，為方便測試，本文規(guī)定任何長度超過16 b的測試數(shù)據(jù)，都將按照多個16 b的基本組的組合形式進行處理.

4.2 測試配置

在模擬中，F(xiàn)EBRE使用了圖3所列出的16個編碼方向模式來產(chǎn)生相應(yīng)的16個編碼向量.作為對照組的PRES方法使用了其中的4個編碼方向模式：Left-to-Right(LR),Right-to-Left(RL),Bottom-to-Top(BT)和Top-to-Bottom(TB).因此，PRES方法所產(chǎn)生的編碼向量集將包括4個一次編碼向量和12個二次編碼向量.FEBRE方法使用了PPREA編碼算法，而PRES采用的是非流水化的編碼算法.此外，為了保證各方法之間的相對公平，本文規(guī)定每種方法的候選向量數(shù)保持一致.因此，參與對比的Flip-N-Write方法和Flip-Min均采用4 b標志位，對應(yīng)16個候選向量.

4.3 PPREA實現(xiàn)的速度與代價分析

PPREA采用如圖4所示的異或門結(jié)構(gòu)實現(xiàn).其執(zhí)行速度、實現(xiàn)代價可以采用增量法來分析.首先假設(shè)數(shù)據(jù)段的長度K?4且能被4整除，并用T來表示一個異或門產(chǎn)生的門延遲.當有4個新的位加入到已有數(shù)據(jù)段時，為了產(chǎn)生新的輸出進位，該算法需要額外增加1T的門延遲，而段內(nèi)編碼時間則可以被完全隱藏，如圖4(b)所示.此時的初始代價為5T，因此，對于K位的數(shù)據(jù)，PPREA需要(K4+5)T完成.例外情況是當K=4時，電路可簡化為僅需要3T的時間，如圖4(a)所示.作為對照，式(2)中定義的非流水化偽隨機編碼算法總是需要K×T的時間來產(chǎn)生同樣的結(jié)果.因此，本文提出的流水化算法最大能夠產(chǎn)生接近400%的加速比.

實現(xiàn)代價方面，本文仍采用增量法進行分析.當為已有的數(shù)據(jù)新加入4 b時，PPREA需要3個額外的異或門來對這些新加入的位進行編碼、另外3個異或門完成奇偶性檢測、2個額外的異或門來產(chǎn)生進位邏輯，總計需要8個異或門.推而廣之，對長度為K的數(shù)據(jù)，PPREA需要2×K個異或門.例外情況是K=4時，僅需7個異或門.作為對比，對于長度為K的數(shù)據(jù)，非流水化的偽隨機編碼算法總是需要K個異或門.

4.4 編碼向量集合生成速度對比

編碼向量集合的生成過程是寫入操作中最為復(fù)雜、關(guān)鍵的步驟.因此可以用該集合的生成速度作為評價寫入速度的指標.圖6給出了PRES和FEBRE 2種方法在這一指標上的歸一化比較結(jié)果.對16/32 b數(shù)據(jù)，F(xiàn)EBRE方法取得了至少2.29倍的加速效果(速度定義為所需時間的倒數(shù))，且加速比還會隨字長的增加而進一步增加,這一加速效果是由PPREA和星型生成規(guī)則所共同帶來的.

Fig. 6 Normalized comparing result of the coded vector set generation speed圖6 編碼向量集合生成速度的歸一化對比

Fig. 7 The comparing result of the average decoding times in each reading operation圖7 每次讀取時所需的平均解碼操作次數(shù)對比

4.5 解碼速度對比

通過模擬多次讀取，可以獲得每次讀取時2種方法的平均解碼次數(shù).如圖7所示，每次讀取時，F(xiàn)EBRE方法比PRES方法少用0.45次解碼操作.

究其原因，F(xiàn)EBRE中的每個編碼向量僅需要一次解碼；而在PRES中，編碼向量的解碼次數(shù)依賴于該向量被生成時所用到的編碼次數(shù)，而且二次編碼向量遠多于一次編碼向量的數(shù)量.因此，在解碼算法相同的前提下，每次讀取時所需的解碼操作次數(shù)是決定2種方法讀取速度的最主要因素.

4.6 位翻轉(zhuǎn)減少能力對比

圖8中給出了FEBRE方法與PRES，F(xiàn)lip-Min，F(xiàn)lip-N-Write(FNW)方法在寫入量減少能力上的歸一化對比結(jié)果.此處的寫入量采用每次寫入時的平均翻轉(zhuǎn)位數(shù)來計量.相比于PRES方法，F(xiàn)EBRE方法在每次寫入中，平均減少了5.13%的位翻轉(zhuǎn)數(shù)量；而相比于其他方法，F(xiàn)EBRE方法的優(yōu)勢更加明顯.鑒于FEBRE和所有參與測試的方法所用到的編碼向量數(shù)量是一樣的，因此FEBRE方法在這方面的優(yōu)勢相對于PRES,可以認為是來源于其編碼向量集合中消除了重復(fù)元素；而相對于其他方法，則是來源于其產(chǎn)生的編碼向量的分布更加隨機.

Fig. 8 Normalized comparing result of the average number of flipped bits per write圖8 寫入時平均翻轉(zhuǎn)位數(shù)的歸一化對比

4.7 FEBRE方法的可擴展性

對于FEBRE，PRES和Flip-Min等差分式方法而言，更多的編碼向量雖然會帶來更好的寫入量減少效果，但也將以更高的空間占用作為代價.例如，即使編碼向量為32個，待寫入的數(shù)據(jù)長度為16 b時，任何上述方法的編碼向量集合也將占用512 b的存儲空間.此時，盡管這些方法仍然有效，但此時的空間占用將對存儲系統(tǒng)產(chǎn)生巨大的負擔，因此難以實用.本文僅討論了16個編碼向量的情況，并將對其他情況的討論留做未來工作之一.

5 結(jié) 論

針對相變內(nèi)存寫入壽命有限的缺點，經(jīng)典方法PRES方法可以很好地減少單次寫入中改變的位數(shù)，從而減少總體寫入量.然而，該方法的編碼向量集合中存在大量的重復(fù)元素，而這一缺點會直接影響其寫入減少效果和讀寫速度.本文首先指出了這一未被注意到的問題.之后，通過引入星型生成規(guī)則和廣義編碼方向模式的概念，本文提出的FEBRE方法解決了編碼向量集合中的重復(fù)元素問題.此外，本文還設(shè)計了一種流水化的偽隨機編碼算法，不僅繼承了原始算法的隨機化能力，而且進一步加速了寫入時所需的編碼操作.綜合以上這些因素，F(xiàn)EBRE方法不僅成功地提高了讀寫速度，而且進一步減少了每次寫入時的平均寫入量，因而成為了一種對比目前領(lǐng)先的PRES方法更加先進的差分式寫入減少方法.

[1]Lee B C, Zhou P, Yang J, et al. Phase-change technology and the future of main memory[J]. Micro IEEE, 2010, 30(1): 143-143

[2]Lee B C, Ipek E, Mutlu O, et al. Architecting phase change memory as a scalable dram alternative[J]. ACM SIGARCH Computer Architecture News, 2009, 37(3): 2-13

[3]Qureshi M K, Srinivasan V, Rivers J A. Scalable high performance main memory system using phase change memory technology[C] //Proc of the 36th Annual Int Symp on Computer Architecture. New York: ACM, 2009: 24-33

[4]Qureshi M K, Karidis J, Franceschini M, et al. Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling[C] //Proc of the 42nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2009: 14-23

[5]Yang B D, Lee J E, Kim J S, et al. A low power phase-change random access memory using a data-comparison write scheme[C] //Proc of IEEE Int Symp on Circuits and Systems. Piscataway, NJ: IEEE, 2007: 3014-3017

[6]Cho S, Lee H. Flip-N-Write: A simple deterministic technique to improve PRAM write performance, energy and endurance[C] //Proc of the 42nd Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2009: 347-357

[7]Luo Xiaolu, Liu Duo, Zhong Kan, et al. Enhancing lifetime of NVM-based main memory with bit shifting and flipping[C] //Proc of Int Conf on Embedded and Real-Time Computing Systems and Applications. Piscataway, NJ: IEEE, 2014: 1-7. DOI: 10.1109/RTCSA.2014.6910554

[8]Jacobvitz A N, Calderbank R, Sorin D J. Coset coding to extend the lifetime of memory[C] //Proc of Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2013: 222-233

[9]Seyedzadeh S M, Maddah R, Jones A, et al. PRES: Pseudo-random encoding scheme to increase the bit flip reduction in the memory[C] //Proc of Design Automation Conf. New York: ACM, 2015: 1-6. DOI: 10.1145/2744769.2755440

[10]Seyedzadeh S M, Maddah R, Kline D, et al. Improving bit flip reduction for biased and random data[J]. IEEE Trans on Computers, 2016, 65(11): 3345-3356

Gao Peng, born in 1982. PhD candidate. His main research interests include computer architecture, non-volatile memory.

Wang Dongsheng, born in 1966. PhD, professor, PhD supervisor. His main research interests include computer architecture, distributed system, and non-volatile memory.

Wang Haixia, born in 1977. PhD, associate professor. Her main research interests include computer architecture, network on chip, and memory hierarchy.

Increasing PCM Lifetime by Using Pipelined Pseudo-Random Encoding Algorithm

Gao Peng1,2, Wang Dongsheng2, Wang Haixia2

1(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)2(ResearchInstituteofInformationTechnology,TsinghuaUniversity,Beijing100084)

Phase change memory (PCM) is a promising technique due to its low static power, non-volatility, and density potential. However, the low endurance remains as the key problem to be solved before it can be widely used in practice. Generally, minimizing modified bits in write operation by writing the different bits, is an effective method to extend the lifetime of PCM. But it’s still challenging to reach the minimum without causing significant slowdown of read/write operations. To this end, we propose FEBRE: A fast and efficient bit-flipping reduction technique to extend PCM lifetime. The key idea of our method is to design and use a novel one-to-many parallel mapping before differential write stage. Specifically, FEBRE employs a new data encoding method to generate multiple highly random distributed encoded vectors from one writing data item, which thus increases the possibility of identifying the nearest one to stored data in those vectors. The other contribution of our technique is a pipelined pseudo-random encoding algorithm (PPREA). The new algorithm reduces writing overhead because it is able to accelerate the procedure of the one-to-many mapping. The experiment shows that our technique, compared with PRES, can reduce bit flips by 5.31% on average, and improve the encoding/decoding speed by 2.29x and 45%, respectively.

phase change memory (PCM); differential write; pseudo-random encoding algorithm; coding direction pattern; star-like generation rule

2017-02-14；

2017-04-21

國家重點研發(fā)計劃(2016YFB1000303)；國家自然科學(xué)基金項目(61373025) This work was supported by the National Key Research and Development Plan of China (2016YFB1000303) and the National Natural Science Foundation of China (61373025).

汪東升(wds@tsinghua.edu.cn)

TP333