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

研究簡報

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 連續(xù)性評測

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

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

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

2 TLB失效評測

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

2.1 評測技術(shù)

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

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

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

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

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

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

2.3 評測結(jié)果

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

表1 評估中使用的TLB的配置[8]

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

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

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

3 結(jié)論

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

國家科技重大專項(2018ZX01029101)資助

2019–11–28;

2020–02–04