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

Cache实验报告姓名：王宇航学号：09283020 安全0901Cache实验报告一、实验要求：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(xlruindexz)/选择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值+1lruindexm+;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比较一下，只要bnb，就表示，相邻两次访问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 右：fullhit 0%miss 100%miss 80%hit 20%hit 40% miss 60%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 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改变，从116C 仅采用全相联都用相同的数据测试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=2n=4n=8n=16由此可知，随着n的增大，缺页率是逐步减小的。3. 全相联映射：Cache大小固定为128，