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

工程论文 2020-05-07 09:41199未知xhm
  摘要:在现代微处理器中,虚实地址代换一般处于Cache访问的关键路径上,旁路转换缓冲(TLB)作为虚实地址代换的专用缓冲,用于提高虚实地址代换的速度。当不命中TLB时,需要逐级查找页表以获取代换后的物理地址。论文提出一种基于状态机控制的硬件自动查找页表并装填TLB的方案,并给出具体实现;同时,结合页表结构Cache,对状态机进行优化,进一步提升硬件查找页表的速度,降低TLB Miss的处理开销。
  关键词:虚实地址代换; 旁路转换缓冲; 页表; 页表查找; 页表结构Cache;

  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状态,根据寄存器PT-BR的值和虚地址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的基址,状态机跳转到AccP-MD状态;
  (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的设计,对于国产高性能微处理器的设计具有一定的指导意义。
  参考文献
  [1]Li Y,Melhem R,Jones A K.PS-TLB:Leveraging page classification information for fast,scalable and efficient translation for future CMPs[J].Acm Transactions on Architecture&Code Optimization,2013,9(4):1-21.
  [2]Taylor G,Davies P,Farmwald M.The TLB slice-a low-cost high-speed address translation mechanism[C]//[1990]Proceedings.The 17th Annual International Symposium on Computer Architecture.IEEE,1990:355-363.
  [3]Talluri M,Hill M D.Surpassing the TLB performance of superpages with less operating system support[J].Acm Sigplan Notices,1994,29(11):171-182.
  [4]Bhattacharjee A,Martonosi M.Characterizing the TLB behavior of emerging parallel workloads on chip multiprocessors[C]//2009 18th International Conference on Parallel Architectures and Compilation Techniques.IEEE,2009:29-40.
  [5]Chen L,Wang Y,Cui Z,et al.Scattered superpage:Acase for bridging the gap between superpage and page coloring[C]//2013 IEEE 31st International Conference on Computer Design(ICCD).IEEE,2013:177-184.
  [6]Karakostas V,Gandhi J,Cristal A,et al.Energy-efficient address translation[C]//2016 ieee international symposium on high performance computer architecture(hpca).IEEE,2016:631-643.
  [7]Kandiraju G B,Sivasubramaniam A.Going the distance for TLB prefetching:an application-driven study[C]//Proceedings 29th Annual International Symposium on Computer Architecture.IEEE,2002:195-206.
  [8]Borg A,Chen J B,Jouppi N P.A simulation based study of TLB performance[C]//[1992]Proceedings the 19th Annual International Symposium on Computer Architecture.IEEE,1992:114-123.
  [9]Talluri M,Kong S,Hill M D,et al.Tradeoffs in supporting two page sizes[J].ACM SIGARCH Computer Architecture News,1992,20(2):415-424.
  [10]Bala K,Kaashoek M F,Weihl W E.Software prefetching and caching for translation lookaside buffers[C]//Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation.USENIX Association,1994:18.

53学术论文网 Copyright @ 53论文网 All Rights Reserved. 版权所有


友情链接: WMS仓储管理系统 北京财经网 宁夏质量体系认证 一对一辅导班加盟 热变形维卡试验机 磁浮子液位计 北京文学网 天津文学网 上海文学网 重庆文学网 石家庄文学网 沈阳文学网 哈尔滨文学网 层流送风天花 均相反应器 十六烷基三甲基氯化 恒温恒湿试验箱 船舶电缆 进口细胞株 延庆文学网 普宁文学网 石嘴山文学网 鹤岗文学网 乐昌文学网 新竹文学网

在线客服系统