Cache替换策略的价值评估

摘要

Cpu容量小速度快，存储器容量大但是读取慢。随着科技的发展两者的速度差了几百倍，而Cpu访问主存的速度问题影响了计算机的速度，Cache作为一个中间的存储点被用来解决这个问题。当Cache的命中率足够高的时候，就相当于用Cache的速度来访问存储器，极大地提高了电脑的性能。为了提高Cache的命中率，产生了许多对Cache存储的策略，Cache的策略研究十分重要。但是任何一种策略对某种环境下相对于其他策略是有优势的。那么怎么衡量这些策略的优劣呢？同时对于一种新的数据怎么找到最适合它的Cache策略呢？本文首先总结了Cache问题，然后基于距离概念和命中函数的定义，用理论分析和模拟的方法对各种替换策略进行评估，找到方法用来计算Cache块容量大小的价值，提出了一个新的算法，并预估这个算法的优劣。最后给出了一定数据下的最优策略，以及Cache大小对命中率的影响。

目录

声明

摘要

表格索引

插图索引

第一章 引言

1．1 Cache简介

1．2 Cache算法简介

1．3 Cache算法的问题

第二章 Cache模型

2．1 Cache问题模型化

2．2 Cache对策略组的限制

2．3 距离，距离函数，页面停留时间

2．3．1 距离

2．3．2 “距离”函数

2．3．3 页面的停留时间

2．4 Cache中页面停留时间的分布

2．5 Cache的期望命中率

2．6 最大化期望命中率的算法

2．7 计算机数据特点

第三章 一种新的算法

3．1 新的算法

3．2 对新算法的评估

3．3 新算法的改进

第四章 总结

4．1 处理Cache容量大小的算法

4．2 处理新数据的算法

4．3 结论

第五章 数据模拟

5．1 例子1

5．2 例子2

5．3 例子3

5．4 例子4

5．5 例子5

参考文献

附录

致谢