摘要: 传统Cache由硬件管理，使用固定的管理策略，包括Cache容量、块大小、相联度、一致性协议等。这种管理方式依据的是程序中数据访问的历史信息，因此，它难以适应不同程序复杂多样的访存模式。为此，研究人员提出了面向数据对象Cache技术。面向数据对象Cache是一种动态可重构Cache技术，程序中不同的数据对象在这种Cache中被分配进不同的Cache段，每个段是一片连续的Cache区域。同时，针对不同数据对象的访存模式，面向数据对象Cache能够为其在相应的段中动态选择不同的Cache策略。针对这种动态可重构Cache结构，本文第一次从定量的角度给出了数据对象访存模式的度量方法，并研究了数据对象在Cache上的分配算法。这使得用编译器实现对面向数据对象Cache的自动管理成为可能，从而大大降低程序员的负担。
针对数据对象访存模式与不同Cache策略的关系，本文基于数据重用模型给出了数据重用的定量度量方法，应用了重用向量、访问矩阵、重用向量空间等代数学方法。同时，结合循环边界等程序信息，定义了时间距离、空间距离、真共享向量、伪共享向量等。它们分别反映了数据重用对不同Cache策略的各种需求，包括Cache容量、块大小、相联度和一致性协议。因此，通过求解这些参数可以定量分析数据对象对Cache策略的各种需求，从而指导面向数据对象Cache中数据对象所在段的各种Cache策略选择。关于数据对象在Cache上的分配问题，本文提出了一种图着色分配算法。通过将数据对象在Cache中的分配问题转换为图论中的图着色问题，本文从数据对象的生命周期出发，给出了在Cache中分配数据对象的高效算法。此外，对于一些特殊数据结构或复杂程序结构引入的特殊问题，本文给出了启发式的解决方案，使得编译器可以应对程序中的各种复杂情况。
针对来自科学计算、数据库管理、多媒体应用等多个领域的15个基准测试程序，本文分别使用Simplescalar和Simics模拟器测试了单核系统和多核系统中面向数据对象Cache的性能。通过使用本文提出的编译管理方法，面向数据对象Cache在单核处理器上的失效率比传统Cache平均降低44.98%，最多达到93.02%，并且与最优替换算法下的理想Cache性能非常接近；在多核处理器上失效率平均降低49.69%，最多为73.99%。因此，本文的方法能够在很大程度上提高Cache的利用率，提高系统性能。此外，本文的编译方法主要由基于仿射下标数组的数据重用模型导出，不能高效处理程序中非仿射下标等一些复杂情况，这些是未来要进一步展开的工作。
在本文方法的指导下，编译器能够通过静态分析得到数据对象对Cache策略的需求，并完成数据对象在Cache上的分配，从而实现对面向数据对象Cache的自动管理，大大降低程序员的负担。同时，本文的方法探索了对重用性的度量，给出了Cache参数与重用性之间的关系，对其他局部性优化技术也有很好的指导意义。