[论文笔记] 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。
      

[论文笔记] Action Recognition from Arbitrary Views using 3D Exemplars

Paper: D. Weinland, E. Boyer and R. Ronfard. Action recognition from arbitrary views using 3D examplars, IEEE International Conference on Computer Vision (ICCV), 2007

---

问题描述：动作识别的研究大致可分为两个方向：1. 以模型为基础(Model based approaches)。建立一个已知的基于描述符或节点的（运动学）模型，通过恢复描述符来恢复动作，这种方法在没有中间介质和界标的情况下很难完成；2. 以模版为基础(Template based or holistic approaches)。这种方法通过图像信息、轮廓或光流等恢复动作，但其要求观察到的动作和学习用的动作是在相似的摄像机配置下采集到的。本文以第2种方法为基础，提出了一种无需相机和物体间相对朝向的先验知识的动作识别方案。这样做的主要目的在于能够识别未知场景中的动作，而无需特定的数据库训练，对于监控识别等领域十分有用。 

      文中提出的识别框架其实是一个以动作样例为基础的HMM模型，如下图所示：
     
       1) 本文将动作看作是一条隐式马尔可夫链，是一串以一定概率随机转换的动作状态；Exemplar是可用于充分表述动作的范例，文中认为所有动作其实可以用有限个范例组合起来表示，类似于全能的关键帧概念；动作状态之间的转移概率通过学习获得。
       2) 实际观察到的动作被视为是人相对相机的朝向和人体中心位置这两个随机值共同作用产生，结合对应的Examplar，生成观察到的图像。其中人体中心位置可以从其轮廓在图像中的位置判断，而人体朝向则是有一个隐形状态，它们之间有一定的转移概率。
       至此，动作的识别问题，就转换为求解这个HMM模型的问题。
       3) 此外，该模型涉及两方面的学习问题：Exemplar的选取和状态间转移概率的确定。前者通过贪心的forward selection算法迭代选取产生，总是选择使得分类器使用其与已知Exemplar对测试集识别率最高者；后者则又分3D和2D，对应图中的两条链，使用forward-backward算法获得。

       本文最大的亮点在于其对动作匹配的HMM建模和识别过程的架构设计，并且应用该模型学习的程序可忽略摄像机的具体位置朝向，并无需特别的训练，都能对动作进行识别，具有很大的通用性。

[论文笔记] Free Viewpoint Action Recognition Using Motion History Volumes

Paper:  Daniel Weinland , Remi Ronfard , Edmond Boyer, Free viewpoint action recognition using motion history volumes, Computer Vision and Image Understanding, v.104 n.2, p.249-257, November 2006

---

问题描述：大多数动作或手势识别的方案都是视点相关的。因此，文本提出了一种视点无关的Motion History Volumes (MHV)方法，可用于识别基本动作或手势，无视性别、个体大小和视点。不同于视点相关方法，MHV需要多摄像机并需要定标。

       文中将动作识别分为两个任务：1. 从图像输入中抽取动作描述符(Motion Despritor)；2. 将这些动作描述符分为不同的动作类。MHV针对第一个任务。

       MHV的灵感来自于平面动作能量图(MEI)和动作历史图(MHI)，类似于动画制作中的半透明过渡帧效果。从公式上，MHV中的每一个体素的值可以看做轮廓体最后一次经过该体素距离当前的时间，时间越短则值越大。轮廓体本身的提取可以通过多个经过定标的摄像机轮廓在3D空间中切割得到。
       
       文中假设所有的动作都可以在一个以人体为中轴的圆柱体中完成。因此对于MHV，可按极坐标展开。而后以旋转角度theta为不变量，对其做傅里叶变换。得到的所有(r, z)对，组成了该MHV的特征向量。
      

      
       最后对该特征向量，使用PCA或LDA或结合两者降维，既可用于动作间的比较和分类。作者的实验结果，MHV方法对于走路、下蹲、抬手等基本动作，给出近93%的平均识别率，效果十分不错。

       本文提出的MHV方法将四维的动作转化为直白的三维体素，体素值可以很直接地表示动作运动的轨迹和趋势，展开为直方图后也更容易应用一些成熟的降维、统计学算法等，在学术上是一种十分有趣的表述动作的方法。但是由于轮廓体本身的获取并不十分准确，很多细节的提取依赖于采集的2D本身的质量、前背景的区分程度、视点的数量和动作本身的特点(有些动作本身就决定它的细节不可能被轮廓体表示，如双手交叉在胸前) 等，使得MHV在目前只能用于简单动作的识别，或者说是动作的粗犷分类。可以预见，如果三维物体恢复技术能够更上一层，MHV将变得更有价值。

[论文笔记] Single View Human Action Recognition using Key Pose Matching and Viterbi Path Searching

Paper: F. Lv and R. Nevatia. Single view human action recognition using key pose matching and viterbi path searching, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007

---

 

问题描述：3D识别姿势主要有两种方法：恢复和样例匹配。前者的困难来自于超大量需要估算和评价的参数和由于透视投影带来的歧义性；后者则建立在样例库中足够大的前提下，因此存在不精确或不匹配情况。

 

       本文基于人体基本动作（如走、坐）展开，认为动作有以下3条特性：动作的发生是有序的；动作之间无法任意地切换；动作间的过渡是平滑的。基于以上观点，文中基于样例匹配提出了一种从2D轮廓序列识别动作的方法。

       1) 样例3D数据从Motion Capture捕获，并分为小片段，使用DTW算法对齐，寻找关键帧（文中以动作幅度定义帧的能量，若该帧是一定滑动窗口中的Min或Max，则认为该帧为关键帧）。此后，以此关键帧表示该3D动作。

       2) 从各个角度获取该3D动作的2D轮廓，并按照定义的相似性度量组织为一个Action Net，如下图所示。在Action Net中，关键帧可停留（Loop Link）；有些动作可以重复循环进行（Back Link）；边缘姿态相似的动作可以平滑过渡（Inter Link）；临近角度的动作可相互过渡（Unrolled）。Action Net是有向的，动作按照箭头指向，在关键帧间平缓过渡。

    

       3) 文中定义的轮廓间相似性度量参考Shape Context。其不同之处在于，将轮廓点集中各点的直方图集合为一个，方便查看和计算。文中使用PMK算法计算两个轮廓间的距离，并提出了改进的PMK-NUT算法强化相似与不相似间值的差距。此为本文的主要贡献之一。

       4) 对于输入的动作，提取轮廓后，动作的每一帧与Action Net中的每一个节点比较，后使用Viterbi算法找到最佳的匹配方案，最后输出对应的3D动作序列。这里可以参考Motion Graph相关，吾觉思想大致相同。

 

       此为整合性论文，无甚特别建树。基于单视角的基本动作识别准确率在80%上下，无甚吸引力。

       唯引出两个有趣的算法Shape Context和PMK，值得一探。

 

[论文笔记] Shape Matching and Object Recognition Using Shape Context

Paper: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002

---

只就其中Shape Context相关核心部分阅读。

问题描述：一些在肉眼看来相似的图形，在旋转、变形等细小变化后就无法被传统图形识别方法（Feature-Based、Brightness-Based）识别。文中提出了一种简单且鲁棒的方法，来寻找图形间的一致性。

    

       文中将图形识别问题分为3步：

       1) 解决两个图形间的对齐问题；

       2) 估计两者间的对齐变换；

       3) 用此对齐变换的matching error计算两个图形间的距离。

       对图形识别应用Shape Context方法的步骤大致如下：

       1) 获取图形的轮廓边缘，并用离散点表示如(a)(b)。这些点不一定是极点或角点，当点的采样越高越能表现图形的细节；

       2) 对于该点集中的每一个点P，应用一个指数-极坐标。该指数-极坐标被分为r个半径区域，theta个角度区域，共N个bin。该坐标系给于靠近参照点的点更高的权重，使得Shape Context方法对局部更敏感；

       3) 对每一个bin，统计除点P外的轮廓点的个数，得到如(d)(e)(f)的直方图；

       4) 对两个图形上的每一对点，使用一下公式计算它们之间的匹配代价；

            

       5) 则使得所有C值的和最小的匹配为对齐变换。

     

       Shape Context无视图形的旋转、缩放等变形，在这方面类似Hu等不变矩，但较之鲁棒得多。但由于其是基于图形轮廓边缘的算法，在应用于实际图像时，若前景与背景很难区分或提取的轮廓效果不好出现漏洞断裂等情况，则不能达到很好的效果。

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