多核计算机系统已成为时代的主流. 适用于早期单核处理器操作系统(operating system, OS)的核心机制(如内存管理等), 在面对日趋复杂的计算环境与内存架构以及多样化的计算需求时, 已很难建立从数据到内存体系的最佳映射, 造成大量的线程间访存互扰和冲突, 进而导致计算机吞吐量(throughput)、服务质量(quality of service, QoS)与理想状态相去甚远^{[1, 4-7, 14]}.

以被广泛使用的Linux操作系统为例, 其内存管理机制采用了近乎“盲目”的随机物理页面分配机制. 即: 在出现“页缺失”时, 从伙伴系统(buddy system)^[2-4]中随机取出一个(或地址连续的多个)物理页面, 通过OS在页表中建立虚实映射. 这种随机分配方式直接导致数据在物理内存介质(DRAM Bank)上映射的位置是不确定的^[5]; 这种不确定性导致被频繁访问的页面可能会被随机地分配到同一个物理内存Bank中, 造成Bank上的访存冲突^[5]. 与此同时, 在片上Cache中也极有可能产生在Cache Set上的数据分布不均^[6], 引发较多的Cache缺失, 影响系统的总体性能. 总之, 由于现有的内存管理与分配机制未考虑数据在物理介质上的运行时分布状态, 导致整个内存体系的资源利用率始终处于较低的状态^{[4, 7-9]}.

内存管理机制的缺陷由来已久, 研究人员有针对性地开展了一系列研究. 其中, 具有里程碑意义的工作是SUN公司于1985年前后, 在MIPS操作系统中引入的“页着色(page-coloring)”技术. 其核心思想是: 在建立虚实映射时, 让虚拟地址的低位和物理地址的低位满足一定的函数关系(如相等、固定偏移等), 使得读入Cache之后的数据分布不会出现明显的不均.

在20世纪90年代, 页着色技术发展迅速, 其中较有代表性的成果来自Richard等人^[10]的研究, 他们发现: 页着色技术会导致不同地址空间(如数据段、代码段、栈等)出现在同一个Cache Bin中(一个Bin包含一组Cache Set), 进而造成访存竞争和干扰, 使得Cache利用率下降. 为了解决该问题, 他们提出了Bin Hopping和Best Bin改进经典的页着色技术, 以Cache Bin为单位, 让连续的页面映射到连续的Cache Bin中, 减少在Cache上的冲突. 此方法提出之后, 被学术界和工业界广泛接受, 从已公开的资料来看, Windows操作系统的内存管理以及VMware虚拟机资源管理体系均已采用相关页着色技术.

进入21世纪后, 在采用多核处理器的系统中, 来自多个计算单元的访存请求会引发在整个共享内存体系(包括Cache和DRAM Bank)上的冲突和互扰^{[4, 9, 11]}, 造成内存资源利用率不高, 进一步拉大了计算速率与访存速率之间的差距. 此时, 页着色技术再一次走进人们的视野, 被用于消除/降低多道程序、线程之间在Cache上的访存互扰. 其核心思想是: 利用物理页帧号(page frame number, PFN)中的Cache Set的索引位, 将整个物理地址空间以页为单位划分为不同“颜色”的区域, 每种颜色代表一段物理地址空间, 并对应一组Cache Set. 在物理页分配的过程中, 依据颜色映射数据, 即: 相同颜色的页帧将会分配到相同的Cache区域; 不同颜色的页面在映射之后, 不会存在重叠的Cache资源, 从而实现不同程序在Cache上的划分, 消除了程序间在Cache上的相互竞争和干扰. 鉴于此方法的有效性以及在工业界应用的潜力, 在随后的几年, 又出现了一系列有代表性的工作^{[12, 13]}.

程序之间的访存干扰同样存在于内存系统的DRAM Bank中. 虽然业界设计了很多访存调度机制^{[22-27, 31]}, 但是这些方法可能需要复杂的硬件逻辑, 调度算法较为固化, 性能在不同应用场景中的差异较大, 且较难部署和大规模应用(需要大规模流片). 本文将介绍一种DRAM Bank划分机制, 该机制首次成功地将页着色技术应用于对DRAM Bank的划分^[5](在某些计算平台上, 主存地址映射中存在若干地址位能够直接索引Bank^[5]), 进而消除了程序间在主存上的访存干扰, 提高了Bank的并发度和响应速率.

在此基础上, 本文进一步引入了内存通道(channel)划分, 在消除程序间主存Bank上相互干扰的同时, 也降低了程序间在内存通道上的访存竞争^[30].

上文介绍的内存划分机制均为“水平”的方式, 即仅划分Cache或仅划分DRAM Bank的单一层次的内存资源. 本文通过对大量真实的工作集运行情况的深入分析, 介绍了首次发现的内存体系“垂直”优化空间的全过程^[4], 亦即通过地址映射中能够同时索引DRAM Bank和Cache Set的地址位协同划分多级存储器, 进而获得更大的性能收益. 垂直划分也可通过页着色完成, 为访存优化提供了新方向和实践方法. 随着内存体系的发展, 非易失性存储单元(non-volatile memory, NVM)以其高密度、大容量和低能耗等优点逐步走进人们的视野, 并广泛应用于主流服务器. 但NVM并未完全替代DRAM, 这两种内存材质将长期并存构成混合内存体系.

近年来, 研究者为充分发挥DRAM与NVM的特点, 开展了许多针对DRAM-NVM混合内存架构的研究^{[8, 9, 32-34, 38, 41, 42]}. 本文介绍了一种最新的面向DRAM-NVM的内存管理机制^[8], 是利用页着色技术的最新成果. 该研究工作不但利用内存体系中的地址位索引(Bank id、Cache set id、Channel id)进行着色, 还对物理页面所在的内存材质进行着色, 区分页面属性, 并进行高效的访存行为监测、页面迁移、数据排布等管理操作.

本文后继内容将梳理、剖析“页着色”技术的发展历史及近年来新的研究工作, 促发更多的关于现代操作系统内存资源管理机制的设计思路的思考. 本文第1节介绍“页着色”技术的历史与发展. 第2节对基于“页着色”的DRAM划分方法进行总结和介绍, 包含DRAM Bank单一层次的划分和DRAM Bank与通道两个层次的划分. 第3节总结上述技术在Cache以及DRAM内存体系中的“垂直”划分. 第4节介绍当前“页着色”技术在新兴DRAM-NVM混合内存体系中的发展与应用. 第5节总结“页着色”技术过去的发展思路, 并展望内存划分技术未来的发展趋势.

1 “页着色”技术的发展历史与演进

中央处理器(CPU)处理数据的速率要远比由DRAM组成的主存系统排出数据的速率高很多. 通常, 一条访存请求需要50-100个时钟周期才能完成, 而在一个时钟周期内, 处理器能执行若干条指令. 这意味着处理器绝大多数的时间都在等待主存的响应, 因此, 内存瓶颈制约了处理器性能的发挥. 这种处理器与主存之间的处理能力的差异即是“内存墙”^[15]. 为了缓解“内存墙”, 高速缓存(Cache)技术被提出. 由静态随机存取存储器(static random-access memory, SRAM)构成的Cache响应速度大于主存, 缓存一部分近期被访问过的数据(不同的缓存算法缓存的数据有所不同). 对于应用程序, 处理器先从Cache中读取数据, 而不是从主存中读取数据, 显著提高了系统性能. 但是, 系统设计者却发现: 由于从虚页到实页的“任意映射(arbitrary mapping)”, 数据块在采用物理地址索引的Cache中的分布通常是不均匀的. 这导致系统性能通常会产生很大的波动, 即使是同一道程序的多次运行, 执行时间也可能会发生明显的变化. 为了解决此类问题, 1985年, MIPS操作系统引入了“页着色(page coloring)”技术, 这是有文献可查的第一次正式出现的“页着色”这一技术词汇^{[1, 10, 16]}. 研究人员设计了新的页面虚实转换的算法: 在映射过程中, 让物理页面的“低几位(low order bits)”与虚拟页面的“低几位”满足一定的函数关系(如固定偏移距离等). 以某几个地址位为依据, 将不同的虚、实页面对应不同的“颜色”(例如: 低3位为000的页面为“红色”, 001的页面为“蓝色”). 因此, 从主存到Cache的页面映射不再是随机、任意和无序的, 而是满足某种“颜色”的对应关系, 从而保证了Cache中不会出现明显的数据分布不均匀的情况.

然而, 在多核时代, 由于多道程序并发执行, 每道程序发出的访存请求会在Cache上产生访存竞争, 导致Cache命中率降低, 从而使得计算机整体性能下降. 为了解决这一问题, 有研究者再次诉诸于页着色技术, 通过给每个程序分配不同颜色的页面, 使得不同程序仅使用分给它对应颜色的一部分Cache资源, 以此消除程序间在Cache上的访存竞争. 具体做法是: 当在程序运行过程中发生“页缺失”时, OS为该程序分配仅属于其所对应颜色的物理页面, 因此实现了不同程序在Cache上的隔离, 消除了彼此之间的干扰. 如图 1所示, 由16路组相连的8MB的LLC(last level Cache)可以与8GB主存构成地址映射关系. 其中, PFN中的12-18位为Cache Set索引位. 通过对Cache Set位中第12位和第13位的着色, 就可以实现4个程序在Cache上的隔离.

上文中提到的页着色仍然是静态的. 静态的页着色是指页着色不会在程序执行过程中更改映射. 虽然静态的页着色易于实现且有较低的开销, 但无法满足程序对Cache资源的动态变化的需求^{[17, 18]}. 页面迁移^[19]可使静态页着色技术支持动态“重着色”^[19], 进而根据运行时实际需求调整页面分配及着色规则. “重着色”技术的核心是“页面迁移(page migration)”, 该技术对OS系统内存管理机制影响深远.

此外, 研究人员设计了一系列编译制导的页着色方法^{[20, 21]}. 研究人员意识到: 通过编译技术, 将具有时间局部性(temporal locality)的代码和数据映射至不同的Cache Set, 可以提升数据缓存(data Cache)和指令缓存(instruction Cache)的性能^[21]. 他们使用软硬件结合的方法对Cache中的页面重排, 提高了Cache命中率. 在软件层, 利用编译器预先为代码页和数据页提供颜色映射, 随后, OS使用这种映射指导物理页的分配. 在硬件层, 向页表缓存(TLB)添加一个页面重新映射字段, 控制是否将页面重新映射到Cache中的不同“颜色”的空间(由物理地址索引表示). 国内也有研究者^[48]将页着色技术应用于Cache划分. 该研究通过动态内存分配的方式, 在不修改程序源码与系统内核的前提下, 实现动态的Cache划分. 通常, 这类研究的不足之处在于, 需要为每个程序单独划分Cache, 如果工作集中程序数量增加, 系统性能提升将在短时间内达到上限, 甚至出现负收益.

工业界对页着色技术产生了浓厚的兴趣, 并分别从降低地址映射开销以及提高Cache使用率的角度出发做出了大量的尝试. SUN早期版本的UNIX操作系统里就采用了页着色技术. 20世纪90年代, 页着色的优势还常常体现在降低地址转换时候的硬件开销上. 因为在采用页着色的机器上, 虚拟页和物理页在若干个低位上已经建立了对应关系, 因此这种设计减轻了负责地址转换的内存管理单元(memory management unit, MMU)的设计开销. VMware考虑到Guest OS可能使用页着色技术, 曾经在虚拟机监控系统ESX Hypervisor中包含了提供页着色优化的兼容版本. 该版本可以在为多个Guest OS分配物理页面的时候, 采用页着色技术来匹配Guest OS所申请页面的颜色. 换言之, Hypervisor尽可能满足Guest OS对颜色的需求, 以最大限度地保留客户系统的优化手段.

在上述研究工作中, 页着色仅应用于对Cache的优化/划分, 而未考虑将其应用到其他内存资源划分. 本文介绍了一种DRAM Bank层次上的划分机制: BPM(Bank partitioning mechanism). 该机制把主存DRAM Bank均分成几组, 每个程序只占用一组DRAM Bank, 程序之间不交迭, 因此在根源上消除了程序间在同一Bank上的访存干扰; 本文进一步介绍了对内存通道的划分(BPM/BPM+)^[30], 以此消除程序在内存通道上的竞争, 提高系统整体吞吐量. 最后, 本文介绍了一种基于页着色技术的“垂直”划分方法^[4]以及“非对称”的垂直划分机制^[7], 并介绍了将这一系列的方法应用于对DRAM-NVM混合内存体系架构上的实践经验^[8]. 本文对近年有代表性的LeiLiu等人的相关工作进行了梳理汇总(见表 1), 下文将详细介绍若干关键性的工作.

2 基于页着色技术的DRAM Bank划分

在多核时代, 程序间的冲突不仅发生在Cache上, 同样发生在DRAM Bank与内存通道上. 有学者将页着色技术应用于DRAM Bank与通道的划分上, 用软件方法消除、降低多道程序间在主存系统上的访存干扰^{[5, 30]}.

2.1 访存调度算法

在多核共享内存的计算机系统中, 当多个程序的访存请求落在同一个Bank上时, 将引发Bank上的访存冲突, 导致行缓冲命中率下降, 进而造成访存性能的下降, 并影响系统的整体性能^[5].

目前被工业界广泛使用的内存调度算法的基础是FR-FCFS(first ready-first come first service), 该算法简洁有效且易于实现. 其核心思想是: 在先来先服务(first come first service, FCFS)算法的基础上, 增加了对DRAM行缓冲的局部性(row buffer locality)的考量, 即: 在打开某个Bank的行缓冲(row buffer)之后, 尽可能地让调度窗口中潜在能够命中该行的后继请求优先于其他的访存请求. 虽然这种以最大化行缓冲利用率为目的的调度方式易于实现, 但在公平性和吞吐量方面的表现却不甚理想^[22].

国内外学者提出了很多先进的内存控制器中的调度算法^{[9, 22-27]}, 但这些算法均存在着诸多不确定因素. 例如, 较为先进的线程簇内存调度(thread cluster memory scheduling, TCM)算法^[22]不仅需要引入额外的至少4K的存储空间, 且调度时需要复杂的硬件逻辑支持. 虽然TCM调度算法在性能上有较好的表现, 但芯片设计与生产的复杂性阻碍了该算法的实际应用. 因此, 虽然当前先进的调度算法在大多数场景下能够缓解内存的访存干扰问题, 但仍难以在根源上彻底消除线程间的访存干扰.

2.2 DRAM Bank划分(Bank partitioning mechanism, BPM)

通过对主存地址映射的研究, 研究人员发现, 在主存地址映射中存在着若干地址位能够直接索引DRAM Bank^{[5, 28]}. 例如, Intel i7-860处理器在配置8 GB DDR3内存、64个DRAM Bank(每个Bank 125MB)时, 其地址映射的第13位-第15位和第21位、第22位可以索引Bank的地址位. 这启发了研究者使用页着色技术消除程序间在DRAM Bank上的访存干扰问题. 即: 通过页着色技术, 对上述5个Bank索引位着色, 即可将系统中所有的DRAM Bank最多划分为2⁵=32组, 让每个程序使用且仅使用其中一组(或若干组)Bank.

至此, 一种从根源上消除进程间访存干扰的机制BPM(Bank partitioning mechanism)^[5]被提出. 如图 2(a)所示: 在BPM中, 程序1只能访问其对应的Bank而不能越界访问属于程序2的Bank, 有效消除了程序间的访存干扰, 程序自身的行缓冲局部性也得以保证. 值得注意的是: 在每个Bank组内部, 访存行为仍然是“交替”的. 在运行时可以明显看到: 不采用Bank划分, 不同程序的访存请求被“交替”分配到任意Bank上, 引发了行缓冲颠簸, 因此会导致部分访存请求的时延较长, 如图 2(b)所示; 相反, 采用Bank划分时, 程序之间的访存干扰被消除, 每个程序的行缓冲局部性有所提高, 故访存请求的响应时延相对减小, 如图 2(c)所示. BPM既有利于系统的整体性能, 同时也提升了系统的服务质量(QoS). BPM是有资料可查的首次在真实的多核服务器上实现的主存DRAM Bank划分机制, 为后来很多内存优化相关的工作奠定了基础.

另一方面, 为了获得更高的性能提升, 为每个程序所分配的Bank的数量是需要考虑的重要问题. 以SPECCPU 2006^[29]中的程序作为测试用例, 图 3显示了不同Bank容量下单个程序运行性能的变化^[5]. 可以看出: 对90%的程序来说, 16个Bank(每个Bank容量125MB)即能满足程序的需要, 分配更多的Bank并不能显著提高程序性能. 这说明程序对Bank数量的需求是有限的, 满足容量需求后, 分配更多的Bank对提高程序性能不起作用. 因此, 对于SPECCPU 2006中的程序, 由于每个程序的内存足迹(MemoryFootprint)较小, 在划分Bank时, 直接使用均分的方法也能满足需求^[30].

为了验证Bank划分的有效性, 实验中使用加权加速比(weighted speedup, WS)来衡量系统的吞吐量, 而公平性(QoS)用工作集中性能下降最大的程序来表示(max slowdown)^[22], 具体表达式为

$\begin{matrix} Weighted\text{ }Speedup=\sum{\frac{{{运行时间}_{alone}}}{{{运行时间}_{shared}}}}, \\ \text{Max }Slowdown=\text{Max }\left\{ \sum{\frac{{{运行时间}_{alone}}}{{{运行时间}_{shared}}}} \right\}. \\ \end{matrix}$

实验在10组随机产生的工作集中开展(每组工作集包含若干个SPECCPU 2006中的程序)^[5], 对采用和不采用BPM情况下系统的吞吐量和公平性分别进行测量, 结果如图 4所示: 使用Bank划分后, 系统的吞吐量均有提升, 平均提升4.8%, 最高达6%; 在公平性方面, 最高能达到16%的提升, 但存在对部分工作集QoS下降的情况. 可见, BPM能够带来的性能提升是可观的. 当前, 计算机性能已接近极限, 能够提高平均1%的性能都是有意义的重大改进. 详细的性能分析可见LeiLiu等人的工作^[4-8]. 采用静态的Bank划分方法后, 每个程序能使用的Bank数量是固定的. 但在有些情况下, 随着程序的运行某个程序的内存足迹增大, 对Bank需求增加时, 静态Bank分配将会导致现有分配不足的情况. 为了解决这一问题, 研究人员提出了动态的Bank划分方法^[30]. 其核心思想是: 根据运行时的信息, 实时动态地调整各个程序划分的Bank数目. 基于文献[5, 30]提出的动态划分机制, 针对不同的优化目标, 内存控制器中的访存调度方法可以是多样化的. 实验结果表明: 在大内存足迹负载下, 动态的Bank划分机制在提升系统性能方面有更好的表现.

为了增加系统的总体带宽, 现代的计算机普遍采用多通道技术. 例如, DDR3-1600的峰值带宽是12.8 GB/s, 双通道系统的理论峰值带宽即为25.6 GB/s. 对于主流的多通道计算机, 通常以Cache line(64B)为单位“交替”访问, 将访存请求平均分布在若干通道, 这样可以达到充分利用带宽的目的. 但是, 如图 5所示(不同颜色的色块代表来自不同程序的访存请求), 盲目地交替访存实际上会加剧多道程序在通道内的竞争, 同时也可能会引发程序在DRAM上更多的冲突.

2.3 通道划分(BPM+)

当前, 主流平台(如Intel i7系列)的BIOS为用户提供了可配置的选项, 可控制是否在通道上执行“交替”访问的策略. 如果取消“交替”访问, 并利用页着色技术对“通道位”进行着色, 这意味着可以通过页着色技术来控制程序访存在通道上的分布, 从而实现通道划分技术.

在传统的DRAM Bank划分的基础上, 一种消除通道间访存干扰的机制(BPM+)^[30]被提出. 该方法通过对通道进行划分, 让每个程序仅使用一条通道, 并在通道内部使用Bank划分. 如图 6所示: BPM+不仅消除了程序在DRAM Bank上的竞争, 还缓解了程序间在通道上的竞争, 所以获得了进一步的性能提升. 同样, 在配置Intel i7-860处理器、8 GB DDR3内存、64个DRAM Bank(每个Bank 125MB)、双通道服务器上, 采用BPM+的性能平均要比仅采用BPM时提高接近两个百分点.

3 基于页着色技术的垂直划分

面对日趋复杂的计算需求以及逐渐加深且相互影响的内存层次结构, 仅在单一某个内存体系层次上进行划分、优化等操作不能最大化系统性能. 例如高速缓存Cache和主存DRAM Bank, 它们之间存在着密切关联, 性能相互影响, 如果仅在一个层次上使用划分技术, 则欠缺了对整个内存体系性能统一的考量, 并不能很好地解决应用程序之间在Cache与DRAM Bank上同时发生访存干扰的问题. 在此背景下, 本节将介绍基于页着色的多级内存体系“垂直”协同划分机制的发现、原理及应用.

3.1 仅划分Cache和仅划分DRAM Bank的性能分布

Liu等人^{[4, 7]}对200余组由SPECCPU 2006^[29]中的程序组成的多道程序工作集展开了测试和详细分析. 在200余组工作集中(这些工作集包括4道或8道程序不等), 分别独立执行仅Cache划分和仅DRAM Bank划分, 可以得到如图 7所示的性能分布结果图. 图中每一个点代表一个工作集, x轴是仅使用DRAM Bank划分得到的性能提升, y轴是仅使用Cache划分得到的性能提升.

从图 7中可以很清晰地看到, 大多数点都分布在第1象限和第4象限. 第1象限的点表示针对这些工作集, 分别执行Cache划分和DRAM Bank划分能有效提升系统性能. 第4象限的点表示针对这些工作集, 执行DRAM Bank划分可以有效提升系统性能, 但执行Cache划分会降低系统总体性能. 从图中可以看出: 在大多数情况下, 对DRAM Bank进行独立划分可以有效提高系统性能, 而Cache划分则只对部分工作集有效. 这些实验具有丰富的启发意义: 第一, 能否设计一种机制, 针对第1象限中的工作集, 可以将两种划分机制带来的好处累加在一起? 第二, 很明显可以看出, Cache划分是工作集敏感的, 因此在实际应用中要根据工作集特点调整划分算法; 第三, Bank划分普遍能对系统性能带来正反馈, 是一种积极的优化策略, 但问题是性能普遍来讲提高得并不多, 平均只有4%左右.

Liu等人经过深入调研发现: 在主流多核计算机系统的地址映射中, 除了包含能够索引Bank的地址位(Bank bits, B-bits)和索引Cache的地址位(Cache bits, C-bits)之外, 还存在一类DRAM Bank和Cache重合的地址位(overlapped bits, O-bits), 能够同时索引DRAM Bank和Cache set. 这表明, 对O-bits着色就能够同时协同划分内存体系中的DRAM Bank和Cache Set. 这种划分方式因为贯穿了内存体系, 即被称为“垂直”划分^{[4, 7]}. 主流服务器的地址映射可被软件检测获得或由合作芯片设计厂商提供, 这种地址映射为在通用计算机系统上实现“垂直”划分提供了可能^[28].

图 8展示了两种通用CPU对应PFN的构成, 其中, 图 8(a)所示为2.80 GHz的Intel i7-860处理器搭载采用16路组相联的LLC(8MB容量)和DDR3主存(8G容量)时系统的地址映射, 图 8(b)所示为2.40 GHz的Intel Xeon 5600处理器搭载采用16路组相联的LLC(12MB容量)和DDR3主存(32GB容量)时系统地址映射.

文献[4, 7]中介绍了除了单独使用O-bits进行的“垂直”划分(a vertical partitioning, A-VP)外, 当工作集中的程序数大于O-bits能划分的最大颜色数时, 例如2位O-bits能划分4种颜色, 当工作集中的程序数大于4时, 还可以使用O-bits与B-bits或C-bits结合的方式, 这样可以实现偏向于DRAM Bank划分的“垂直”划分(B-VP)或偏向于Cache划分的“垂直”划分(C-VP). 表 2展示了两种水平划分机制和3种垂直划分机制的综合情况.

合理选择划分策略可以最大化性能提升. 从图 7所示第1象限的工作集中随机选择50个工作集, 分别对它们进行Bank-only划分、Cache-only划分、A-VP划分、B-VP划分以及C-VP划分. 结果显示: “垂直”划分(A-VP)技术是普遍有效的, 形成了性能累加的效果, 最高的性能提升可达到16.8%; 而单独DRAM Bank划分和单独Cache划分只有11.7%和5.9%的性能提升, 如图 9(a)所示. 对于图 9(b)所示的工作集, 采用B-VP获得的性能提升比C-VP和仅划分Bank或Cache获得的性能提升要多. 对于图 9(c)所示的工作集, 采用C-VP获得的性能提升比B-VP和仅划分Bank或Cache获得的性能提升要多. 综合来看, 由于累加了多级内存划分的效果, VP的效果要优于单层次内存划分, 但同样也存在工作集敏感性的问题. 后文将进一步分析这一问题.

3.2 “划分”和“融合”规则

从图 7可以看出: 部分工作集是对Cache划分敏感的, 即Cache划分只对部分工作集有效, 而部分工作集采用Cache划分后性能反而有所下降. 因此, 在启用垂直划分时, 应考虑工作集对Cache资源的敏感性. 在前期的探索中, 研究者分别以动态在线或静态离线的采样方式获取单个程序运行参数(如带宽、局部性、Cache缺失率等), 并建立性能模型, 最后利用机器学习方法预测任务级或访存级的调度. 这类方法通过预先建立性能模型, 可以有效降低调度开销, 但也存在着不可忽视的问题. (1) 建模的准确性和复杂度; (2) 采样的开销. 通常, 预测结果的准确度依赖于模型的复杂度以及采样的频率, 这也意味着将增加额外的系统开销^[4]. 此外, 确定性能最佳的内存划分策略需要准确地预测工作负载中每个程序的访存特征及其对每个分配策略的反应, 然而, 由于每个程序的资源需求、访存特征差异较大, 一旦工作负载中的应用程序发生变化, 则对当前划分策略的影响就会较大.

基于上述原因, 为了减少系统总体开销, 并提高策略的适用性, Liu等人提出了一种基于分类的Cache划分机制^[4], 即: 依据程序对Cache资源的敏感性进行分类, 再对不同类的程序采用不同“划分”和“融合”策略. 首先, 依据应用程序对Cache资源的敏感度不同, 将程序分为4类. (1) 对LLC(last level Cache)需求量高的LLCH; (2) 对LLC需求量中等的LLCM; (3) 对Cache资源不敏感且带宽需求小的CCF(core Cache fitting);(4) 对Cache资源不敏感但有很高带宽需求的LLCT(LLC thrashing, “刷Cache”), 如图 10所示. 在运行过程中, LLCT类的程序在Cache上对其他程序干扰较大(造成LLC污染), 在Cache上将其与其他类程序划分开有利于提高系统的整体性能; LLCH和LLCM类的程序对Cache的需求较大, 所以在Cache上不应该限制该类程序的使用(减少少量的LLC容量就会引发较大的性能下降). 在对大量真实工作集测试、分析、总结的基础上, 本文总结了3条“划分”规则.

● 规则1. 包含LLCT类程序的工作集, 采用A-VP/C-VP划分能获得最大的性能提升;

● 规则2. 不包含LLCT类程序、但包含LLCH类程序的工作集, 采用Bank-only划分能获得最大的性能提升;

● 规则3. 不包含LLCT和LLCH类程序、但包含LLCM类程序的工作集, 采用A-VP/B-VP划分能获得最大的性能提升.

以及两条“融合”规则:

● 规则4. LLCH和LLCM类程序可以共享划分的颜色;

● 规则5. LLCT和CCF类程序可以分别融合在一块较小的Cache资源里.

这是因为LLCH和LLCM类程序对于Cache资源的需求量较大, 而现有的最近最少使用算法(least recently used, LRU)能够较好地处理这两类程序产生的访存冲突, 并不会降低系统整体性能. 而LLCT和CCF类程序对于Cache的需求量较小, 采用完全划分的方式并不会提升系统整体性能, 反而会降低资源使用率, 给予它们最小的Cache资源就能够满足多道程序的需求.

3.3 非对称的“垂直”划分架构

页着色技术的核心是调整内存储器体系中的数据排布. 垂直划分技术由Liu等人在ISCA-2014上提出^[4], 并在实践中不断演变. 随后, 一种“非对称”的“垂直”划分机制^[7]被提出, 该机制应用得更为灵活、可靠, 数据排布方式更为简洁、高效, 在实际部署应用过程中开销更低. 以前文所述的Intel i7-860的地址映射为例, 图 11展示了相关“非对称”的“垂直”划分情况.

首先, 在Cache上划分一个较小的区域(占整个Cache的1/8), 即图 11中“000”的区域. 工作集中所有的LLCT类程序共享该区域, 剩余的Cache容量让LLCH、LLCM和CCF类的程序共享, 虽然该划分方法与第4.2节的规则相悖, 但研究发现, 现在多级Cache的设计使得CCF类程序的访存请求在一级缓存和二级缓存中能够得到响应, 所以将CCF类程序在LLC上的划分和LLCH及LLCM类程序的划分合并在一起并不会造成性能的明显下降. 此外, 研究表明^[7]: 从服务器总体性能的角度来讲, 给予CCF类程序一块单独的LLC区域会造成LLCH和LLCM类程序的性能下降, 而这部分下降并不能通过CCF类程序的性能提升得到弥补.

其次, 在DRAM Bank上, 通过O-bits(14位、15位)可以将DRAM Bank划分为4组, 再通过B-bits(21位、22位)可以将这4组划分为16个子组. 这使得在Cache中共享的程序可以在DRAM Bank上进行划分, 从而消除多道程序在DRAM Bank上的访存冲突. 如图 11所示: O-bits为“00”的Bank组被划分给LLCT类程序, 多个LLCT类程序在该Bank组中可以通过B-bits再次划分, 消除彼此在DRAM Bank上的访存冲突; 同理, 也可将O-bits为“01”“10”“11”的DRAM Bank组划分给LLCH、LLCM和CCF类程序, 再通过B-bits进一步划分给各程序, 消除在DRAM Bank上的访存冲突. 此外, 在LLC上共享000区域的若干程序在DRAM Bank上依然可以被划分开, 虽然按照需求在LLC上没有划分, 但在主存Bank上的相互干扰依然可被消除. 具体内容请参考Liu的论文^[7].

综合来看, 采用“非对称”的多层次协同的“垂直”划分更能发挥出计算机潜在的性能. 在实践中, 这种方式比之前的VP表现得更好(无论在页面迁移开销、系统易用度、灵活度, 还是在系统吞吐量、服务质量提升等方面均表现优良); 在最优的情况下, 超过经典的Linux“伙伴系统”的性能21%. 更多细节请参考文献[7].

4 基于页着色的DRAM-NVM混合内存管理

本节介绍的是页着色技术在新内存体系中的应用, 是对该技术在新时代的发展与演进. 目前, 以NVM为代表的新内存材质已经逐步商用. NVM与DRAM相比, 具有大容量, 高存储密度、低能耗以及非易失性的优点. 但NVM写入延迟高、寿命与DRAM相比较低等缺点也限制了其单独作为内存系统的可行性. 为此, 研究者提出了DRAM-NVM混合内存系统. 针对这种新内存体系, 本文将介绍如何将页着色技术应用于对异构混合内存的管理, 并通过设计混合内存访存行为监控器、双层伙伴系统以及页面迁移引擎等机制, 形成一整套内存管理体系.

4.1 页着色技术在DRAM-NVM存储架构中的应用

目前, DRAM-NVM混合内存体系存在两种不同的组织架构.

● 一种是“垂直”管理架构, 将DRAM与NVM置于不同内存层级, 速度较快的DRAM被作为NVM的缓存^{[9, 32, 33]}. 在这种架构中, 需要由专用的硬件逻辑控制NVM和DRAM之间的数据移动;

● 另一种是DRAM和NVM“水平”管理架构, 将DRAM与NVM置于内存层次结构中的同一层级, 且依赖OS等系统软件管理页面和迁移数据^{[32-37, 49, 51]}. 相比于“垂直”管理架构, “水平”架构能够提供更大的物理内存空间. 此外, 设计合理的面向“水平”内存体系的内存管理机制, 可使得水平内存架构性能优于垂直架构. 在“水平”架构下, 内存管理机制的主要挑战是: 数据排布的软件控制、数据迁移以及最大化内存体系的利用率.

针对“水平”架构, 已有研究者^[33]提出了面向NVM的管理策略, 该策略在运行时动态地监测每个内存页的写操作, 并将写密集型页从NVM迁移到DRAM(NVM的写操作速率较低且存在写寿命等问题). 有研究者^{[36-38, 51]}改进了页面迁移算法、管理策略等机制, 并依据页面的热度(即被访问频率)对页面分类, 减少了页面迁移的频次. 实际上, 现有针对DRAM-NVM混合内存管理架构的研究普遍存在着访存行为采样开销过高的问题. 此外, 这些研究更加注重主存架构, 忽视了主存与Cache间的相互影响的联动关系, 以至于使用这些策略得到的通常为次优解. 在上述DRAM-NVM混合内存管理研究的基础上, Liu等人^[8]尝试将页着色应用到DRAM-NVM混合内存管理. 总的思路是: 通过将事件采样与页表遍历结合起来, 以较低的监控采样频率精确地获取页面的热度; 利用NVM/DRAM所处的地址空间对页面着色(位于不同材质上的页面为不同颜色), 同时利用如前文所述的Cache/Bank/Channel index bits将页面与Cache, Bank和通道等绑定, 在能够控制不同内存材质之间数据分布的同时, 也可利用页着色消除多道程序之间在内存体系上的相互干扰, 进而有效提高了包含NVM在内的整个内存体系的资源利用率.

以Inteli7-860平台为例, 如图 12所示: 在64位系统中, 每页的大小为4KB, 第0位至第11位是页面偏移, 第32位作为通道位被使用(每条通道仅连接一种内存材质, NVM或DRAM). 通过为第32位着色(0或1), 可以控制使用哪条内存通道, 即哪个内存段(DRAM或NVM)容纳该页. Cache Set的颜色由PFN的第15位至第18位构成(这些位同样可以索引内存Bank中的一些行), 其大小是LLC中的一个Slab(8MB LLC总容量的1/16). 所以, 可以利用这些位实现对Cache的划分及分配. 此外, 对于NVM和DRAM通道中的内存Bank资源, 可以利用Bank索引位(图 12中的第12位至第14位和第20位、第21位)实现对Bank划分分配. 通常情况下, 第20位、第21位作为一个组合来指定一个Bank Group的颜色. 一个Bank Group由8个内存Bank组成, 内存管理系统可以通过使用多个Bank Group颜色来为某个程序分配多个Bank Group. 因此, 借助页着色技术, 可以实现从DRAM-NVM到Cache的完整内存体系划分. 在通道划分方面, 可以根据页面的读/写特征选择DRAM或者NVM来映射页面, 以求最大限度地利用DRAM和NVM通道提供的总带宽. Liu等研究者^[8]将“热”页(被频繁访问的页面或者流式页面), 特别是那些热写页面, 分配至DRAM中. “冷”页, 以读操作为主的热页(NVM的读速率和DRAM相仿), 则被保存在NVM中以节省能耗, 并为“热”页留出DRAM空间.

在带宽调度方面, 新型DRAM-NVM混合内存管理系统的设计目标是最大化DRAM和NVM的组合带宽(即最大化数据传输速率), 以此避免NVM带宽的明显下降(并且这部分下降不能通过增加DRAM带宽来弥补). 如后文图 14所示: 在活动期, 内存管理系统将10 000个“热”页从迁移队列中迁移到DRAM, 然后监视DRAM和NVM通道上产生的带宽. 当DRAM带宽增加幅度小于前一个周期时, 系统将在下一个周期减少迁移页面的数量(即默认为前一次迁移量的1/5). 此外, 如果发现NVM带宽的减少幅度比DRAM带宽的增加幅度大, 那么它将在下一个周期停止将页面迁移到DRAM; 移动更多的页面不会提高带宽利用率, 因为DRAM带宽接近饱和, 但这会进一步降低NVM带宽, 损害整体带宽. 最后, 内存管理系统会将一些页面迁移回NVM, 以弥补NVM在带宽上的损失. 具体设计细节请参见文献[8, 53].

在Cache与内存Bank的划分方面, 将LLC Slab分为3部分, 分别供流式程序、冷页面和热页面使用. 通过Cache/Bank访存频率记录表, 记录Cache Slab和内存Bank利用率; 将页面放置在低利用率的Cache Slab和内存Bank中, 以提升内存系统利用率, 减少“热”区域访存冲突. 若目标存储区域已被占用, 则选择其他利用率低的Slab. 通过跟踪“冷”页面, 并将“冷”页面迁移至NVM. 图 12详细展示了整个内存管理体系, 设计细节参见文献[8, 53].

4.2 面向DRAM-NVM混合内存管理系统的运行逻辑

DRAM-NVM混合内存管理系统如图 13所示, 由混合内存监控器(hybrid memory monitor, HyMM)、双层伙伴系统(two-tiered buddy system, TBS)以及数据迁移引擎(data migration engine, DME)这3个主要的模块构成. 通过HyMM识别访问频率较高的读/写页面(“热”页)、流式页面以及访问频率较低的页面(“冷”页). 双层伙伴系统是对Linux经典的内存管理伙伴系统的扩展, 系统中的页面按照前文所述着色规则排布^[8], 已着色的页面与通道、NVM/DRAM Bank等绑定. “冷”页面因为被访问频率低, 会被暂时保存在NVM中; “热”页面会被移动到更快速的DRAM中. 最后, 利用数据迁移引擎控制“冷”/“热”页面在DRAM与NVM间的移动.

在先前的工作^{[4, 7, 42]}中, 研究者通过对页表项(PTE/access_bit/dirty_bit)采样的方法判断桌面级应用程序的内存访问模式(冷热页面所在区域以及读写模式). 但该方法在应对占用大量内存以及内存访问模式多变的工作负载则显得捉襟见肘, 例如: 利用PTE采样判断冷热页面区域需要不断地遍历PTE的access_bit位, 产生较大开销. 为了解决该弊端, HyMM模块将事件采样(TLBMiss)和页表遍历结合起来, 可以有效提高识别精度并降低采样开销^[8].

HyMM的监控范围包括TLB的命中率/缺失率、PTE的dirty_bit位以及access_bit位. 如图 14所示的一个实例, HyMM一次完整的检测由准备期与活动期构成. 在初始状态时, 所有程序的数据都预先存储在NVM中. HyMM持续监控TLB命中情况5s, 以确定“热”页面区域与“冷”页面区域. 随后, 通过监控dirty_bit位判断页面的读写模式. 上述两个步骤在准备期完成, 持续时间大约为21s. 在准备期, HyMM通过分析存储在NVM中的数据页, 收集TLB未命中数较大的页面(热页面), 并对这些数据页排序, 为接下来的迁移做准备. 之后是20s的活动期, 在该时期, 页面根据排序高低被动态迁移到DRAM中(热页面被移动到DRAM中). 迁移后, HyMM会以较低的频率地扫描PTE的access_bit位, 以监控DRAM中的页面的冷热程度. HyMM在运行逻辑中会不断循环. 更详细设计请参见文献[8].

双层伙伴系统(TBS)用于分配能够映射到内存体系中指定位置物理页面. 如前文所述, TBS使用PFN中的通道位(channel bit), 将所有物理页面分配到两个子伙伴系统中. 这两个子伙伴系统分别对应管理NVM与DRAM中的页面. 两个子系统仍可以使用其他索引位分配资源. 实际上, PFN中有9位可用于颜色控制(如图 12所示), 即, 共有512种颜色用于多样化的内存资源分配.

在数据迁移引擎(DME)中, 应用两种不同的数据迁移方法: 当NVM的页面向DRAM迁移时, 使用有锁页面迁移^[8], 目的是保证数据迁移的一致性(因为有大量的热页面将被迁移); 当DRAM的页面向NVM迁移时, 使用基于DMA的无锁迁移(因为加锁操作的开销较大, 而从DRAM中替换出的页面通常是冷页面)^{[8, 39]}. 有锁页面迁移是在OS内核原生页面复制方法的基础上实现的^[40], 因此, 该迁移过程需要CPU参与. 当“冷”页面被移出DRAM时, 由于这种页面在迁移的过程中被修改的概率较小, 所以针对“冷”页面迁移, 可以使用基于DMA的无锁迁移, 如果发现页面在此过程中“脏”了, 则可回滚^[8].

在系统验证过程中, 采用划分通道的方式^{[8, 30, 50]}将内存地址空间划分为DRAM段和NVM段, 模拟DRAM-NVM内存架构. 实验平台是一台配置Intel i7-860/2.8GHz CPU和DDR3内存的服务器. 在工作集预热完成后, 研究者采用PIN工具^[52]采集工作集的运行参数, 并将这些参数作为输入, 传入一个开源的x86多核混合内存模拟器^{[44, 45]}. 为了更好地模拟DRAM与NVM的存储架构, 使用Dinero IV^[46]和DRAMsim2^[47]分别优化了该模拟器对Cache的模拟和包含NVM配置的内存模拟. 此外, OS运行时的开销(包括页表项更新开销和页面迁移开销等)以及使用HyMM的采用开销也被记录量化之后输入模拟器. 该模拟器也分别拥有DRAM和NVM内存控制器, 它们均采用FR-FCFS调度策略. 混合内存管理系统中, NVM, DRAM及Cache的详细参数见表 3.

图 15显示了在不同NVM容量配置下的5种应用(包括云计算应用)的执行时间. 在实验过程中, 使用4 GB容量的DRAM与不同容量的NVM组成异构混合内存系统, 验证基于“页着色”的混合内存管理的性能. 实验的基线(baseline)是仅使用DRAM、不在内存架构中使用NVM的情况.

从图 15中可以看出: 仅配备NVM的系统由于NVM较高的写延迟, 性能较差. 在DRAM-NVM混合内存系统中, 如果内存页随机映射到DRAM或NVM中, NVM的高延迟也会导致整体性能下降. 4GB DRAM作为NVM缓冲的“垂直”架构系统也被用作对比实验^[34], 该系统的性能接近基准系统(系统仅使用DRAM的情况). 这是由于大多数热页面在运行时可以通过硬件逻辑迁移到DRAM中, 然而, 由于页面迁移以及硬件采样的开销, 该系统比基准系统的执行时间长4%左右. “水平”架构内存管理系统的性能基本接近完全使用DRAM的情况, 这是一个好的现象, 证明了本文论述的技术的优势. 原因在于以下几点: (1) 平均83.2%的“热”页在运行时迁移到DRAM中, 因此“水平”异构内存架构系统的总延迟与纯DRAM系统大致相同; (2) “水平”架构可以使用NVM通道向CPU传输数据, 与仅使用DRAM相比, 具有更高的总带宽, 并且随着NVM Bank数量增多, Bank并行度越高, 能提供的带宽越大, 也就越有优势; (3) HyMM和数据迁移引擎的开销较低. 这些性能指标的提升与内存体系中数据划分、排布优化有直接关系.

图 16展示了将页着色技术应用在整个内存体系时产生的性能优势. 这里展示了3种情况下的对比: 第1种情况是仅划分缓存; 第2种情况是在缓存划分的基础上对内存Bank划分(也就是前文提到的VP), 但并未将内存通道映射纳入优化范畴; 第3种情况是在缓存、内存Bank和内存通道这3个层面上的整体划分优化. 对比基线是未经修改的Linux原始内核. 第3种情况的平均性能提升比第2种情况高出7.2%, 比基线高出23%. 此外, 由于引入了对内存Bank的管理, 第2种情况的平均性能提升略高于第1种情况. 在第3种情况中, 通过指定特殊页面进入某条特定通道(例如将流式访问的页面限定访问某一条通道, 而不是交替访问所有通道), 能减少如流式程序等对其他程序的干扰. 这说明通过合理地使用页着色技术, 实现对内存资源的精细化管理, 可以有效提升系统的吞吐量. 此外, 工作集1至工作集10中的测试程序数量从4升至8, 系统带来的性能提升仍保持稳定增长. 这说明在干扰越严重的工作集中, 应用“水平”架构内存管理系统能获得的性能收益越高. 更详尽的内容请参见文献[8].

有参考文献^{[6, 43]}表明: 为了保证关键程序的服务质量, 可以采用“多核变单核”的简单处理方法, 即让高性能多核服务器只运行一道程序, 如果存在N个需要保证服务质量的程序, 那么需要N台服务器. 在这种情况下, 资源的有效利用率不到10%. 这对于数据中心这样的大规模计算环境来说, 会造成极其严重的算力资源浪费, 无论与“低碳”环保的全球理念, 还是利益至上的商业目标, 都是严重冲突的. 而基于“页着色”的内存体系划分系列技术可以对数据中心的相关优化提供丰富的参考知识体系. 通过内存划分, 可以隔绝多道程序在数据中心的访存冲突, 从而提高程序的服务质量, 同时还可以提高服务器的资源利用率.

5 总结

本文梳理了内存划分技术的发展, 介绍了有代表性的基于页着色技术内存体系划分机制. 经典的页着色技术仅是用在划分Cache, 而本文涉及的代表工作创新的将页着色用在了整个内存体系(memory hierarchy), 拓展了内存体系优化、操作系统设计的维度, 系国内科研人员Liu首创的成果. 在多核时代, 多道程序在DRAM上的访存冲突制约了计算系统整体性能的提升. 为此, 页着色技术被应用于DRAM划分, 即从OS软件层面出发, 为不同的应用程序分配不同的内存通道与DRAM Bank, 以达到有效消除多道程序在DRAM中的访存冲突, 提高系统的整体性能的目的. 随后, “垂直”划分方法被提出. 其通过合理利用PFN上特殊的地址位(O-Bits), 实现了Cache与DRAM的协同划分. 最后, 本文介绍了如何将页着色技术应用于当前包含NVM的混合内存架构中, 并揭示了这项技术的潜力, 展示了内存划分技术的应用架构和前景.

随着技术的进步, Intel等公司推出了一系列新的内存划分技术, 例如CAT技术等. 底层技术时刻在发生着变化, 内存划分的核心思想一直也在向前演进. 本文的作者相信: 通过阅读本文, 不但能对内存划分技术有较清晰的认识, 同时也能对整个内存体系架构有深刻的理解. 在未来的工作中, 如何将机器学习应用于内存资源划分, 是一个值得探讨的问题. 利用更加复杂的运行参数作为应用程序分类的依据, 构建分类模型, 实现更加多样化的程序分类. 并根据每类的特点, 有针对性地实现对内存资源的划分, 以进一步提高系统性能. 然而, 在这一过程中, 采集更加复杂的运行时参数势必增加额外的开销; 并且, 运行时参数与系统平台的配置密切相关, 会导致已构建的机器学习分类模型针对不同平台移植性较差. 如何解决这两方面问题, 将是未来研究的工作重点.