《计算机体系结构》第六次实验 cache.docx

计算机体系结构第六次实验 cacheCache实验报告 姓名：王宇航 学号：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<lruindexz)/选择lru值最大的一个 x=lruindexz; y=z; if(z=(assoc*2)-2)/没有命中时 newarrayindexy+1=tag; /把lru值最大的替换掉 misscount+; c=misstype(blockaddressj,NOofblock,j); cc=1; for(m=0;m<(assoc*2);m=m+2)/所有的lru值+1 lruindexm+; lruindexy=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 hit 0% hit 20% miss 80% hit 40% miss 60% miss 100% 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+) quecnt+ = rand % e + p; if (quecnt - 1 > N - 1) quecnt - 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改变，从116 C 仅采用全相联 都用相同的数据测试1000次观察效果 Direct mapped直接映射，BlockSize大小增加 Cache大小固定为128，序列长度为100 当BlockSize = 1的时候： 当BlockSize = 2的时候： 当BlockSize = 4的时候： 由此可见，在直接映射下，当blocksize从1、2、4依次的增长时，缺页率在减少。 组相联映射中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中的三种映像规则：直接映射、组相联映射和全相联映射的各自的优缺点和性能对比。也提高了我阅读代码的能力，同时也理解了作业中遇到的问题。总之，受益匪浅。