题目：热度感知的内存布局优化

简介

本项目旨在对现有内存分配器进行优化，使其具有分配对象访问热度的感知能力，能够在分配时预测被分配对象在未来的访问频率，从而调整相应对象的布局，使得使用该分配器的应用程序能够获得更优的程序局部性，提高硬件缓存的使用率，进而在运行性能方面得到提升。

本项目核心思想是将冷热对象的布局进行分离，分别为冷热对象设置了内存池，将热对象集中在一起，冷对象集中在一起，由于程序会频繁的访问热对象，因此能够充分利用硬件的预取能力和缓存能力，提高cache line的命中率和TLB的命中率。

优化后的内存分配器主要包含两个模块：离线分析模块和在线推理模块。其中：

1. 离线分析模块主要利用Profiling-Guided Optimization技术，预先对应用的内存分配行为和对分配对象的访问进行插桩，离线地分析应用的内存访问行为，并采集行为数据（如调用栈、对象访问热度、对象大小等）。
2. 在线推理模块主要在运行时实时采集应用的当前行为，并于离线分析模块采集到的行为数据进行匹配，从而感知程序未来对内存对象的访问热度。如果匹配成功，则认为该对象在未来会被频繁访问，因此将其放置在热的内存池中，否则将其放置在冷的内存池中。

详细技术报告见report.pdf。

挑战

本项目的主要挑战着在于如何在线推理时的开销。具体体现在：

1. 实时采集应用当前行为会引入较大开销。本项目通过优化调用链解析，利用动态库名加库内偏移来区分每一个调用栈，而不是函数名加函数偏移，降低符号表的查询开销。
2. 实时推理也会引入较大开销。本项目通过引入缓存机制，记录近期推理过的调用栈及其推理结果，减少重复推理的开销

开发量 & 交付件

• tcmalloc：本项目基于Google的TCMalloc分配器 [1] 进行二次开发，使其支持热度感知能力；同时基于intel pintool实现profiling。总体代码改动约910行
• GeminiGraph：本项目的测试应用 [2]，通过LD_PRELOAD预加载我们编译好的tcmalloc分配器，应用程序可以无感知地、透明地获得性能提升。
• pin：基于Intel Pintools实现的Profiling分析工具，用于离线分析程序的内存分配行为和访存行为。
• lstm.py：基于LSTM神经网络的访问热度模型

测试

在 GeminiGraph 上进行测试，应用twitter数据集和rgg数据集，与使用没有热度感知的内存分配器相比，性能提升约5%。

性能提升、对象布局等测试结果详见results目录下文件。

References

1. TCMalloc. https://github.com/google/tcmalloc.
2. Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. Gemini: A Computation-Centric Distributed Graph Processing System. 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI’16).