異構內存系統全局優化的數據預取算法

裴頌文，趙夢旖，姬燕飛

（1.上海理工大學 光電信息與計算機工程學院，上海 200093；2.復旦大學 管理學院，上海 200433）

處理器性能的提升對訪存帶寬提出了新的要求，訪存延時已經成為影響處理器性能的重要瓶頸。處理器需要花費大量時間等待數據結果返回，這造成了性能的損失。數據預取正是降低或隱藏訪存延時的重要手段[1]，它有效地緩解了處理器與動態隨機存取存儲器（dynamic random access memory，DRAM）之間存在的訪存速度差異。

許多新興的存儲器架構利用不同存儲器技術，以不同方式將3D堆疊存儲器集成到處理器存儲器中，結合了多種處理的性能和功率特性，構成異構內存架構。異構內存架構的研究主要集中在優化快速存儲器作為慢速存儲器的緩存，或者將快速存儲器和慢速存儲器放置為平級結構兩個方面。設計異構內存架構的目標是既可以獲得快速存儲器速度上的性能優勢，又擁有慢速存儲器巨大的內存容量。處理器的性能以每年60%的速度提升，而以DRAM作為內存的處理器每年性能提升速度只有10%[2]，DRAM的性能制約了處理器性能的提升。現今已有一些存儲器可以滿足這些需求，包括3D堆疊DRAM（3D-DRAM）以及非易失性存儲器（non-volatile memory，NVM）。新型NVM的出現，為擴展計算機內存提供了新的途徑，同時推動了傳統計算機系統結構的改變。相比現存的DRAM，新興的NVM能耗更低，并且具有良好的擴展性。現有的NVM包括FeRAM（鐵電隨機存儲器），PCM（相變存儲器），STTRAM（自旋轉移矩磁隨機存儲器），MRAM（磁性隨機存儲器），RRAM（阻變隨機存儲器）等[3]。其中PCM應用范圍廣，性能接近DRAM，但容量遠遠大于DRAM，能耗和價格遠遠低于DRAM，這為新型的內存體系結構提供了良好的硬件保障；然而它訪問延時較長[3]，單元存取能量消耗較高。以上為新型存儲器和傳統存儲器結合構成新型存儲結構提供了理論基礎。它在大幅提升內存容量、降低成本的同時，又可以提供和DRAM相近的訪問速度。因此，本文主要研究混合式存儲系統的數據預取方法，這對于緩解存儲墻問題具有重要意義。對于混合內存的數據預取有多種方法，有靜態閾值的預取算法、動態閾值的預取算法。以上算法不能達到性能的最優化，因此，本文提出了一種新的數據預取算法。

1 研究背景

1.1 異構混合內存結構

Park等[4]提出了PCM和DRAM同級的異構內存結構，DRAM和PCM都用作主存儲器。這種異構內存架構減少了功率的預算，它與傳統的主存儲器架構十分類似，在混合主內存和二級存儲器之間有內存頁面交換。在這種異構內存架構中，DRAM和PCM被分配了統一的物理地址空間。Linux內核可以直接管理PCM和DRAM的頁面，這種情況下，在內核中對DRAM和PCM進行分區很有必要。結構如圖1（a）所示，它充分結合了PCM和DRAM的優點，采用線性統一編址[5]。

Qureshi等[6]提出了另一種異構內存結構，考慮到DRAM快速的訪存速度以及PCM的大容量，把DRAM作為PCM的緩存[7]。這種混合存儲內存架構利用了DRAM在訪問速度上的優勢。PCM上可以存儲大量的信息，進而減少了對外存的訪問。此種結構中DRAM采用3D芯片堆疊技術[8]，PCM由操作系統管理，DRAM是透明的，DRAM發出的訪問請求都到達PCM中。在DRAM上層有一個控制器，在請求到達時，這種混合結構首先在DRAM中查找目標數據，當查找失敗時，再對PCM進行查找[3]。如圖1（b）所示，這種層次式的結構克服了DRAM容量小及PCM速度慢的缺點。

圖1 異構內存系統結構Fig.1 Structure of the heterogeneous memory system

1.2 數據預取方法介紹

鑒于數據訪問的局部性原理，數據預取技術可以利用它提前預測訪存地址并提前請求訪存，從而達到降低或隱藏訪存延時的效果[9]。數據預取（data prefetching）主要分為 3 種：

a.基于硬件控制的數據預取（hardware prefetching），基于動態的分支預測，可以動態發射數據預取指令，沒有額外的預取指令開銷，并且提高了程序性能；

b.基于軟件控制的數據預取（software prefetching），編譯器編譯或者程序員手動插入預取指令，從而預先得到數據，隱藏了延時；

c.基于軟硬件結合的混合數據預取方式（mixed data prefetching），這種數據預取結合了上述兩種預取方式，由編譯器初始化標簽存儲器，由硬件直接從存儲器中預取數據，避免了軟件預取的開銷，實現了性能的優化[10]。

Ramos等[11]提出了RaPP（rank-based page placement）內存管理機制，把訪問級別低的頁面放置在PCM中，級別高的頁面放置在DRAM中，使用多級隊列的方法存儲頁面的最近存儲及訪問信息。該方法使用計數器統計每個頁面的讀寫訪問次數，每訪問一次計數器增加1。當頁面的訪問次數達到一定閾值時，把該頁面提升到更高級的隊列中，此時兩個隊列中就發生頁遷移。但是，這種方法有很大的局限性，它只考慮到了頁面的局部訪存信息。張進寶[12]提出了基于頁面熱度的異構內存能效管理機制，它考慮了全局和部分的讀寫信息，在RaPP的基礎上得到了更為理想的劃分冷熱頁面的方法。根據頁面的冷熱度值，可以有效區分冷熱頁面，并且利用建模的方法篩選出耗能最少的頁面組合，建立了異構內存上的能效遷移模型。Islam等[3]提出了平地址內存結構中的數據預取策略，這種預取策略使用了距離預取，其好處在于可以檢測重復序列中的非單位步幅；使用全局歷史緩沖區（GHB）結構來實現距離預取器，這種方法開銷小，預取準確性更高，訪存沖突較少。Yoon等[13]提出了把DRAM作為PCM緩存情況下的異構內存系統管理策略，這種策略記錄行緩沖區缺失數目，并且把缺失數目多的數據放在DRAM中，避免過大的PCM訪問開銷。Liu等[14]提出了軟硬件協同管理（HSCC）的異構內存系統，這種結構簡化了硬件設計，并且在軟件層提供了緩存管理技術。軟硬件協同管理系統利用擴展的頁表、快表緩沖（TLB）記錄NVM和DRAM之間的地址映射，并且還記錄了訪問NVM頁面的次數。HSCC系統中采用了爬山算法決定遷移到DRAM中的頁面數。

2 模擬退火的全局優化數據預取算法

2.1 數據預取方法

數據預取就是一種求解最優可遷移頁面數量的機制，模擬退火算法是一種全局的求解最優化問題的算法，適用于該問題的求解。這個算法的思想借鑒于固體的退火原理，固體的內能隨著溫度的升高而增大，粒子的運動就越接近于無序[15]，隨著溫度的降低，運動就趨向于有序的狀態。最終，當溫度恒定時粒子達到最穩定的狀態。爬山算法也是啟發式算法，文獻[16]采用了爬山算法改進了深度優先搜索，但容易陷入局部擇優的情況，模擬退火算法可以克服爬山算法的缺點。

本文采用DRAM作為PCM緩存的層次化異構內存系統結構，異構內存系統已經被證明了它的有效性與實用性。在此結構中，本文預取算法的思想是通過確定合理的預取閾值，尋找全局優化的頁面遷移數量。基于模擬退火的數據預取算法可以高效地調整預取閾值，從而避免陷入局部最優，避免了資源的浪費和非必要的預取。本文提出了一種基于模擬退火的全局優化數據預取算法 （ simulated annealing data prefetching algorithm，SADPA）。經實驗證明，這種啟發式的算法可以按照一定的概率收斂于全局最優解。根據頁面訪問次數，當次數達到閾值時，就可以將頁面從NVM預取到DRAM，可以避免不必要的頁面預取。

在異構內存系統中，選擇合適的時機把NVM預取到DRAM中是關鍵的問題，以往通常是在一個固定的時鐘周期內統計預取帶來的性能增益，觸發相應的預取。在生存周期T內，性能增益gain的計算為[14]

式中：timerd為DRAM平均讀時延；timerp為PCM平均讀時延；Mrd為緩存的讀次數；timewp為PCM平均寫時延；timewd代表DRAM平均寫時延；Mwd代表緩存的寫次數；Mp代表預取次數；timep代表緩存DRAM消耗的時間。初始化預取閾值為thresholdt0，前T個和現T個時鐘周期的預取閾值分別為thresholdt-1，thresholdt，對應的性能增益分別為gaint-1，gaint。性能增益差deltag的計算式為

2.2 算法流程

圖2展示了SADPA流程，其中stride為步長。數據預取的關鍵在于選擇合適的時機預取到需要的數據。SADPA本質上是一種貪心算法，貪心算法是在舊解附近尋找新解，這個解很可能是局部最優解，而不是全局的。本文在貪心算法的基礎上引入隨機因子，可以隨機對多個點進行搜索，以一定的概率來接受一個比當前解要差的解。這種方式在一定程度上可以防止陷入局部最優解，實現全局優化。

圖2 SADPA流程圖Fig.2 Flow chart of SADPA

在SADPA中，每個周期內在凈收益增加的方向上動態調整預取閾值，使得最終閾值收斂在凈收益最大的點。本文設置閾值初始值為7，每次減小的步幅長度為0~2之間的隨機整數，閾值在遞減的時候要保證始終大于0。若當前增益大于之前的增益，說明選取的策略是正確的。當增益趨勢為上升趨勢時，閾值增加；反之閾值減小。若當前增益小于之前的增益，引入隨機因子α。α和凈增益相關，若α滿足一定的概率，則執行和當前增益大于之前增益時的閾值調整方法，否則執行相反的閾值調整。

2.3 算法偽代碼

SADPA具體算法如下：

輸入：閾值threshold，當前增益gaint，先前的增益gaint-1，增益增減趨勢標志flag，可變步幅stride輸出：int 0./*初始化增益差值 delta 為 0，stride 取整數*/1.delta =0，flag =0，stride =int （random（0，2）），threshold =7 2.repeat 3.delta =gaint - gaint-1 4.if delta >=0 5./* 增益呈現遞減趨勢并且閾值大于 0 */6.if flag <&&threshold >0 7.threshold =threshold - stride 8.else if flag >0 9.threshold =threshold + stride 11./* 引入隨機因子，跳出局部最優解 */10.if delta <=0 11./* 引入隨機因子，跳出局部最優解 */12.α =exp （-delta/gaint）13.if α >random（0，1）14./* 增益呈現遞減趨勢并且閾值大于 0 */15.if flag <0 &&threshold >0 16.threshold =threshold - stride 17.else if flag >0 19.else 20./* 增益呈現增長趨勢并且閾值大于 0 */21.if flag >0 &&threshold >0 22.threshold =threshold + stride 23.else if flag >0 24.threshold =threshold - stride 25.gaint-1 =gaint 26.end for

3 實驗與評估

3.1 實驗平臺

采用Zsim模擬器集成NVMain構建實驗評估系統。Zsim是業內廣泛采用的時鐘精確的系統模擬器，可以用來模擬大型異構計算系統和內存存儲層次系統[17]。NVMain可以在內存結構層面模擬新型非易失性存儲器，也可以模擬DRAM存儲器[18]。Ubuntu 14.04的實驗評估系統的硬件環境包括：處理器Intel Core i5-6400；一級緩存64 kB，采用4路組相聯；二級緩存256 kB，采用8路組相聯；三級緩存8 MB，采用16路組相聯。存儲結構為DRAM和 PCM混合（DRAM容量為1 GB，PCM容量為32 GB），其中DRAM和PCM的頁大小為4 kB。測試實驗選取了SPEC CPU 2006基準測試程序集中的astar，bzip2，cactusADM，hmmer，calculix作為預取性能和能耗分析的測試子程序[19]。

3.2 實驗數據及結果分析

圖3為SADPA內存訪問延時分布圖，周期間隔為22，最后的（88，110]是為了補全周期間隔，縱坐標為周期對應的有效延時數據的個數。在[0，22]周期內，有效延時訪問記錄的數量為23。在（88，110]周期內，有效延伸訪問記錄的數量為11。

本文還進一步對比了其他預取算法下的內存訪問延時，并用多個基準測試程序進行評估。圖4為平均訪問延時分布圖。對于astar應用，SADPA與軟硬件協同的動態閾值調整算法相比，平均訪問延時從 27.69 ns降低到 25.79 ns，降低了 6.8%。因為SADPA采用了全局優化的啟發式搜索方法，減少了PCM和DRAM之間的頁遷移次數，從而減少了平均訪問延時。對于bzip2應用，SADPA與軟硬件協同的靜態閾值調整算法相比，平均訪問延時分布從 37.14 ns降低到 35.32 ns，降低了4.9%。因為SADPA可以動態調整預取閾值，確定從PCM遷移到DRAM的頁面，降低了寫操作延時，從而減少了平均訪問延時。在不同的測試程序下，SADPA與硬件預取算法相比，平均訪問延遲均有大幅降低。因為SADPA是一種基于軟硬件協同的預取算法，它預取訪問頻率超出最優閾值的頁面，而硬件預取僅根據歷史訪問記錄信息可能會預取到一些不必要的頁面，故與硬件預取算法相比，SADPA可以獲得更低的訪問延時。

圖3 內存訪問延時分布圖Fig.3 Latency distribution of memory accessing

圖4 平均訪問延時圖Fig.4 Average latency of memory accessing

圖5為各種預取算法在不同測試程序下的IPC（instructions per cycle）。SADPA 與軟硬件協同的動態閾值調整算法[14]相比，平均IPC增加了4.5%。因為SADPA算法是基于全局優化的動態調整閾值，相比基于局部最優的爬山算法的動態閾值調整，具有更優的全局閾值。這種方式可以提高數據頁的遷移頻率，因此增加了單位時間內執行的指令數，提高了系統平均IPC。SADPA與軟硬件協同的靜態閾值調整算法[14]相比，系統平均IPC增加了10.1%。因為靜態閾值調整算法中，閾值是固定不變的，這會帶來不必要的數據頁遷移，從而增加能耗、時間等開銷。SADPA和硬件預取算法相比，IPC增加了8.4%。因為SADPA算法從軟件的角度出發，采用啟發式搜索來動態調整閾值，優化了整個預取過程，從而提高了IPC。

圖5 IPC圖Fig.5 Normalized IPC

圖6為各種預取算法在不同測試程序下的能耗分析圖。以硬件預取為基準，對其他預取算法下的測試數據進行歸一化處理。對于cactusADM應用，SADPA與軟硬件協同的動態閾值調整算法相比，能耗降低了3.4%。因為cactusADM中PCM寫占比較低，并且DRAM讀占比較高，SADPA選取了全局優化閾值，避免了不必要的頁面預取，從而減少了能耗。對于astar應用，SADPA相對于硬件預取算法能耗降低了11%。因為astar是一種尋路算法，SADPA算法考慮到全局因素，降低了PCM寫延時長對性能的影響，因而可以獲得更低的能耗。

圖6 能量消耗歸一化統計圖Fig.6 Normalized power dissipation

圖7為各種預取算法在不同基準測試程序下的預取率。SADPA比軟硬件協同的動態閾值調整算法平均預取率提高了2.5%。對于bzip2應用，SADPA算法和軟硬件協同的動態閾值調整算法相比，預取率從89.01%提升到93.12%，預取率提高了4.6%。因為bzip2的DRAM和PCM的寫占比低于讀占比，基于全局的啟發式搜索算法可以動態調整閾值，在一定程度上能跳出局部最優解，尋找出全局優化解。得到全局優化值后，可以合理確定預取的頁面，使得預取率得到提升。圖中最顯著的是對于cactusADM，和硬件預取算法相比，SDAPA算法預取率提高了13%。因為它是一種PCM寫占比和DRAM讀占比相差非常大的應用，所以SADPA算法提高了預取率。

圖8為各種算法在不同基準測試程序下的DRAM cache利用率分析圖。對于bzip2應用，SADPA與軟硬件協同的靜態閾值調整算法相比，DRAM cache利用率從33.15%提高到35.02%，提高了5.3%。因為SADPA是基于全局優化的動態閾值調整預取算法，合理的數據頁遷移可以避免靜態閾值調整算法預取不到訪問頻度較高的數據頁，因而提高了 DRAM cache利用率。對于 hmmer應用，SADPA算法和軟硬件協同的動態閾值調整算法相比，DRAM cache利用率從16.35%提高到17.84%，提高了9.1%。因為SADPA算法可以避免陷入局部最優的情況，所以提高了利用率。

圖7 預取命中率Fig.7 Ratio of prefetching hit

圖8 DRAM cache利用率Fig.8 Utilization ratio of DRAM cache

4 總結與展望

本文主要研究DRAM-PCM混和存儲系統數據預取算法，介紹了異構內存系統的結構及發展，描述了SADPA的思想及實現步驟。SADPA根據頁面的訪問次數與閾值判斷，啟發式地預測將NVM頁面遷移到DRAM頁面的數量。該算法可以防止陷入局部最優，尋找出全局優化的閾值。相對于局部最優的算法，SADPA可以獲得更高的性能。面向混合式存儲系統的高效能數據預取機制是下一步的研究方向。近來隨著機器學習的發展，本文考慮結合機器學習方法，進一步實現預取操作的能耗和預取時間之間的最優化設計。