利用內(nèi)存映射連續(xù)性提高TLB地址覆蓋范圍的技術(shù)評(píng)測(cè)

班義琨 張煒奇 周昱晨 易江芳

研究簡(jiǎn)報(bào)

利用內(nèi)存映射連續(xù)性提高TLB地址覆蓋范圍的技術(shù)評(píng)測(cè)

班義琨 張煒奇 周昱晨 易江芳?

北京大學(xué)信息科學(xué)技術(shù)學(xué)院系統(tǒng)結(jié)構(gòu)研究所, 北京 100871; ?通信作者, E-mail: yijiangfang@mprc.pku.edu.cn

定義并評(píng)測(cè)典型基準(zhǔn)測(cè)序程序內(nèi)存映射中的連續(xù)性分布, 驗(yàn)證程序的內(nèi)存映射中普遍存在多樣的連續(xù)性(混合連續(xù)性)。對(duì)利用內(nèi)存映射連續(xù)性提高 TLB 翻譯覆蓋范圍的技術(shù)進(jìn)行評(píng)測(cè), 發(fā)現(xiàn)混合連續(xù)性的存在能夠限制現(xiàn)有技術(shù)在真實(shí)場(chǎng)景中的實(shí)際效果。

虛擬存儲(chǔ); 混合連續(xù)性; 變換旁路緩沖器

虛擬存儲(chǔ)技術(shù)在通用計(jì)算機(jī)系統(tǒng)中普遍使用, 并且逐漸應(yīng)用到像圖形處理器(graphics processing unit, GPU)等加速器中[1–3]。變換旁路緩沖器(tran-slation lookaside buffer, TLB)對(duì)虛擬地址(VPN)到物理地址(PPN)的翻譯性能十分關(guān)鍵。然而, 由于高內(nèi)存占用的程序引發(fā)的存儲(chǔ)容量需求逐漸增大, 地址翻譯的時(shí)間開(kāi)銷(xiāo)也越來(lái)越大, 甚至可以達(dá)到實(shí)際執(zhí)行時(shí)間的 50%[4]。為了減少頁(yè)表遍歷(page table walk)的開(kāi)銷(xiāo), 許多方法都利用內(nèi)存映射中存在的連續(xù)性來(lái)擴(kuò)大 TLB 表項(xiàng)的覆蓋范圍[5–9]。

本文通過(guò)對(duì)廣泛使用的基準(zhǔn)測(cè)試程序進(jìn)行連續(xù)性評(píng)測(cè), 并定量地分析各種連續(xù)性的分布情況, 發(fā)現(xiàn)大多數(shù)程序中都存在不止一種連續(xù)性。通過(guò)分析和評(píng)測(cè)一些現(xiàn)存的擴(kuò)大 TLB 地址覆蓋范圍的技術(shù), 發(fā)現(xiàn)這些技術(shù)都采用合并表項(xiàng)或合并頁(yè)面的 TLB結(jié)構(gòu), 能夠匹配的連續(xù)性是單一的甚至固定的, 未能充分利用存在的多種連續(xù)性, 所以在真實(shí)場(chǎng)景下不能獲得理想的效果。

1 內(nèi)存映射中的連續(xù)性

本文使用連續(xù)性來(lái)描述程序執(zhí)行過(guò)程中內(nèi)存映射中的連續(xù)塊分布。

定義 1 連續(xù)塊表示頁(yè)表中多個(gè)頁(yè)的集合, 這些頁(yè)的虛擬地址和物理地址都是連續(xù)的, 不存在一個(gè)連續(xù)塊包含另一個(gè)連續(xù)塊的情況。連續(xù)塊的大小指塊中頁(yè)的數(shù)量。

1.1 連續(xù)性的多樣性

應(yīng)用程序是復(fù)雜多樣的, 不同的應(yīng)用程序在運(yùn)行時(shí), 內(nèi)存映射中的連續(xù)性也是多樣的。根據(jù)連續(xù)塊的大小, 內(nèi)存映射中存在的連續(xù)性分為 3 類(lèi)。

第 1 類(lèi)連續(xù)性指程序中存在大小為 512 個(gè)及以上頁(yè)面的連續(xù)塊, 稱(chēng)為大連續(xù)性。透明超頁(yè)(trans-parent huge page, THP)[5]是這類(lèi)連續(xù)性的典型體現(xiàn)。如 x86-64 架構(gòu)支持使用 2MB 和 1GB 的超頁(yè)分別代替 512 和 512×512 個(gè)連續(xù)映射的 4KB 基本頁(yè)。

與大連續(xù)性相反, 第 2 類(lèi)連續(xù)性指程序中存在大小為 32 個(gè)及以下頁(yè)面的連續(xù)塊, 稱(chēng)為小連續(xù)性。這類(lèi)連續(xù)性在碎片化的內(nèi)存映射中很普遍。當(dāng)系統(tǒng)運(yùn)行一段時(shí)間后, 正在使用中的頁(yè)(尤其是大連續(xù)塊的分布)使得很難在內(nèi)存中找到大型連續(xù)區(qū)域, 限制了新的大連續(xù)塊的分配。另外, 常見(jiàn)的 NUMA架構(gòu)需要利用細(xì)粒度的內(nèi)存映射, 將經(jīng)常訪(fǎng)問(wèn)的頁(yè)面放在靠近內(nèi)存的位置, 如 3D 堆疊式DRAMs[10]、基于網(wǎng)絡(luò)的混合存儲(chǔ)立方體(HMC)[11]和非易失性存儲(chǔ)器(NVM)[12], 這導(dǎo)致更嚴(yán)重的內(nèi)存碎片[13]。

第 3 類(lèi)連續(xù)性介于大連續(xù)性與小連續(xù)性之間, 稱(chēng)為中連續(xù)性。在這類(lèi)連續(xù)性下分布的連續(xù)塊比細(xì)粒度的內(nèi)存映射大, 但比超頁(yè)小。一些研究已在許多真實(shí)應(yīng)用程序中發(fā)現(xiàn)中連續(xù)性[7–9]。

事實(shí)上, 內(nèi)存分配是雜亂且碎片化的, 所以真實(shí)系統(tǒng)中幾乎不會(huì)只存在單一類(lèi)型的連續(xù)性。程序中包含不止一種連續(xù)性的情況稱(chēng)為混合連續(xù)性。

1.2 連續(xù)性評(píng)測(cè)

我們使用一臺(tái) 4 核 Intel Core i7-7700HQ, 頻率為 2.8 GHz 的 x86-64 機(jī)器進(jìn)行評(píng)測(cè), 內(nèi)存為 4GB, 操作系統(tǒng)為 Linux 4.16。預(yù)熱后, 周期性地記錄內(nèi)存映射中的連續(xù)塊分布, 用以評(píng)測(cè)應(yīng)用程序運(yùn)行時(shí)內(nèi)存映射中的連續(xù)性。使用 SPEC CPU 2006[14]和Graph500 中的基準(zhǔn)測(cè)試程序, 其中 Graph500 工作集的大小設(shè)置為 8 GB。

使用 Linux 提供的 pagemap[15]接口獲得虛擬地址和物理地址的映射。在程序執(zhí)行過(guò)程中, 每分鐘掃描一次進(jìn)程的頁(yè)表, 并記錄連續(xù)性信息。

在執(zhí)行過(guò)程中采用上述連續(xù)塊分類(lèi)。15 個(gè)評(píng)測(cè)程序連續(xù)塊大小分布的平均情況如圖 1 所示。為了排除 THP 技術(shù)[5]的影響, 統(tǒng)計(jì) THP 開(kāi)和關(guān)時(shí)的連續(xù)塊大小分布?？梢园l(fā)現(xiàn), 無(wú)論 THP 如何設(shè)置, 除 hmmer 程序只有小連續(xù)性外, 幾乎所有程序的內(nèi)存映射中都會(huì)同時(shí)出現(xiàn)多種連續(xù)性。例如, 應(yīng)用程序 mcf 在執(zhí)行過(guò)程中的連續(xù)塊有小、中、大 3 種連續(xù)性, 并且每種連續(xù)性的連續(xù)塊數(shù)量都占據(jù)一定的比例。與不使能 THP 相比, 使能 THP 時(shí)有更多的應(yīng)用程序(如 omnetpp)呈現(xiàn)大連續(xù)性, 這是因?yàn)門(mén)HP 技術(shù)使得在程序執(zhí)行過(guò)程中, 一些小連續(xù)塊或中連續(xù)塊合并成為大連續(xù)塊。

2 TLB失效評(píng)測(cè)

到目前為止, 已經(jīng)有許多技術(shù)考慮到利用內(nèi)存映射的連續(xù)性來(lái)擴(kuò)大 TLB 地址的覆蓋范圍。

2.1 評(píng)測(cè)技術(shù)

THP[5]是 Linux 操作系統(tǒng)中超頁(yè)(2MB)的一個(gè)實(shí)現(xiàn), 使用超大頁(yè)面代替原本連續(xù)的一系列基本頁(yè)面。但是, 由于超頁(yè)的大小是固定的, 而待分配的連續(xù)塊大小是多樣的, 所以勢(shì)必造成超頁(yè)空間的浪費(fèi), 導(dǎo)致在擴(kuò)大 TLB 覆蓋范圍時(shí)有很大的局限性, 并只能匹配固定大小的連續(xù)塊。

RMM[6]中引入基于硬件的段來(lái)完全覆蓋連續(xù)塊, 排除了頁(yè)的尺寸限制, 但需要添加額外的段TLB。段 TLB 的硬件結(jié)構(gòu)是全相聯(lián)的, 每個(gè)段都覆蓋一個(gè)非常大的連續(xù)塊, 因此操作系統(tǒng)需要做出重大改變來(lái)保持這種分配。與 THP 類(lèi)似, RMM 可以覆蓋大連續(xù)塊, 但會(huì)忽視小連續(xù)塊和中連續(xù)塊。因此, 在具有混合連續(xù)性的真實(shí)場(chǎng)景中, 段 TLB 技術(shù)的效果必然會(huì)受到影響。

CoLT[7]和 Cluster[9]是兩種基于硬件的合并技術(shù), 用于應(yīng)對(duì)小連續(xù)性或者單一連續(xù)性。改進(jìn)后的 TLB 表項(xiàng)最多覆蓋大小為 8 的連續(xù)塊, 隨著程序執(zhí)行中連續(xù)塊大小的增加, 需要改進(jìn)的表項(xiàng)數(shù)目不斷增加。例如, 一個(gè)大連續(xù)塊(512)需要大量(至少64 個(gè))合并表項(xiàng)才能完全覆蓋。然而, 這些技術(shù)的TLB 結(jié)構(gòu)擴(kuò)展性較差, 無(wú)法滿(mǎn)足連續(xù)性的不斷增長(zhǎng)。

Anchor[8]引入錨表項(xiàng)的概念。錨表項(xiàng)在普通頁(yè)表項(xiàng)之間均勻分布, 以便記錄連續(xù)性。通過(guò)調(diào)整頁(yè)表中最優(yōu)的錨距離, 可以適配連續(xù)塊的大小。具體地, 在頁(yè)表中每(錨距)個(gè)表項(xiàng)中都放置一個(gè)錨表項(xiàng), 記錄連續(xù)頁(yè)面的數(shù)量。例如, 如果內(nèi)存頁(yè)被分配大小為 16 的連續(xù)塊, 那么最優(yōu)的錨距離就是16。然而, 對(duì)于比錨距大的連續(xù)塊, 就需要多個(gè)錨表項(xiàng)才能覆蓋。對(duì)于比錨距離小的連續(xù)塊, 如果在塊與相應(yīng)的錨表項(xiàng)之間存在不連續(xù)的頁(yè), 就會(huì)被忽略。所以在一個(gè)時(shí)期, Anchor 只能匹配一種類(lèi)型的連續(xù)性, 并且會(huì)使操作系統(tǒng)增加較大的開(kāi)銷(xiāo)。

2.2 TLB 參數(shù)設(shè)置

表 1 展示以上技術(shù)中 TLB 的配置, 盡量保證各種技術(shù)間 TLB 配置的一致性以及每種方法在效果上的最優(yōu)選擇。所有方法 L1 TLB 的配置都相同, L2TLB 容量設(shè)置為 1024 個(gè)表項(xiàng)。除常規(guī)的 L2TLB外, Cluster需要額外的合并 TLB, RMM 需要增加一個(gè) 32 個(gè)表項(xiàng)的全相聯(lián)段 TLB。

2.3 評(píng)測(cè)結(jié)果

對(duì)于現(xiàn)有技術(shù), 仍然使用評(píng)測(cè)連續(xù)性時(shí)的應(yīng)用程序進(jìn)行評(píng)測(cè), 用 TLB 失效率來(lái)評(píng)估每個(gè)技術(shù)的效果。TLB 配置與文獻(xiàn)[8]中的現(xiàn)有技術(shù)相同(表 1)。THP 是 Linux 系統(tǒng)的自帶實(shí)現(xiàn), Cluster 和 RMM 需要額外的硬件結(jié)構(gòu)來(lái)支持。以基本配置的 TLB 為基準(zhǔn), 對(duì)所有應(yīng)用程序在各種技術(shù)下的 TLB 失效進(jìn)行歸一化, 結(jié)果見(jiàn)圖 2。

表1 評(píng)估中使用的TLB的配置[8]

對(duì)不同的基準(zhǔn)測(cè)試程序, 不同方法減少的 TB失效也不同, 原因是基準(zhǔn)測(cè)試程序相應(yīng)的連續(xù)性分布與不同方法對(duì)各類(lèi)連續(xù)性的利用側(cè)重點(diǎn)不同。操作系統(tǒng)分配的連續(xù)塊越多, 可以擴(kuò)大的 TLB地址覆蓋范圍就越大, 不同方法的性能差異也越大。

有些應(yīng)用程序在各種技術(shù)下都會(huì)減少一定的TLB 失效, 呈現(xiàn) TLB 失效的階梯式下降。例如, 應(yīng)用程序 zeusmp 在執(zhí)行過(guò)程中同時(shí)呈現(xiàn) 3 種連續(xù)性, 所以 THP 和 RMM 可以利用大連續(xù)性來(lái)減少 TLB失效, 同時(shí) CoLT 和 Cluster 可以利用小連續(xù)性進(jìn)一步減少更多的 TLB 失效。有些程序在執(zhí)行過(guò)程中連續(xù)性較單一, 所以只有一類(lèi)利用同種連續(xù)性的技術(shù)效果明顯。例如, 應(yīng)用程序 gromacs 在執(zhí)行過(guò)程中未呈現(xiàn)大連續(xù)性, 并且中連續(xù)性對(duì)應(yīng)的連續(xù)塊數(shù)量也較少, 所以 THP 和 RMM 幾乎沒(méi)有減少 TLB 失效。相反地, 主要利用小連續(xù)性的 CoLT 和 Cluster就取得很好的效果。應(yīng)用程序 graph500, THP 和RMM, 可以減少很大部分的 TLB 失效, 但再使用CoLT 和 Cluster 時(shí), 幾乎沒(méi)有進(jìn)一步的效果。

作為目前最先進(jìn)的技術(shù), Anchor 在一些應(yīng)用程序上的效果很好。例如, 應(yīng)用程序 libquantum, 因其與 zeusmp 類(lèi)似地呈現(xiàn)出多種連續(xù)性, 所以關(guān)注于大連續(xù)性和小連續(xù)性的技術(shù)都取得一定的效果。Anchor 技術(shù)在這個(gè)應(yīng)用程序中的表現(xiàn)格外好, 幾乎消除所有的 TLB 失效。但是, Anchor 在某些應(yīng)用程序中的表現(xiàn)仍不如人意。例如, 應(yīng)用程序 hmmer 在所有技術(shù)下都很難減少 TLB 失效, 包括 Anchor。

3 結(jié)論

本文首先定義內(nèi)存映射中存在的多種連續(xù)性; 然后評(píng)測(cè)并定量地分析一些典型基準(zhǔn)測(cè)序程序內(nèi)存映射中的連續(xù)性分布, 驗(yàn)證了程序的內(nèi)存映射中普遍存在多樣連續(xù)性(混合連續(xù)性); 最后對(duì) THP, RMM, CoLT, Cluster 和 Anchor 等現(xiàn)有技術(shù)進(jìn)行 TLB 失效評(píng)測(cè), 發(fā)現(xiàn)混合連續(xù)性的存在限制了現(xiàn)有技術(shù)在真實(shí)場(chǎng)景中的實(shí)際效果。綜上所述, 需要提出新的結(jié)構(gòu)和技術(shù), 可以充分利用內(nèi)存映射中的混合連續(xù)性, 進(jìn)一步改善虛擬存儲(chǔ)系統(tǒng)的性能。

[1] AMD Corporation. Compute cores [EB/OL]. (2014–01) [2019–10–01]. https://www.amd.com/Documents/ Compute_Cores_Whitepaper.pdf

[2] Swapnil H, Mark D H, Michael M S. Devirtualizing memory in heterogeneous systems // ACM International Conference on Architectural Support for Program-ming Languages and Operating Systems. Williams-burg, 2018, 53: 637–650

[3] Olson L E, Power J, Hill M D, et al. Border control: sandboxing accelerators // IEEE/ACM International Symposium on Microarchitecture. Waikiki, 2015: 470–481

[4] Basu A, Gandhi J, Chang J, et al. Efficient virtual memory for big memory servers. Computer Architec-ture News, 2013, 41(3): 237–248

[5] Linux Kernel Documentation. Transparent hugepage support [EB/OL]. (2017) [2019–10–01]. https://www. kernel.org/doc/Documentation/vm/transhuge.txt

[6] Karakostas V, Gandhi J, Ayar F, et al. Redundant memory mappings for fast access to large memories // ACM SIGARCH Computer Architecture News. Port-land, OR, 2015, 43: 66–78

[7] Pham B, Vaidyanathan V, Jaleel A, et al. CoLT: coa-lesced large-reach TLBs // IEEE/ACM International Symposium on Microarchitecture. Vancouver, 2012: 258–269

[8] Park C H, Heo T, Jeong J, et al. Hybrid TLB coales-cing: improving TLB translation coverage under di-verse fragmented memory allocations. Computer Ar-chitecture News, 2017, 45(2): 444–456

[9] Pham B, Bhattacharjee A, Eckert Y, et al. Increasing TLB reach by exploiting clustering in page transla-tions // International Symposium on High Performa-nce Computer Architecture. Orlando, 2014: 558–567

[10] Loh G H. 3D-stacked memory architectures for multi-core processors // ACM SIGARCH computer archi-tecture news. Beijing, 2008, 36: 453–464

[11] Pawlowski J T. Hybrid memory cube (HMC) // Hot Chips 23 Symposium. Stanford, 2011: 1–24

[12] Dulloor S R, Roy A, Zhao Z, et al. Data tiering in heterogeneous memory systems // European Confe-rence on Computer Systems. London, 2016: 1–16

[13] Park C H, Heo T, Huh J. Efficient synonym filtering and scalable delayed translation for hybrid virtual caching. ACM SIGARCH Computer Architecture News, 2016, 44(3): 217–229

[14] Henningjohn L. SPEC CPU2006 benchmark descrip-tions. ACM SIGARCH Computer Architecture News, 2006, 34(4): 1–17

[15] Linux Kernel Documentation. Pagemap, from the userspace perspective [EB/OL]. (2016) [2019–10–01]. https://www.kernel.org/doc/Documentation/vm/pagemap.txt

Evaluation of Technologies Improving Translation Coverage of TLB Using Continuity of Memory Mapping

BAN Yikun, ZHANG Weiqi, ZHOU Yuchen, YI Jiangfang?

School of Electronics Engineering and Computer Science, Peking University, Beijing 100871; ? Corresponding author, E-mail: yijiangfang@mprc.pku.edu.cn

The authors define and evaluate the continuity distribution in memory mapping of some typical benchmark programs, and verifiy the existence of multiple types of continuity (mixed continuity) in memory mapping of programs. Furthermore, some technologies using continuity of memory mapping to improve translation coverage of TLB are evaluated. It is found that the existence of mixed continuity limits the actual effect of existing technologies in real scenes.

virtual memory; mixed continuity; TLB (translation lookaside buffer)

10.13209/j.0479-8023.2020.101

國(guó)家科技重大專(zhuān)項(xiàng)(2018ZX01029101)資助

2019–11–28;

2020–02–04