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

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

1 引言

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

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

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

虛擬機(jī)工作集WSS(Working Set Size)是指一臺(tái)正在運(yùn)行的虛擬機(jī)實(shí)際使用的內(nèi)存量[9,10]。工作集是指導(dǎo)虛擬機(jī)內(nèi)存分配量最直接的指標(biāo)，如何高效實(shí)時(shí)測(cè)算虛擬機(jī)的工作集是虛擬機(jī)動(dòng)態(tài)調(diào)配的主要挑戰(zhàn)。在x86架構(gòu)上，已有諸多研究者開(kāi)展了相關(guān)的工作。主流的測(cè)算工作集的方式是通過(guò)內(nèi)存缺失率曲線MRC(page Miss Ratio Curve)進(jìn)行估算[11 - 13]。繪制內(nèi)存缺失率曲線需要獲取較為完整的內(nèi)存訪問(wèn)流，這與CPU架構(gòu)直接相關(guān)。

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

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

2 訪存特征提取方法

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

2.1 訪存特征提取基本原理

在申威架構(gòu)服務(wù)器上首次實(shí)現(xiàn)了訪存特征提取機(jī)制，整個(gè)訪存特征提取機(jī)制主要包括3部分：“內(nèi)存缺失率曲線”構(gòu)建方法、“置位-中斷”頁(yè)面追蹤方法和“熱頁(yè)集”優(yōu)化方法。下面分別闡述3個(gè)部分的原理與功能。

2.1.1 內(nèi)存缺失率曲線構(gòu)建方法

Mattson等[19]于1970年提出的LRU棧式算法是最經(jīng)典的存儲(chǔ)體系缺失率曲線構(gòu)建方法。LRU棧式算法的基本原理就是使用一個(gè)LRU棧的結(jié)構(gòu)來(lái)模擬Linux內(nèi)核對(duì)內(nèi)存的管理，從而獲取重用距離直方圖，通過(guò)直方圖來(lái)計(jì)算內(nèi)存缺失率曲線。

LRU棧利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)，每當(dāng)訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)面號(hào)。內(nèi)存不足時(shí)，系統(tǒng)就會(huì)淘汰最近最久未使用的頁(yè)面。

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

(1)

其中,rd[k]表示重用距離為k的訪問(wèn)出現(xiàn)的次數(shù),也就是距離棧頂為k的條目保存的頁(yè)面被訪問(wèn)的次數(shù)。棧大小為c即內(nèi)存有c個(gè)不同頁(yè)面。

2次訪問(wèn)相同的頁(yè)面，第2次訪問(wèn)能否命中內(nèi)存與2次訪問(wèn)的重用距離有關(guān)。如果2次訪問(wèn)重用距離大于c，第2次訪問(wèn)時(shí)該頁(yè)面已經(jīng)被淘汰出LRU棧，會(huì)產(chǎn)生缺頁(yè)中斷；反之，如果2次訪問(wèn)重用距離小于c，當(dāng)前頁(yè)還在內(nèi)存中，訪存命中。據(jù)此計(jì)算得出任意內(nèi)存大小時(shí)的內(nèi)存缺失率，進(jìn)而繪制內(nèi)存缺失率曲線。

2.1.2 “置位-中斷”頁(yè)面追蹤方法

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

2.1.3 “熱頁(yè)集”優(yōu)化方法

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

一段時(shí)間內(nèi)被頻繁訪問(wèn)的內(nèi)存頁(yè)面稱為熱頁(yè)，當(dāng)前所有熱頁(yè)構(gòu)成的集合稱為熱頁(yè)集。熱頁(yè)集通過(guò)一個(gè)有限長(zhǎng)度的先進(jìn)先出(FIFO)隊(duì)列來(lái)維護(hù)。在程序開(kāi)始運(yùn)行的時(shí)候，程序中的所有內(nèi)存頁(yè)面都被初始標(biāo)記為冷頁(yè)，所有對(duì)冷頁(yè)的訪問(wèn)都會(huì)被跟蹤。一旦一個(gè)冷頁(yè)被訪問(wèn)，根據(jù)時(shí)間局部性原理，這個(gè)頁(yè)面最近被再次訪問(wèn)的可能性非常大，因而這個(gè)正在被訪問(wèn)的冷頁(yè)會(huì)被標(biāo)記為熱頁(yè)并加入熱頁(yè)集進(jìn)行維護(hù)。

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

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

使用熱頁(yè)集的效果是避免了對(duì)大量發(fā)生在熱頁(yè)上的頁(yè)面訪問(wèn)的監(jiān)控跟蹤，也就是說(shuō)，進(jìn)入熱頁(yè)集的頁(yè)面會(huì)被清除置位標(biāo)記，從而不會(huì)因?yàn)橹梦欢l(fā)生缺頁(yè)中斷。短時(shí)間內(nèi)將會(huì)被頻繁訪問(wèn)的頁(yè)面，CPU對(duì)它們的訪問(wèn)都被熱頁(yè)集過(guò)濾掉，極大地降低了頁(yè)面跟蹤的總量，減小了頁(yè)面跟蹤的時(shí)間開(kāi)銷。

熱頁(yè)集的大小直接關(guān)系著訪存特征提取的開(kāi)銷與準(zhǔn)確性。過(guò)小的熱頁(yè)集會(huì)導(dǎo)致過(guò)量的頁(yè)面被置位標(biāo)記，帶來(lái)大的額外開(kāi)銷；過(guò)大的熱頁(yè)集會(huì)導(dǎo)致小工作集虛擬機(jī)訪存特征提取失敗，即熱頁(yè)集完全覆蓋了工作集對(duì)應(yīng)的內(nèi)存量。因此，熱頁(yè)集大小應(yīng)當(dāng)根據(jù)虛擬機(jī)的實(shí)際應(yīng)用場(chǎng)景進(jìn)行確定，以保證訪存特征提取有合理的性能開(kāi)銷和較高的準(zhǔn)確度。

2.1.4 具有熱頁(yè)集的訪存特征提取方法

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

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

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

2.2 申威平臺(tái)訪存特征提取實(shí)現(xiàn)

2.2.1 申威架構(gòu)虛擬化簡(jiǎn)介

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

Figure 3 Comparison of x86 and Sunway architecture圖3 x86與申威架構(gòu)層級(jí)對(duì)比

傳統(tǒng)x86架構(gòu)下的虛擬機(jī)訪存特征提取所依托的是Intel EPT機(jī)制，通過(guò)對(duì)EPT頁(yè)表項(xiàng)進(jìn)行置位中斷處理，就可以在虛擬機(jī)管理器(如KVM)中獲取到虛擬機(jī)的訪存地址流。申威架構(gòu)下虛擬機(jī)內(nèi)存分配采用了段式映射的方式，將虛擬機(jī)的地址直接映射到連續(xù)的物理內(nèi)存段上，避免了2級(jí)地址轉(zhuǎn)換帶來(lái)的額外開(kāi)銷。因此，在申威架構(gòu)中無(wú)法直接使用x86架構(gòu)的訪存特征提取機(jī)制 。本文結(jié)合申威架構(gòu)的特點(diǎn)，充分發(fā)揮HMCODE帶來(lái)的軟件靈活性，在申威平臺(tái)上構(gòu)建了多層協(xié)調(diào)的訪存特征提取機(jī)制。

2.2.2 多層協(xié)調(diào)的訪存特征提取實(shí)現(xiàn)接口

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

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

缺頁(yè)處理接口將被標(biāo)記頁(yè)的必要信息以參數(shù)的形式傳入內(nèi)核缺頁(yè)處理模塊，參數(shù)包括訪存地址(缺頁(yè)處理的頁(yè)面地址)、VPN(Virtual Processor Number)和UPN(User Processor Number)。VPN和UPN用于申威CPU的TLB當(dāng)中，是申威架構(gòu)獨(dú)有的用于區(qū)分虛擬機(jī)和進(jìn)程的特殊標(biāo)記。

發(fā)生缺頁(yè)中斷并進(jìn)入內(nèi)核層缺頁(yè)處理模塊的頁(yè)面，若有置位標(biāo)記，則將其清除，然后頁(yè)面進(jìn)入熱頁(yè)集存儲(chǔ)；若沒(méi)有置位標(biāo)記，則說(shuō)明該頁(yè)面是熱頁(yè)，已存在于熱頁(yè)集中。熱頁(yè)集通過(guò)一個(gè)先進(jìn)先出隊(duì)列進(jìn)行維護(hù)，熱頁(yè)集中保存著熱頁(yè)的頁(yè)幀號(hào)、VPN和UPN。若熱頁(yè)集已滿，則最舊頁(yè)面離開(kāi)熱頁(yè)集，進(jìn)入LRU模塊進(jìn)行下一步處理。

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

用戶關(guān)閉訪存特征提取后，系統(tǒng)關(guān)閉特征提取各模塊并啟動(dòng)數(shù)據(jù)分析模塊。該模塊會(huì)收集LRU模塊中采集的重用次數(shù)，繪制重用距離分布直方圖與內(nèi)存缺失率曲線，由此可以獲取申威虛擬機(jī)的工作集大小。

3 實(shí)驗(yàn)

為驗(yàn)證訪存特征提取方法的有效性和高效性，本文通過(guò)真機(jī)實(shí)驗(yàn)的方式加以驗(yàn)證，從訪存特征提取構(gòu)建的內(nèi)存缺失率曲線準(zhǔn)確性、時(shí)間開(kāi)銷和存儲(chǔ)空間開(kāi)銷3個(gè)方面進(jìn)行實(shí)驗(yàn)分析。本文以SPEC2006[20]中工作集大小大于20 MB的程序作為測(cè)試程序(共計(jì)18個(gè))，這是因?yàn)楣ぷ骷^(guò)小的程序的訪存序列會(huì)被熱頁(yè)集完全覆蓋而無(wú)法構(gòu)建重用距離分布直方圖。實(shí)際上，工作集的大小和對(duì)虛擬機(jī)內(nèi)存壓力的影響成正比，我們更關(guān)注內(nèi)存需求較大的程序。

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

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

軟件層面上，宿主機(jī)與虛擬機(jī)均采用基于Linux的深度服務(wù)器操作系統(tǒng)，每臺(tái)虛擬機(jī)分配4個(gè)物理核和4 GB的初始內(nèi)存。

3.2 內(nèi)存缺失率曲線準(zhǔn)確性檢驗(yàn)

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

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

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

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

3.3 特征提取時(shí)間開(kāi)銷

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

圖6展示的是SPEC2006測(cè)試程序有無(wú)特征提取條件下歸一化時(shí)間開(kāi)銷對(duì)比結(jié)果。申威平臺(tái)上開(kāi)啟訪存特征提取的平均時(shí)間開(kāi)銷約為8.3%，時(shí)間開(kāi)銷和程序的工作集大小成正比，程序工作集越大，訪存開(kāi)銷也就越大，提取訪存特征所帶來(lái)的額外開(kāi)銷也就越明顯，比如429.mcf的額外開(kāi)銷高達(dá)24.5%，這是因?yàn)樵摮绦虻墓ぷ骷^大(1 676 MB)。訪存特征提取的時(shí)間開(kāi)銷也與開(kāi)啟的時(shí)間有關(guān)，開(kāi)啟時(shí)間越久，開(kāi)銷越大，特征提取的準(zhǔn)確性越高，這需要折衷考慮。此外，申威平臺(tái)自身的缺陷也會(huì)影響開(kāi)銷，現(xiàn)有的申威架構(gòu)還在發(fā)展的初步階段，嚴(yán)重缺乏硬件方面的支持，比如硬件MMU以及硬件輔助虛擬化機(jī)制。

Figure 6 Comparison of normalized execution time of on/off memory access feature extraction圖6 開(kāi)啟/關(guān)閉訪存特征提取時(shí)間開(kāi)銷對(duì)比

3.4 特征提取空間開(kāi)銷

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

(2)

例如，對(duì)于一個(gè)4 GB內(nèi)存虛擬機(jī)，若熱頁(yè)集大小設(shè)定為1 600，則總的存儲(chǔ)約為6 MB，相對(duì)于4 GB的虛擬機(jī)內(nèi)存而言，訪存特征提取的存儲(chǔ)開(kāi)銷可以忽略不計(jì)。

4 結(jié)束語(yǔ)

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

在下一步工作中，將進(jìn)一步完善申威平臺(tái)的內(nèi)存虛擬化支持，并逐步實(shí)現(xiàn)多層協(xié)調(diào)的虛擬機(jī)內(nèi)存動(dòng)態(tài)調(diào)度系統(tǒng)，為國(guó)產(chǎn)服務(wù)器的發(fā)展增磚添瓦。