Object-Level Memory Allocation and Migration in Hybrid Memory Systems

Paper

发布日期: 2023-05-01

文章字数: 3.2k

阅读时长: 11 分

阅读次数:

1. 论文信息

文章来自HPCA 2022属于CCF-A
Object-Level Memory Allocation and Migration in Hybrid Memory Systems

所有作者及单位

Haikun Liu, Renshan Liu, Xiaofei Liao, Hai Jin, and Yu Zhang 华中科技大学大数据技术与系统Lab、服务计算技术与系统Lab、集群与网格计算Lab
Bingsheng He 新加坡国立大学

2. Background

充分利用NVM和DRAM混合系统的优势，主要目标是将应用程序数据正确放置在混合存储器上。

观察发现1：每个页面中的热数据只占应用程序总内存足迹的一小部分，但却导致了应用程序总内存引用的很大比例。X轴显示了应用程序所有内存页中频繁访问的数据流量的百分比(按访问频率降序排列)，Y轴显示了应用程序的总内存引用的累积分布。对于soplex来说，近35%的热数据占了总内存引用的98%。这意味着迁移soplex中的部分热数据(变量和对象)比迁移整个页面更有好处。然而，对于一些应用程序，如dict，内存访问均匀地分布在应用程序的地址空间中，因此从数据迁移中获益较少。

观察发现2：很大一部分的应用程序的对象都比页小得多。这些应用程序的对象大小的分布函数。我们可以发现对于dict、isort、gcc和maxMatch来说，95%以上的对象都小于50字节。对于soplex，小对象的比例也超过85%。由于大多数应用层面的内存引用是对象和变量。程序员可以充分利用应用语义来优化对象粒度的数据放置/迁移。相反，一个页面可以包含许多对象，这些对象可能有不同的访问行为，合成的页面级访问统计可能变得复杂和不可预测。

观察发现3：很大一部分应用程序的对象显示出较长的寿命。虽然以前的研究表明，许多程序的对象往往有一个相对较短的寿命[15]，[22], [23], 我们发现，在某些情况下，仍然有很大一部分长寿命的对象。图3显示了一些应用程序的对象寿命的累积分布函数。我们发现在gcc、isort和soplex中几乎所有的对象都有超过1000秒的寿命。特别是，gcc中所有对象的寿命都等于应用程序的总执行时间。

观察发现4：一部分应用对象在不同的执行阶段表现出高度突变的内存访问频率。尽管许多对象在其整个生命周期中表现出相对一致的访问行为（即所谓的不可改变的对象），但仍有很大一部分对象在不同的执行阶段表现出高度突变的访问频率（即所谓的易变对象），如表1所示。这意味着仍有很大的空间可以通过运行时的对象迁移来优化数据放置。

总之，观察结果1和2清楚地表明，数据访问监控和内存分配/迁移应该是在对象上，而不是在页面上。观察结果3和4表明，在混合内存系统中需要对对象迁移进行仔细的设计。

3. 解决了什么问题

提出混合内存系统编程接口，对象粒度迁移，减少迁移开销。减少系统耗能，同时提高应用性能。

4. 其他学者解决这个问题的思路和缺陷

以前的研究主要集中在页面迁移方案上，以实现更高的性能和能源效率。但是，这些方案都依赖于在线页面访问监控成本高。并且还会由于多核时维护缓存/TLB一致性和dram带宽争用产生更多页粒度迁移的开销。

依赖于页面访问的recency and frequency来决定数据在DRAM或NVM上的位置。1)一些用硬件辅助页迁移的方案由于目前硬件不支持页面访问技术，需要对硬件架构进行大量修改[5][6][11]。2)用操作系统监控内存访问只能引用1个访问位不足以表达页面冷热度[12][Thermostat13]。3)页面迁移通常需要一段时间来检测热页。4)预测的页面访问模式可能与未来的访问行为不一致，导致不必要的页面迁移。5)大页（huge page）已被越来越多地用于大数据应用和虚拟化平台[13][14]，由于对DRAM容量和带宽的低效利用，粗粒度的页面迁移甚至会降低系统性能。

5. 围绕该问题作者如何构建解决思路

1）首先静态分析对象被引用的次数。使用LLVM从源代码中生成中间代表（IR）。为了计算对象级的内存引用，我们利用LLVM的PASS来遍历所有的加载/存储/分配/调用/映射指令，并在IR中插入探针。运行由修改后的IR生成的可执行文件，并通过LLVM PASS自动收集所有对象的访问信息到一个跟踪文件中。内存跟踪包含5个项目，包括”内存访问类型、虚拟地址、对象名称、对象类型和访问时间”。通过跟踪，我们很容易计算出对象的总内存引用和寿命。

2）然而，只有一部分指令导致了对主内存的实际数据流量。原因是片上高速缓存可以过滤大量的内存访问热数据。于是设计了缓存模拟器，将LLVM生成的跟踪文件作为输入，并过滤程序中所有在模拟缓存中被击中的虚拟地址。剩余的虚拟地址反映了高速缓存的缺失或高速缓存的驱逐操作，并导致对主内存的实际内存访问。图5显示了不同应用程序对高速缓存和主内存的所有数据访问的分布。我们发现，片上高速缓存平均能够过滤68%的总内存引用。对于gcc，甚至87%的数据访问都被过滤掉了。因此，当考虑到缓存过滤的影响时，应用程序的内存访问模式可能会非常不同。一些非常热的数据可能总是在高速缓存中被命中，而只导致对主内存的极少量的数据访问。因此，没有必要将这些数据从NVM迁移到DRAM上。通过我们的缓存过滤器，我们可以在NVM上获得真实的内存访问统计，并避免在运行时进行不必要的对象迁移。

但问题是片上缓存也不是缓存的对象啊？

3）建模决定数据效用（就是一个该不该放DRAM的权重吧）。提出了一个效用函数（延迟和能耗）来计算在给定的时间段 $T_i$内将对象放在DRAM或NVM上的好处

4）程序执行期间的热对象迁移工作。因为之前说了有易变对象和不易变对象（指热度）。将对象的内存访问模式分为不同的阶段，设定阈值E，在每个时隙去计算当前这个对象效用值，并且判断是不是不可变对象。对于不可变的对象，如果其平均效用大于E，这些对象将被放置在DRAM上。对于突变的对象，其第一阶段的平均效用决定了该对象应该被放置的位置，而对象的迁移应该在一个阶段发生变化时进行。在图6中，对象A、B和D首先应该被分配到DRAM上。对象C一开始应该被分配在NVM上，然后应该被迁移到DRAM上。

5）初始对象分配的实现。根据效用值的阈值、当前DRAM容量这些情况来决定分配的层级的。

扩展了Glibc库，为混合内存系统提供DRAM分配和NVM分配API。因此我们修改了Linux内核，在虚拟地址空间（VMA）中将NVM页与DRAM页区分开来。因此，我们在逻辑上将主内存分为两个区域。我们在VMA中标记NVM页，并为NVM分配提供一个新的分支NVM mmap。

6）运行时对象迁移的实现。采用静态代码工具，在应用程序的源代码中添加对象迁移指令。在运行时，应用程序本身执行对象迁移，没有任何操作系统的干预。我们观察到，大量密集的内存访问主要归因于循环状态[25]。我们用循环作为断点，将源代码分成几个代码片段。首先，我们用LLVM跟踪对象的访问次数以及循环开始和结束时的时间戳。对于每个对象，我们在循环的执行过程中计算其效用值。循环开始和结束时效用值的突然变化意味着内存访问模式发生了变化，该对象应该在循环之前被迁移到另一种内存。我们用时间戳来定位这个特定的循环状态。最后，我们使用LLVM在循环的开头插入对象迁移语句。

图7显示了一个混合内存分配和对象迁移的代码工具化的例子。我们根据LLVM中的抽象语法树（AST），以静态单一赋值（SSA）的形式遍历所有对象，并用DyMalloc改变源代码中的所有malloc。我们使用shared_ptr创建对象，这是一个智能指针，通过指针保留对象的共享所有关系。这允许几个shared_ptr对象共享同一个对象的内存。shared_ ptr使用一个控制块来记录所有指向目标对象的指针和总引用的数量。例如，在图8中，指向对象3的两个指针被记录在控制块中。只有当引用计数器变为零时，被管理对象才会被销毁。对于可改变的对象，我们使用MigrateToX API将对象复制到另一种内存中，然后所有存储的指向被管理对象的指针现在应该指向新的内存地址，如图8所示。对象迁移指令被插入到一个适当的地方（很可能是在循环语句之前），在那里对象的访问模式的变化。通过这种方式，我们在迁移后改变对象的虚拟地址，并在运行时更新对对象的所有引用。