[论文笔记] 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。
       ![dsssdf[7]](http://lh6.ggpht.com/_NFbnZk4IksM/TKQ94gmjZrI/AAAAAAAAAGk/oq-y5zK-qJ8/s1600-h/dsssdf%5B7%5D%5B2%5D.jpg)