[论文笔记] Adaptive Insertion Policies For High Performance Caching

Paper: Moinuddin K. Qureshi , Aamer Jaleel , Yale N. Patt , Simon C. Steely , Joel Emer, Adaptive insertion policies for high performance caching, Proceedings of the 34th annual international symposium on Computer architecture(ISCA), June 09-13, 2007, San Diego, California, USA

---

 

问题描述：当程序重用Working Set大于可用Cache时或者其存储访问具有低局部相关性时，Cache替换策略中最常用的LRU策略表现出十分低下的命中率。大量新替换入Cache的行对命中率的贡献为零，而原本可能命中的行则由于长期不被访问而替换出Cache。

        本文认为对于以上描述的情况，如果Working Set的一些片段能被驻留于Cache中而不被LRU策略替换，将能有效地提高Cache的命中率。文章将Cache替换策略分为两个部分：牺牲者选择策略和插入策略，并通过简单地修改插入策略显著地改善Cache性能，且无需对现有硬件设计作大的改动或消耗大量的存储空间。

        本文的主要贡献在于：
        1) 提出了LRU Insertion Policy (LIP) 。该策略将所有替换入Cache的行置于LRU端。相对于传统策略将所有替换入的行置于MRU端，LIP使一部分行得以驻留于Cache中，其驻留时间能比Cache本身容量更长。LIP策略能够很好地应对Thrashing，尤其对于循环访问内存的程序其性能近似于OPT策略。由于LIP中并没有引入年龄，其无法响应Working Set的切换。
        2) 提出了Bimodal Insertion Policy (BIP) 。BIP策略是对LIP的加强和改进，新换入的行会小概率地被置于MRU端。BIP可以很好地响应Working Set的切换，并保持一定的命中率。
        以上两种策略对于LRU-friendly（高局部性）的程序，性能均不佳。
        3) Dynamic Insertion Policy (DIP) 能动态地在LRU和BIP间切换，选择其中命中率较高的策略执行后续指令。DIP对于LRU-friendly的程序块使用LRU策略，对于LRU-averse的程序块使用DIP策略，以求通用效率。对于1MB16路L2 Cache，DIP策略较LRU降低21%的失配率。
        4) 文中还提出了Set Dueling作为DIP中的调度选择策略。Set Dueling选择块中的少部分来分别执行两种竞争策略，而其余部分执行两者中失配率较低者。Set Dueling方法除了失配计数器，并不需要额外的Cache开销。
        本文在不同大小的Cache、不同的benchmark下，对各种策略进行了比较，并给出了详尽的图表和分析报告。

        本文最突出的地方在于提出了一种实现起来十分简单、且不用消耗过多资源却能有效地提高了Cache性能的策略。文中的插入策略都是针对LRU进行的，但思路可以被推广到LFO等其他页面调度算法中，或许也能得到不错的性能改善；Set Dueling也可被用于其它需要动态调度的策略。