面向非易失內(nèi)存寫優(yōu)化的重計(jì)算方法

張 銘 華 宇 劉璐榮 胡 蓉 李子怡

(武漢光電國家研究中心(華中科技大學(xué)) 武漢 430074) (華中科技大學(xué)計(jì)算機(jī)學(xué)院 武漢 430074)

隨著大數(shù)據(jù)時(shí)代數(shù)據(jù)規(guī)模的快速增長，數(shù)據(jù)存儲與訪問給內(nèi)存帶來了更高的性能要求.傳統(tǒng)的DRAM技術(shù)因其易失性以及刷新功耗大等問題在系統(tǒng)的可靠性以及能耗等方面會面臨諸多挑戰(zhàn).而非易失存儲器[1](non-volatile memory, NVM)可以按字節(jié)尋址用作持久性內(nèi)存[2]，具有非易失、能耗低以及存儲密度高等優(yōu)點(diǎn)，為構(gòu)建更高效的存儲系統(tǒng)帶來了機(jī)遇，是下一代內(nèi)存的理想選擇.按字節(jié)尋址的非易失存儲器主要包括相變存儲器[3-4](phase change memory, PCM)、阻變存儲器[5](resistive random access memory, RRAM)、磁隨機(jī)存儲器[6](magnetic random access memory, MRAM)以及自旋矩存儲器[7](spin transfer torque random access memory, TT-RAM)等.英特爾公司與鎂光科技公司于2015年公布了非易失存儲技術(shù)3D XPoint[8]，并于2018年發(fā)布了基于3D XPoint的商用非易失DDR4內(nèi)存Optane DC Persistent Memory[9]，可以配合現(xiàn)有的Skylake-SP架構(gòu)Intel Xeon處理器用于數(shù)據(jù)服務(wù)器.隨著硬件技術(shù)日漸成熟，基于NVM的下一代存儲系統(tǒng)也成為了當(dāng)前的研究熱點(diǎn)[10].

然而使用NVM作為內(nèi)存應(yīng)用于計(jì)算機(jī)系統(tǒng)中仍面臨著諸多挑戰(zhàn)，這主要包括2點(diǎn)：一是NVM的寫延遲比DRAM高[11]；二是NVM的擦寫次數(shù)有限，使用壽命比DRAM短[12].因此如何優(yōu)化NVM的寫操作是一個(gè)非常重要的問題.

現(xiàn)有的解決方案從寫暫停、對比寫、翻轉(zhuǎn)寫、減少寫數(shù)據(jù)量以及磨損均衡[13]等角度對NVM的寫操作做了優(yōu)化.由于NVM讀操作的延遲和耗能都低于寫操作，因此Qureshi等人[14]提出了寫取消及寫暫停策略，使得系統(tǒng)可以優(yōu)先處理讀請求以縮短系統(tǒng)響應(yīng)速度.Yang等人[15]利用NVM的字節(jié)尋址特性提出了對比寫的策略，在數(shù)據(jù)更新時(shí)通過對比新舊數(shù)據(jù)只修改發(fā)生變化的比特.Cho等人[16]提出了翻轉(zhuǎn)寫的策略，使用一個(gè)標(biāo)志位記錄翻轉(zhuǎn)操作，當(dāng)修改的數(shù)據(jù)位超過一半時(shí)，翻轉(zhuǎn)標(biāo)志位和未修改的數(shù)據(jù)位，當(dāng)修改的數(shù)據(jù)位不超過一半時(shí)直接寫入修改的數(shù)據(jù)位并保持標(biāo)志位不變，以此保證數(shù)據(jù)更新時(shí)修改的數(shù)據(jù)位不超過一半.Tseng等人[17]使用線性規(guī)劃方法尋求任務(wù)的最佳調(diào)度順序以減少對臟數(shù)據(jù)的寫回，從而達(dá)到減少寫數(shù)據(jù)量的目的.Chen等人[18]使用計(jì)數(shù)器以及基于桶的磨損均衡算法為物理頁維護(hù)一個(gè)空閑頁面和磨損避免頁面以達(dá)到磨損均衡的目的，從而提高NVM的耐久性和使用壽命.

為了解決NVM寫延遲高和寫壽命短的問題，與上述解決方案不同，本文從計(jì)算替換存儲的角度提出了一種基于結(jié)點(diǎn)出度的重計(jì)算方法稱作ROD(re-computation scheme based on the out degree of computing nodes)，ROD方法利用NVM材料讀寫延遲的不對稱性，通過讀取輸入數(shù)據(jù)重新計(jì)算代碼塊的結(jié)果以減少對NVM的寫次數(shù).具體而言，首先按照程序指令間的數(shù)據(jù)依賴關(guān)系在編譯期構(gòu)造數(shù)據(jù)流圖[19](data flow graph, DFG)，DFG中的每個(gè)結(jié)點(diǎn)表示一條程序語句，從輸入開始到輸出結(jié)束，再跟據(jù)指令執(zhí)行周期以及NVM的讀寫延遲對DFG決策出所有的存儲結(jié)點(diǎn)和重計(jì)算結(jié)點(diǎn)，最后根據(jù)重計(jì)算結(jié)點(diǎn)的計(jì)算路徑完成重計(jì)算過程.其中存儲結(jié)點(diǎn)表示該結(jié)點(diǎn)的計(jì)算結(jié)果寫入NVM，需要使用時(shí)直接從內(nèi)存中讀出，重計(jì)算結(jié)點(diǎn)表示該結(jié)點(diǎn)的計(jì)算結(jié)果不寫入NVM，當(dāng)使用時(shí)需要回溯到最近的存儲結(jié)點(diǎn)并將計(jì)算路徑重新執(zhí)行一遍.傳統(tǒng)的存儲主導(dǎo)的方法便是將所有計(jì)算結(jié)果存入內(nèi)存，需要使用時(shí)再從內(nèi)存中取出.一種貪心重計(jì)算的方法是只對當(dāng)前結(jié)點(diǎn)的重計(jì)算開銷和存儲開銷做比對從而作出決策.由于在DFG中結(jié)點(diǎn)的重計(jì)算路徑越長則開銷越大，因此需要適當(dāng)?shù)剡x擇存儲結(jié)點(diǎn)，而結(jié)點(diǎn)的出度決定了數(shù)據(jù)被依賴的程度，出度越高說明結(jié)點(diǎn)被使用的次數(shù)越多，讀開銷或重計(jì)算開銷也就越大，這是貪心方法未考慮到的，因此ROD方法結(jié)合結(jié)點(diǎn)的出度可以做準(zhǔn)確的決策.

本文的主要貢獻(xiàn)包括3個(gè)方面：

1) 提出了基于結(jié)點(diǎn)出度的重計(jì)算方法稱作ROD，從而減少NVM的寫操作，緩解CPU與內(nèi)存之間的IO開銷.

2) 設(shè)計(jì)并實(shí)現(xiàn)ROD方法的3個(gè)組成模塊，分別是數(shù)據(jù)流圖的構(gòu)建、結(jié)點(diǎn)的決策算法以及重計(jì)算路徑的生成.

3) 使用搭載NVMain的Gem5模擬器對ROD方法、貪心重計(jì)算方法以及存儲主導(dǎo)的方法做了性能對比，驗(yàn)證了ROD方法的有效性.

1 研究背景

本節(jié)首先介紹現(xiàn)代CPU與內(nèi)存之間的性能差距，這是重計(jì)算的動機(jī)所在，然后介紹重新計(jì)算的定義和內(nèi)涵，接著描述重計(jì)算路徑圖，最后介紹對程序語句執(zhí)行結(jié)果的重計(jì)算或存儲的權(quán)衡策略.

1.1 CPU與內(nèi)存間性能瓶頸

現(xiàn)代CPU性能比內(nèi)存性能高3個(gè)數(shù)量級[20]，頻繁讀寫內(nèi)存不僅會縮短N(yùn)VM的使用壽命，而且較大的IO延遲會導(dǎo)致CPU空轉(zhuǎn)，從而浪費(fèi)計(jì)算資源并降低系統(tǒng)性能.

在傳統(tǒng)的執(zhí)行方式中，程序的中間計(jì)算結(jié)果寫入內(nèi)存，需要時(shí)再從內(nèi)存中讀出.考慮到CPU與內(nèi)存間的性能瓶頸，重計(jì)算方法通過丟棄部分需要寫入內(nèi)存的計(jì)算結(jié)果，需要時(shí)再按計(jì)算路徑重新計(jì)算出來，以此降低IO的開銷，對于以NVM為內(nèi)存的系統(tǒng)即可減少對內(nèi)存的寫操作，提高NVM的使用壽命.

1.2 定義及研究方向

與重計(jì)算相關(guān)的研究主要可分為2類：1)降低系統(tǒng)訪存次數(shù)；2)系統(tǒng)容錯(cuò)和恢復(fù).

對于第1類研究，重新計(jì)算是指在需要程序的中間計(jì)算結(jié)果時(shí)將其重新計(jì)算出來，以替代將計(jì)算結(jié)果寫入內(nèi)存并在需要時(shí)讀取出來的方案[21].該方案的優(yōu)勢在于可以減少寫NVM的次數(shù)，提高NVM的耐久性并降低IO開銷，但問題在于會帶來額外的計(jì)算開銷.因此需要合理地對計(jì)算結(jié)果做存儲或重計(jì)算的決策，以較少的額外計(jì)算開銷換取較大的寫開銷.

對于第2類研究，重計(jì)算大多應(yīng)用于高性能計(jì)算系統(tǒng)的容錯(cuò)和恢復(fù)中[22]，在應(yīng)用程序運(yùn)行崩潰時(shí)，保存在NVM上的數(shù)據(jù)不會丟失，即可恢復(fù)計(jì)算場景以重新計(jì)算出結(jié)果，因此如何減少保存的數(shù)據(jù)量和加快系統(tǒng)恢復(fù)速度是其主要的研究問題.

這2類研究方向的具體工作將在第4節(jié)“相關(guān)研究工作”做詳細(xì)介紹.本文的研究內(nèi)容是利用重計(jì)算降低系統(tǒng)訪存次數(shù)，以減少對NVM的寫操作.

1.3 重計(jì)算路徑

由于重計(jì)算不保存部分計(jì)算結(jié)果，因此需要確定重新計(jì)算執(zhí)行的指令及其順序，來保證程序運(yùn)行的正確性.將程序按數(shù)據(jù)依賴劃分為代碼段，為了方便描述，使用生產(chǎn)者與消費(fèi)者的概念，如圖1所示，代碼段G需要直接使用代碼段F的運(yùn)行結(jié)果，稱F是G的直接生產(chǎn)者，也即G是F的直接消費(fèi)者.若代碼段F的計(jì)算結(jié)果沒有保存至NVM，那么在執(zhí)行代碼段G時(shí)需要重新運(yùn)行代碼段F以產(chǎn)生G的輸入數(shù)據(jù).若F的直接生產(chǎn)者D的計(jì)算結(jié)果沒有保存，那么需要遞歸回溯到最近的保存了計(jì)算結(jié)果的生產(chǎn)者.由此可知，將耗能較高的讀寫內(nèi)存操作替換為計(jì)算指令，便可得到重計(jì)算路徑，它是一條沿著數(shù)據(jù)流遞歸回溯的路徑.

Fig. 1 The re-computation path圖1 重計(jì)算路徑圖

圖1展示了一個(gè)具有4層結(jié)點(diǎn)的重計(jì)算路徑圖，這是一棵倒長的樹.其中A，B，C表示程序的輸入，其結(jié)果需要寫入內(nèi)存；D，E，F(xiàn)為中間計(jì)算結(jié)點(diǎn)，不保存它們的計(jì)算結(jié)果；G為程序輸出結(jié)點(diǎn).第1層的結(jié)點(diǎn)對應(yīng)于根結(jié)點(diǎn)的直接生產(chǎn)者，從第2層往上，第i層的結(jié)點(diǎn)對應(yīng)于第i+1層結(jié)點(diǎn)的直接消費(fèi)者.每個(gè)結(jié)點(diǎn)的入度表示其直接生產(chǎn)者的個(gè)數(shù)，出度表示其直接消費(fèi)者的個(gè)數(shù).由于代碼段D，E，F(xiàn)的計(jì)算結(jié)果沒有保存，因此在計(jì)算G時(shí)，需要重新計(jì)算D，E，F(xiàn)的結(jié)果，故需要沿著數(shù)據(jù)流回溯到結(jié)點(diǎn)A,B,C，從內(nèi)存中讀取數(shù)據(jù)重新計(jì)算.

1.4 權(quán)衡策略

重計(jì)算雖然能減少對NVM寫的次數(shù)，但如果對于代碼段執(zhí)行結(jié)果的存儲或重計(jì)算的決策不佳，可能會使得重計(jì)算路徑過長導(dǎo)致計(jì)算開銷過大，或者存儲結(jié)點(diǎn)過多導(dǎo)致寫NVM開銷增大.本節(jié)介紹對代碼段執(zhí)行結(jié)果的存儲或重計(jì)算的權(quán)衡策略.

考慮圖2所示的2種重計(jì)算路徑形態(tài)，圖2中灰色圓形表示程序的輸入，其結(jié)果保存到內(nèi)存，結(jié)點(diǎn)G表示程序的輸出.圖2(a)的結(jié)點(diǎn)層數(shù)較多，只保存輸入結(jié)點(diǎn)，會使得后續(xù)結(jié)點(diǎn)的重計(jì)算路徑過長，需要遞歸回溯執(zhí)行的指令過多，更優(yōu)的策略應(yīng)適當(dāng)存儲中間的計(jì)算結(jié)果，避免重計(jì)算開銷過大.而圖2(b)的結(jié)點(diǎn)層數(shù)較少，計(jì)算路徑短，將中間計(jì)算結(jié)果都存入NVM必然會造成大量的寫開銷，因此對中間結(jié)點(diǎn)做重計(jì)算的優(yōu)勢能更好地體現(xiàn)出來.

Fig. 2 Different forms of re-computation path圖2 不同形態(tài)的重計(jì)算路徑

Kandemir 等人[23]提出了貪心的決策方法，即只考慮當(dāng)前的計(jì)算結(jié)果，當(dāng)保存到內(nèi)存的開銷小于將其重新計(jì)算出來的開銷，即使用存儲策略，否則使用重計(jì)算策略.但是貪心方法忽略了數(shù)據(jù)的使用次數(shù)，當(dāng)一個(gè)數(shù)據(jù)在短期內(nèi)被重復(fù)使用時(shí)，選擇保存該數(shù)據(jù)的結(jié)果能獲得更大的收益.

2 基于結(jié)點(diǎn)出度的重計(jì)算方法

為了減少對NVM的寫操作，提出基于結(jié)點(diǎn)出度的重計(jì)算方法ROD，其考慮指令間數(shù)據(jù)依賴的程度，對計(jì)算結(jié)果做出合理的存儲或重計(jì)算的決策.本節(jié)先介紹ROD方法的總體設(shè)計(jì)，再介紹各個(gè)組成模塊的具體實(shí)現(xiàn).

2.1 總體設(shè)計(jì)

本節(jié)介紹ROD方法的總體流程設(shè)計(jì)，共有3個(gè)主要的功能模塊，分別是數(shù)據(jù)流圖的生成模塊、結(jié)點(diǎn)決策模塊以及重計(jì)算路徑的生成模塊，如圖3所示.

Fig. 3 The process design of ROD scheme圖3 ROD方法總體流程設(shè)計(jì)

ROD方法通過數(shù)據(jù)流對程序按語句劃分結(jié)點(diǎn)，一條語句即為一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)之間的箭頭指向關(guān)系即表示生產(chǎn)者結(jié)點(diǎn)與消費(fèi)者結(jié)點(diǎn)之間存在數(shù)據(jù)依賴.在本方法中，數(shù)據(jù)分為可重計(jì)算數(shù)據(jù)與非可重計(jì)算數(shù)據(jù)，程序的輸入數(shù)據(jù)屬于非可重計(jì)算數(shù)據(jù)，除了輸入結(jié)點(diǎn)，中間結(jié)點(diǎn)的重計(jì)算開銷大于存儲開銷的數(shù)據(jù)也屬于非可重計(jì)算數(shù)據(jù)，其他數(shù)據(jù)則屬于可重計(jì)算數(shù)據(jù).產(chǎn)生非可重計(jì)算數(shù)據(jù)的結(jié)點(diǎn)稱為存儲結(jié)點(diǎn)，其計(jì)算結(jié)果需寫入到NVM中.產(chǎn)生可重計(jì)算數(shù)據(jù)的結(jié)點(diǎn)稱為重計(jì)算結(jié)點(diǎn)，其計(jì)算結(jié)果被使用到時(shí)需按照數(shù)據(jù)依賴關(guān)系回溯到最近的存儲結(jié)點(diǎn)，將其值讀出后按計(jì)算路徑重新計(jì)算出結(jié)果.

為了得到結(jié)點(diǎn)之間的數(shù)據(jù)依賴關(guān)系必須先構(gòu)造數(shù)據(jù)流圖.使用LLVM[24]工具對源程序生成中間表示(intermediate representation, IR)指令，即可根據(jù)IR表示中的loadstore指令找到對應(yīng)的結(jié)點(diǎn)，再使用詞法分析的方式對這些結(jié)點(diǎn)提取對應(yīng)的操作數(shù)，最后依賴操作數(shù)之間的讀寫依賴構(gòu)造數(shù)據(jù)流圖，如圖4所示，圖中每個(gè)結(jié)點(diǎn)表示一條語句，結(jié)點(diǎn)Vi指向結(jié)點(diǎn)Vj表示第j條語句的執(zhí)行依賴第i條語句的計(jì)算結(jié)果.

Fig. 4 Transform the source code to the data flow graph圖4 將源程序轉(zhuǎn)化為數(shù)據(jù)流圖

在得到數(shù)據(jù)流圖之后，便可以計(jì)算結(jié)點(diǎn)的存儲開銷和重計(jì)算開銷來確定存儲結(jié)點(diǎn)和重計(jì)算結(jié)點(diǎn).ROD方法在決策的過程中綜合考慮了結(jié)點(diǎn)出度(即直接消費(fèi)者個(gè)數(shù))的影響，結(jié)點(diǎn)的出度越大，說明其所在的重計(jì)算路徑越多，因此保存其計(jì)算結(jié)果往往會有利于其他結(jié)點(diǎn)的重計(jì)算過程.

例如，經(jīng)過決策后將圖4的數(shù)據(jù)流圖轉(zhuǎn)換為決策圖，其中S結(jié)點(diǎn)表示存儲結(jié)點(diǎn)，R結(jié)點(diǎn)表示重計(jì)算結(jié)點(diǎn)，如圖5所示，可以看出程序的輸入和輸出結(jié)點(diǎn)都被標(biāo)為存儲結(jié)點(diǎn)，其他中間計(jì)算結(jié)果均可通過重新計(jì)算得到，比如計(jì)算結(jié)點(diǎn)V5需要重新計(jì)算結(jié)點(diǎn)V3和結(jié)點(diǎn)V4，而計(jì)算結(jié)點(diǎn)V6則需要重新計(jì)算結(jié)點(diǎn)V3、結(jié)點(diǎn)V4和結(jié)點(diǎn)V5.

Fig. 5 The decision of the store node and the re-computation node圖5 存儲結(jié)點(diǎn)和重計(jì)算結(jié)點(diǎn)的決策

通過決策圖5可以回溯每個(gè)重計(jì)算結(jié)點(diǎn)的重計(jì)算路徑，重計(jì)算路徑應(yīng)從重計(jì)算結(jié)點(diǎn)開始一直回溯到距離它最近的存儲結(jié)點(diǎn)為止，以此為每個(gè)重計(jì)算任務(wù)生成重計(jì)算函數(shù).由于本方法是在編譯期確定重計(jì)算結(jié)點(diǎn)，在所有重計(jì)算函數(shù)確定后，便可以運(yùn)行程序，在遇到重計(jì)算結(jié)點(diǎn)時(shí)進(jìn)入相應(yīng)的重計(jì)算函數(shù)得到計(jì)算結(jié)果即可，因此程序?qū)嶋H執(zhí)行的指令數(shù)量也相應(yīng)地增多了.

2.2節(jié)將詳細(xì)介紹數(shù)據(jù)流圖生成的實(shí)現(xiàn)，2.3節(jié)將詳細(xì)介紹ROD方法中對于存儲或重計(jì)算選擇策略的實(shí)現(xiàn)細(xì)節(jié)，2.4節(jié)將對如何尋找重計(jì)算路徑并生成重計(jì)算函數(shù)做詳細(xì)的介紹.

2.2 生成數(shù)據(jù)流圖

本節(jié)將介紹生成數(shù)據(jù)流圖的實(shí)現(xiàn)細(xì)節(jié).通過使用LLVM工具鏈中Clang編譯器為源程序生成IR指令，通過分析IR中的loadstore指令在源程序中找到對應(yīng)的讀寫內(nèi)存的語句，其中l(wèi)oadstore指令的具體含義表示如下：

1) load指令.讀內(nèi)存，需要記錄讀取的地址與存入的操作數(shù).

2) store指令.寫內(nèi)存，需要記錄被保存的數(shù)據(jù)與寫入的地址.

對含load和store操作的IR指令舉例如下：

%p=alloca i32;

store i32 8,i32*%p;

%v=load i32,i32*%p;

首先向內(nèi)存申請一個(gè)32 b的整型空間p，然后將32 b的數(shù)8寫入地址p處，再從內(nèi)存中讀出地址p處的值，將其存入v中，此時(shí)v的值為8.

在得到所有讀寫內(nèi)存的程序語句之后便可以利用詞法分析的方式提取左右操作數(shù)存入每個(gè)結(jié)點(diǎn)中.在這之后便可對每條語句的左操作數(shù)遍歷匹配所有在其之后語句的右操作數(shù)，匹配成功就說明語句間有數(shù)據(jù)讀寫關(guān)系，將二者連接起來便構(gòu)成數(shù)據(jù)流圖的邊.這個(gè)過程中要考慮到操作數(shù)被覆蓋寫(overwrite)的情況，即結(jié)點(diǎn)A和結(jié)點(diǎn)B含有相同作用域的左操作數(shù)Lop，且A的語句順序在B之前，那么在遍歷到B時(shí)，對A的Lop的匹配任務(wù)應(yīng)立即停止，因?yàn)長op將被B的計(jì)算結(jié)果寫覆蓋，B之后所有用到Lop的結(jié)點(diǎn)將不再依賴A.在得到所有的結(jié)點(diǎn)和邊之后，便可通過構(gòu)造鄰接表(adjacency list)的方式構(gòu)造數(shù)據(jù)流圖，用于決定結(jié)點(diǎn)的存儲或重計(jì)算的策略.

2.3 存儲與重計(jì)算策略

介紹ROD方法所使用的結(jié)點(diǎn)存儲或重計(jì)算決策模型的設(shè)計(jì)與實(shí)現(xiàn)細(xì)節(jié).使用Vi表示每個(gè)結(jié)點(diǎn)，定義寫內(nèi)存開銷為Mw(Vi)，讀內(nèi)存開銷為Mr(Vi).使用0-1變量αi來決定是否將結(jié)點(diǎn)Vi的計(jì)算結(jié)果存入內(nèi)存，如式(1)所示：

(1)

定義每個(gè)結(jié)點(diǎn)的生產(chǎn)開銷為P(Vi)，如式(2)所示，分為計(jì)算開銷C(Vi)和保存計(jì)算結(jié)果的開銷Mw(Vi)這2部分.

P(Vi)=C(Vi)+αiMw(Vi)，

(2)

其中計(jì)算開銷C(Vi)的定義如式(3)所示，包括結(jié)點(diǎn)計(jì)算自身結(jié)果所產(chǎn)生的開銷o(Vi)以及訪問其所有直接生產(chǎn)者的開銷D(Vj).

(3)

結(jié)點(diǎn)數(shù)據(jù)要么從內(nèi)存中讀出，要么通過計(jì)算產(chǎn)生，因此結(jié)點(diǎn)的直接生產(chǎn)者開銷D(Vj)如式(4)所示：

D(Vj)=αjMr(Vj)+(1-αj)C(Vj)，

(4)

當(dāng)αj=1時(shí)，說明其生產(chǎn)者結(jié)點(diǎn)為存儲結(jié)點(diǎn)，只存在讀內(nèi)存的開銷Mr(Vj)，當(dāng)αj=0時(shí)，說明其生產(chǎn)者結(jié)點(diǎn)為重計(jì)算結(jié)點(diǎn)，因此需要使用式(3)遞歸計(jì)算其開銷.由此可以看出重計(jì)算路徑越長，其遞歸層數(shù)越深，重計(jì)算開銷也就越大.

1.4節(jié)介紹了一種貪心的決策方法，即只根據(jù)當(dāng)前結(jié)點(diǎn)的重計(jì)算開銷和存儲開銷做決策，不考慮所做的決策對其消費(fèi)者產(chǎn)生的讀開銷，即：

1) 若當(dāng)前結(jié)點(diǎn)Vi采用存儲策略，則將計(jì)算結(jié)果保存到內(nèi)存，需要用到時(shí)直接從內(nèi)存中讀取，產(chǎn)生的開銷為Mw(Vi)；

2) 若當(dāng)前結(jié)點(diǎn)Vi采用重計(jì)算策略，則不保存計(jì)算結(jié)果，需要時(shí)重新計(jì)算產(chǎn)生，產(chǎn)生的開銷為C(Vi).

由于程序的輸入結(jié)點(diǎn)不可重計(jì)算，因此輸入結(jié)點(diǎn)均采用存儲的方案，其余結(jié)點(diǎn)則需要比較Mw(Vi)與C(Vi)之間的大小關(guān)系，Mw(Vi)

為此提出一種新型的決策模型.記每個(gè)結(jié)點(diǎn)Vi的出度為φi，那么該結(jié)點(diǎn)若使用存儲策略，則其計(jì)算結(jié)果將被讀φi次，若使用重計(jì)算策略，則需要被重計(jì)算φi次.因此結(jié)點(diǎn)的存儲開銷WS和重計(jì)算開銷WR如式(5)所示：

(5)

其中C(Vi)的定義同式(3)，當(dāng)WS

算法1.結(jié)點(diǎn)存儲或重計(jì)算的決策算法.

輸入：程序的數(shù)據(jù)流圖DFG；

輸出：存儲結(jié)點(diǎn)集合A和重計(jì)算結(jié)點(diǎn)集合B.

①A←?,B←?;

② for each nodeNin DFG do

③ ifN是輸入結(jié)點(diǎn)then

④ addNto setA;

⑤ else

⑥P←producer ofN;

⑦φ←the out degree ofN;

⑧RCost←0;*RCost為重計(jì)算開銷*

⑨ whilePis not NULL do

⑩ addP’s cost toRCost;

算法1的行③～⑤表示存儲所有的輸入結(jié)點(diǎn)，第⑥行的P表示結(jié)點(diǎn)N的一個(gè)生產(chǎn)者，由于采用鄰接表法表示數(shù)據(jù)流圖，因此結(jié)點(diǎn)N的其他生產(chǎn)者均可以由P訪問到.行⑨～表示累加結(jié)點(diǎn)N的所有生產(chǎn)者的開銷，得到再加上結(jié)點(diǎn)N自身的計(jì)算開銷o(N)，最后利用式(3)(5)即可得到結(jié)點(diǎn)N的重計(jì)算開銷RCost.在決策時(shí)認(rèn)為每條IR指令運(yùn)行的CPU時(shí)鐘周期數(shù)為1，通過IR指令的數(shù)量與C程序語句的數(shù)量之比即可確定計(jì)算每個(gè)結(jié)點(diǎn)的時(shí)鐘周期數(shù).行通過式(5)計(jì)算結(jié)點(diǎn)N的存儲開銷，在實(shí)現(xiàn)中采用的是PCM的讀寫延遲.行～通過比較RCost與SCost來決定結(jié)點(diǎn)N的計(jì)算結(jié)果是存儲還是重計(jì)算.

為了更好地理解重計(jì)算過程，對不同的存儲與重計(jì)算策略進(jìn)行舉例說明.圖6是包含7個(gè)結(jié)點(diǎn)的數(shù)據(jù)流圖，共有3個(gè)輸入結(jié)點(diǎn)、1個(gè)輸出結(jié)點(diǎn)以及3個(gè)中間結(jié)點(diǎn)，其中圖6(a)表示只存儲輸入結(jié)點(diǎn)的數(shù)據(jù)，記為決策(a).圖6(b)表示不僅存儲輸入結(jié)點(diǎn)的數(shù)據(jù)，還存儲中間結(jié)點(diǎn)V4的計(jì)算結(jié)果，記為決策(b).

Fig. 6 Different decisions on store or re-computation圖6 關(guān)于結(jié)點(diǎn)存儲或重計(jì)算的不同決策

在傳統(tǒng)的執(zhí)行流程中需要將7個(gè)結(jié)點(diǎn)的計(jì)算結(jié)果都寫入NVM，但決策(a)中只存儲結(jié)點(diǎn)V1～V3，決策(b)中只存儲結(jié)點(diǎn)V1～V4.決策(a)在執(zhí)行過程中對每個(gè)結(jié)點(diǎn)所產(chǎn)生的操作如表1所示：

Table 1 Operations on Each Node of Decision (a)表1 決策(a)對每個(gè)結(jié)點(diǎn)的操作

從表1可以看到?jīng)Q策(a)產(chǎn)生了10次讀NVM、3次寫NVM、5次重計(jì)算，相比較于傳統(tǒng)執(zhí)行流程減少了4次寫NVM的操作.決策(b)在執(zhí)行過程中對每個(gè)結(jié)點(diǎn)所產(chǎn)生的操作如表2所示:

Table 2 Operations on Each Node of Decision (b)表2 決策(b)對每個(gè)結(jié)點(diǎn)的操作

從表2可以看到?jīng)Q策(b)產(chǎn)生了7次讀NVM、4次寫NVM、2次重計(jì)算，相比較于傳統(tǒng)執(zhí)行流程減少了3次寫NVM的操作.

這2種決策方案相較于傳統(tǒng)的執(zhí)行流程都可以減少對NVM的寫操作，雖然決策(a)比決策(b)少了1次寫操作，但卻多出了3次讀操作開銷和2次重計(jì)算開銷.由此可以看出不同的決策方案即使相似，也可以對系統(tǒng)性能產(chǎn)生截然不同的影響.

2.4 重計(jì)算路徑的生成

通過2.3節(jié)的結(jié)點(diǎn)決策算法得到?jīng)Q策圖后，下一步便是從決策圖中尋找重計(jì)算路徑，對此部分做詳細(xì)介紹.

由于重計(jì)算結(jié)點(diǎn)并不保存計(jì)算結(jié)果，因此需要從其生產(chǎn)者結(jié)點(diǎn)開始回溯到最近的存儲結(jié)點(diǎn)，從NVM中讀取相應(yīng)的值，再從存儲結(jié)點(diǎn)開始順著回溯的路徑重新計(jì)算出所需的結(jié)果，這條回溯的路徑便是重計(jì)算路徑，本文通過構(gòu)造重計(jì)算函數(shù)來實(shí)現(xiàn)重計(jì)算路徑.

第1步.為了找到回溯的路徑，需要記錄每個(gè)重計(jì)算結(jié)點(diǎn)的直接生產(chǎn)者，通過逐級查找的方式找路徑.為了達(dá)到這個(gè)目的，需要在構(gòu)造數(shù)據(jù)流圖時(shí)通過結(jié)點(diǎn)鏈表記錄每個(gè)結(jié)點(diǎn)指向的所有生產(chǎn)者結(jié)點(diǎn)，在經(jīng)過ROD方法的決策之后，便可以得到所有的重計(jì)算結(jié)點(diǎn)及其直接生產(chǎn)者結(jié)點(diǎn)的關(guān)系表，進(jìn)而找到重計(jì)算路徑.例如，對于圖4的源代碼及圖5的決策結(jié)果，其重計(jì)算結(jié)點(diǎn)及重計(jì)算路徑如表3所示：

Table 3 Re-computation Nodes and TheirRe-computation Paths表3 重計(jì)算結(jié)點(diǎn)及其重計(jì)算路徑

ROD方法采用深度優(yōu)先全路徑遍歷的方式尋找重計(jì)算路徑.對于結(jié)點(diǎn)V3，其直接生產(chǎn)者為V1，但V1是存儲結(jié)點(diǎn)，沒有直接生產(chǎn)者，因此重計(jì)算V3的路徑為V3→V1.同理可得結(jié)點(diǎn)V4的重計(jì)算路徑為V4→V2，對于結(jié)點(diǎn)V5，其直接生產(chǎn)者V3和V4均可在表3中找到，需要對V3和V4做遞歸遍歷，因此其路徑遍歷的結(jié)果為V5→V3→V1和V5→V4→V2.

第2步.在找到每個(gè)重計(jì)算結(jié)點(diǎn)的重計(jì)算路徑之后，需要實(shí)現(xiàn)重計(jì)算這個(gè)過程，因此需要構(gòu)造重計(jì)算函數(shù)，構(gòu)造重計(jì)算函數(shù)的過程實(shí)質(zhì)上就是根據(jù)重計(jì)算路徑做遞歸計(jì)算的過程.例如，對于上述的重計(jì)算結(jié)點(diǎn)V3，V4，V5，它們的重計(jì)算函數(shù)rec_x3，rec_x4，rec_x5如圖7所示：

intrec_x3(intx1){

returnx1+4;

}

intrec_x4(intx2){

returnx2×2;

}

intrec_x5(intx1,intx2){

returnrec_x3(x1)-rec_x4(x2);

}

int main(){

intx1=1;

intx2=2;

intx3=x1+4;

intx4=x2×2;

intx5=rec_x3(x1)-rec_x4(x2);

intx6=rec_x5(x1,x2)+8;

}

Fig. 7Theimplementationofre-computationfunctions
圖7 重計(jì)算函數(shù)的實(shí)現(xiàn)

重計(jì)算方法雖然具有減少寫NVM次數(shù)的優(yōu)點(diǎn)，但也會有計(jì)算開銷大的缺點(diǎn)，因此在實(shí)際的決策過程中，要充分考慮到NVM材料的讀寫開銷與指令的執(zhí)行開銷，選擇保存出度較大的結(jié)點(diǎn)的計(jì)算結(jié)果可以對后續(xù)結(jié)點(diǎn)的重計(jì)算過程更有利，這也是ROD方法的核心決策觀點(diǎn).

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

在實(shí)現(xiàn)數(shù)據(jù)流圖的生成、結(jié)點(diǎn)決策算法以及重計(jì)算路徑的生成等模塊之后，使用Gem5模擬器對比了ROD方法、存儲主導(dǎo)方法和貪心方法的性能.

3.1 實(shí)驗(yàn)環(huán)境

在Ubuntu操作系統(tǒng)上使用LLVM套件，C++語言以及g++編譯器完成各功能模塊的開發(fā)部分，各開發(fā)工具的版本號如表4所示：

Table 4 The Version Configurations of Development Tools表4 開發(fā)工具的版本配置

完成開發(fā)后使用Gem5[25]模擬器對各方法做性能評測.Gem5模擬器用于計(jì)算機(jī)系統(tǒng)架構(gòu)的相關(guān)研究，包括系統(tǒng)級架構(gòu)和處理器微架構(gòu).為了模擬非易失內(nèi)存的讀寫延遲，使用NVMain[26]作為插件配合Gem5做模擬，NVMain是一個(gè)體系結(jié)構(gòu)級的非易失內(nèi)存模擬器，可以準(zhǔn)確地模擬內(nèi)存系統(tǒng)的時(shí)序和能耗.Gem5實(shí)現(xiàn)了x86指令集中的clflush[27]指令和mfence[28]指令，可以利用這些指令將緩存行的數(shù)據(jù)有序的刷回NVM中，Gem5模擬的系統(tǒng)配置如表5所示，其中NVMain的配置與Choi等人[29]提出的PCM配置相同，使用NVMain內(nèi)置的PCM_ISSCC_2012_4GB.config即可，其中PCM的頻率為500 MHz，讀延遲為120 ns，寫延遲為150 ns.

實(shí)驗(yàn)采用的測試集為powerstone benchmark[30]，它包含一系列嵌入式和可移植的應(yīng)用程序，包括分頁、自動控制、信號處理以及圖像處理等方面，程序中數(shù)據(jù)依賴關(guān)系明顯，具有不同的訪存特征.實(shí)驗(yàn)選取了powerstone benchmark部分測試程序，各測試程序的描述[30]如表6所示.

Table 5 The Configurations Parameters of Gem5表5 Gem5配置參數(shù)

Table 6 The Description of Benchmark表6 Benchmark各程序描述

為驗(yàn)證ROD方法的有效性，對比了傳統(tǒng)的無重計(jì)算的存儲主導(dǎo)方法和1.4節(jié)所描述的貪心方法，并測試在不同PCM讀寫延遲下3種方法的運(yùn)行耗時(shí).

3.2 實(shí)驗(yàn)結(jié)果

1) 測試不同程序按數(shù)據(jù)依賴劃分出的結(jié)點(diǎn)數(shù)，包括輸入結(jié)點(diǎn)數(shù)和非輸入結(jié)點(diǎn)數(shù).實(shí)驗(yàn)中提取了每個(gè)測試程序的所有賦值語句，每條賦值語句為一個(gè)結(jié)點(diǎn)，賦值語句之間存在典型的數(shù)據(jù)依賴關(guān)系.賦值語句中不可被重計(jì)算的屬于輸入結(jié)點(diǎn)，其他可以被重計(jì)算的屬于非輸入結(jié)點(diǎn).測試結(jié)果如圖8所示.

分析上述實(shí)驗(yàn)結(jié)果，除了g3fax和qurt，不同應(yīng)用程序的非輸入結(jié)點(diǎn)數(shù)較多，平均占比約為65%，由于只有非輸入結(jié)點(diǎn)才可以被重計(jì)算，因此程序的輸入結(jié)點(diǎn)越少，臨時(shí)的存儲開銷就越少，重計(jì)算方法的多算少讀的優(yōu)勢就會越明顯.

Fig. 8 The number of input nodes and non-input nodes of different programs圖8 不同測試程序的輸入結(jié)點(diǎn)數(shù)和非輸入結(jié)點(diǎn)數(shù)

2) 測試ROD方法對結(jié)點(diǎn)的決策結(jié)果.由于程序輸出結(jié)點(diǎn)的計(jì)算結(jié)果一般會被寫入NVM，因此每個(gè)程序的存儲結(jié)點(diǎn)數(shù)會比輸入結(jié)點(diǎn)數(shù)多.ROD方法通過結(jié)點(diǎn)的出度權(quán)衡讀開銷和重計(jì)算開銷，其決策結(jié)果如圖9所示:

Fig. 11 The performance comparisons among the ROD scheme, the greedy and the store-only schemes圖11 ROD方法、貪心方法和存儲主導(dǎo)方法之間的性能對比

分析上述實(shí)驗(yàn)結(jié)果，g3fax的重計(jì)算結(jié)點(diǎn)數(shù)較少，占比總結(jié)點(diǎn)數(shù)的12.5%，所有程序的重計(jì)算結(jié)點(diǎn)數(shù)占比平均為44.3%，最高為68.5%.這也說明了使用ROD方法最多能減少程序68.5%的寫NVM操作，這一方面可以減少IO帶來的延遲，另一方面也能提高NVM的壽命.

3) 測試貪心方法對結(jié)點(diǎn)的決策結(jié)果，結(jié)果如圖10所示:

Fig. 10 The decision result of the greedy scheme圖10 貪心方法的決策結(jié)果

分析上述實(shí)驗(yàn)結(jié)果，g3fax的重計(jì)算結(jié)點(diǎn)數(shù)較少，占比總結(jié)點(diǎn)數(shù)的10.4%，所有程序的重計(jì)算結(jié)點(diǎn)數(shù)占比平均為39.8%，最高為57.1%，存儲結(jié)點(diǎn)數(shù)平均比ROD方法增多了4.5%.雖然貪心方法也能減少對NVM的寫操作，但從結(jié)果看ROD方法更優(yōu).

從圖10可以看出,經(jīng)過貪心方法決策出存儲結(jié)點(diǎn)的數(shù)量和ROD方法的決策結(jié)果相近.但其實(shí)對選擇哪些結(jié)點(diǎn)做存儲，二者有著不同的結(jié)果.比如對于程序engine，ROD方法和貪心方法分別存儲了20個(gè)和21個(gè)結(jié)點(diǎn)的計(jì)算結(jié)果，但ROD方法存儲了4個(gè)貪心方法未存儲的結(jié)點(diǎn)，而貪心方法存儲了3個(gè)ROD方法未存儲的結(jié)點(diǎn).

4) 測試ROD方法、貪心方法以及存儲主導(dǎo)方法的性能.三者數(shù)據(jù)流圖的生成算法相同，ROD方法和貪心方法的重計(jì)算路徑生成算法相同，存儲主導(dǎo)的方法將每個(gè)結(jié)點(diǎn)的計(jì)算結(jié)果都存儲到NVM，無重計(jì)算路徑.Gem5中使用ticks數(shù)作為程序的運(yùn)行耗時(shí)，通過運(yùn)行后的統(tǒng)計(jì)信息可知1 000 ticks為1個(gè)CPU時(shí)鐘周期.使用3種方法的程序運(yùn)行耗時(shí)結(jié)果如圖11(a)所示.以存儲主導(dǎo)方法為基準(zhǔn)，對程序運(yùn)行耗時(shí)做歸一化處理，結(jié)果如圖11(b)所示.

分析上述實(shí)驗(yàn)結(jié)果，使用式(6)計(jì)算ROD方法相對于貪心方法的性能提升.

(6)

結(jié)果顯示ROD方法的運(yùn)行耗時(shí)比存儲主導(dǎo)的方法平均減少28.1%(最高68.6%)，比貪心重計(jì)算的方法平均減少9.3%(最高19.4%).

從圖11可知由于g3fax程序的輸入結(jié)點(diǎn)占比過多，導(dǎo)致其存儲開銷大，雖然非輸入結(jié)點(diǎn)占比少，但重計(jì)算仍可以有效減少IO開銷.由于fir程序和qurt程序的指令數(shù)較少，運(yùn)行時(shí)間短，因此在3種方法下ticks數(shù)相差不大.從圖9可知bcnt程序的重計(jì)算結(jié)點(diǎn)數(shù)是其存儲結(jié)點(diǎn)數(shù)的2倍，但重計(jì)算方法的性能相比于存儲主導(dǎo)方法的性能只提升了19.5%左右.分析其源程序可知，所有重計(jì)算結(jié)點(diǎn)均在主循環(huán)內(nèi)，且循環(huán)次數(shù)為256，因此對于重計(jì)算路徑較長的結(jié)點(diǎn)而言是不利的，這樣的路徑需要被循環(huán)計(jì)算256次，因此對于bcnt程序而言，重計(jì)算所帶來的收益不是很明顯.

5) 測試在不同的PCM寫延遲下，ROD方法、貪心方法以及存儲主導(dǎo)方法的運(yùn)行耗時(shí).圖9～11展示了在PCM讀延遲120 ns，寫延遲150 ns，記為延遲A(latencyA)情況下的實(shí)驗(yàn)結(jié)果.為了進(jìn)一步探究寫延遲對重計(jì)算方法的影響，根據(jù)Kim等人[31]關(guān)于PCM延遲的工作選取了另外一組延遲，其中讀延遲仍為120 ns，寫延遲設(shè)置為338 ns，記為延遲B(latencyB).

如2.3節(jié)所述，PCM的寫延遲會影響結(jié)點(diǎn)的存儲開銷或重計(jì)算開銷，因此對于不同的PCM寫延遲，ROD方法和貪心方法對結(jié)點(diǎn)的存儲或重計(jì)算策略均有著不同的選擇.測試在不同寫延遲下，程序使用3種方法的運(yùn)行耗時(shí)，實(shí)驗(yàn)結(jié)果如圖12所示：

Fig. 12 The performance comparisons between different latencies with the ROD scheme, the greedy and the store-only schemes 圖12 不同延遲下使用ROD方法、貪心方法和存儲 主導(dǎo)方法的性能對比

分析上述實(shí)驗(yàn)結(jié)果，對于ROD方法、貪心方法和存儲主導(dǎo)方法，程序使用延遲B的運(yùn)行耗時(shí)比使用延遲A的運(yùn)行耗時(shí)分別平均增加了32.1%，31.6%，40.8%.由于存儲主導(dǎo)方法沒有使用重計(jì)算以減少寫次數(shù)，因此其運(yùn)行耗時(shí)增加的幅度最大.

在使用延遲B的情況下，各測試程序使用ROD方法、貪心方法與存儲主導(dǎo)方法的運(yùn)行耗時(shí)結(jié)果如圖13(a)所示.以存儲主導(dǎo)方法為基準(zhǔn)，對程序運(yùn)行耗時(shí)做歸一化處理，結(jié)果如圖13(b)所示.

Fig. 13 The performance comparisons among the ROD scheme, the greedy and the store-only schemes圖13 ROD方法、貪心方法和存儲主導(dǎo)方法之間的性能對比

上述實(shí)驗(yàn)結(jié)果顯示ROD方法的運(yùn)行耗時(shí)比存儲主導(dǎo)的方法平均減少31.3%(使用延遲A為28.1%)，比貪心重計(jì)算的方法平均減少10.7%(使用延遲A為9.3%).與延遲A相比，延遲 B中NVM的寫延遲更高，因此ROD方法通過減少寫操作，在使用延遲B的情況下性能提升也更大.

6) 實(shí)驗(yàn)總結(jié).以上實(shí)驗(yàn)結(jié)果驗(yàn)證了ROD方法的有效性，并說明了重計(jì)算“以計(jì)算換存儲”的方式可以有效減少對NVM的寫操作，進(jìn)而提升程序的運(yùn)行效率，同時(shí)也應(yīng)當(dāng)對結(jié)點(diǎn)做出合理的決策以避免重計(jì)算路徑過長導(dǎo)致計(jì)算開銷過大的缺點(diǎn).

3.3 實(shí)驗(yàn)細(xì)節(jié)

實(shí)驗(yàn)中，在編譯期根據(jù)決策模型對結(jié)點(diǎn)做靜態(tài)決策，以確定需要重計(jì)算的數(shù)據(jù).因此編譯期的開銷在時(shí)間和空間上包括數(shù)據(jù)流圖的構(gòu)造開銷、結(jié)點(diǎn)的決策計(jì)算開銷和生成重計(jì)算函數(shù)的開銷.

由于是靜態(tài)決策，無法得知程序運(yùn)行時(shí)CPU緩存的狀態(tài)，因此在結(jié)點(diǎn)決策時(shí)不考慮CPU緩存對數(shù)據(jù)loadstore的影響，load操作默認(rèn)為從NVM中讀取數(shù)據(jù)，store操作默認(rèn)為向NVM中寫數(shù)據(jù).實(shí)驗(yàn)中讀寫NVM開銷和重計(jì)算開銷的產(chǎn)生過程如下：

1) 對于存儲結(jié)點(diǎn)均使用clflush和mfence指令，顯式地將其計(jì)算結(jié)果從CPU緩存直接刷回NVM，這一部分是結(jié)點(diǎn)的讀寫NVM開銷；

2) 對于重計(jì)算結(jié)點(diǎn)的計(jì)算結(jié)果，CPU緩存并不將其刷回NVM，而是通過編譯期靜態(tài)決策所確定的重計(jì)算路徑，在使用時(shí)將其重新計(jì)算出來，這一部分是結(jié)點(diǎn)的重計(jì)算開銷.程序運(yùn)行時(shí)，如果重計(jì)算所需的輸入數(shù)據(jù)存在于CPU緩存中，則可以加速計(jì)算過程，但由于CPU緩存狀態(tài)的不確定性和多樣性，所以在靜態(tài)決策時(shí)沒有考慮這種情況.

對同一結(jié)點(diǎn)做不同的決策，通過比較讀寫NVM的開銷和重計(jì)算開銷以體現(xiàn)重計(jì)算方法的先進(jìn)性.

實(shí)驗(yàn)?zāi)M的CPU使用了緩存，主要目的是緩存中間計(jì)算結(jié)果，因?yàn)闆Q策是以C語言一條語句為粒度，但一條語句可能產(chǎn)生多條匯編指令，這其中會產(chǎn)生中間計(jì)算結(jié)果.如果不用緩存，雖然可以確保loadstore指令只面向NVM，但中間計(jì)算結(jié)果可能會寫入NVM，會導(dǎo)致重計(jì)算過程對NVM產(chǎn)生額外的寫操作.

需要說明的是，clflush指令可以指定刷回?cái)?shù)據(jù)的地址，確保數(shù)據(jù)寫入NVM，但帶來的副作用是此緩存行的其他數(shù)據(jù)也被刷回NVM，會造成一定的額外開銷.

4 相關(guān)研究工作

首先討論在系統(tǒng)容錯(cuò)和恢復(fù)方面的工作，然后討論重計(jì)算在減少對內(nèi)存寫操作方面的相關(guān)工作.

1) 系統(tǒng)容錯(cuò)和恢復(fù).在高性能計(jì)算(high per-formance computing， HPC)應(yīng)用或者并行的大規(guī)模系統(tǒng)中容易出現(xiàn)運(yùn)行錯(cuò)誤的情況.Alshboul等人[32]提出了基于重計(jì)算的故障安全方法，并證明了它對HPC應(yīng)用中循環(huán)代碼的適用性，該方法只記錄足夠的應(yīng)用級數(shù)據(jù)來啟動重新計(jì)算，并且相比日志文件和檢查點(diǎn)文件方法能大幅減少執(zhí)行時(shí)間以及額外的寫次數(shù).Ren等人[33]基于HPC應(yīng)用的固有容錯(cuò)性，引入了EasyCrash框架，在應(yīng)用程序執(zhí)行期間選擇性地持久保存應(yīng)用程序數(shù)據(jù)對象, 與傳統(tǒng)檢查點(diǎn)技術(shù)一起使用提高系統(tǒng)效率.

2) 減少對內(nèi)存的寫操作.Hu等人[34]結(jié)合數(shù)據(jù)遷移和重計(jì)算，利用嵌入式系統(tǒng)的便箋存儲器(scratch pad memory， SPM)減少對NVM的寫操作，其工作將數(shù)據(jù)在多個(gè)核之間的遷移轉(zhuǎn)化為圖計(jì)算并尋求最短遷移路徑，如此，不同的核便可以利用遷移的數(shù)據(jù)進(jìn)行重計(jì)算.Huang等人[35]提出用重計(jì)算方法減少嵌入式系統(tǒng)中寄存器分配過程的變量溢出數(shù)目，從而減少對NVM的寫操作.Hu等人和Huang等人關(guān)注的重點(diǎn)是嵌入式系統(tǒng)中減少對NVM的寫操作，并分別從數(shù)據(jù)遷移和寄存器分配過程中的變量溢出數(shù)目的角度應(yīng)用重計(jì)算方法.Koc等人[36]利用距離處理器更近的片上存儲(on-chip memory)的數(shù)據(jù)重新計(jì)算遠(yuǎn)離處理器的數(shù)據(jù)，而不是直接訪問遠(yuǎn)數(shù)據(jù)，以減少訪問延遲.Akturk等人[37]給出了在微架構(gòu)級別的概念性驗(yàn)證，對重計(jì)算能耗和存儲能耗做了比較，提出通過最后一級緩存(last level cache， LLC)是否缺失的方法以動態(tài)決策重計(jì)算.Koc等人和Akturk等人均從被訪問的數(shù)據(jù)與處理器之間距離的角度考慮重計(jì)算方法，并沒有限定存儲器的種類.

與現(xiàn)有的這些重計(jì)算方法相比，本文更關(guān)注如何對程序的中間計(jì)算結(jié)果做存儲或重計(jì)算的決策，以較小的重新計(jì)算開銷換取較大的寫NVM開銷.為此提出基于結(jié)點(diǎn)出度的重計(jì)算方法，本方法的創(chuàng)新點(diǎn)在于對結(jié)點(diǎn)做存儲或重計(jì)算的決策時(shí)考慮到其直接消費(fèi)者個(gè)數(shù)對于決策的影響.

5 結(jié) 論

相比于DRAM，新興的非易失存儲器(NVM)作為持久性內(nèi)存帶來了非易失性、低能耗以及高存儲密度的優(yōu)點(diǎn)，但同時(shí)也存在寫操作延遲高和寫壽命短的缺點(diǎn)，因此如何減少對NVM的寫操作成為一個(gè)非常重要的問題.為了解決這個(gè)問題，本文設(shè)計(jì)并實(shí)現(xiàn)了一種基于結(jié)點(diǎn)出度的重計(jì)算方法稱作ROD.ROD方法按數(shù)據(jù)流圖對程序語句劃分結(jié)點(diǎn)，利用結(jié)點(diǎn)的出度規(guī)劃了重計(jì)算或存儲的選擇策略，通過選擇性丟棄要寫回NVM的數(shù)據(jù)，需要時(shí)再重新計(jì)算產(chǎn)生，以此減少對NVM的寫操作，降低系統(tǒng)的IO開銷.在搭載了NVMain的Gem5模擬器中使用powerstone測試集對ROD方法做了性能評測，并與貪心重計(jì)算方法和傳統(tǒng)的以存儲為主導(dǎo)的無重計(jì)算方法作比較.實(shí)驗(yàn)結(jié)果顯示，ROD方法相比于存儲主導(dǎo)的方法平均減少44.3%(最高68.5%)的寫操作.ROD方法的運(yùn)行耗時(shí)比存儲主導(dǎo)的方法平均減少28.1%(最高68.6%)，比貪心重計(jì)算的方法平均減少9.3%(最高19.4%).