多核环境下程序存储局部性检测与预测方法

As multi-core and multi-processor become commonplace, the competition of shared resource between concurrent programs has become the bottleneck of program performance. Due to the complexity of computer architecture, the CPUs distribute on one machine will share the last level cache (LLC) and read/write memory and disk through the same bus. By analyzing the behavior and periodicity of a program, we could intelligently assign shared resource to the concurrent programs, and schedule their usage of shared cache, memory and bandwidth, so as to improve their performance. We'll seek for a measurement with online-availability and low cost, by the benefit of Performance Monitor Unit (PMU) in x86 architecture, and also the mechanism of page tables, to use it to direct the scheduling via predicting one program's locality and periodicity. This measurement and scheduling policy will be applied onto virtualized environment to manage the virtual machines and their migration.

随着多核、多处理器应用的普及，并发程序对共享资源的竞争成为程序运行的瓶颈。由于计算机存储架构变得越加复杂，分布在一台机器上的CPU通常会共享最底层的缓存资源，并共同通过总线对内存及磁盘进行读写操作，从而共用总线带宽。通过分析程序行为特征和程序的周期性，我们可以合理的分配程序对共享资源的占用，通过调整程序对缓存资源、内存资源以及带宽的使用，从而提升并发程序的性能。我们将寻找一个开销低并支持即时检测的测量方法，利用x86架构中的性能检测单元，以及操作系统的页表机制，在线监测程序的行为特征，如程序的存储局部性和周期性，来预测其对缓存、内存和带宽的占用，进而进行合理的调度。这种方法同时也可以被应用到虚拟化系统中,用于调度虚拟机以及对虚拟机的迁移做出决策。

本项目主要围绕多核环境下程序局部性理论以及在局部性理论指导下的Cache/内存管理分析与优化等开展研究。..在局部性理论方面：提出了一种基于平均淘汰时间（Average Eviction Time，AET）的缓存动力学模型，能够以当前最低的时间和空间复杂度来动态探测程序缓存失效曲线，可以适用于各种存储缓存系统中；针对系统虚拟化环境，提出了一种基于硬件计数器的间歇式虚拟机内存工作集预测方法，可以同时在小页或大页内存环境下以很低的平均开销获得很高的平均精度；此外，还探索了利用机器学习方法来进行AI训练任务的存储资源预测的研究，可以根据AI训练任务的参数特征准确预测其在运行时的Cache/内存资源需求。..在Cache管理分析和优化方面：提出了共享逻辑时间的概念，建立了多核环境下多个程序并发执行时的缓存失效曲线组合模型，并据此给出一个共享缓存下并发程序最优共生和公平调度策略；提出了缓存定量配给、缓存划分共享等新的“保守共享”的缓存管理策略，在保证每个应用拥有一定比例的缓存的同时，又使得多余缓存能够在被所有应用按另一比例共享；基于Intel CAT技术和局部性理论，提出了一种基于部分共享的高速缓存动态分配方法，能够细粒度地动态分配缓存资源，支持多种优化目标；针对访存密集型的GPGPU程序，提出了一种同步栅栏感知的缓存管理策略，根据非关键线程束的一级数据缓存命中率来动态选择不同的线程束调度策略，可以显著加快关键线程束的执行。..在内存管理分析和优化方面：针对虚拟化环境，设计实现了虚拟机内存动态调配机制，以虚拟机内存工作集预测为依据，基于动态规划算法，可以以较小的代价找到最合适的内存调度方案；提出了一个基于对齐的大页优化机制，提升大页使用率，并对不同内存虚拟化方法下如何使用大页机制进行了全面分析；针对分布式内存缓存系统（如Memcached和Redis），提出了缓存失效代价感知、局部性感知的内存分配算法，使得系统整体的失效率或平均响应时间最小；系统分析了GPU程序并行访存请求的熵值分布，以此为依据提出了一种高效节能的地址映射机制，可以充分发挥DRAM的带宽，提高GPU程序的性能。