基于状态机控制的硬件Page Walk 方案与实现∗

路冬冬 王炳凯 杜 鑫，

（1.上海高性能集成电路设计中心 上海 201204）（2.电子科技大学电子科学与工程学院 成都 610054）

1 引言

现代操作系统通常采用页表结构管理每个进程的虚地址空间，实现虚地址到物理地址的映射。在微处理器中，访问物理地址标记（Physical Tag，PTag）的Cache时，虚实地址代换通常处于Cache访问的关键路径上，为提高虚地址到物理地址代换的速度，高性能处理器通常会使用旁路转换缓冲（Translation Lookaside Buffer，TLB）缓存虚实地址的映射关系。TLB 通常采用全相联或组相联的结构实现，访存请求在访问Cache 的同时，并行查找TLB 进行虚实地址代换，将访问TLB 代换得到的物理地址与Cache 的PTag 进行比较，判断是否命中Cache，以及组相联Cache 的命中路号［2］。由于TLB的访问处于Cache命中判断以及组相联Cache读出数据路选的关键路径上，因此其访问延迟直接影响微处理器的性能及工作频率。

当访存请求不命中TLB（TLB Miss）时，通常需要通过逐级查找页表（Page Walk）的方式，获取代换后的物理地址，并将查找页表得到的物理地址和虚地址的映射关系装入TLB 中。页表查找的开销通常是很大的，例如，在一个支持4 级页表的处理器中，Page Walk 通常需要4 次访存［1］，在支持虚拟化的处理器中，Page Walk的访存次数会更多，相关研究表明，实际应用课题的很大一部分运行时间被用于Page Walk（最高可达50%［3］）。发生TLB Miss时的处理有两种基本思路，一种是完全交给软件处理，显式使用访存指令逐级访问页表，典型代表是Sparc 处理器和MIPS 处理器［4］；另外一种是硬件自动生成访存请求，逐级访问页表，并负责将虚地址和物理地址的映射关系装入TLB 中，典型代表是x86处理器［4］。

本文提出一种基于状态机控制的硬件自动查找页表并装填TLB 的方案，同时，结合页表结构Cache（Page Structure Cache，PSC），对Page Walk 的控制状态机进行优化，进一步提升硬件Page Walk的性能。

2 相关研究工作

TLB 是微处理器中一个十分重要的部件，对于物理地址标记的Cache，其每一次访问都需要同时访问TLB 进行虚实地址代换，因此，TLB 的访问延迟、命中率及不命中时处理开销对处理器的性能具有十分重要的影响。

2.1 提高TLB的命中率

使用大页，可以在保持TLB容量相对不变的情况下，有效提升TLB 的命中率，采用大页的负面影响是存储空间的管理不够灵活，特别是当前操作系统普遍以页面为粒度管理存储空间，大页的使用会造成多方面的负面影响［5］，因此，现代微处理器普遍支持多种粒度的页面，操作系统可以根据具体课题的实际需求自主选择页面的粒度［6］。

当支持多种粒度的页面时，TLB 一般采用全相联的结构实现。全相联结构的缺点是访问延迟和功耗较大，特别是对于大容量的TLB，其访问延迟往往是处理器频率提升的瓶颈。为了在保持较低访问延迟的同时，能够使用较大TLB容量以提高其命中率，大多数处理器会使用两级或三级TLB的结构，容量较小的一级TLB 采用全相联的结构，容量较大的二级TLB和三级TLB采用组相联的结构。

TLB 的预取是另外一种能够有效提升TLB 命中率的技术，TLB 预取和数据预取具有很多相似之处，一种常见的思路都是通过对访存地址的数据流模式进行识别，预测并预取即将访问页面；常见的模式包括顺序地址流、跨步地址流以及链式地址流等。Kandiraju［7］等提出一种对页面间隔进行预测（Distance Prefetching，DP）的预取技术，例如，发生TLB Miss的页面虚地址分别是“10，11，13，14，16”，可以发现页面间隔分别是“1，2，1，2，…”，因此，可以预测即将发生TLB Miss 的页面时17 和19；TLB预取可以有效降低TLB Miss率。

2.2 降低TLB Miss的处理开销

相比软件处理TLB Miss 的方式，硬件处理TLB Miss可以显著降低TLB Miss对性能的影响，以Intel 和AMD 为代表的处理器，均采用硬件处理TLB Miss 的方法。为了进一步加快硬件Page Walk的速度，主流的商业处理器普遍会使用存储管理单元 Cache（Memory Manager Unit Cache，MMU Cache）。

以Intel 为代表处理器采用页表结构Cache（Page Structure Cache，PSC）加速硬件Page Walk 的速度。页表结构Cache 的结构类似于TLB，存储部分虚地址及对应的页表基地址的映射关系；其优点是在进行Page Walk 时，命中页表结构Cache 可以直接减少访存的次数。

以AMD 为代表的处理器采用页表查找过程Cache（Page Walk Cache，PWC）加速硬件Page Walk的速度。页表查找过程Cache 实际上是一个专用Cache，组织结构与数据Cache类似，存储Page Walk过程中访问过的数据；其优点是在进行Page Walk时，命中页表查找过程Cache 可以有效降低访存延迟。

3 基于状态机控制的硬件Page Walk方案

本文提出一种基于状态机控制的硬件Page Walk 方案，并在页面粒度最小为8KB、页表按3 级组织的情况下，具体描述状态机的设计及状态跳转。3 级页表分别是：页全局目录（Page Global Directory，PGD），页中间目录（Page Middle Directory，PMD），以及页表（Page Table，PT）。如图1 所示，专用寄存器“页表基址寄存器（Page-table Base Register，PTBR）”存储PGD的基地址，虚地址VA［42：33］用于索引PGD 条目，VA［32：23］用于索引PMD 条目，VA［22：13］用于索引PT条目。

3.1 Page Walk控制状态机的设计

硬件Page Walk控制状态机的状态跳转图如图2所示。

当请求不命中TLB 时，硬件Page Walk 的具体流程如下所示：

1）首先，跳转到AccPGD 状态，根据寄存器PTBR的值和虚地址VA［42：33］计算对应PGD条目地址，产生并发出对PGD 条目的访存请求后，状态机跳转到WTPGDAck状态，等待访存响应返回；

图1 3级页表下的虚实地址代换流程

图2 硬件Page Walk的控制状态机

2）在WTPGDAck 状态，收到访问PGD 条目的访存响应后，状态机跳转到AccPMD状态；

3）在AccPMD 状态，根据访问PGD 条目得到的数据，结合虚地址VA［32：23］计算对应PMD 条目的地址，产生并发出对PMD 条目的访存请求后，状态机跳转到WTPMDAck状态，等待访存响应返回；

4）在WTPMDAck 状态，收到访问PMD 条目的访存响应后，状态机跳转到AccPT状态；

5）在AccPT 状态，根据访问PMD 条目得到的数据，结合虚地址VA［22：13］计算对应PT 条目的地址，产生并发出对PT条目的访存请求后，状态机跳转到WTPTAck状态，等待访存响应返回；

6）在WTPTAck 状态，收到访问PT 条目的访存响应后，状态机跳转到FillTLB状态；

7）在FillTLB 状态，将访问PT 得到的数据与虚地址的页内偏移VA［12：0］进行拼接，得到最终代换出的物理地址PA，并将虚地址VA 和PA 同时装填到TLB中。

在采用3 级页表结构的情况下，硬件Page Walk 时逐级访问PGD、PMD 和PT，共需3 次访存，其优点是无需软件参与，且相比软件处理TLB Miss的方式，TLB Miss 的处理开销较小；缺点是页表结构对硬件必须可见，且不能随意更改。

3.2 页表结构Cache的设计

基于访存行为的时间局部性和空间局部性，设置一定规模的页表结构Cache，可以有效提高硬件Page Walk的性能，减少TLB Miss处理的开销；分别设置PGD Cache和PMD Cache两部分。

PGD Cache 采用全向联的组织结构和最近未使用（Least Recent Use，LRU）淘汰算法，每个条目存储虚地址VA［42：33］和对应PGD 条目的映射关系。PMD Cache 也采用全向联的组织结构和LRU淘汰算法，每个条目存储虚地址VA［42：23］和对应PMD条目的映射关系。

选取Spec2006 课题458.sjeng 作为实验对象，在国产申威处理器SW411 上记录发生TLB Miss 的访存地址流，编写脚本对TLB Miss的地址流进行分析，计算页表结构Cache 设置为不同条目数时的命中率，实验结果表1所示。

表1 不同PGD Cache条目和PMD Cache条目配置下的命中率

由表1 可见，当PGD Cache 设置为4 条目，PMD Cache 设置为32 条目时，两者均具有较高的命中率，且硬件开销相对较小。

3.3 Page Walk控制状态机的优化

增加页表结构Cache 后，对Page Walk 的控制状态机进行优化，优化后的状态机跳转图如图3 所示。

如图3 所示，当请求不命中TLB 时，硬件Page Walk的具体流程如下所示：

1）首先，进入AccPSC 状态，并行访问PGD Cache 和PMD Cache，并根据命中结果决定状态机的跳转：

（1）若命中PMD Cache，命中数据即是对应PT的基址，状态机跳转到AccPT状态；

图3 增加页表结构Cache后硬件Page Walk的控制状态机

（2）若不命中PMD Cache，命中PGD Cache，命中数据即是对应PMD 的基址，状态机跳转到AccPMD状态；

（3）若不命中PMD Cache 和PGD Cache，状态机跳转到AccPGD状态；

2）在AccPGD 状态，根据寄存器PTBR 的值和虚地址VA［42：33］计算对应PGD 条目地址，产生并发出对PGD 条目的访存请求后，状态机跳转到WTPGDAck状态，等待访存响应返回；

3）在WTPGDAck 状态，收到访问PGD 条目的访存响应后，状态机跳转到AccPMD 状态，同时将虚地址VA［42：33］和响应数据装填到PGD Cache中；

4）在AccPMD 状态，根据PGD 条目的内容，结合虚地址VA［32：23］计算对应PMD 条目的地址，产生并发出对PMD 条目的访存请求后，状态机跳转到WTPMDAck状态，等待访存响应返回；

5）在WTPMDAck 状态，收到访问PMD 条目的访存响应后，状态机跳转到AccPT 状态，同时将虚地址VA［42：23］和响应数据装填到PMD Cache中；

6）在AccPT 状态，根据PMD 条目的内容，结合虚地址VA［22：13］计算对应PT 条目的地址，产生并发出对PT 条目的访存请求后，状态机跳转到WTPTAck状态，等待访存响应返回；

7）在WTPTAck 状态，收到访问PT 条目的访存响应后，状态机跳转到FillTLB状态；

8）在FillTLB 状态，将访问PT 得到的响应与虚地址的页内偏移VA［12：0］进行拼接，得到最终代换出的物理地址PA，并将虚地址VA 和PA 同时装填到TLB中。

相比3.1节中的处理，当请求不命中TLB时，首先访问页表结构Cache，并根据页表结构Cache 的命中情况进行Page Walk，当命中PMD Cache 时，Page Walk只需一次访存就能得到代换后的物理地址；当命中PGD Cache 时，Page Walk 需要两次访存就能到的代换后的物理地址。只有不命中页表结构Cache时，Page Walk才需要三次访存。通过选择合理的结构和条目数，在页表结构Cache 命中率较高时，可以有效降低Page Walk的访存次数，显著减低TLB Miss的处理开销。

4 结语

TLB 作为处理器中的重要部件，其访问延迟、命中率及不命中处理开销对处理器的性能具有重要影响。本文首先对三级页表结构下的虚实地址代换流程进行了研究分析，并提出一种基于状态机控制的硬件Page Walk方案，同时，通过使用页表结构Cache，对Page Walk 的控制状态机进行了优化；当命中页表结构Cache时，可以显著减少Page Walk的访存次数，降低TLB Miss的处理开销。高性能处理器普遍采用硬件Page Walk 的方式处理TLB Miss，本文提出的基于状态机控制的硬件Page Walk方案及页表结构Cache的设计，对于国产高性能微处理器的设计具有一定的指导意义。