1. 某计算机的主存地址空间大小为256 MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64 B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：

假定int类型数据用32位补码表示，程序编译时$i,j,sum$均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于$Cache$一致性维护和替换算法的控制位，则数据$Cache$的总容量为多少？

（2）数组元素$a[0][31]$和$a[1][1]$各自所在的主存块对应的$Cache$行号分别是多少（$Cache$行号从$0$开始）？

（3）程序$A和B$的数据访问命中率各是多少？哪个程序的执行时间更短？

---

分析：

• 主存地址空间大小为$256MB$
  • 主存总容量为 $2^{28}B$
• 按字节编址
  • 单位为字节
• 指令$Cache$和数据$Cache分$离
  • 这句话意味着在计算$Cache$容量时，不单单是计算$Cache$数据容量那么简单了，还需加上指令所占的容量。
• $8$个$Cache$行，每个$Cache$行大小为$64B$
  • 计算出$Cache$的总容量为$8\ast 64=2^{9}B$，同时也告诉了我们主存一个块有$64B(2^6)$大小,一共有$2^{28}/2^6=2^{22}$ 个块。
• 数据$Cache$采用直接映射方式
  • 直接映射意味着$Cache$的指令包含着标记位+有效位

整理得：

1. 对于主存
   1. 主存总容量为 $2^{28}B$
   2. 一共有 $2^{22}$ 个块，一个块有$2^6$大小
2. 对于$Cache$
   1. $Cache$的总容量为$2^{9}B$
   2. 一共有 $2^3$ 个块，一个块有$2^6$大小
3. $Cache总容量=Cache数据容量+Cache指令容量$

---

对于第一题：数据$Cache$的总容量为 $Cache数据容量+Cache指令容量$

$Cache数据容量: $ $64\ast 8$

$Cache指令容量(标记位+有效位): $ $有效位始终为1位$，下面来求标记位：

首先明确标记位来自于哪里，标记位是为了找到主存中某一块内容在$Cache$中的映射位置，所以它来源于主存块地址

主存地址

• 主存块号（直观看出主存有多少块）
  • 标记（就是通过它来与$Cache$建立联系）
  • 行号（直观看出$Cache$有多少行（块））
• 块内地址

因此可以明确的是:对于本题，主存地址：$28=22(19+3)+6$，因此得出结论$Cache指令容量的标记位为19$，最终得出本题答案$512+19+1=532$

简介写法：

---

对于第二题：一个$int$型数据$4$个字节，而主存（$Cache$）一个块$64$个字节，故而得出一个块可以存放$16$个$int$型数据

对于$a[0][31]$，$32mod16==0$不难知道该元素的主存地址为$320+31\ast 4=444=$ $\mathrm{0000....0001}$ $1011$ $1100$

• 六位块内地址为$111100$
• 22位主存块号$\mathrm{0000....0110}$

观察22位储存块号的后四位得到该元素处于$Cache$的第六块

简介写法：

• 算出改元素的主存地址
• 直接将其与$Cache$块大小取余得到结果

$444$ $div$ $64$ = $6$

---

对于第三题：

• 当程序A存入一个元素时，由于$Cache$ 会一下子将给元素的附近的（包括该元素）共16个元素一起存入，再次访问该元素的下一个元素时，由于元素按行再按列存入，元素的存储顺序与使用顺序高度吻合，除了访问的第一个元素不会命中，剩下15个均会命中，因此命中率位$16/15$ = $93.75$。
• 第二个程序按列执行循环，在执行内层循环时，将连续访问不同行的同一列数据，不同行的同一列数据使用的是同一$Cache$单元，每次都不会命中，命中率为0。
• 显然A快于B

---