高速缓存问题

《高速缓存问题》由会员分享，可在线阅读，更多相关《高速缓存问题（28页珍藏版）》请在金锄头文库上搜索。

1、6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存问题高速缓存问题 1高速缓存问题高速缓存问题你想了解哪7种东西?命中命中缺失缺失!最近最少使用算法不，通过8种?14种?19种?先进先出算法?写回?2002年年11月月12日日L19 高速缓存问题高速缓存问题 16.004 2002年秋季年秋季6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存问题高速缓存问题 2通用高速缓存原理通用高速缓存原理设置：设置： 请求者向数据仓库提出了一连串的查找请求。请求者向数据仓库提出了一连串的查找请求。 访问模式中一些观察到的可预测性访问模式中一些观察到的可预

2、测性例如，局部性。例如，局部性。 诀窍：诀窍： 在请求者与数据仓库之间设置小型的快速高速缓存存储器。在请求者与数据仓库之间设置小型的快速高速缓存存储器。 最有可能请求的是带有成对的高速缓存。最有可能请求的是带有成对的高速缓存。只有在高速缓存中找不到标记时，才会提出 该请求，也就是说，在概率为1的情况下 提出请求。其中，是高速缓存拥有该数据 的概率（一次“命中” ）。请求者请求者数据仓库 tM数据仓库 tM高速缓存 tC (2,0,1,3) (2,0,1,3)命中1 - (1,2,0,3) (1,2,0,3) 缺失 - (3,1,2,0) (3,1,2,0)命中3 - (3,1,2,0)LRU（

3、最近最少使用）：LRU（最近最少使用）： 将最经常使用的存储单元保存在高速缓存中;将最经常使用的存储单元保存在高速缓存中; 需要保持按顺序排列的N个条目列表N!种排序需要保持按顺序排列的N个条目列表N!种排序 O(log2N!) = O(N log2N) O(log2N!) = O(N log2N) “LRU位LRU位”+复杂逻辑。+复杂逻辑。FIFO/LRR（先进先出/最近最少替换）：FIFO/LRR（先进先出/最近最少替换）： 廉价的选择方案：替换最旧的条目（按访问时间来确定日期）；廉价的选择方案：替换最旧的条目（按访问时间来确定日期）； 在每个组中：保持某个计数器来指向被替换的行。在每个

4、组中：保持某个计数器来指向被替换的行。 随机算法（使用随机的统一分配法来选择替换行）：随机算法（使用随机的统一分配法来选择替换行）： 不存在因不存在因“病态病态”访问流而导致的最坏结果；访问流而导致的最坏结果；使用伪随机发生器来得到可再生的行为；使用伪随机发生器来得到可再生的行为； 利用利用真实真实的随机性来防止逆向工程！的随机性来防止逆向工程！开销是 O(N log2N) 位/组开销是 O(log2N) 位/组开销是 O(log2N) 位/组!2002年年11月月12日日L19 高速缓存问题高速缓存问题 206.004 2002年秋季年秋季6.004 2002年秋季年秋季2002年年11月月

5、12日日L19 高速缓存问题高速缓存问题 21替换策略与缺失率的比较替换策略与缺失率的比较H 开始写入到MemX中。缺失: 在任何高速缓存行的标记中都找不到X。 替换选择： 选择某个行k来保存MemX。 读: 读MemX。 ?设置标记k=X，数据k=MemX。 写: 开始写入到MemX中。 ?设置标记k=X，数据k=new MemX。2002年年11月月12日日L19 高速缓存问题高速缓存问题 246.004 2002年秋季年秋季写回法值得这么费心吗？它取决于（1）写操作的成本；（2）一致性问题。在访问MemX时: 在标记中查找X。命中：针对某个高速缓存行i，X=TAG(i)。 读：返回数据(

6、i)； 写: 改变数据(i)；开始写入到MemX中。缺失:在任何高速缓存行的标记中都找不到X。 替换选择: 选择某个行k来保存MemX； 写回: 将数据(k)写入到MemTagk中。 读: 读MemX。 - 设置标记k=X，数据k=MemX。 写: 开始写入到MemX中。 - 设置标记k=X，数据k=new MemX。写回写回6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存问题高速缓存问题 252002年年11月月12日日L19 高速缓存问题高速缓存问题 256.004 2002年秋季年秋季6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存

7、问题高速缓存问题 26写回 w/写回 w/“脏脏”位位主存储器中央 处理器有效位 标记数据脏位在访问MemX时: 在标记中查找X 命中：针对某个高速缓存行i，X=TAG(i)。 读：返回数据(i)； 写：改变数据(i)；开始写入到MemX中。Di=1。缺失：在任何高速缓存行的标记中都找不到X。 替换选择:选择某个行k来保存MemX； 如果Dk=1（写回），则将数据(k)写回到MemTagk中。 读：读MemX；设置标记k=X，数据k=MemX, Dk=0。 写：开始写入MemX Dk=1 - 设置标记k=X，数据k = new MemX。2002年年11月月12日日L19 高速缓存问题高速缓存

8、问题 266.004 2002年秋季年秋季6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存问题高速缓存问题 27高速缓存分析高速缓存分析给出一个高速缓存设计，找出病态的访问字串符：给出一个高速缓存设计，找出病态的访问字串符： 手工模拟高速缓存；使缺失最大化；手工模拟高速缓存；使缺失最大化；对于缺失来说，要注意那些对于缺失来说，要注意那些被替换被替换的地址。进行下一次访问。的地址。进行下一次访问。 比较高速缓存A和B：比较高速缓存A和B： 通常能为每个高速缓存找到病态情况，使得其他情况看上去更好一些通常能为每个高速缓存找到病态情况，使得其他情况看上去更好一些无论高速缓

9、存在何时制定了不同的替换决策，你都能设计出下一次访问无论高速缓存在何时制定了不同的替换决策，你都能设计出下一次访问 方案，使得两个高速缓存看上去都更好一些。方案，使得两个高速缓存看上去都更好一些。 优势：优势： 对于每个访问字符串来说，高速缓存A要优于高速缓存B，因为高速对于每个访问字符串来说，高速缓存A要优于高速缓存B，因为高速 缓存A中包含了B中包含的每一个值。因此，A不会缺失，除非B也缺失。缓存A中包含了B中包含的每一个值。因此，A不会缺失，除非B也缺失。 例如：给出2个其他方面完全相同、全相联、采用最近最少使用算例如：给出2个其他方面完全相同、全相联、采用最近最少使用算 法的高速缓存，

10、则较大的那个高速缓存要优于较小的高速缓存。法的高速缓存，则较大的那个高速缓存要优于较小的高速缓存。2002年年11月月12日日L19 高速缓存问题高速缓存问题 276.004 2002年秋季年秋季6.004 2002年秋季年秋季2002年年11月月12日日L19 高速缓存问题高速缓存问题 28高速缓存：小结高速缓存：小结相联度：相联度： 当尺寸不断增大时，重要性不断变小。当尺寸不断增大时，重要性不断变小。 对于典型的程序聚类来说，通常使用2路或者4路高速缓存就足够了；对于典型的程序聚类来说，通常使用2路或者4路高速缓存就足够了； 但是，额外的相联度：但是，额外的相联度： 能使性能曲线变平滑；能

11、使性能曲线变平滑； 能减少所选择的位数（我们很快会看到这一点是如何有用的）。能减少所选择的位数（我们很快会看到这一点是如何有用的）。 趋势：在随机存储器上投资，而不在比较器上投资。趋势：在随机存储器上投资，而不在比较器上投资。 替换策略:替换策略: 大高速缓存：任何明智的方法都起了很好的作用。大高速缓存：任何明智的方法都起了很好的作用。 真实随机性可以减轻偏执狂症状。真实随机性可以减轻偏执狂症状。 性能分析：性能分析： 单调的手工合成可以通过简单样例来建立直觉，但是，单调的手工合成可以通过简单样例来建立直觉，但是， 利用计算机来模拟真实程序的高速缓存行为（或是使用真实的跟踪数据利用计算机来模拟真实程序的高速缓存行为（或是使用真实的跟踪数据），）， 是大多数真实世界高速缓存设计决策的基础。是大多数真实世界高速缓存设计决策的基础。2002年年11月月12日日L19 高速缓存问题高速缓存问题 286.004 2002年秋季年秋季