乐趣区

关于操作系统:ASPLOS2020Elastic-Cuckoo-Page-Tables

☕️ 并行化地址翻译

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

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)
退出移动版