缓存MRC模型
参考论文：
DCAPS- Dynamic Cache Allocation with Partial Sharing
Kinetic Modeling of Data Eviction in Cache
Evaluation techniques for storage hierarchies
一：综述
内存系统是一种多级结构，其中上层内存通常扮演底层存储的缓存角色。这种设计的考虑是：在任何时间段内，程序中只有一小部分数据会被频繁使用。
过去已经有很多working set locality theory，通过Working set size来刻画locality数据，Locality characterization techniques（Locality建模技术）已经发展了几十年。它们广泛用于不同级别的内存层次结构的管理和优化。
截止目前已经有很多关于MRC(miss ratio curves)的理论，来对上层缓存进行建模，得出程序分配缓存大小和性能的关系模型：MissRatio=F(capacity)
基本分为两种方法：
第一个系统提出MRC模型的是1970年的Stack Processing理论，简单的说就是通过记录负载访问内存的reuse distance来得到MRC模型。
之后的几年有两个方面的改进：
二：算法介绍
1）Stack Processing
可以将LRU-cache抽象化为一个栈。按照每个数据的最近一次访问时间进行排序，每当数据被从新访问时候，就会被移动到栈的顶部。当栈中的数据长度超过栈的大小的时候，最后一个数据就会被换出。
如图阴影部分所示，当一个数据miss的时候，会被从新写入放到栈的顶部，随着时间的推移中间可能会被从新访问几次，最后数据逐步移动到栈尾部最后换出。
下面定义几个变量：
1>
假如数据换出的时间是t，数据最后一次访问的时间是u，那么书记的换出时间就是:
evicted time = t - u
上图阴影部分，数据d的换出时间是9-4=5
2>
数据最后一次访问到数据到达位置m的时间，就是数据到达时间Tm。
上图阴影部分，数据d位置2的到达时间是6-5=1
2）reuse distance MRC
定义n为cache总访问次数，rd(x)为reuse distance是x的访问次数，则size为c时的miss ratio为reuse distance大于c的访问次数占比。
3）reuse time MRC
定义大小为c的cache，平均换出时间为AET(c)。
队列位置c的平均到达时间是Tc。
则AET(c) = Tc
由
t=AET(d)
得：
定义rd(x)为reuse distance为x的访问次数，rt(t)为reuse time为t的访问次数，n为总的访问次数。
从而：
所以，当满足下面条件的时候miss ratio的计算可以用reuse time替代reuse distance：
3）cache share情况
多个实例（1～n）共享cache，各自的AETi(c)和group的总AET(c)相等：
总mr(c)为各自mri(c)之和：
三：数据采集
根据上述理论，通过记录缓存访问的Reuse Distance Histogram (RDH) Sampling 或者 Reuse Time Histogram (RTH) Sampling，就可以得到MRC的模型曲线。
目前我们perf工作在采样模式，通过Performance Event Select Registers和Performance Monitoring Counters（PMC）对事件进行统计采样。
可以使用intel的Precise Event-Based Sampling (PEBS)机制，采集cache读写地址信息，获取RTH(sampled reuse time histogram)，进而获取缓存的MRC模型。
参考资料：
GUIDE, P. Intel® 64 and ia-32 architectures software developer’s manual. Volume 3B: System programming Guide, Part 3 (2017).
四：效果比较
目前公布准确率已经在98%以上，近几年新的研究论文主要在通过优化算法来降低数据存储空间和cpu资源占用。
AET vs SHARDS
总结
- 上一篇： Vue 删除列表项的淡出动画
- 下一篇： GAN综述及其在图像生成领域的应用（含原