计算机体系结构——
Cache模拟器实验
实验报告
姓名崔雪莹
学号 ********
班级计科1202班
老师董岚
2015年 06月07日
一、阅读分析附件模拟器代码 (3)
1、关键参数 (3)
2、关键算法 (4)
二、课后习题 (6)
1、习题内容 (6)
2、题目分析 (6)
3、计算及结果 (7)
4、模拟器上实验结果检验 (8)
三、整体分析 (11)
1、三种映射方式对Cache效率的的影响 (11)
2、block块大小与Cache容量对Cache效率的影响 (12)
3、Cache容量与相连度对Cache效率的影响 (13)
4、三种失效类型影响因素 (14)
四、实验思考和感受 (16)
1、关于模拟器的思考 (16)
2、关于整个实验的思考 (17)
一、阅读分析附件模拟器代码
1、关键参数
（1）用户可见参数：（用户通过命令行输入参数）
（2）程序内部主要参数：（代码内部重要参数）
2、关键算法
注：这里不粘贴代码，只是进行简单的代码算法说明
（1）块地址表示：
注：图是我按照自己的想法自己画的，可能有些地方并不准确，望老师指正。图中以一个例子来解释cache模拟器中block和数据地址的关系，以及和组地址和标志位的关系。
（2）Index与tag：
由上面计算：index = blockaddress % NOofset index = 16 % 8 = 2
tag = blockaddress / Noofset tag = 16/8 = 2
以上例，字地址16为例，写成二进制为0001 0010 B，其中组数为8，又
因为2^3=8，所以字地址取后3位为：index = 010 B = 2 ，取前29位为：
tag = 0…0010 B = 2 。所以，算法与理论是一致的。
（3）Valid：
有效位。当通过上述方式寻址找到了数据存放的数据块，接下来判断有效位：
有效位为1，说明数据是有效的，可以从block提取数据；
有效位为0，说明块里的数据是无效的，所以不能从block提取数据，出现miss，此时判断miss类型，同时需要访问内存或下一级存储，将数
据放到cache里。
（4）失效类型及判断方法：
判断失效类型，函数misstype（int ba ，int nb ，int l）。
Compulsory miss（强制性失效，冷启动）：当第一次访问某一个块的时候，数据是肯定不在块中的，此时出现强制性失效，或者说是冷启动
失效。
Capacity miss（容量失效）：所需的数据不能全部调入cache中，块被替换后又被重新访问，意思就是当所有的块都被占满了，这样又有数据
希望被调入缓存时，就出现了容量失效。
Conflict miss（冲突失效）：在组相联或直接映像中，数据想要替换进某一组中，组内的块都被占满了，但是别的组的块有空余，数据只能替
换这一组，尽管别的组有空余也不能替换。这样就出现了冲突失效。（5）LRU算法实现替换：
LRU替换算法是采用最近最久未使用的块，其中Lru[][]数组存放最近多少次未被使用，因为是采用循环访问，当循环访问到这一组时，把这
组所有的块的Lru[][]值都加1，如果成功访问到这一块，数据能从其中取
出来，就把这一块的Lru[][]值置0，退出循环。
（6）直接映射、组相联映射、全相联映射：
直接映射：是特殊的组相联映射，就是相联度为1的组相联映射。
所以采取和组相联一样的程序和算法，当识别该组第一块失效时，直接
进行替换，因为有且只有一块。
组相联映射：当识别该组某块失效时，如果块都被占满，要根据Lru[][]值的大小，判断哪一块被替换掉。
全相联映射：从上到下cache块存数据，则从上到下循环即可，遇到失效时，要根据Lru[][]值的大小，判断哪一块被替换掉。
二、课后习题
1、习题内容
在CacheSimulator模拟器上模拟如下程序的运行过程：
int i,j,c stride,array[256]
for(i=0;i<10000;i++)
for(j=0;j<256;j=j+stride)
c = array[j]+5;
假设Cache总大小是256个字节，且块大小为16字节（4个字）。
同时假设内存当中只有这一个程序在运行，而且整形数字的长度为一个字长（字长为32位），在直接相连映射下，stribe分别等于132、131时程序的运行结果，并分析原因。而当采用两路组相连时又会有什么结果并分析原因。
2、题目分析
当stribe = 132/131 时，程序相当于循环访问内存偏移地址为0和地址132/131的内容，循环10000次，也就是访问了2000次存储。
结合cache机制，cache大小为256个字节，块大小为16个字节，所以块的个数为256/16 = 16个。若为2路组相连，则有16/2 = 8组。
当第一次访问块时，一定会发生强制性失效，计一次miss。
3、计算及结果
1）直接映像时：
●stride=132
array[0]的块地址为0，映射到cache的块号为0：
0 mod 16 = 0
array[132]的块地址为132/4 = 33，映射到cache的块号为1：
33 mod 16 = 1
因为第一次访问cache，0和1一定会发生强制性失效，之后因为调入
cache，不会发生失效。则失效次数为2，则失效率为：
2/20000 = 0.01%
命中次数为19998次，命中率为：
19998/20000 = 99.99% = 1（近似）
失效类型为强制性失效，次数为2。
●stride=131
array[0]的块地址为0，映射到cache的块号为0：
0 modulo 16 = 0
array[131]的块地址为131/4 = 32，映射到cache的块号为0：
32 modulo 16 = 0
因为第一次访问cache，0一定会发生强制性失效，之后cache里块号为
0的块不断地被替换写入替换写入，此时发生冲突失效。则失效次数为
20000，则失效率为：
20000/20000 = 1 = 100%
命中率为0。失效类型为强制性失效次数1，冲突失效次数为19999。2）2路组相联：
●stride=132
array[0]的块地址为0，映像到cache的组号为0：
0 modulo 8 = 0
array[132]的块地址为132/4 = 33，映像到cache组号为1：
33 modulo 8 = 1
