高相联度Cache.docx

计算机体系结构

题目：
高相联度Cache之顺序虚拟多体Cache

学 院:
计算机科学与技术学院
专 业:
软件工程
任课教师:

学 号:
201213703029
姓 名:
田贝贝
E - mail :
523155998@
电 话:
13554217283

武汉科技大学 计算机科学与技术学院
摘要：摘要高相联度Cache具有失效率低的优点，而且高相联度在许多情况下是非常重要的。但是高相联度Cache的一个突出问题是访问时间较长。本文提出的虚拟多体Cache能较好地解决这一问题，文中论述了顺序虚拟多体Cache的思想和具体方案，并给出了详细的性能模拟结果。模拟结果表明，它能非常有效地提高Cache的性能。
关键词：Cache 相联度 性能分析

目录
1. 引言
2. 相关工作分析
3. 顺序虚拟多体Cache
4. 性能评价
5. 总结
6. 参考文献

1. 引言
近十年来，CPU的速度提高的很快，但是主存速度的提高却慢得多，因此，CPU和主存之间在性能上的差距越来越大，因此我们多采用Cache来解决这个问题。在影响Cache性能的诸多因素中，相联度是非常重要的一个因素，即是指当一个数据块从主存调入Cache时，Cache中可用于存放该数据块的位置的个数。

2. 相关工作分析
近年来，人们提出了不少改进Cache性能的方案，其中与本文工作关系较大的有：Hash——Rehash Cache，伪相联 Cache，MRU Cache等。但由于在平均访问时间上，伪相联 Cache最小而且高相联度Cache的突出问题就是访问时间较长，因此，在后面的性能分析中，我们与伪相联 Cache进行比较。

3. 顺序虚拟多体Cache
下面我们进入主题，看一下顺序虚拟多体Cache的设计思想。
虚拟多体Cache在概念上把Cache等分为若干个逻辑体（如6体，8 体等）。对于每一次访问，采用类似于位选择算法的映象方法从各逻辑体中选出一个候选位置。这些候选位置构成逻辑上的一个组。对于这些候选位置，我们采用顺序查找的方法，既是本文介绍的顺序虚拟多体Cache。
首先介绍一下该方案用到的多MRU块技术。在相联度大于1 的Cache中，对于每一次访问来说，在其相应组中的各候选位置上命中（找到需要的内容）的可能性不相同。一般应按“从可能性最大的位置到可能性最小的位置”的顺序查找。在MRU Cache中，每一组只有一个固定的查找顺序。也就是说，对于映象到该组的所有访问来说，查找时只有一个公共的入口，即该组的MRU块位置。这就是MRU Cache有时会出现首次命中率低的原因。为解决上述问题，提出了多MRU块的技术：对于任何一个访问来说，把它按照直接映象规则映射到的那个位置称为主位置，而把相应组中的其它位置称为非主位置。这里把映象到同一逻辑组中的访问根据其主位置划分为若干个集合，每一个集合对应于一个主位置。如果对于每一个集合中的访问，都提供独立的查找顺序，则可以达到最佳效果。但是，考虑到大多数访问都会在MRU块命中，为了减少复杂度，只记录多个MRU块（每一个对应于一个集合）。这样，映象到同一组中的访问就有多个入口，每一个入口对应该组中的某个集合。通过采用交换的方法来保证在主位置中的块为MRU 块。仅当发生非首次命中或失效时才进行交换，这时把命中的块或新调进来的块放到主位置上，而把原来在主位置上的块交换到其他位置上。采用多MRU 块技术后，上述访问序列中的所有命中都将是首次命中。如下图所示：
单个入口：
图（1）
图（2）
3. 顺序虚拟多体Cache
在该方案中，是从主位置开始，依次对各候选位置顺序进行查找。虽然除主位置以外的候选位置的重要性比主位置小得多，但如何高效地对它们进行查找，对于整个方案的性能有很大的影响。对于一次访问来说，并不是相应的组中所有的候选位置都有可能包含所访问的数据。考虑该组中的任何一个位置，当且仅当其中的块是在以下情况下从主存调进来：先前有一个与本次访问具有相同主位置的访问失效，它才有可能包含本次访问所要的数据。可以称这些位置为相关位置。用一些索引表来记录相关的位置。这样，在查找时，就可以过滤掉那些根本不可能包含所访问数据的块。流程图如下：
图（3）
相关位置的地址由两部分构成：逻辑体号（高位），该逻辑体内的相对块号（低位）。相对块号可由本次访问的块地址的低位直接截取获得，逻辑体号则是根据索引表中的信息产生。

索引表
本次访问的块地址低位

逻辑体号（高位）

相对块号（低位）

图（4）

在索引表中，给每一个主位置分配一个长度为n的位向量，该向量中每一位对应于相应组中一个位置；若值为“1”，则表示该位置是相关位置，否则就不是。为了便于修改，同一组中各位置的位向量串接为一项

4. 性能评价
通过模拟，把SMC——Cache和PMC——Cache与伪相联Cache在性能上进行了比较。对相联度为4、8、16三种情况进行了模拟， Cache大小的变化范围为1KB到128KB，块大小取为16B。模拟结果如下图所示：

图（5）不同Cache容量情况下的性能改进

从图（5）中可以看出顺序虚拟多体Cache能有效地减少失效率和平均访问时间，在平均访问时间上，比伪相联Cache有很大的改进。从图中还可以看出，当相联度提高到16或更大时，性能上的改进已经很小，不值得开发。

图（6）不同失效开销情况下的性能改进
在图（6）中，给出了IMP与失效开销的关系。从图中可以看
到以下事实：
（1）当失效开销增加时，顺序虚拟多体Cache的曲线比伪相联Cache的曲线上升得更快。这意味着Cache方案在失效开销较大时能带来更大的益处。
（2）当n从4增加到8时，性能上有较大的提高，但当n进一步增加到16时，改进效果就不大了。

5. 总结
高相联度可以减少失效率，但同时满足访问周期短的特点在传统的Cache实现中是难以实验的。而该方案在不牺牲高相联度Cache的有点的前提下同时实现减小访问周期的要求，有效的改进了性能。

6. 参考文献
1. 一种面向CMP的可变相联度混合Cache结构- 电子学报 - 2011, 39(3)
2. 期刊论文 基于实验的测试Cache性能参数的算法及实现- 计算机工程与应用 - 2005, 41(9)
3. 一种低功耗动态可重构Cache方案 - 计算机应用 - 2009, 29(5)
4. B Calder Predictive Sequential Associative Cache - 1996
1