实验6：Cache性能分析
一、实验目的
1：加深对 Cache 的基本概念、基本组织结构以及基本工作原理的理解。
2：掌握 Cache 容量、相联度、块大小对 Cache 性能的影响。
3：掌握降低 Cache 不命中率的各种方法以及这些方法对提高 Cache 性能的好处。
4：理解 LRU 与随机法的基本思想以及它们对 Cache 性能的影响。
二、实验平台
Cache模拟器：MyCache。
三、实验内容与步骤
3.1：掌握 MyCache 模拟器的使用方法
1：启动 MyCache。
2：用鼠标点击“复位”按钮，把各参数设置为默认值。
3：选择一个地址流文件。方法： 选择“访问地址”的“地址流文件”选项，然后点击“浏览”按钮，从 MyCache 模拟器所在的文件夹下的“地址流”文件夹中选取地址流文件（如：ed.din）。
4：设置相关参数，选择执行到底或步进执行，得到相关失效率结果。
3.2：Cache 容量对失效率的影响
地址流文件：eg.din（由于eg.din文件在后面表现不好，因此本实验在初步检测效果时均改为使用all.din文件）
| Cache 容量 （KB） | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |
| 失效率 | 5.4% | 5.4% | 5.0% | 4.7% | 4.7% | 4.7% | 4.7% | 4.7% |
表0：不同容量下 Cache 的失效率
地址流文件：all.din
| Cache 容量 （KB） | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 |
| 失效率 | 9.87% | 7.19% | 4.48% | 2.65% | 1.42% | 0.89% | 0.60% | 0.49% |
表1：不同容量下 Cache 的失效率
【结论】增大Cache的容量时，可以在一定程度上减少容量失效，降低Cache的失效率。
3.3：相联度对失效率的影响
地址流文件：all.din
【Cache容量 = 64KB时】
| 相联度 | 1 | 2 | 4 | 8 | 16 | 32 |
| 失效率 | 0.89% | 0.53% | 0.47% | 0.45% | 0.44% | 0.44% |
表2：当容量为 64KB 时， 不同相联度下 Cache 的失效率
【Cache容量 = 256KB时】
| 相联度 | 1 | 2 | 4 | 8 | 16 | 32 |
| 失效率 | 0.49% | 0.38% | 0.36% | 0.36% | 0.35% | 0.35% |
表3：当容量为 256KB 时， 不同相联度下 Cache 的失效率
【结论】增大Cache的相联度时，可以在一定程度上减少冲突失效，降低Cache的失效率。
3.4：Cache 块大小对失效率的影响
地址流文件：all.din
| 块大小 （B） | Cache 容量（KB） | ||||
| 2 | 8 | 32 | 128 | 512 | |
| 16 | 12.02% | 5.79% | 1.86% | 0.95% | 0.71% |
| 32 | 9.87% | 4.48% | 1.42% | 0.60% | 0.42% |
| 64 | 9.36% | 4.03% | 1.20% | 0.43% | 0.27% |
| 128 | 10.49% | 4.60% | 1.08% | 0.35% | 0.20% |
| 256 | 13.45% | 5.35% | 1.19% | 0.34% | 0.16% |
表4：各种块大小情况下 Cache 的失效率
【结论】对于给定的Cache容量，当块大小增加的时候，失效率先下降后上升。同时，Cache的容量越大，失效率达到最低的块大小（极小值点）就越大。因此，在一定范围内增加Cache的块大小，可以减少强制性失效。给定容量cache，块太小1次调进cache数据少，失效率增加；块太大，块数太少，冲突失效增加。
3.5：替换算法对失效率的影响
地址流文件：all.din
| Cache 容量 | 相 联 度 | |||||
| 2 路 | 4 路 | 8 路 | ||||
| LRU | 随机算法 | LRU | 随机算法 | LRU | 随机算法 | |
| 16KB | 1.71% | 2.05% | 1.33% | 1.77% | 1.21% | 1.97% |
| 64KB | 0.53% | 0.63% | 0.47% | 0.58% | 0.45% | 0.59% |
| 256KB | 0.38% | 0.40% | 0.36% | 0.37% | 0.36% | 0.36% |
| 1MB | 0.35% | 0.35% | 0.35% | 0.35% | 0.35% | 0.35% |
表5：LRU 和随机替换法的失效率的比较
【结论】当Cache容量较小时（<=64KB），同种相联度采用LRU替换算法的失效率明显低于采用随机算法的失效率，即说明Cache容量较小时LRU替换算法更优。当Cache容量较大时，同种相联度采用LRU替换算法的失效率与采用随机算法的失效率大致相同，即说明Cache容量较大时LRU替换算法和随即替换法的效果相似。
3.6：混合 Cache 和分离 Cache 的比较
地址流文件：all.din
其中，指令Cache的容量 = 数据Cache的容量 = 1/2 混合Cache的容量。
| 总容量 | 指令 Cache | 数据 Cache | 混合 Cache |
| 4KB | 6.01% | 7.19% | |
| 8KB | 4.16% | 4.48% | |
| 16KB | 2.65% | 2.65% | |
| 32KB | 1.52% | 1.42% | |
| 64KB | 0.79% | 0.89% | |
| 128KB | 0.53% | 0.60% | |
| 256KB | 0.45% | 0.49% | |
表6：分离 Cache 和混合 Cache 失效率的比较
【结论】当总容量一定时，分离Cache的失效率通常低于混合Cache的失效率。随着Cache容量的增加，无论是分离Cache还是混合Cache，失效率都有所降低。
3.7：Cache 工作原理剖析
（1）测试eg.din地址流
参数设置：
执行控制采用“步进”模式，观察结果，填写实验“实验 6- 中间结果分析”中的“eg.din” 页表， 进行分析并回答问题。
【步进结果】
Step1：
Step2：
Step3：
Step4：
Step5：
Step6：
Step7：
Step8：
Step9：
Step10：
【问题回答】
1）Cache分为几组？每组多少块，块的大小是多少？
组数 = 容量 / 块大小 / 相联度 = 2KB / 16B / 2 = 2^6 = 64，因此Cache分为64组。
每组2块，因为是2路组相联。
块大小是16B，条件中已经给出。
2）索引用多少位表示？对应地址的第几位到第几位？组号和索引之间什么关系？用多少位？块号用多少位，块内地址多少位？
索引的长度与Cache的组数相关，用于映射所在组的行号。Cache一共64（2^6）组，因此索引需要6位来表示。
由于块大小是16B = 2^4 B，因此块内地址占4位。所以从右侧数起的第5位地址~第10位地址是索引对应的地址位置。
主存的组号与Cache的索引之间是一一映射的，即相同。
均用6位。
主存的块号用28位，块内地址用4位。
3）目录表中多少行，多少列？如何找到对应块号并读入？
目录表中的行数与Cache的组数相同，所以是64行。目录表需要存储主存的块号和Cache的组号，所以是2列。
根据主存地址，可以求出主存的Tag、映射的Cache组号、块内地址。在目录表中找到该主存地址映射的Cache组号，比较目录表该行的Tag是否与该主存地址的Tag相同。该Tag是主存块号去掉末尾映射的Cache组号所构成的。
4）如果是直接相联，索引用多少位？目录表中多少行？
直接相联的组数 = 容量 / 块大小 = 2KB / 16B = 2^7 = 128。索引用7位。
目录表中有128行。
5）从内存读取的数据多大，读取操作完毕之后Cache里面得到的数据多少位？
从内存读取数据以块为单位，块有多大则读取的数据有多大。所以读取的数据为16B。
读取操作完毕后，Cache里面得到的数据是16B = 16 * 8 bit = 128bit。
6）这里的块号是主存块号还是Cache块号？
主存块号。明显超出了Cache的块数。
7）按照索引进行寻址，要进行几次比较？跟什么有关系？
2次比较。首先比较索引，然后比较Tag。
跟相联度有关系。
8）Cache里面会把该数据调入吗？是先调入后写还是先写后调入？
会。
先调入后写。
9）采用写回策略，存储器中的数据会修改吗？
不会修改。仅当Cache中相应的块被替换时，才写回主存。
10）解释什么是命中？最后传给CPU的数据是多少位？
CPU在Cache中寻找所需的数据，若该数据存在Cache中，就表示命中，否则缺失。
最后传给CPU的数据是32位，调入是一整个块，但是CPU执行只传送一个字。
【Excel表格填写】
基本设置：
序号1~序号8：
序号9~序号10：
（2）测试mytest.din地址流
例题：设一个 Cache 中有 8 个块，访问主存进行读操作的块地址序列为 22、26、22、26、16、 4、16、18（地址内位移可以随机设定），分析每次访问后的 Cache 内容和命中率。
参数设置：
内存地址范围 0X00000000-0XFFFFFFFF，编写地址流文件，保证 Cache 的块数为 8。
执行控制采用 “步进” 模式，观察结果，填写实验“实验 6- 中间 结果分析 ”中的“mytest.din”页表，进行分析并回答问题。
验证结构是否和下图的分析结构相同。
【步进结果】
Step1：
Step2：
Step3：
Step4：
Step5：
Step6：
Step7：
Step8：
【Excel表格填写】
基本设置：
序号1~序号8：
【验证结构】
由Excel表的结果可知，Cache实际工作的结果和下图的分析结构基本相同。（除了第8次执行的替换中，Cache第4行的数据消失了）
在第1次执行时，由于Cache第6行为空，所以向Cache第6行写入主存第22块的内容。
在第2次执行时，由于Cache第2行为空，所以向Cache第2行写入主存第26块的内容。
在第3次执行时，需要访问主存中第22块的内容，因此先向Cache第6行中比对Tag，发现Tag一致，则命中。
在第4次执行时，需要访问主存中第26块的内容，因此先向Cache第2行中比对Tag，发现Tag一致，则命中。
在第5次执行时，由于Cache第0行为空，所以向Cache第0行写入主存第16块的内容。
在第6次执行时，由于Cache第4行为空，所以向Cache第4行写入主存第4块的内容。
在第7次执行时，需要访问主存中第16块的内容，因此先向Cache第0行中比对Tag，发现Tag一致，则命中。
在第8次执行时，需要访问主存中第18块的内容，因此先向Cache第2行中比对Tag，发现Tag不一致，则不命中，且将原来主存第26块的内容，替换为主存第18块的内容。
【地址流文件内容】
mytest.din文件的内容如下所示：
| 2 1680 00010110 10000000 2 1AA5 00011010 10100101 2 1663 00010110 01100011 2 1A48 00011010 01001000 2 1021 00010000 00100001 2 401 00000100 00000001 2 1006 00010000 00000110 2 12E3 00010010 11100011 |
【问题回答】
1）Cache分为几组？每组多少块，块的大小是多少？
2KB / 256B = 2^11B / 2^8B = 2^3，所以Cache分为8块。
每组1块，因为是直接相联。
块的大小是256B。
2）索引用多少位表示？对应地址的第几位到第几位？组号和索引之间什么关系？用多少位？块号用多少位，块内地址多少位？
索引用3位表示，因为一共有2^3=8块。
由于块大小是256B = 2^8 B，因此块内地址占8位。所以从右侧数起的第9位地址~第11位地址是索引对应的地址位置。
主存的组号与Cache的索引之间是一一映射的，即相同。
均用3位。
所以主存的块号用32 – 8 = 24 位，块内地址用8位。
3）目录表中多少行，多少列？如何找到对应块号并读入？
目录表中的行数与Cache的组数相同，所以是8行。目录表需要存储主存的块号和Cache的组号，所以是2列。
读出目录表中的tag内容与主存的比较。
4）从内存读取的数据多大，读取操作完毕之后Cache里面得到的数据多少位？
从内存读取的数据为一个块的大小，即256B。
读取操作完毕之后，Cache里面得到的数据位数是：256 * 8 bit = 2048bit。
四、实验总结
1：在mytest.din的实验中，主存的地址范围是0X0000 0000 – 0XFFFF FFFF ，最大地址对应的十进制数是4294967295。4294967295 / 8 = 536870911.875，取整后可知主存需要划分为536870912个块，十六进制下为2000 0000。
2：全相联的映射关系如下图所示。主存和Cache按照块大小进行划分编号后，主存中任意一块都可以映射到Cache的任意一行。如果Cache存满（每一行都对应了一个主存块），则采用相应的替换原则进行主存块内容的替换。
3：直接相联的映射关系如下图所示。主存和Cache按照块大小进行划分编号后，主存中块必须按照【主存块号 % Cache块数】的关系进行映射，即相同余数的主存块存到Cache的同一行位置处，如果已经存有主存块的数据，则需要替换。
4：组相联的映射关系如下图所示。主存和Cache按照块大小进行划分编号后，Cache按照相联度进行组的划分，而主存按照Cache中的组数进行组群的划分。主存中的组群按照直接相联的方法进行映射，主存中组群内的块按照全相联的方法在对应的Cache组里面进行映射。
5：在编写mytest.din文件时，可以使用记事本打开，只需要编写1个label和1个address，其余内容会自动默认是注释。在label中的对应关系如下表所示。同时，address的范围是[0,FFFFFFFF]。
| Label类型 | 类型含义 |
| 0 | read data 读数据 |
| 1 | write data 写数据 |
| 2 | instruction fetch 取指令 |
| 3 | escape record (treated as unknown access type) |
| 4 | escape record (causes cache flush) |
6：Cache的失效类型分为以下三种：
- 强制性失效：第一次访问Cache，该块不在Cache中，要从下级存储器中调入；发生在空Cache中。
- 容量失效：Cache容量有限，所需块无法全部调入；块被替换后可能被重新访问，发生失效；发生在全相联Cache中。
- 冲突失效：直接相联或组相联Cache，组内空间已满，进行替换后又被重新访问（其他组有空闲块，或对某些组块数要求超过了n路）。
7：2:1的Cache经验规则：容量为N的直接映象Cache失效率约等于容量为N/2的2路组相联Cache失效率，当N > 128KB时不成立。
8：降低Cache失效率 的方法。
