申威架构下的虚拟机访存特征提取方法*

沙 赛，王 超，杜翰霖，罗英伟，汪小林，王振林

(1.北京大学信息科学技术学院,北京100871;2.江南计算技术研究所,江苏 无锡 214083;3.密歇根理工大学计算机系，霍顿 密歇根州 49246)

1 引言

近年来，以申威(Sunway)、飞腾、龙芯为主要代表的国产CPU不断发展。国产超级计算机神威·太湖之光的成功确定了申威在国产CPU界的重要地位。申威架构已经成为诸多国产领域的主流CPU架构，特别是在政府部门等对于自主可控、安全高效要求较高的部门[1]。作为国产CPU的典型代表，申威CPU备受关注，近年来涌现了一批申威平台的学术成果[2]。申威架构指令集源自Alpha架构指令集，在此基础上进行了优化和多方面的扩展，已形成独有的申威扩展指令集[3]。如今中美贸易摩擦不断，坚持自主可控，提升国产CPU芯片的性能势在必行。国内已经基本形成了CPU架构到操作系统内核专业定制，再到PC操作系统与服务器操作系统桌面化设计，最后到国产系统应用程序适配的一整套完整国产申威架构生态链。如何充分发挥国产CPU性能、如何充分利用国产CPU架构新特性是操作系统内核设计者的主要工作内容。随着国家信息化程度的不断提高，国产服务器的应用不再仅仅限制于简单的办公桌面系统，而是面向市场更为广阔的云服务系统。

虚拟化是云服务的重要支撑技术之一。虚拟化是指将一台物理计算机系统虚拟化为一台或多台虚拟计算机系统(虚拟机)。每台虚拟机都拥有自己的虚拟硬件(如CPU、内存等)来对外提供一个独立且完整的计算机执行环境[4]。虚拟化可提供多个隔离的执行环境，这种将运行环境完整地封装带来了明显优势:多个虚拟机之间具有很强的隔离性，虚拟机和硬件之间没有关联，并且在功能上可以实现整机的快照、克隆和挂起等功能，灵活多样[4,5]。在一台计算机上运行多个虚拟机使得资源的调度更为优化。虚拟化具有多样的功能和灵活性，同时也带来了诸多问题。虚拟化主要分为CPU虚拟化、内存虚拟化和I/O虚拟化3个方面。其中，内存虚拟化是最为复杂的部分，内存虚拟化的优劣往往成为虚拟机系统性能的瓶颈[4]。就内存虚拟化技术而言，主要面临2个方面的问题，一是如何降低内存虚拟化带来的额外开销。虽然内存虚拟化技术日益成熟，但很多应用场景下仍存在着不小的性能开销。二是如何充分利用虚拟化的灵活性来提高多虚拟机内存的利用率[6]。大数据时代背景下，云服务所承载的程序需要的内存量越来越大，虚拟机内存资源利用率低，分配不均衡的问题日益突出[7]。本文主要就国产服务器如何有效解决虚拟机内存利用率低的问题展开讨论。

相较于以x86为代表的国际主流CPU架构服务器，申威仍处于较为初步的阶段，就单核性能而言，仍有数倍差距，但核数众多是申威服务器的优势。多核服务器很好地满足了多任务操作系统对于CPU的需求，但是激烈的内存竞争是限制其性能的主要瓶颈之一。根据调查目前国内外知名的云计算平台供应商，其内存等资源的利用率均不足40%[8]。导致这种情况的核心问题之一是虚拟机对共享资源的竞争导致系统整体性能下降，为保证云服务性能而不得不过量分配虚拟机内存。在虚拟化环境下，如何充分地发挥虚拟化带来的资源调配的灵活性，以提高内存资源的利用率是重要的研究课题。

虚拟机工作集WSS(Working Set Size)是指一台正在运行的虚拟机实际使用的内存量[9,10]。工作集是指导虚拟机内存分配量最直接的指标，如何高效实时测算虚拟机的工作集是虚拟机动态调配的主要挑战。在x86架构上，已有诸多研究者开展了相关的工作。主流的测算工作集的方式是通过内存缺失率曲线MRC(page Miss Ratio Curve)进行估算[11 - 13]。绘制内存缺失率曲线需要获取较为完整的内存访问流，这与CPU架构直接相关。

申威架构服务器虽不具有硬件辅助的虚拟化支持(如Intel扩展页表EPT(Extended Page Table)技术[14])，但是其独特的固件层HMCODE带来了充分的软件灵活性以帮助实现系统虚拟化。HMCODE是申威架构独有的位于硬件层和操作系统层之间的固件层，通过申威指令汇编代码编写，以最高特权实现一系列操作(如修改寄存器、软件刷新旁路缓存TLB(Translation Lookaside Buffer)等)。因此，传统的x86架构下的工作集测算方法已不再适用申威架构。如何结合申威架构自身的虚拟化实现以及如何充分发挥申威架构软件灵活性的优势是实现访存特征提取面临的主要挑战。

本文提出了基于申威架构的多层协从虚拟机访存特征提取技术，并在申威1621服务器实现和测试了该技术[15]。从原理上讲，本文采用基于最近最少使用栈LRU(Least Recently Used)构建重用距离分布直方图并进一步绘制内存缺失率曲线，实现虚拟机工作集预测，同时使用热页集削减访存提取开销。实验结果表明，该方法能够在申威平台上高效准确地获得虚拟机高精度的内存缺失率曲线并计算虚拟机工作集大小，同时引入的热页集可以有效降低访存特征提取所带来的性能开销。

2 访存特征提取方法

访存特征提取是在计算机操作系统层面(或更底层)对运行在计算机上的应用程序访存行为进行数据采集并分析的技术。访存特征提取的核心是获取应用程序的内存缺失率曲线。内存缺失率曲线反映的是应用程序内存用量和缺页率之间的关系。通过访存特征提取，可以有效地评估应用程序的访存行为，分析应用程序局部性特征，计算应用程序的工作集大小，这对指导虚拟机系统的内存分配具有重要意义[16 - 18]。

2.1 访存特征提取基本原理

在申威架构服务器上首次实现了访存特征提取机制，整个访存特征提取机制主要包括3部分：“内存缺失率曲线”构建方法、“置位-中断”页面追踪方法和“热页集”优化方法。下面分别阐述3个部分的原理与功能。

2.1.1 内存缺失率曲线构建方法

Mattson等[19]于1970年提出的LRU栈式算法是最经典的存储体系缺失率曲线构建方法。LRU栈式算法的基本原理就是使用一个LRU栈的结构来模拟Linux内核对内存的管理，从而获取重用距离直方图，通过直方图来计算内存缺失率曲线。

LRU栈利用一个特殊的栈来保存当前使用的各个页面的页面号，每当访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。内存不足时，系统就会淘汰最近最久未使用的页面。

“重用距离”是指一个页面在LRU栈中再次被访问时与栈顶的距离，即连续2次访问之间有多少个不同的页面被访问。使用LRU栈模拟程序访存的操作，使用计数器统计每个条目的访问次数构建出重用距离分布RDD(Reuse Distance Distribution)直方图。内存缺失率(MissRatio)计算公式如式(1)所示：

(1)

其中,rd[k]表示重用距离为k的访问出现的次数,也就是距离栈顶为k的条目保存的页面被访问的次数。栈大小为c即内存有c个不同页面。

2次访问相同的页面，第2次访问能否命中内存与2次访问的重用距离有关。如果2次访问重用距离大于c，第2次访问时该页面已经被淘汰出LRU栈，会产生缺页中断；反之，如果2次访问重用距离小于c，当前页还在内存中，访存命中。据此计算得出任意内存大小时的内存缺失率，进而绘制内存缺失率曲线。

2.1.2 “置位-中断”页面追踪方法

内存缺失率曲线构建机制的输入是连续的CPU访存虚地址流。CPU在进行数据访存之前，需要进行虚实地址转换即将虚拟地址转换成物理地址，由于旁路缓存TLB的存在，绝大部分的地址转换会被硬件TLB直接命中，这就导致在软件层面无法获取到完整的CPU访存地址流信息。虚拟化环境下，虚拟机管理器难以直接感知这类访存行为，因此本文采用了置位的方式对虚拟机内存页进行标记，从而所有的被标记页面都会陷入缺页处理函数，以被虚拟机管理器捕获。具体来讲，针对每个64位的页表项，规定了一位未使用的位作为标记，以标识该页的追踪状态。当页面即将进入LRU时，刷新其对应的TLB项并置位页表项有效位，以保证该页面下次被访问时依旧发生缺页中断，虚拟机管理器就可以感知到该页面的访存行为。

2.1.3 “热页集”优化方法

页面追踪机制需要完整的CPU访存流，截获每一次CPU的访存操作，并且每次访存操作都需要发生TLB 未命中(TLB MISS)、页表遍历和缺页中断处理。这种方法会带来巨量的性能开销，而实际上访存特征提取机制的目标是实时计算虚拟机的工作集大小。一方面，理论上，根据重用距离直方图(或MRC)来计算工作集大小，起决定因素的是长距离的访存重用，因为最长距离的重用决定了该虚拟机所需要的不同页面数目的最大值。另一方面，根据程序局部性原理，绝大部分访存都是短距离重用，追踪这部分访存开销巨大。热页集机制就是过滤短距离重用，只保留有计算工作集价值的长距离重用分布的方式来大幅减少页面追踪开销。

一段时间内被频繁访问的内存页面称为热页，当前所有热页构成的集合称为热页集。热页集通过一个有限长度的先进先出(FIFO)队列来维护。在程序开始运行的时候，程序中的所有内存页面都被初始标记为冷页，所有对冷页的访问都会被跟踪。一旦一个冷页被访问，根据时间局部性原理，这个页面最近被再次访问的可能性非常大，因而这个正在被访问的冷页会被标记为热页并加入热页集进行维护。

图1中展示了内存页面跟踪中热页集的位置，其中热页集是一个先进先出的队列，它记录了所有热页的地址及其他必要信息。如图1所示，当程序访问到内存中的冷页时，触发缺页中断，此时在队列中记录下该页的信息，并将其加入到热页集中，即标记为热页。通常热页集都是满的，新页加入到热页集中就需要从热页集中移除一个最旧的页面。从热页集中移除的页被重新标记为冷页。

Figure 1 Principle of memory access feature extraction图1 访存特征提取原理

使用热页集的效果是避免了对大量发生在热页上的页面访问的监控跟踪，也就是说，进入热页集的页面会被清除置位标记，从而不会因为置位而发生缺页中断。短时间内将会被频繁访问的页面，CPU对它们的访问都被热页集过滤掉，极大地降低了页面跟踪的总量，减小了页面跟踪的时间开销。

热页集的大小直接关系着访存特征提取的开销与准确性。过小的热页集会导致过量的页面被置位标记，带来大的额外开销；过大的热页集会导致小工作集虚拟机访存特征提取失败，即热页集完全覆盖了工作集对应的内存量。因此，热页集大小应当根据虚拟机的实际应用场景进行确定，以保证访存特征提取有合理的性能开销和较高的准确度。

2.1.4 具有热页集的访存特征提取方法

图1是申威架构下虚拟机访存特征提取方法的实现原理示意图。虚拟机在运行过程中不断访问物理内存，用户开启某虚拟机的访存特征提取，系统立即清空该虚拟机的TLB和进程页表，此时所有访存均发生缺页中断，访存序列在缺页中断处理函数中被捕获。被捕获的访存序列进入热页集进行过滤，进入热页集的页面，清除其置位标记；若热页集满，离开热页集的页面进行置位标记，并刷新其TLB和页表项，最终页面进入LRU栈。重复上述过程直到用户关闭访存特征提取，此时系统根据LRU栈计数器统计获得重用距离分布直方图，绘制内存缺失率曲线MRC，计算虚拟机工作集大小。一次完整的虚拟机访存特征提取结束。

图2 举例展示实验测得的SPEC2006-400.perlbench重用距离分布直方图与内存缺失率曲线。设置热页集大小为1 600，因此重用距离分布直方图中，重用距离小于1 600的页面均被过滤，重用次数为0。重用距离越小，重用次数越高，这也符合程序局部性原理。与之对应的是由式(1)计算得到的内存缺失率曲线，由图2可知，随着给定内存值越大，程序的缺页率越小，不断逼近于零。

Figure 2 Perlbench reuse distance distribution histogram and memory page miss ratio curve图2 SPEC2006-400.perlbench重用距离分布直方图与内存缺失率曲线

2.2 申威平台访存特征提取实现

2.2.1 申威架构虚拟化简介

如图3所示，相比于x86为代表的传统CPU架构申威架构多了一层固件(HMCODE),于是在系统模式上，申威增加了一种新的具有最高权限级的硬件模式HM(Hardware Mode)。在HM下，系统具有最高特权级，不响应各类中断，所执行的即是位于固件层的汇编代码。就虚拟化而言，当前申威架构下的虚拟化工作仍处于比较初级的阶段，特别是在硬件上缺少类似Intel VT-x的虚拟化相关的支持。所以，为了保证虚拟化在申威平台上的功能与性能，研究者们采用了软件与固件相结合的方式提供较为全面的虚拟化支持。就申威虚拟化而言，设计者在内核层实现复杂的且使用频率较低的功能部件；在固件层实现功能简单但高频使用的功能模块(如MMU)，从而保证其运行效率。

Figure 3 Comparison of x86 and Sunway architecture图3 x86与申威架构层级对比

传统x86架构下的虚拟机访存特征提取所依托的是Intel EPT机制，通过对EPT页表项进行置位中断处理，就可以在虚拟机管理器(如KVM)中获取到虚拟机的访存地址流。申威架构下虚拟机内存分配采用了段式映射的方式，将虚拟机的地址直接映射到连续的物理内存段上，避免了2级地址转换带来的额外开销。因此，在申威架构中无法直接使用x86架构的访存特征提取机制 。本文结合申威架构的特点，充分发挥HMCODE带来的软件灵活性，在申威平台上构建了多层协调的访存特征提取机制。

2.2.2 多层协调的访存特征提取实现接口

如图4所示，申威轻量级虚拟机运行在用户层，访存特征提取机制主要实现在内核层与固件层(HMCODE)。虚拟机访存发生TLB未命中，经中断程序进入TLB脱靶处理模块。若用户开启访存特征提取，此模块首先对发生TLB未命中的页面进行“标记位”检查，若该页面是被置位标记的页面，则直接陷入缺页处理接口，否则就进行正常的页表访问。在x86架构下，TLB未命中之后硬件陷入MMU进行页表遍历，对于页面的拦截就不得不推迟到页表遍历之后，而申威架构下，对于需要采样的页面(即标记页面)无需进行页表遍历，这在一定程度上减少了额外的开销。

Figure 4 Interface of memory access feature extraction of Sunway virtual machine图4 申威虚拟机访存特征提取接口

缺页处理接口将被标记页的必要信息以参数的形式传入内核缺页处理模块，参数包括访存地址(缺页处理的页面地址)、VPN(Virtual Processor Number)和UPN(User Processor Number)。VPN和UPN用于申威CPU的TLB当中，是申威架构独有的用于区分虚拟机和进程的特殊标记。

发生缺页中断并进入内核层缺页处理模块的页面，若有置位标记，则将其清除，然后页面进入热页集存储；若没有置位标记，则说明该页面是热页，已存在于热页集中。热页集通过一个先进先出队列进行维护，热页集中保存着热页的页帧号、VPN和UPN。若热页集已满，则最旧页面离开热页集，进入LRU模块进行下一步处理。

LRU模块负责通过LRU栈式算法构建重用距离分布直方图。进入LRU模块的页面会根据LRU替换规则进行管理。栈中的每个条目都包含一个访问计数器，用于记录该条目被访问次数即重用次数。首先自栈顶向下遍历栈，若找到该页面，则将该条目的访问计数器自增并将页面提到栈顶；若页面不存在于栈中，则直接将页面压入栈顶。LRU栈的大小由当前虚拟机的内存大小决定，例如在申威架构下，每个页面的大小是8 KB，一个具有4 GB内存的虚拟机对应的LRU栈大小为219。

用户关闭访存特征提取后，系统关闭特征提取各模块并启动数据分析模块。该模块会收集LRU模块中采集的重用次数，绘制重用距离分布直方图与内存缺失率曲线，由此可以获取申威虚拟机的工作集大小。

3 实验

为验证访存特征提取方法的有效性和高效性，本文通过真机实验的方式加以验证，从访存特征提取构建的内存缺失率曲线准确性、时间开销和存储空间开销3个方面进行实验分析。本文以SPEC2006[20]中工作集大小大于20 MB的程序作为测试程序(共计18个)，这是因为工作集过小的程序的访存序列会被热页集完全覆盖而无法构建重用距离分布直方图。实际上，工作集的大小和对虚拟机内存压力的影响成正比，我们更关注内存需求较大的程序。

3.1 实验环境

本文在申威1621型多核服务器上实现访存特征提取并测试。实验机具有16核CPU，工作频率为2 GHz。存储体系上，系统具有3级CPU缓存，缓存大小分别是32 KB,512 KB,32 MB；集成8路64位DDR3存储控制器，传输速率为1 066～2 133 MBps，支持ECC校验，内存大小为64 GB；HDD硬盘容量为2 TB。

软件层面上，宿主机与虚拟机均采用基于Linux的深度服务器操作系统，每台虚拟机分配4个物理核和4 GB的初始内存。

3.2 内存缺失率曲线准确性检验

为验证访存特征提取的准确性，本文对比分析了申威平台虚拟机访存特征提取得到的程序内存缺失率曲线和使用Intel-PIN工具模拟测定的内存缺失率曲线。Intel-PIN是Intel公司开发的动态二进制插桩框架，用于动态分析程序特征，它可以监控程序的每一步执行，提供了丰富的API，可以在二进制程序运行过程中插入各种函数，比如可以获取程序执行过程中的访存虚地址序列[21]。由此，本文将Intel-PIN获取到的访存序列作为输入，然后模拟程序的访存行为，通过具有热页集的访存特征提取机制，获取准确的程序内存缺失率曲线。

Figure 5 Sunway virtual machine memory access feature extraction and Intel-PIN simulation memory page miss ratio curves图5 申威虚拟机访存特征提取与Intel-PIN模拟内存缺失率曲线

图5展示的是SPEC2006部分程序的测试结果。虚线代表Intel-PIN模拟结果，实线代表申威平台虚拟机访存特征提取结果。2条曲线形状具有高度的相似性，这表明提取的程序访存特征是正确的；申威访存特征提取方法获得的内存缺失率曲线明显高于Intel-PIN获取的曲线，这是因为热页集过滤了导致重用距离小的访存。实验结果表明，SPEC2006程序集程序重用距离小于1 600的访存数目占总访存的比例平均高达99.9%，这也符合程序局部性原理。通过统计实验的结果进行动态修正可以明显提高缺页率数值的准确性，并且访存特征提取机制的最终目标是计算程序的工作集大小，在图中表现为曲线在横轴的最大值，而热页集仅会影响曲线在纵轴(缺页率)的数值，并不会影响横轴(内存需求)的数值。实验结果表明，测算工作集的平均误差低于3%，这说明申威平台上访存特征提取准确性高，效果良好。

其他影响实验结果的因素还包括对比实验环境，主要是指x86和申威的架构差异性。Intel-PIN仅支持IA-32和x86-64指令集架构，因此本文在x86平台上进行模拟。一方面，申威架构下页面的大小为8 KB，而x86架构下页面的大小为4 KB，页面大小不同一定程度上会影响程序访存特征。因此在实验中，通过修正Intel-PIN获取的重用距离分布直方图，将相邻页面数据进行加法合并，以模拟8 KB页面访存的效果。另一方面，不同架构的程序编译器具有一定的差异，可能存在一些访存指令上的不同优化。

3.3 特征提取时间开销

程序访存在程序执行时间中占比较高，特别是密集访存程序。程序访存主要分为2步：一是访存地址转换，即虚拟地址到物理地址的转换；二是程序读/写内存。地址转换所带来的时间开销不容小视，特别是在虚拟化环境下，有研究表明，虚拟地址转换开销平均占到总执行开销的5%，特别条件下高达40%[22]。访存特征提取机制就是利用了程序访存的地址转换，特别是置位标记操作导致程序发生大量的缺页中断，这将带来比较严重的性能开销，因此本文引入了热页集机制过滤掉短距离重用访存，短距离重用的访存占比高达99.9%，因此可以大幅度削减特征提取的开销。

图6展示的是SPEC2006测试程序有无特征提取条件下归一化时间开销对比结果。申威平台上开启访存特征提取的平均时间开销约为8.3%，时间开销和程序的工作集大小成正比，程序工作集越大，访存开销也就越大，提取访存特征所带来的额外开销也就越明显，比如429.mcf的额外开销高达24.5%，这是因为该程序的工作集较大(1 676 MB)。访存特征提取的时间开销也与开启的时间有关，开启时间越久，开销越大，特征提取的准确性越高，这需要折衷考虑。此外，申威平台自身的缺陷也会影响开销，现有的申威架构还在发展的初步阶段，严重缺乏硬件方面的支持，比如硬件MMU以及硬件辅助虚拟化机制。

Figure 6 Comparison of normalized execution time of on/off memory access feature extraction图6 开启/关闭访存特征提取时间开销对比

3.4 特征提取空间开销

访存特征提取方法的空间开销主要由2部分构成：热页集存储开销和LRU栈存储开销。热页集是一个先进先出队列，LRU栈是一个栈式结构。队列和栈的每个条目均保存页面的64 bit地址、2 bit VPN和8 bit UPN，此外栈的每个条目还包含一个16 bit的计数器。对于一个内存为VM_memGB的虚拟机，设热页集大小为HS_size，则访存特征提取总的存储开销TSO的计算如式(2)所示：

(2)

例如，对于一个4 GB内存虚拟机，若热页集大小设定为1 600，则总的存储约为6 MB，相对于4 GB的虚拟机内存而言，访存特征提取的存储开销可以忽略不计。

4 结束语

本文首次在国产处理器申威架构上提出了虚拟化环境下的访存特征提取方法。本文充分结合了申威架构特性，基于Mattson栈式算法构建了重用距离分布直方图和内存缺失率曲线，并准确计算了虚拟机内程序的工作集大小，采用“置位-中断”的页面追踪方法，平均误差不高于3%；引入热页集机制过滤页面，大幅削减页面追踪的开销，平均开销约为8.3%。

在下一步工作中，将进一步完善申威平台的内存虚拟化支持，并逐步实现多层协调的虚拟机内存动态调度系统，为国产服务器的发展增砖添瓦。