第二次互评作业： cache性能评测与分析

问题1：请说明程序实现的功能。(5分)

$$\begin{equation} tmp(x) = \begin{cases} 3& \text{x = 1}\\ 5& \text{x = 2}\\ 9& \text{x = 3}\\ tmp(x -1) + tmp(x -2) + tmp(x -3)& 25 \geq \text{x > 3} \end{cases} \end{equation}$$

问题2：分析程序的访存行为，仅考虑数据访存。（5分）

（提示：访存行为包括程序一共发生了多少次访存操作，每次访存操作的地址之间有什么样的关系等）

访存仅在：

       lw       $t3, 0($t0)    #t3 = array[i+0]    load1
       lw       $t4, 4($t0)    #t4 = array[i+1]    load2
       lw       $t5, 8($t0)    #t5 = array[i+2]    load3
       sw       $t2, 12($t0)    #array[i+3] = t2    store1

这个部分发生，循环之行了25次，故有100次访存。后面三次访存都与第一次访存有4、8、12byte的偏移量，而前一个周期和后一个周期所读取的整个数据块都有4byte的偏移量。

问题3：根据MARS内置的Data Cache Simulation Tool，构建一个容量为8字节的cache，要求块大小为4字节（one word），替换策略为LRU，组策略为直接映射。运行上述MIPS程序，得到cache命中率为多少？（5分）

运行上述的程序，得到24%命中率。详细原因下一题解释。

问题4：结合程序的访存行为，详细分析问题3中cache miss的原因。（10分）

根据对程序的运行以及手工模拟过程，可以得知前后周期（也就是进行三次lw，一次sw），都会产生一个元素的偏移量，因此在除了第一个周期以外，其他周期都会产生一次cache hit与三次cache miss。
可以计算得命中率为24/100=24%（除了第一个周期一定会产生义务失效，没有cache hit）。

问题5：根据MARS内置的Data Cache Simulation Tool，构建一个容量为8字节的cache，要求块大小为4字节（one word），替换策略为LRU，组策略为全相联。运行上述MIPS程序，得到cache命中率为多少？（5分）

运行上述的程序，得到0%命中率。详细原因下一题解释。

问题6：结合程序的访存行为，详细分析问题5中cache miss的原因。（10分）

由于使用了全相联与LRU的替换策略，每一个周期三次lw和sw的访问对应位置相同。根据全相联策略，只要有空缺就使用空缺，结合LRU替换策略，lw0产生在slot0，lw1产生在slot1，lw2产生在slot0。根据LRU替换策略，由于上一次替换产生在slot0，因此下一个产生的替换在slot1。

问题7：保持其他参数不变，通过增加block数量的方式将cache的容量扩大为16个字节，评测不同组策略下cache命中率的变化，并分析原因？进一步扩大cache容量，cache命中率会如何变化？（10分）

不同组策略的cache命中率稳定在72%，而且不随着cache容量增大而增大。根据我的模拟，除第一次义务失效，直接映射下每一次都会会有新的一个新的数据需要读取，产生cache miss，其他情况下都会cache hit，计算可得命中率为24*3/100=72%；全相联映射下，LRU替换策略会使得新加入的数据刚好在上一轮最后加入数据的下一个slot；四路组相连也与全相联映射类似，只不过他是产生在用一个set当中。
但是在上述条件情况下，如果扩大cache block size，就可以发现有明显的提升，因为他一次性会读取两个word，会使得第一轮第二个lw产生cache hit，因此扩大cache block size是非常有必要的。