Cache实验报告姓名：王宇航学号：09283020 安全0901
Cache实验报告
一、实验要求：
1.阅读分析附件模拟器代码
要求：1）读懂2）关键注释3）总结关键参数和算法的实现方法
2.通过读懂代码加深了解cache的实现技术
3.结合书后习题1进行测试
4.通过测试和进行实验设计了解参数和算法选择的特点和相互关系（比较，组合等），需要定性和量化结合说明，可以用数字或图表等多种描述手段配合说明。
二、实验代码：
1. LRU页面置换算法
程序一共有3中模式：
Direct_mapped 2 Set_associate 3 Fully_associate
对于第一种，直接映射，显然用不到LRU算法，因为每一个地址在cache中只有一个地方可以去。
对于后两种，组相联映射和全相联映射，就需要用到LRU算法了。
其中，全相联映射等于是只有一个set的Set_associate，而LRU正是用在一个set中，所以，后面两种模式的LRU问题可以归结为一种：一个set中，来了一个没有的页面，需要置换出一个，应该置换出哪一个的问题。
那么，具体过程如下：
1 这个set中的每一个block都有一个lru值，初始为0。
2 每次访问这个set的时候，不管是否命中，这个set中的所有block的lru值都+1。
3 当需要置换出去一个页面的时候，选择一个lru值最大的那个置换出入，用来放入刚刚进来的。
4 不管是否命中，刚刚访问过的，或者加入的那个block的lru值置为0。
if(x<lru[index][z])//选择lru值最大的一个
{
x=lru[index][z];
y=z;
}
if(z==((assoc*2)-2))//没有命中时
{
newarray[index][y+1]=tag; //把lru值最大的替换掉
misscount++;
c=misstype(blockaddress[j],NOofblock,j);
cc=1;
for(m=0;m<(assoc*2);m=m+2)//所有的lru值+1
lru[index][m]++;
lru[index][y]=0;//把lru值最大的替换掉
}
z=z+2;
2. 用于判断缺页类型的算法
在程序中，体现了3中缺页的类型：
Compulsory Miss：之前没有出现的地址，肯定不会命中
Conflict Miss：由于冲突而产生的不命中
Capacity Miss：由于容量不足而导致的不命中
在函数int misstype(int ba, int nb, int l)中。
ba：表示当前不命中的地址
nb：表示NOofblock，即cache中block的数目
l：表示当前ba在访问序列bytearray数组中的位置
before数组，用来表示当前已经访问过了那些页面。
blarray数组，表示相邻两次访问ba之间，访问过的地址。
变量b，表示blarray数组的大小。
Compulsory Miss：
那么，只要当前访问的页面，在之前没有访问过，那么，就是Compulsory Miss这种类型。
代码上就是：遍历before数组，看看有没有和ba相同的，没有的话就是Compulsory Miss，同时不要忘记把ba加入到before数组，供下次使用。
Conflict Miss：
在统计相邻两次访问ba之间的不同的地址数目时，数组blarray的大小b就是这个值。
那么只要和nb比较一下，只要b<nb，表示其实还有多余的空间可以使ba在之前不被调出，就说明其实是ba由于冲突而被调出，即Conflict Miss。
Capacity Miss：
反之，如果b>nb，就表示，相邻两次访问ba之间的地址数目过大，导致空间不够使用，即Capacity Miss。
三、实验过程：
1. 原始代码测试
第一个测试：Direct mapped
第二个测试：two-way set associative
第三个测试：fully associative
可见三次测试的结果是相同的，因为我们给的三组输入数据是相同的。
下面我们用书上的例子进行测试：
第一个测试：Direct mapped：
如图，和课本的结果吻合。
全部miss，由于其中有3种不同的地址，所以Compulsory miss 的数目是3.
第二个测试：two-way set associative
如图，和课本的结果吻合。
只有一个hit，由于其中有3种不同的地址，所以Compulsory miss 的数目是3.
第三个测试：fully associative
如图，和课本的结果吻合。
有2个hit，由于其中有3种不同的地址，所以Compulsory miss 的数目是3.
综上，上述三种模式的miss率如下：左：direct 中：2-way 右：full
2. 代码测试
依据课后题进行代码测试：为了测试block 的大小和n-way 中n 的大小对miss 率的影响，需要反复实验。
所以，就需要一种策略来生成访问序列地址，但是又不能随便生成，因为序列需要满足一定的空间局部性和时间局部性。
在源代码中加入一小段测试代码如下：（网上找的测试代码，且将源代码中的指定打开文件注释掉，改为由以下函数生成：页面访问序列生成函数）
int num, e, N; int Gen(int que[]) {
double t = (rand() % 100) * 0.01; int m = (rand() % (N / 2)) + 1; int p = rand() % (N / 2); int cnt = 0; while(true) {
e = rand() % (N / 2) + 1; for(int i = 0; i < m; i++) {
que[cnt++] = rand() % e + p;
if (que[cnt - 1] > N - 1) que[cnt - 1] = N - 1; if (cnt == num) break; }
if (cnt == num) break;
double r = (rand() % 100) * 0.01; if (r < t)
p = rand() % N; else p = (p + 1) % N; }
return cnt;
}
那么，为了兼顾到3种模式，下面将按照
A Direct mapped模式下，仅BlockSize大小增加。
B 仅n-way的n改变，从1~16
C 仅采用全相联
都用相同的数据测试1000次观察效果
（1）Direct mapped直接映射，BlockSize大小增加
Cache大小固定为128，序列长度为100
当BlockSize = 1的时候：
当BlockSize = 2的时候：
当BlockSize = 4的时候：
由此可见，在直接映射下，当blocksize从1、2、4依次的增长时，缺页率在减少。
（2）组相联映射中n对缺页率的影响测试实验：
Cache大小固定为64，BlockSize为1，序列长度为100，n从1变到16，看结果：n=1时：
n=2
n=4
n=8
n=16
由此可知，随着n的增大，缺页率是逐步减小的。
3. 全相联映射：
Cache大小固定为128，BlockSize为2，序列长度为100
由此可见，综合各方面，全相联映射是最优方法，其缺页率最低。
4.实验总结
通过这次实验，我了解了cache中的三种映像规则：直接映射、组相联映射和全相联映射的各自的优缺点和性能对比。
也提高了我阅读代码的能力，同时也理解了作业中遇到的问题。
总之，受益匪浅。
