[论文笔记] 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也可被用于其它需要动态调度的策略。