申威架構下的虛擬機訪存特征提取方法*

沙 賽，王 超，杜翰霖，羅英偉，汪小林，王振林

(1.北京大學信息科學技術學院,北京100871;2.江南計算技術研究所,江蘇 無錫 214083;3.密歇根理工大學計算機系，霍頓 密歇根州 49246)

1 引言

近年來，以申威(Sunway)、飛騰、龍芯為主要代表的國產CPU不斷發展。國產超級計算機神威·太湖之光的成功確定了申威在國產CPU界的重要地位。申威架構已經成為諸多國產領域的主流CPU架構，特別是在政府部門等對于自主可控、安全高效要求較高的部門[1]。作為國產CPU的典型代表，申威CPU備受關注，近年來涌現了一批申威平臺的學術成果[2]。申威架構指令集源自Alpha架構指令集，在此基礎上進行了優化和多方面的擴展，已形成獨有的申威擴展指令集[3]。如今中美貿易摩擦不斷，堅持自主可控，提升國產CPU芯片的性能勢在必行。國內已經基本形成了CPU架構到操作系統內核專業定制，再到PC操作系統與服務器操作系統桌面化設計，最后到國產系統應用程序適配的一整套完整國產申威架構生態鏈。如何充分發揮國產CPU性能、如何充分利用國產CPU架構新特性是操作系統內核設計者的主要工作內容。隨著國家信息化程度的不斷提高，國產服務器的應用不再僅僅限制于簡單的辦公桌面系統，而是面向市場更為廣闊的云服務系統。

虛擬化是云服務的重要支撐技術之一。虛擬化是指將一臺物理計算機系統虛擬化為一臺或多臺虛擬計算機系統(虛擬機)。每臺虛擬機都擁有自己的虛擬硬件(如CPU、內存等)來對外提供一個獨立且完整的計算機執行環境[4]。虛擬化可提供多個隔離的執行環境，這種將運行環境完整地封裝帶來了明顯優勢:多個虛擬機之間具有很強的隔離性，虛擬機和硬件之間沒有關聯，并且在功能上可以實現整機的快照、克隆和掛起等功能，靈活多樣[4,5]。在一臺計算機上運行多個虛擬機使得資源的調度更為優化。虛擬化具有多樣的功能和靈活性，同時也帶來了諸多問題。虛擬化主要分為CPU虛擬化、內存虛擬化和I/O虛擬化3個方面。其中，內存虛擬化是最為復雜的部分，內存虛擬化的優劣往往成為虛擬機系統性能的瓶頸[4]。就內存虛擬化技術而言，主要面臨2個方面的問題，一是如何降低內存虛擬化帶來的額外開銷。雖然內存虛擬化技術日益成熟，但很多應用場景下仍存在著不小的性能開銷。二是如何充分利用虛擬化的靈活性來提高多虛擬機內存的利用率[6]。大數據時代背景下，云服務所承載的程序需要的內存量越來越大，虛擬機內存資源利用率低，分配不均衡的問題日益突出[7]。本文主要就國產服務器如何有效解決虛擬機內存利用率低的問題展開討論。

相較于以x86為代表的國際主流CPU架構服務器，申威仍處于較為初步的階段，就單核性能而言，仍有數倍差距，但核數眾多是申威服務器的優勢。多核服務器很好地滿足了多任務操作系統對于CPU的需求，但是激烈的內存競爭是限制其性能的主要瓶頸之一。根據調查目前國內外知名的云計算平臺供應商，其內存等資源的利用率均不足40%[8]。導致這種情況的核心問題之一是虛擬機對共享資源的競爭導致系統整體性能下降，為保證云服務性能而不得不過量分配虛擬機內存。在虛擬化環境下，如何充分地發揮虛擬化帶來的資源調配的靈活性，以提高內存資源的利用率是重要的研究課題。

虛擬機工作集WSS(Working Set Size)是指一臺正在運行的虛擬機實際使用的內存量[9,10]。工作集是指導虛擬機內存分配量最直接的指標，如何高效實時測算虛擬機的工作集是虛擬機動態調配的主要挑戰。在x86架構上，已有諸多研究者開展了相關的工作。主流的測算工作集的方式是通過內存缺失率曲線MRC(page Miss Ratio Curve)進行估算[11 - 13]。繪制內存缺失率曲線需要獲取較為完整的內存訪問流，這與CPU架構直接相關。

申威架構服務器雖不具有硬件輔助的虛擬化支持(如Intel擴展頁表EPT(Extended Page Table)技術[14])，但是其獨特的固件層HMCODE帶來了充分的軟件靈活性以幫助實現系統虛擬化。HMCODE是申威架構獨有的位于硬件層和操作系統層之間的固件層，通過申威指令匯編代碼編寫，以最高特權實現一系列操作(如修改寄存器、軟件刷新旁路緩存TLB(Translation Lookaside Buffer)等)。因此，傳統的x86架構下的工作集測算方法已不再適用申威架構。如何結合申威架構自身的虛擬化實現以及如何充分發揮申威架構軟件靈活性的優勢是實現訪存特征提取面臨的主要挑戰。

本文提出了基于申威架構的多層協從虛擬機訪存特征提取技術，并在申威1621服務器實現和測試了該技術[15]。從原理上講，本文采用基于最近最少使用棧LRU(Least Recently Used)構建重用距離分布直方圖并進一步繪制內存缺失率曲線，實現虛擬機工作集預測，同時使用熱頁集削減訪存提取開銷。實驗結果表明，該方法能夠在申威平臺上高效準確地獲得虛擬機高精度的內存缺失率曲線并計算虛擬機工作集大小，同時引入的熱頁集可以有效降低訪存特征提取所帶來的性能開銷。

2 訪存特征提取方法

訪存特征提取是在計算機操作系統層面(或更底層)對運行在計算機上的應用程序訪存行為進行數據采集并分析的技術。訪存特征提取的核心是獲取應用程序的內存缺失率曲線。內存缺失率曲線反映的是應用程序內存用量和缺頁率之間的關系。通過訪存特征提取，可以有效地評估應用程序的訪存行為，分析應用程序局部性特征，計算應用程序的工作集大小，這對指導虛擬機系統的內存分配具有重要意義[16 - 18]。

2.1 訪存特征提取基本原理

在申威架構服務器上首次實現了訪存特征提取機制，整個訪存特征提取機制主要包括3部分：“內存缺失率曲線”構建方法、“置位-中斷”頁面追蹤方法和“熱頁集”優化方法。下面分別闡述3個部分的原理與功能。

2.1.1 內存缺失率曲線構建方法

Mattson等[19]于1970年提出的LRU棧式算法是最經典的存儲體系缺失率曲線構建方法。LRU棧式算法的基本原理就是使用一個LRU棧的結構來模擬Linux內核對內存的管理，從而獲取重用距離直方圖，通過直方圖來計算內存缺失率曲線。

LRU棧利用一個特殊的棧來保存當前使用的各個頁面的頁面號，每當訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。內存不足時，系統就會淘汰最近最久未使用的頁面。

“重用距離”是指一個頁面在LRU棧中再次被訪問時與棧頂的距離，即連續2次訪問之間有多少個不同的頁面被訪問。使用LRU棧模擬程序訪存的操作，使用計數器統計每個條目的訪問次數構建出重用距離分布RDD(Reuse Distance Distribution)直方圖。內存缺失率(MissRatio)計算公式如式(1)所示：

(1)

其中,rd[k]表示重用距離為k的訪問出現的次數,也就是距離棧頂為k的條目保存的頁面被訪問的次數。棧大小為c即內存有c個不同頁面。

2次訪問相同的頁面，第2次訪問能否命中內存與2次訪問的重用距離有關。如果2次訪問重用距離大于c，第2次訪問時該頁面已經被淘汰出LRU棧，會產生缺頁中斷；反之，如果2次訪問重用距離小于c，當前頁還在內存中，訪存命中。據此計算得出任意內存大小時的內存缺失率，進而繪制內存缺失率曲線。

2.1.2 “置位-中斷”頁面追蹤方法

內存缺失率曲線構建機制的輸入是連續的CPU訪存虛地址流。CPU在進行數據訪存之前，需要進行虛實地址轉換即將虛擬地址轉換成物理地址，由于旁路緩存TLB的存在，絕大部分的地址轉換會被硬件TLB直接命中，這就導致在軟件層面無法獲取到完整的CPU訪存地址流信息。虛擬化環境下，虛擬機管理器難以直接感知這類訪存行為，因此本文采用了置位的方式對虛擬機內存頁進行標記，從而所有的被標記頁面都會陷入缺頁處理函數，以被虛擬機管理器捕獲。具體來講，針對每個64位的頁表項，規定了一位未使用的位作為標記，以標識該頁的追蹤狀態。當頁面即將進入LRU時，刷新其對應的TLB項并置位頁表項有效位，以保證該頁面下次被訪問時依舊發生缺頁中斷，虛擬機管理器就可以感知到該頁面的訪存行為。

2.1.3 “熱頁集”優化方法

頁面追蹤機制需要完整的CPU訪存流，截獲每一次CPU的訪存操作，并且每次訪存操作都需要發生TLB 未命中(TLB MISS)、頁表遍歷和缺頁中斷處理。這種方法會帶來巨量的性能開銷，而實際上訪存特征提取機制的目標是實時計算虛擬機的工作集大小。一方面，理論上，根據重用距離直方圖(或MRC)來計算工作集大小，起決定因素的是長距離的訪存重用，因為最長距離的重用決定了該虛擬機所需要的不同頁面數目的最大值。另一方面，根據程序局部性原理，絕大部分訪存都是短距離重用，追蹤這部分訪存開銷巨大。熱頁集機制就是過濾短距離重用，只保留有計算工作集價值的長距離重用分布的方式來大幅減少頁面追蹤開銷。

一段時間內被頻繁訪問的內存頁面稱為熱頁，當前所有熱頁構成的集合稱為熱頁集。熱頁集通過一個有限長度的先進先出(FIFO)隊列來維護。在程序開始運行的時候，程序中的所有內存頁面都被初始標記為冷頁，所有對冷頁的訪問都會被跟蹤。一旦一個冷頁被訪問，根據時間局部性原理，這個頁面最近被再次訪問的可能性非常大，因而這個正在被訪問的冷頁會被標記為熱頁并加入熱頁集進行維護。

圖1中展示了內存頁面跟蹤中熱頁集的位置，其中熱頁集是一個先進先出的隊列，它記錄了所有熱頁的地址及其他必要信息。如圖1所示，當程序訪問到內存中的冷頁時，觸發缺頁中斷，此時在隊列中記錄下該頁的信息，并將其加入到熱頁集中，即標記為熱頁。通常熱頁集都是滿的，新頁加入到熱頁集中就需要從熱頁集中移除一個最舊的頁面。從熱頁集中移除的頁被重新標記為冷頁。

Figure 1 Principle of memory access feature extraction圖1 訪存特征提取原理

使用熱頁集的效果是避免了對大量發生在熱頁上的頁面訪問的監控跟蹤，也就是說，進入熱頁集的頁面會被清除置位標記，從而不會因為置位而發生缺頁中斷。短時間內將會被頻繁訪問的頁面，CPU對它們的訪問都被熱頁集過濾掉，極大地降低了頁面跟蹤的總量，減小了頁面跟蹤的時間開銷。

熱頁集的大小直接關系著訪存特征提取的開銷與準確性。過小的熱頁集會導致過量的頁面被置位標記，帶來大的額外開銷；過大的熱頁集會導致小工作集虛擬機訪存特征提取失敗，即熱頁集完全覆蓋了工作集對應的內存量。因此，熱頁集大小應當根據虛擬機的實際應用場景進行確定，以保證訪存特征提取有合理的性能開銷和較高的準確度。

2.1.4 具有熱頁集的訪存特征提取方法

圖1是申威架構下虛擬機訪存特征提取方法的實現原理示意圖。虛擬機在運行過程中不斷訪問物理內存，用戶開啟某虛擬機的訪存特征提取，系統立即清空該虛擬機的TLB和進程頁表，此時所有訪存均發生缺頁中斷，訪存序列在缺頁中斷處理函數中被捕獲。被捕獲的訪存序列進入熱頁集進行過濾，進入熱頁集的頁面，清除其置位標記；若熱頁集滿，離開熱頁集的頁面進行置位標記，并刷新其TLB和頁表項，最終頁面進入LRU棧。重復上述過程直到用戶關閉訪存特征提取，此時系統根據LRU棧計數器統計獲得重用距離分布直方圖，繪制內存缺失率曲線MRC，計算虛擬機工作集大小。一次完整的虛擬機訪存特征提取結束。

圖2 舉例展示實驗測得的SPEC2006-400.perlbench重用距離分布直方圖與內存缺失率曲線。設置熱頁集大小為1 600，因此重用距離分布直方圖中，重用距離小于1 600的頁面均被過濾，重用次數為0。重用距離越小，重用次數越高，這也符合程序局部性原理。與之對應的是由式(1)計算得到的內存缺失率曲線，由圖2可知，隨著給定內存值越大，程序的缺頁率越小，不斷逼近于零。

Figure 2 Perlbench reuse distance distribution histogram and memory page miss ratio curve圖2 SPEC2006-400.perlbench重用距離分布直方圖與內存缺失率曲線

2.2 申威平臺訪存特征提取實現

2.2.1 申威架構虛擬化簡介

如圖3所示，相比于x86為代表的傳統CPU架構申威架構多了一層固件(HMCODE),于是在系統模式上，申威增加了一種新的具有最高權限級的硬件模式HM(Hardware Mode)。在HM下，系統具有最高特權級，不響應各類中斷，所執行的即是位于固件層的匯編代碼。就虛擬化而言，當前申威架構下的虛擬化工作仍處于比較初級的階段，特別是在硬件上缺少類似Intel VT-x的虛擬化相關的支持。所以，為了保證虛擬化在申威平臺上的功能與性能，研究者們采用了軟件與固件相結合的方式提供較為全面的虛擬化支持。就申威虛擬化而言，設計者在內核層實現復雜的且使用頻率較低的功能部件；在固件層實現功能簡單但高頻使用的功能模塊(如MMU)，從而保證其運行效率。

Figure 3 Comparison of x86 and Sunway architecture圖3 x86與申威架構層級對比

傳統x86架構下的虛擬機訪存特征提取所依托的是Intel EPT機制，通過對EPT頁表項進行置位中斷處理，就可以在虛擬機管理器(如KVM)中獲取到虛擬機的訪存地址流。申威架構下虛擬機內存分配采用了段式映射的方式，將虛擬機的地址直接映射到連續的物理內存段上，避免了2級地址轉換帶來的額外開銷。因此，在申威架構中無法直接使用x86架構的訪存特征提取機制 。本文結合申威架構的特點，充分發揮HMCODE帶來的軟件靈活性，在申威平臺上構建了多層協調的訪存特征提取機制。

2.2.2 多層協調的訪存特征提取實現接口

如圖4所示，申威輕量級虛擬機運行在用戶層，訪存特征提取機制主要實現在內核層與固件層(HMCODE)。虛擬機訪存發生TLB未命中，經中斷程序進入TLB脫靶處理模塊。若用戶開啟訪存特征提取，此模塊首先對發生TLB未命中的頁面進行“標記位”檢查，若該頁面是被置位標記的頁面，則直接陷入缺頁處理接口，否則就進行正常的頁表訪問。在x86架構下，TLB未命中之后硬件陷入MMU進行頁表遍歷，對于頁面的攔截就不得不推遲到頁表遍歷之后，而申威架構下，對于需要采樣的頁面(即標記頁面)無需進行頁表遍歷，這在一定程度上減少了額外的開銷。

Figure 4 Interface of memory access feature extraction of Sunway virtual machine圖4 申威虛擬機訪存特征提取接口

缺頁處理接口將被標記頁的必要信息以參數的形式傳入內核缺頁處理模塊，參數包括訪存地址(缺頁處理的頁面地址)、VPN(Virtual Processor Number)和UPN(User Processor Number)。VPN和UPN用于申威CPU的TLB當中，是申威架構獨有的用于區分虛擬機和進程的特殊標記。

發生缺頁中斷并進入內核層缺頁處理模塊的頁面，若有置位標記，則將其清除，然后頁面進入熱頁集存儲；若沒有置位標記，則說明該頁面是熱頁，已存在于熱頁集中。熱頁集通過一個先進先出隊列進行維護，熱頁集中保存著熱頁的頁幀號、VPN和UPN。若熱頁集已滿，則最舊頁面離開熱頁集，進入LRU模塊進行下一步處理。

LRU模塊負責通過LRU棧式算法構建重用距離分布直方圖。進入LRU模塊的頁面會根據LRU替換規則進行管理。棧中的每個條目都包含一個訪問計數器，用于記錄該條目被訪問次數即重用次數。首先自棧頂向下遍歷棧，若找到該頁面，則將該條目的訪問計數器自增并將頁面提到棧頂；若頁面不存在于棧中，則直接將頁面壓入棧頂。LRU棧的大小由當前虛擬機的內存大小決定，例如在申威架構下，每個頁面的大小是8 KB，一個具有4 GB內存的虛擬機對應的LRU棧大小為219。

用戶關閉訪存特征提取后，系統關閉特征提取各模塊并啟動數據分析模塊。該模塊會收集LRU模塊中采集的重用次數，繪制重用距離分布直方圖與內存缺失率曲線，由此可以獲取申威虛擬機的工作集大小。

3 實驗

為驗證訪存特征提取方法的有效性和高效性，本文通過真機實驗的方式加以驗證，從訪存特征提取構建的內存缺失率曲線準確性、時間開銷和存儲空間開銷3個方面進行實驗分析。本文以SPEC2006[20]中工作集大小大于20 MB的程序作為測試程序(共計18個)，這是因為工作集過小的程序的訪存序列會被熱頁集完全覆蓋而無法構建重用距離分布直方圖。實際上，工作集的大小和對虛擬機內存壓力的影響成正比，我們更關注內存需求較大的程序。

3.1 實驗環境

本文在申威1621型多核服務器上實現訪存特征提取并測試。實驗機具有16核CPU，工作頻率為2 GHz。存儲體系上，系統具有3級CPU緩存，緩存大小分別是32 KB,512 KB,32 MB；集成8路64位DDR3存儲控制器，傳輸速率為1 066～2 133 MBps，支持ECC校驗，內存大小為64 GB；HDD硬盤容量為2 TB。

軟件層面上，宿主機與虛擬機均采用基于Linux的深度服務器操作系統，每臺虛擬機分配4個物理核和4 GB的初始內存。

3.2 內存缺失率曲線準確性檢驗

為驗證訪存特征提取的準確性，本文對比分析了申威平臺虛擬機訪存特征提取得到的程序內存缺失率曲線和使用Intel-PIN工具模擬測定的內存缺失率曲線。Intel-PIN是Intel公司開發的動態二進制插樁框架，用于動態分析程序特征，它可以監控程序的每一步執行，提供了豐富的API，可以在二進制程序運行過程中插入各種函數，比如可以獲取程序執行過程中的訪存虛地址序列[21]。由此，本文將Intel-PIN獲取到的訪存序列作為輸入，然后模擬程序的訪存行為，通過具有熱頁集的訪存特征提取機制，獲取準確的程序內存缺失率曲線。

Figure 5 Sunway virtual machine memory access feature extraction and Intel-PIN simulation memory page miss ratio curves圖5 申威虛擬機訪存特征提取與Intel-PIN模擬內存缺失率曲線

圖5展示的是SPEC2006部分程序的測試結果。虛線代表Intel-PIN模擬結果，實線代表申威平臺虛擬機訪存特征提取結果。2條曲線形狀具有高度的相似性，這表明提取的程序訪存特征是正確的；申威訪存特征提取方法獲得的內存缺失率曲線明顯高于Intel-PIN獲取的曲線，這是因為熱頁集過濾了導致重用距離小的訪存。實驗結果表明，SPEC2006程序集程序重用距離小于1 600的訪存數目占總訪存的比例平均高達99.9%，這也符合程序局部性原理。通過統計實驗的結果進行動態修正可以明顯提高缺頁率數值的準確性，并且訪存特征提取機制的最終目標是計算程序的工作集大小，在圖中表現為曲線在橫軸的最大值，而熱頁集僅會影響曲線在縱軸(缺頁率)的數值，并不會影響橫軸(內存需求)的數值。實驗結果表明，測算工作集的平均誤差低于3%，這說明申威平臺上訪存特征提取準確性高，效果良好。

其他影響實驗結果的因素還包括對比實驗環境，主要是指x86和申威的架構差異性。Intel-PIN僅支持IA-32和x86-64指令集架構，因此本文在x86平臺上進行模擬。一方面，申威架構下頁面的大小為8 KB，而x86架構下頁面的大小為4 KB，頁面大小不同一定程度上會影響程序訪存特征。因此在實驗中，通過修正Intel-PIN獲取的重用距離分布直方圖，將相鄰頁面數據進行加法合并，以模擬8 KB頁面訪存的效果。另一方面，不同架構的程序編譯器具有一定的差異，可能存在一些訪存指令上的不同優化。

3.3 特征提取時間開銷

程序訪存在程序執行時間中占比較高，特別是密集訪存程序。程序訪存主要分為2步：一是訪存地址轉換，即虛擬地址到物理地址的轉換；二是程序讀/寫內存。地址轉換所帶來的時間開銷不容小視，特別是在虛擬化環境下，有研究表明，虛擬地址轉換開銷平均占到總執行開銷的5%，特別條件下高達40%[22]。訪存特征提取機制就是利用了程序訪存的地址轉換，特別是置位標記操作導致程序發生大量的缺頁中斷，這將帶來比較嚴重的性能開銷，因此本文引入了熱頁集機制過濾掉短距離重用訪存，短距離重用的訪存占比高達99.9%，因此可以大幅度削減特征提取的開銷。

圖6展示的是SPEC2006測試程序有無特征提取條件下歸一化時間開銷對比結果。申威平臺上開啟訪存特征提取的平均時間開銷約為8.3%，時間開銷和程序的工作集大小成正比，程序工作集越大，訪存開銷也就越大，提取訪存特征所帶來的額外開銷也就越明顯，比如429.mcf的額外開銷高達24.5%，這是因為該程序的工作集較大(1 676 MB)。訪存特征提取的時間開銷也與開啟的時間有關，開啟時間越久，開銷越大，特征提取的準確性越高，這需要折衷考慮。此外，申威平臺自身的缺陷也會影響開銷，現有的申威架構還在發展的初步階段，嚴重缺乏硬件方面的支持，比如硬件MMU以及硬件輔助虛擬化機制。

Figure 6 Comparison of normalized execution time of on/off memory access feature extraction圖6 開啟/關閉訪存特征提取時間開銷對比

3.4 特征提取空間開銷

訪存特征提取方法的空間開銷主要由2部分構成：熱頁集存儲開銷和LRU棧存儲開銷。熱頁集是一個先進先出隊列，LRU棧是一個棧式結構。隊列和棧的每個條目均保存頁面的64 bit地址、2 bit VPN和8 bit UPN，此外棧的每個條目還包含一個16 bit的計數器。對于一個內存為VM_memGB的虛擬機，設熱頁集大小為HS_size，則訪存特征提取總的存儲開銷TSO的計算如式(2)所示：

(2)

例如，對于一個4 GB內存虛擬機，若熱頁集大小設定為1 600，則總的存儲約為6 MB，相對于4 GB的虛擬機內存而言，訪存特征提取的存儲開銷可以忽略不計。

4 結束語

本文首次在國產處理器申威架構上提出了虛擬化環境下的訪存特征提取方法。本文充分結合了申威架構特性，基于Mattson棧式算法構建了重用距離分布直方圖和內存缺失率曲線，并準確計算了虛擬機內程序的工作集大小，采用“置位-中斷”的頁面追蹤方法，平均誤差不高于3%；引入熱頁集機制過濾頁面，大幅削減頁面追蹤的開銷，平均開銷約為8.3%。

在下一步工作中，將進一步完善申威平臺的內存虛擬化支持，并逐步實現多層協調的虛擬機內存動態調度系統，為國產服務器的發展增磚添瓦。