☕️ 并行化地址翻译

论文浏览笔记 弹性布谷哈希页表

Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism

https://dl.acm.org/doi/pdf/10…

​

???? 简介

???? 根本思维

将传统多层基数页表的程序指针追踪，转化为齐全并行查找，第一次实现了内存级并行的地址翻译。

???? 背景

• 地址转换是存取的性能瓶颈
• 传统多层基数页表的程序指针追踪，没有充分利用内存级并行，理当被取代。
• 哈希页表局限：空间局部性的缺失；每个页表项都须要哈希标签，耗费更多空间；哈希抵触须要屡次存取操作。（前两项可通过精心设计页表[73]来解决，页表项汇集和压缩）
• 凋谢地址、链地址需昂扬存取开销。为防止哈希抵触，哈希页表需动静调整大小，开销大。
• 繁多全局哈希页表的毛病：在不减少额定地址翻译层下，不反对过程间页表共享、多种页表大小；完结过程时，需线性扫描整个页表，删除相干项。
• 可调整大小的哈希页表：超过占用阈值，需调配新的大哈希表，需从新哈希、迁徙到新哈希表，十分耗时。
• 渐进式可调整大小的哈希页表：保护新、旧哈希表约需两倍内存开销；需查找新、旧页表，两倍cache存取时间。
• 布谷哈希：多个哈希函数，踢出法。

???? 弹性布谷页表

• 地址翻译时应用齐全并行查找，升高指针追踪开销。
• 应用弹性布谷哈希，这种哈希无效反对页表大小动静调整。
• 这种页表可无效解决哈希抵触，提供过程公有页表，反对多种页表大小，反对过程间共享页表，以及按需动静调整页表大小。
• 试验：8核处理器全系统模拟，包含图剖析、生物信息学、HPC、零碎负载试验。与传统基数页表相比，在地址转换上有41%晋升，在应用程序执行上有3-18%的减速。

???? 弹性布谷哈希

$d$-路布谷哈希。

从旧$d$-表路中随机选取一路$T_i$，用哈希函数$H_i$，若哈希值落在live区，直接插入；否则，应用新的$d$-路表的同一路$T_i’$的哈希函数$H_i’$，被踢出的元素插入$T_i’$。

查找元素只需$d$次探查：应用旧的$d$-表的所有$H_D$函数，对每一路，若哈希值落在live区，则探查到，否则应用$T_i’$。

从两方面改良布谷哈希的渐进式扩大：$d$次探查（存取），而非$2d$次；不用从旧表的迁徙区取条目到cache中。

???? Rehash

???? Look-up

能够并行化。

例子：

case1：探查$T_1[H_1(x)],T_2[H_2(x)]$

case2：探查$T_1′[H_1′(x)],T_2′[H_2′(x)]$

case3：探查$T_1′[H_1′(x)],T_2[H_2(x)]$

case4：探查$T_1[H_1(x)],T_2′[H_2′(x)]$

???? Delete

查找到后，革除条目。耗时与Look-up雷同。

???? Insert

• $d$ 组中随机选取一组$i$
• 若$H_i(x) \ge P_i $，元素插入$T_i[H_i(x)]$地位；否则，插入$T_i'[H_i'(x)]$ 地位
• 若原来的地位有元素$y$，则$y$被踢出。从剩下的路中随机选一组，对$y$进行同样的插入操作。

​ ⊥示意空值

???? Hash Table Resize

• 参数：再哈希阈值 $r_t$ ，乘法因子 $k$。 一个哈希表的占有率达到 $r_t$ 时，调配一个新的哈希表，其大小为原来的 $k$ 倍。
• 选$ r_t $ ，使得有较小的插入抵触和渺小的插入失败。$d$ = 3 时，较好的 $r_t$ 为0.6或更小。
• 选$k$， 使得不占用过多间断内存，且不造成过多页表大小调整。
• $ k > (r_t + 1) / r_t $ （附录A）
• 若在调整大小之外产生插入失败，则触发调整大小；若在调整大小期间产生插入失败，则将多个元素散列到其余中央，再从新插入。 试验证实，选取适合的 $r_t$，可完全避免插入失败。
• downsize参数：downsize阈值 $d_t$, downsize 因子 $g$。

???? 弹性布谷哈希页表

???? 结构

多级独立页表，可反对任意大小的页面。（基数页表只能反对固定几种大小的）

两层并行：（与基数页表不同）

• 并行查找独立的页表（有cache减速）
• 并行查找不同的组

页表项：8个PTE项和1个tag放在一个cache line里。

Cuckoo Walk

???? Cuckoo Walk Tables

• 有PUD-CWT, PMD-CWT, PTE-CWT：渐进保留更细粒度的信息，按程序拜访。
• 为缩小提早，将它们缓存到MMU的Cuckoo walk caches (CWCs)。只缓存前两个。缓存PTE-CWT提供的局部性太少（相似于基数页表不缓存PTE项）
• OS线程应用锁更新PUD-CWT和PMD-CWT。

CMT项：蕴含一个VPN标签、多个间断的Section头，一个项占一个缓存行。Section是虚拟内存地址范畴。每个section头保留由页表中一个条目映射的虚拟内存段的信息（指定该section中页面的大小、页表哪一组保留着这个section对应的翻译）。

如图。2MB位：该section是否映射到一或多个2MB页面；4KB位：该section是否映射到一或多个4KB页面。仅当2MB位为1时，最初的way bits才有意义（哪一组）。

含意：

调配2MB和4KB页面时，2MB bit和4KB bit第一次更新。当4KB页面调配或rehash时，way bits不用更新。

PUD-CWT 相似于PMD-CWT。每个section头有5bit：1GB位、2MB位、4KB位、2 way bits（记录1GB页面映射到哪一路）。

???? Cuckoo Walk Caches

• CWCs缓存页大小、路信息（传统的基数页表游走缓存存页表项），CWC项十分小、命中率高。
• CWC 和 CWT 可独立拜访

???? 地址翻译过程

（这里假如没有1GB的页）

TLB缺失后，页表游走硬件查看PUD-CWC。失去翻译后果，写回TLB。

• PUD-CWC命中，3种状况：仅4KB，⑤失去翻译后果或页缺失；后两种，访PMD-CWC。
• PMD-CWC命中，3种状况。
• PMD-CWC缺失，应用PUD-CWC的信息进一步探查，2种状况。
• PUD-CWC缺失，拜访PWD-CWC。
• 若思考1GB的页，PUD-CWC缺失和PMD-CWC命中，须要取出PUD-CWT项。

???? 并发管制

• 页缺失时，仍可查找。相似于Linux下基数页表的并发解决。OS更新弹性布谷页表或CWT时，应用锁。读线程临时读到旧的数据。
• 应用同步和原子指令执行：插入、挪动（way间、resize时不同页表间）、更新重哈希指针、更新CWT。
• 若应用CWC的内容去找地址映射而失败了，再次执行游走：只拜访指标页表的残余路（若呈现resize，则拜访两个页表的残余way）。这就会发现条目挪动到另一路。这样CWC的旧条目就失去更新。

???? 试验

baseline 4 KB, Cuckoo 4KB; baseline THP, Cuckoo THP. (THP：通明大页面)

• 图利用：2个社交图剖析算法（BC, DC）；2个图遍历算法；单源点最短门路（SSSP)；连通分支（CC）；三角计数（TC）；PageRank
• 生物信息：BioBench suite的MUMmer。
• HPC：GUPS，度量整数随机内存更新。
• 零碎：SysBench suite的内存基准测试。

试验做得挺充沛……学学……

???? 其余

作者的后续工作：将弹性布谷哈希页表用于虚拟环境。

缩小TLB缺失的办法：clustering, coalescing, contiguity, prefetching, speculative TLBs, large part-of-memory TLBs

减少TLB reach的办法：OS层改良的大页面反对，去虚拟化内存，应用程序治理虚拟内存。

这些办法着眼于制作translation contiguity：大的间断虚拟空间映射到大的物理间断空间。这可缩小翻译，升高TLB缺失率，从而缩小多步页面游走。

然而，大面积的连续性毁坏了内核和其他软件享有的映射灵活性 counterproductive performance-wise。

该论文着眼于通过一个单步翻译过程来大大降低page walk的开销，同时保护了内核和其他软件的现有的形象。因此，不须要连续性，且保留了以后零碎的映射灵活性。

未懂：

• 乘法因子选取的论证（附录A）