动态模型预测存储Cache的快速未命中率曲线

ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月存储Cache的快速未命中率曲线建模Xiameng Hu，Xiaolin WANG，and LAN ZHOU，北京大学北京大学深圳市云计算技术应用重点实验室ZHENLIN WANG，密歇根理工大学陈丁，罗切斯特大学CHENCHENG YE，华中科技大学重用距离（最近最少使用（LRU）堆栈距离）是存储缓存性能预测和优化的重要指标在过去的四十年里，重用距离测量的算法效率得到了稳步提高。近年来，无论是在理论上还是在实际执行上，这一进展都在加快。在这篇文章中，我们提出了一个动力学模型的LRU高速缓存存储器，基于平均驱逐时间（AET）的缓存数据。AET模型能够快速测量和使用低成本采样。它可以在线性时间内以极低的空间代价产生脱靶率曲线在存储跟踪基准测试中，与以前的技术相比，AET此外，AET是一个可组合的模型，可以通过对单个程序或跟踪进行采样和建模来表征共享缓存行为。CCS概念：·计算方法学→建模方法学; ·信息系统→高级存储管理;附加关键词和短语：缓存系统，数据局部性，未命中率曲线ACM参考格式：Xiameng Hu，Xiaolin Wang，Lan Zhou，Yingwei Luo，Zhenlin Wang，Chen Ding，and Chencheng Ye.2018.存储Cache的快速未命中率曲线建模 ACM Trans. 存储14，2，第12条（2018年4月），34页。https://doi.org/10.1145/31857511介绍存储系统是一个多层次的结构，其中上层存储器通常起作用的缓存为较低级别的存储。这种设计的动机是程序局部性的一个简单事实：在任何时间段内，程序中只有一小部分数据会被频繁使用。这种行为过去是用工作集局部性理论来建模的 （Denning1980），其中数据局部性的特征在于工作集大小（WSS）（Denning1968; Denning and Slutz1978）。本研究得到了中国国家自然科学基金的部分资助（资助号：61232008、61472008、61672053和61672053）。U1611461）;深圳市重点科研项目编号：JCYJ 20170412150946024;国家自然科学基金（合同号：CSR-1618384，编号CSR-1422342，编号CCF-1717877，编号CCF-1629376和No.CNS-1319617）;和IBM CAS Faculty Fellowship。作者Hu，X.王湖，加-地Zhou和Y.北京市海淀区颐和园路5号北京大学罗先生王，密歇根理工大学，1400汤森大道，霍顿，MI 49931-1295;电子邮件：zlwang@mtu.edu; C。丁，罗切斯特大学，500约瑟夫C。威尔逊大道，Rochester，NY 14627;电子邮件：cding@cs.rochester.edu; C.中国武汉市珞喻路1037号，华中科技大学，电子邮箱：yechencheng@ gmail. com。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要。以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。从permissions@acm.org请求权限。© 2018 ACM 1553-3077/2018/04-ART12 $15.00https://doi.org/10.1145/318575112ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月十二：2X. Hu等人图1.一、MRC分析技术的时间和空间开销定位技术已经发展了几十年。它们被广泛用于在不同级别的内存层次结构的管理和优化。如图1所示，通过重用距离分析和结果未命中率曲线（MRC），在模型局部性方面取得了很大进展。根据程序的参考轨迹，可以通过测量重用距离（Mattson等人定义的最近最少使用（LRU）堆栈距离）（1970））。重用距离是指对同一位置的两次连续访问之间的不同数据访问次数。精确的重用距离跟踪需要O（NlogM）时间和O（M）空间来跟踪N次访问M个不同的元素（Olken1981 a）。对 于 CPU 工 作 负 载 ， 最 近 的 足 迹 理 论 （ Xiang et al.2013 ） ， StatStack （ Eklov andHagersten2010）和时间到位置转换（Jiang et al.2010; Shen等人2007）使用重用时间而不是重用距离来建模工作负载。（后向）重用时间是数据访问与最近访问同一位置之间的时间。足迹方法将MRC测量的运行时开销减少到O（N）。1但是，足迹算法的空间开销仍然是O（M）。至于存储工作负载，它们的大小通常比CPU工作负载大得多，它们的寿命可能持续数周或更长时间。因此，像足迹分析这样的技术可能需要太多的空间。Counter Stacks（Wires et al.2014）和SHARDS（Waldspurger et al. 2015）是最近的突破，以减少空间成本的渐近复杂性（电线等。2014）和实践中（Waldspurgeret al.2015年）。CounterStacks使用概率计数器，并且首次可以在次线性空间中以有保证的精度测量重用距离（Drudi et al.2015年）。但柜台堆栈SHARDS使用一个splay树来跟踪采样数据的重用距离时间和空间消耗降低到一个很低的水平。然而，SHARDS不能通过对单个程序建模来表征共享缓存行为本文提出了一种基于平均回收时间（AET）的LRU缓存MRC构造动力学模型。AET在线性时间内渐近运行，使用采样来最小化空间开销，并采用自适应相位采样来捕获时变行为。在评估中，AET具有最低级别的空间和运行时开销相比，过去的技术，同时保持高MRC的准确性。尽管SHARDS在时间和空间开销方面与AET相当，但AET是可组合的度量，即，共享高速缓存中的多程序化工作负荷的MRC可以直接从其成员程序的AET计算。[1]工作集理论具有类似的效果和相同的时间和空间复杂性（Denning and Schwartz1972; Denning and Slutz1978）。参见第二节。2.8 Xiang et al.（2013）进行比较。存储Cache的快速未命中率曲线建模十二：3ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月−图二、示例4-块缓存，视为堆栈（优先级列表）。该表显示了逻辑时间、每次引用的数据（ref）、每次访问的重用时间（rt）以及访问是否是缓存命中。阴影区域是d的驱逐过程。2AET模型本节描述动力学模型。第2.1节用一个例子介绍了基本概念，特别是驱逐时间。第2.2节通过求解距离积分方程来制定和计算平均驱逐时间（AET）。AET模型将MRC与重用时间分布联系起来。第2.3节讨论了模型的正确性。第2.4节显示了使用利特尔定律推导AET模型的另一种方法。第2.5节对共享缓存进行建模，并求解回收时间均衡方程。第2.6节展示了使用AET的多级缓存建模2.1LRU堆叠和逐出时间LRU高速缓存在逻辑上可以被视为堆栈（Mattson et al.1970年）。数据块按其最近访问时间从最近到最近排列每次访问都会将访问的数据带到堆栈的顶部。堆栈的底部存储最近最少使用的数据，并在未命中时（当缓存已满时）被驱逐。当数据块在未命中时被加载到高速缓存中时，在它被逐出之前，它可以被重用多次（命中）驱逐时间是指上次访问和驱逐之间的时间它是块最后一次从堆栈顶部移动到底部的我们把这个LRU移动的周期称为驱逐过程，把向栈底移动的数据块称为驱逐块。在时间t处的驱逐时，向后看引用驱逐块的最近时间u，时间间隔t u是驱逐时间。请注意，u也可以是逐出块被引入的时间（未命中）。通常，驱逐时间是驱逐块的驻留时间的最后一段。例如，对于图2中的示例高速缓存中的数据块d，其在时间3被加载，在时间5被最后访问，并且在时间10被逐出回收时间为5，由阴影区域显示驱离时间十二：4X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月−−−–表1.图2中阴影区域中d的逐出所示的动力学模型逻辑时间5678910位置m01223驱逐到达时间Tm012245当前复用时间22627∞到达时间Tm（第三行）取决于移动条件：重用时间（最后一行）是否大于Tm。驱逐时间为T4=5。是停留时间的一部分，在本例中为7，通常可以使用排队理论进行估计（作为这一观察促使我们在2.4节中使用排队论推导AET模型。为了对驱逐时间建模，我们需要对导致驱逐的进程建模。我们将到达时间Tm定义为驱逐块到达堆栈位置m（从其最后一次访问开始）所花费的时间。对于大小为c的高速缓存，到达时间是（下标）函数Tm，m= 0，.，c 1。自然地，驱逐时间是Tc，其是驱逐块离开位置c1并到达虚拟位置c的时间。为了说明，表1示出了大小为4的高速缓存的d的到达时间Tm当m从0增加到4时，Tm从0增加到5。驱逐块d的移动取决于如何访问其他数据。在驱逐过程中的每次访问（图2中的阴影区域），d要么停留在其当前位置，要么逐步下降一个位置。移动的条件很简单：d从位置m向下移动，当且仅当访问是未命中，或者被访问数据的堆栈位置m>m，也就是说，被访问数据位于优先级列表的远端，更靠近尾部。我们定义T0为0.显然，T1总是1，因为对任何其他块的访问必须将其带到堆栈位置0并驱逐d，因为它发生在d的时间6。移动的条件可以简化，因为我们不需要访问数据的确切位置。只要知道相对位置就够了。对于更简单的测试，我们使用重用时间而不是堆栈位置。我们定义在堆栈位置i的停留时间Si为驱逐块在位置i停留的时间，因为它到达该位置。下面的语句总结了移动条件，它将LRU堆栈中的数据移动和回收时间与重用时间联系起来。当访问块z时，并且驱逐块d位于堆栈位置m-1，当且仅当z的重用时间大于d的到达时间T m-1加上其当前逗留时间S m-1时，d向下移动到位置m。如果前述条件为真，则在Tm1+Sm1内尚未访问z，即，因为d一个有趣的观察是，当运动条件为真且d运动时，它在时间Tm−1+Sm−1到达位置m，等于Tm。移动条件：当访问块z时，并且驱逐块d在堆栈位置m1处，当且仅当z的重用时间大于Tm时，d向下移动以到达位置m。通过实例说明了回收时间和重用时间之间的关系。表1的最后一行显示了在d每当重用时间（最后一行）大于到达时间（第三行）时，块d移动到下一个位置（在第二行中示出）。在每个位置，速度都在变化。最快的速度是在每一个访问移动一个位置。最慢的速度是没有运动。存储Cache的快速未命中率曲线建模十二：5ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月← −−←←.算法1：重用时间直方图以补充累积分布函数（CCDF）Require：rt[]//重用时间直方图（无冷未命中）Require：len//最大复用时间Require：sum//包括冷未命中确保：：P[] //重复使用时间1：函数CA lcCCDF（rt[]，len，sum）2：P [0]1. 03：for i1.. 伦多4：P[i]P[i 1]rt[i]/sum5：结束6：结束功能接下来，我们对缓存中所有数据的平均回收时间进行到达时间Tm将被类似地定义为所有数据的平均值。个别地，到达速度可能会减慢，然后加快。然而，平均而言，到达速度是不增加的，正如我们接下来讨论的那样。2.2平均逐出时间（AET）AET（c）是大小为c的全关联LRU缓存中所有数据逐出的平均逐出时间。它是数据块自上次访问以来的预期驻留时间。我们的AET模型基于以下假设：缓存未命中概率假设：重用时间大于AET的引用的概率是该数据块不再位于缓存中并导致缓存未命中的概率。缓存未命中率实际上是导致未命中的访问的概率。因此，该假设可以应用于预测未命中率，即具有比AET更大的重用时间的数据重用的比例。这个假设是我们MRC预测技术的基础。其余部分派生AET。对于高速缓存大小c，令Tm为驱逐数据块到达位置m的平均到达时间（在其驱逐过程中）。显然，T0=0且AET（c）=Tc。移动条件不再是个人的，而是集体的，并取决于所有数据的重复使用次数。设N为引用总数，rt（t）为具有重用时间t. f（t）是重用时间为t的重用比例，定义如下：f（t）=rt（t）N.（一）f（t）描述了重用时间分布，我们将在3.1节中讨论它。对于接入，P（t）是其重用时间大于t的概率：P（t）=∞i=t+1f（i）。（二）P（t）实际上是复用时间的累积分布函数（CCDF）的P（t）是1减去重用时间小于或等于t的概率。算法1实现等式（1）和（2）以将重用时间直方图转换为CCDF。接下来，我们表明，AET可以来自CCDF。十二：6X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月−−图3.第三章。 当平均到达时间（Tm）沿x轴增加时，y轴表示在每个Tm处的到达速度v（Tm）. v在T上的积分给出了移动距离，即曲线下的面积。阴影区域显示堆栈位置的增量（为1）。当检查平均到达时间时，移动条件现在是概率移动概率：在位置m 1的驱逐块移动到（到达）位置m的概率是P（Tm），其中Tm是到达位置m的平均时间。这可以解释如下：在单位时间内，位置m1处的驱逐块移动1个位置，以概率P（Tm）到达位置m。所以单位时间内的期望移动距离为P（Tm）为了使用一个熟悉的概念，我们称之为到达速度。在逻辑时间内到达位置m的速度等于概率P（Tm）。此外，我们跟踪相对于驱逐过程的相对时钟的到达速度：v（Tm）=P（Tm），（3）当m>0。一个特殊的情况是v（T0）=v（0），它总是跟在逻辑时间之后，即，一次一个访问相应地，P[T0]=P[0]= 1。因此，方程（3）对所有m都成立。到达速度v（Tm）是单调的，并且不随位置m而增加。根据定义，P（Tm）是单调的且不随m而增加。现在我们构造一个方程来求解Tm，然后求解AET（c）。该等式连接三个度量：到达速度v（Tm）、平均到达时间Tm和缓存大小c。这种连接如图3所示。在图3中，x轴表示平均到达时间（Tm）随时间的增加而变化.在每个Tm处，我们使用等式（3）来计算到达速度v（Tm），如y轴所示。该图示出了示例曲线，其是单调非增加的。v在T上的积分给出了运动的距离，即，它移动到的堆栈位置。它是曲线下的面积。阴影区域显示堆栈位置的增量（即1）。这三个度量是离散函数。微妙但关键的问题是它们的离散单元的差异。当我们测量缓存大小和缓存中的数据移动时，单个步骤是堆栈位置。当我们测量重用时间时，一个步骤就是一次访问。我们可以把前者称为空间单位，而把后者称为时间单位。这两个单位是不一样的。图3示出了从相同的基Tm开始，时间增量Tm+1小于或等于空间增量Tm+1。我们利用复用时间的时间单位函数推导出AET的空间单位函数让我们考虑当数据块移动时速度如何改变。从前面提到的单调性来看，变化一定是减速。基于到达速度公式（等式（3）），存储Cache的快速未命中率曲线建模十二：7ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月.∫0=不=不=给出了从Tm到Tm+ ΔT的精确减速度：v（Tm+ΔT）=v（Tm）−Tm+ΔTt=Tm+1f（t），（4）其中ΔT代表T m上的时间增量。单位是时间的，所以最小ΔT是1，即，一个访问。现在，我们准备用公式表示第一个动力学方程，距离积分（DI）。它结合时间和空间增量来计算完整的运动。首先，让从Tm到Tm+1，数据移动一个堆栈位置（图3中的阴影区域）。其次，我们添加时间增量如下。对于每个空间增量（m），我们通过在时间单位（dx）中积分来计算减速度，如等式（4）所示。最后，我们对从0到缓存大小c的空间增量求和。结果是移动的总距离，例如，图3中的示例曲线下方的区域，其是到达时间达到Tc时的缓存大小c：.c−1<$Tm+1（v（Tm）−.f（t））dx = c.（五）m=0Tmt =Tm +1DI是一个隐式方程。它的解是AET（c），即，Tc.考虑从0到AET（c）的每个时间步长x处的速度，以及每一步所花费的时间，我们有AET（c）实际上，该等式与等式（5）相同。等价性证明如下：.c−1<$Tm+1不（v（Tm）−.f（t）dxm=0mt=Tm+1.c−1<$Tm+1（P（Tm）−.f（t）dxm=0mt=Tm+1.c−1<$Tm+1（P（Tm）−（P（Tm）−P（x）dxm=0m.c−1<$Tm+1P（x）dxm=0T1=的t0TmP（x）dx+锝Tc−1T2P（x）dxT1AET（c）=0P（x）d x.从AET到MRC。 公式（6）表明，AET计算仅需要重用时间的CCDF P（x），其可以基于XXX∫∫P（x）dx = c.（六）... +的P（x）dx十二：8X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月重用时间分布或重用时间直方图（RTH）计算，并且可以在线性时间中测量（参见第3节）。存储Cache的快速未命中率曲线建模十二：9ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月←≤←←←←←−−∞算法2：从重用时间的CCDF到MRC要求：P[] //重用时间的CCDF要求：M//最大缓存大小要求：len//最大重用时间确保：MRC[] //未命中率曲线1：函数CA lcMR c（P[]，M，len）2：整数03：t04：对于c1.. Mdo5：while（inte <$rationc and t len）do<6：inte <$ration inte <$ration+P[t]7：t t+18：结束时9：MRC[c]P[t1]10：结束11：返回MRC[]12：结束功能基于高速缓存未命中概率假设，高速缓存大小c处的未命中率mr（c）是重用时间大于平均驱逐时间AET（c）的概率：mr（c）= P（AET（c））。（七）算法2实现等式（6）和（7）以基于重用时间的CCDF来计算MRC在等式（6）从0到最大重用时间的积分期间，可以在线性时间O（N）中一起计算所有高速缓存大小的未命中率。请注意，第7行最多可以执行len+1次，其中len小于N，因为大小为N的迹线的最大可能重用时间为N1.在实践中，我们将算法1和算法2合并到一个函数中，并将数组P替换为标量以节省空间。冷思念的影响在程序执行中，对任何数据块的第一次访问应该是冷未命中。由于每次冷未命中都会在LRU优先级列表的头部插入一个新的数据块，因此它会将列表中的所有数据向下推一个位置。在动力学方程中，无论数据在哪里，冷错过总是贡献一个固定的概率份额来移动数据。因此，在AET模型中，我们将每个冷未命中的重用时间定义为无限大，并在重用时间直方图（RTH）的bin中计算冷未命中的数量，如图4所示。2.3正确性从AET到脱靶率的转换并不总是正确的。缓存大小c是重用距离d>c的比例。AET函数的倒数实际上是对重用距离的估计对于重用时间t，重用距离d是数据块沿高速缓存栈向下移动的距离，因此t=AET（d），并且d=AET −1（t）。（八）AET转换相当于首先估计重用距离，然后使用估计的重用距离：十二：X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月..≥≤图四、RTH和冷小姐的例子。mr（c）= x>crd（x）N.t>AET（c）rd（AET−1（t））N=t>AET（c）rt（t）N=P（AET（c）），其中rd（x）是具有重用距离x的引用的数量。因此，如果重用距离的估计是正确的，则AET对于所有高速缓存大小都我们给出一个正确性条件如下：所有缓存大小的正确性条件。对于所有t>0，如果时间t的重用次数rt（t）的数量与距离AET-1（t）的重用距离rd（AET-1（t））的数量相同，则基于AET的转换对于所有高速缓存大小都是准确的。当两者相等时，使用AET转换与对所有高速缓存大小c0使用重用距离相同。该条件是等式（8）的重复，但在数学上将连接显示为函数组合rd和AET−1。接下来，我们给出各个缓存大小的正确性条件。对于大小为c的高速缓存，具有重用时间rt>AET（c）的每个访问将被AET模型预测为高速缓存未命中。这个预-如果某些重用的重用距离等于或小于c，则措辞是不准确的，这意味着它们是命中。我们将此误差定义为对于具有重用时间rt AET（c）的每个访问，AET预测命中。我们将“命中预测错误”或HPE定义更具体地说，我们使用一个矩阵来表示重用时间的分布及其相应的重用距离。如图5所示，元素Xrt，rd代表具有重用时间rt和重用距离rd的访问次数。注意，当rtrd为0时，元素为0，因为重用距离总是等于或小于重用时间。<对于缓存大小c，我们使用两条虚线将矩阵分为四个部分。矩阵中的左上（UL）区域是具有等于或小于AET（c）的重用时间以及等于或小于c的重用距离的元素（rt=AET（c），rd=c）。它们代表了AET预测为命中的重用，并且是真正的命中。右下（LR）区域是具有比AET（c）更大的重用时间和比高速缓存大小c更大的重用距离的元素（rt>AET（c），rd>c）。它们代表了AET预测为未命中的重用，并且是真正的未命中。UL和LR部分在AET模型中都是正确的预测然而，右上（UR）区域，其是具有等于或小于AET（c）的重用时间但大于AET（c）的重用距离的重用。=存储Cache的快速未命中率曲线建模十二：ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月∞ ∞C..MM||||||||||||i=1j=1图五、重用时间-重用距离矩阵，被划分为四个象限，如标记的：UL、LL、UR和LR。X∞，∞未给出。c（rt <= AET（c），rd> c）。这部分表示命中预测误差，因为AET将它们预测为命中，但它们实际上是未命中。另一方面，矩阵中的左下（LL）区域表示误预测误差。它们是AET预测为未命中但实际上是命中（rt>AET（c），rd=c）。请注意，此矩阵中未显示冷未命中的数量（X1）。在AET模型中，对任何数据的第一次访问被预测为缓存未命中。此预测在任何缓存大小下都是正确的。现在，我们可以得出结论，在一定的缓存大小的AET模型的错误是由MPE和HPE之间的差异。显然，MPE的数量是LL中元素的总和：|MPE|为N.−1.Xi，j，（9）i=AET（c）+1j=1其中N是访问的总次数。同样，HPE的数量是UR中元素的总和：|HPE|为AET（c）i=1.Xi，j=AET（c） .Xi，j，（10）其中M代表程序的数据大小。如果MPE和HPE相等，则它们彼此抵消，然后AET预测在该高速缓存大小处是如果MPE大于HPE，则预测的未命中率应高于实际未命中率。相反，如果MPE小于HPE，则预测的未命中率应低于实际未命中率。现在，我们有在高速缓存大小c下的AET预测的绝对误差E（c）：E（c）=||HPE| − |MPE|| 为||HPE| − |MPE||.（十一）.N−1。M Xi，j+X∞，∞N在图6中，我们在大小为3的缓存上运行一个简单的跟踪，以消除两种类型的预测错误。数据参考流由两个循环构成（ABCCBA）100（MNPQ）2.（十二）每个循环都有一个独特的参考模式，具有不同的迭代次数。第一个循环迭代100次，而第二个循环迭代两次。整个跟踪具有从7个不同元素生成的608个引用。在图6中，我们给出了从第一个周期中的第二次迭代开始的每个引用的重用时间和重用距离，以及使用AET的命中/未命中预测j=c+1i=c+1j=c+ 1十二：X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月图六、示例跟踪显示3块缓存中不同类型的预测错误（由于空间原因，跳过了第一个周期的迭代1）。模型对于3块缓存，平均回收时间可以推导如下：∫40P（x）dx=P（0）+P（ 1）+P（ 2）+P（ 3）+P（ 4）409 409 210 206=1+608+ 608+ 608=3。03号。上述等式给出了平均驱逐时间，AET（3）= 4。任何重复使用时间大于4的引用都被预测为缓存未命中。迭代2及以后的第一个周期中的第一个C和第二个A的重用时间为5，AET模型将其预测为未命中。但是，这两个引用的重用距离为3，这意味着它们实际上是缓存命中。这两个参考是AET模型中的未命中预测误差（MPE）。在第二周期的第二次迭代中，所有参考具有相等的重用时间4和相同的重用距离4。AET模型预测它们为命中，但它们的重用距离大于缓存大小，这表示它们实际上是未命中。这种类型的错误是命中预测错误（HPE）。在该示例中，由于极度偏斜的访问模式，AET预测206次未命中，而通过精确的重用距离模型预测11次未命中然而，在我们的评估中，我们观察到两种类型的预测误差的数量通常很小，并且在大多数情况下彼此接近。只有在极端不稳定的访问模式下，它们之间的差异才明显。在这里，我们给出了缓存大小c的正确性条件。一个高速缓存大小的正确性条件对于高速缓存大小c，如果重用时间大于AET（c）但重用距离小于或等于c的重用次数等于重用时间等于或小于AET（c）但重用距离大于c的重用次数，则基于AET的转换是准确的。2.4与理论一致在排队论中，一个经典的数学概率理论，利特尔定律，是由约翰·利特尔提出的一个定理：在一个稳定的系统中，长期平均的该关系不受到达过程分布、服务分布和服务顺序的影响。缓存系统也可以看作是一个排队系统。新数据和丢失的数据从内存层次结构的较低级别到达。缓存的数据在离开缓存之前会在缓存中停留一段时间（驱逐）。存储Cache的快速未命中率曲线建模十二：ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月∞...∗_在本节中，我们将从利特尔定律推导出AET模型。AET模型假设所有复用时间大于平均回收时间的复用都是缓存未命中。由于缓存是一个排队系统，我们希望在与AET模型相同的假设下使用Little定律来表示缓存未命中率利特尔定律的第一部分是数据对象在缓存中停留的平均时间，我们称之为数据对象的平均停留时间。它是所有数据对象从进入缓存到被逐出或离开的平均时间。假设我们有一个大小为c的缓存，对于任何重用时间t，如果它小于或等于AET（c），则数据自上次访问以来已驻留在缓存中t如果t大于AET（c），则这意味着数据已经驻留在高速缓存中用于AET（c），并且然后从自上次访问以来的高速缓存中被如果此访问是冷未命中（t=），则数据对象以前从未被缓存过。然而，在每个对象的最后一次引用之后，它将留在缓存中等待AET（c）并被驱逐。由于冷未命中的数量等于最后引用的数量，因此我们可以假设每个冷未命中具有AET（c）的停留时间。现在，我们知道了数据的重用时间和驻留时间之间的关系，其他上网设备如果我们有所有数据引用的重用时间分布，那么我们可以很容易地得到所有数据对象的总驻留时间假设rt（x）是如等式（1）中所使用的具有重用时间x的参考的数量总停留时间all_time可表示如下：all_time=rt（1）+rt（ 2） 2+rt（ 3） 3+···+rt（AET（c））AET（c）+rt（AET（c）+1）ΔAET（c）+rt（AET（c）+ 2）ΔAET（c）+···+rt（∞）ΔAET（c）AET（c）=x=1rt（x）x+∞x=AET（c）+1rt（x）Δ ET（c）。现在，我们有了所有数据对象的总停留时间。为了获得所有到达数据的平均驻留时间，我们需要知道有多少数据对象到达了缓存。在回收时间假设下，缓存未命中率是重用时间大于 AET（c），即，P（AET（C））。进入缓存all_arrival的数据对象的数量是所有引用的数量乘以此缓存的未命中率：all_arrival =∞rt（x）P（AET（c））。（十三）x=1通过上述讨论，我们可以得到平均停留时间W：所有时间W=所有到达 .（十四）注意，逻辑时间中的数据到达率λ等于未命中率，因为只有未命中才能将新对象引入队列（高速缓存）中。根据利特尔c=λW所有时间=未命中率_所有到达.AET（c）rt（x）<$x+。∞rt（x）≤AET（c）=P（AET（c））x=1.x=AET（c）+1.AET（c）rt（x）<$x+。∞=x∞=1rt（x）P（AET（c））rt（x）≤AET（c）x =1x =AET（c）+1十二：X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月.x∞=1rt（x）存储Cache的快速未命中率曲线建模十二：ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月+=.x∞=1rt（x）+.x∞=2rt（x）+· · ·+.x∞=AET（c）+1rt（x）x∞=1rt（x）x∞=2rt（x）.x∞=1rt（x） .x∞=1=00...x∞=1rt（x） .=P（0）+P（ 1）+···+P（AET（c））AET（c）通过以上分析，我们可以得出结论，在相同的驱逐时间假设下，AET模型符合利特尔定律。也就是说，利特尔2.5共享缓存中的AET当共享缓存时，一组共同运行的程序相互交互。我们考虑的情况下，共同运行的程序有不相交的数据集。每次一个程序执行一个引用时，被访问的块被带到缓存中最近使用（MRU）的位置。缓存填满后，任何程序新插入的数据都可以驱逐属于其他节目。这种缓存共享的情况很普遍，存在于许多系统设计中。我们需要一个可组合的模型来从单独运行的局部性分析中得出对共享缓存的组合效果。Ding等人（2014）将可组合性定义如下：如果共同运行的度量可以从单独运行的度量计算，则局部性度量是可AET是可组合的：给定单独程序的单独运行AET，我们可以在共享缓存中导出共同运行AET。对于n个共同运行的程序，有n+1个共同运行的Aynomial：每个程序一个，组一个。我们通过求解另一个AET方程得到它们。方程求解有两个基本问题：解是否存在，如果存在，解是否唯一？对于共享缓存中的任何数据块，一旦不再访问它，它将从共享缓存中的MRU位置移因为每个被驱逐的数据都经过了所有程序共享的同一个LRU堆栈，所以无论数据块属于哪个程序，所有被驱逐的数据都应该具有相同的预期驱逐时间。因此，我们有一个用于驱逐时间均衡假设的等式：当n个程序共享大小为c的缓存时，所有n个共同运行的AET，每个程序i的AET i（c）和组的AET（c）是相同的：AET1（c）= AET 2（c）=···= AET n（c）= AET（c）。（十五）我们现在证明这个方程有且只有一个解。为了解释推导，我们从对称的情况开始，其中n个共同运行的程序是相同的。 对于p图i，l e trsolo，ib e其访问速率，rtsolo，i（t）是剩余时间直方图，Psolo，i（t）是CCDF，如第2.2节中所定义。总访问速率自然是rco=nrsolo，i。我们定义了共同运行的逻辑时钟。协同运行时钟的运行速度提高了n倍，每个程序每n个滴答中就有一个滴答对于程序i，共同运行重用时间rt_co，i（nt）=rt_solo，i（t），或者等价地rtco，i（t）=rtsolo，i（t/n）。由于时间的变化，联合运行时钟下的概率函数P_c_o，i（t）=P_s_o_l，i（t/n）。聚集概率是群组：n nP（t）=.Pco，i（t）/n=.Psolo，i（t/n）/n=Psolo，i（t/n）。（十六）i=1i=1从P（t），我们使用距离积分方程（方程（6））来导出共运行AET：AET（c）=x∞=AET（c）+1rt（x）rt（x）+···+.x∞=1rt（x）P（x）d x.P（x）dx = c.（十七）十二：X. Hu等人ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月←←∗∗←←←←i=1（t）。程序的CCDF、、R算法3：从复用时间的单个CCDF组成复用时间的聚合CCDF，P []要求：Psolo[][] //每个共同运行程序Require：num//共办项目Require：r[] //每个程序Require：len//最大复用时间确保：P[]//聚合CCDF，P[]1：函数MER gE（Psolo[][]，num，r[]，len）2：Rдetsum（r[]）3：P [0]1. 04：对于t1.. 伦多5：P[t] 06：for i1.. 南岛7：P[t]P[t]+Psolo[i][t r[i]/R]r[i]/R8：结束9：结束10：returnP[]11：结束功能该等式看起来与等式（6）相同，但是P（x）是聚合概率，x是协同运行时间，并且AET（c）是共享高速缓存的平均驱逐时间在共享高速缓存中，任何程序的任何访问都是未命中，当且仅当其重用时间大于AET（c）。因此，组未命中率是mr（c）=P（AET（c）），并且该未命中的部分第i幅图的贡献率为：mrco ，i（c）=Pco，i（AET（c））/n。 这个常数在每个程序中都是相同的，所以mr co，i（c）= mr（c）/n。联合运行AET和脱靶率的求解对于这种对称的情况是唯一的。注意，第i个程序的共同运行未命中率mrco，i（c）是第i个程序中的未命中计数除以所有程序的访问次数的比率换句话说，它是在共同运行时钟上定义的单独未命中率该定义使我们能够直接添加不同程序的未命中率它也可以很容易地转换为传统的脱靶率。我们现在考虑一般情况。它在两个方面不同于前面的对称情况：每个程序i可以具有不同的访问速率rsolo，i和不同的重用时间直方图，因此，CCD F，Psolo，i（t）。 设总访问速率be r=.n罗索洛岛对于prgrami，再用时间（t）=rtrsolo，i科岛索洛岛在联合运行时钟下的ri变为Pcoi（t）=Psoloi。我是一个人。（十八）g_regat_eP（t）是P_c_o，i（t）与它们的访问速率的加权和P（t）=.Pco，i（t）rsolo，i=. P索洛，我.trsolo，i 阿尔索洛岛.（十九）i=1ri=1r r算法3实现等式（19），其将各个程序的CCDF共享高速缓存距离积分方程（方程（17））现在可以计算如算法2中实现的一般情况下的AET（c）我们现在研究共同运行的失误率和失误率之间的关系，从每个单独的程序。组未命中率是mr（c）=P（AET（c）），并且nn存储Cache的快速未命中率曲线建模十二：ACM Transactions on Storage，Vol.号142、第十二条。出版日期：2018年4月R1co1独奏 1独奏 1、co2solo 2solo 2、R、、rsolo，1+rsolo，2、、、rsolo，1+rsolo，2、图7.第一次会议。并以单机复用时间为例，给出了单机复用时间程序i贡献的未命中率为高先生，我 （c）=P科岛（AET（c））rsolo，i.（二十）R贡献现在是个体化的，并且取决于个体访问速率r_solo，i和重用时间直方图rt_solo，i（t）而不同。以下是该组的共同运行未命中率，作为每个个体的共同运行未命中率的总和这些解决方案对于每个程序组都是独一无二的n nmr（c）= P（AET（c））=. 柯议员（丙）Pcoi（AET（c））