[论文笔记] Adaptive Insertion Policies for Managing Shared Caches

Paper: Aamer Jaleel , William Hasenplaugh , Moinuddin Qureshi , Julien Sebot , Simon Steely, Jr. , Joel Emer, Adaptive insertion policies for managing shared caches, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada

---

问题描述：在多核处理器中往往存在多个应用程序竞争使用Cache的情况，而传统的LRU策略基于程序的需求率Rate of demand来决定Cache资源的分配，但事实证明根据程序是否从Cache获益才是更为合理的分配方式。文中基于近期发表的DIP插入策略扩展，考虑同时运行的多个程序的Cache分配问题，提出了Thread-Aware Dynamic Insertion Policy(TADIP)。并，使用TADIP策略的Cache，其性能相当于两倍容量的使用LRU策略的Cache。

       文中认为程序按照Cache容量与失配率间的关系可分为四类：1) “Cache Friendly”；2) “Cache Fitting”；3) “Cache Thrashing”；4) “Streaming”。其重用运行所需的Cache容量依次增大，在TADIP策略中的资源分配优先级依次降低。TADIP策略认为，要将更多的资源分配给能从Cache中获益的程序，也就是能够重用Cache的程序。

      

       TADIP是DIP插入策略在多线程上的应用，它试图对每一个运行中的程序决策其Cache插入策略(LRU=0, BIP=1)。那么，当N个程序竞争Cache时，就等于从2N种组合策略中，选择最佳的一条N位Stream作为方案。最Naive的方法就是对所有的组合策略遍历运行后选取失配率最小的一种，但这种方法面临着指数危机，只有当N较小时，才能使用Set Dueling做实时决策。
       因此，文中对TADIP做了两种扩展：
       1) TADIP-Isolated。这种方法对每个程序单独决策。它使用N+1个SDM，其中：第一个SDM称为baseline-SDM，所有的App均使用LRU策略；其余的SDM称为bimodal-SDM，有且仅有一个App使用BIP（其余LRU）。如<0, 1, 0, 0>，App2使用BIP，App1/3/4使用LRU。这种方法同样使用Counter计数的方法决策。当baseline-SDM发生失配时，所有App对应的Counter++；而当bimodal-SDM发生失配时，只有对应1位的Counter--。也就是说，当LRU对Cache性能造成伤害时，那就是用BIP吧。当然如果Counter=0，还是使用LRU。
       2) TADIP-Feedback。这种策略认为插入决策是不能与其他程序剥离开的。它使用2N个SDM，每个程序占用其中的一对SDM。在这一对SDM中，拥有者分别使用LRU和BIP策略，而其余程序则使用它们当前的最佳策略。然后通过Counter计数决定跟随块的插入策略。这种策略引入了所有程序的当前策略作为新策略的参考，显然要比第一种更加合理可靠，但却需要更多的SDM和Counter。