44.（12分）某计算机的主存地址空间大小为256MB，按字节编址。指令Cache 和数据Cache 分离，均有8个 Cache 行，每个Cache 行大小为64B，数据 Cache 采用直接映射方式。现有两个功能相同的程序 A和B，其伪代码如下所示∶ 程序A∶int a[256][256];int sum_array 1()int ij,sum=0;for(i=0;i<256;++) 程序B∶int a[256][256];int sum_array 2()int ij,sum=0;for(j=0:j<256j++) 假定 int类型数据用32位补码表示，程序编译时i、j、sum均分配在寄存器中，数组a按行优先方式存放，其首地址为 320（十进制）。请回答下列问题，要求说明理由或给出计算过程。 （1）若不考虑用于Cache一致维护和替换算法的控制位，则数据Cache 的总容量为多少? （2）数组元素 a【0】【31】和a【1】【1】各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）? （3）程序A 和B的数据访问命中率各是多少?哪个程序的执行时间更短?
【参考答案及解析】
（1）数据 Cache有8个 Cache 行，每个 Cache 行大小为64B，Cache 中每个字块的 Tag 字段的位数是28一9 =19位，此外还需使用一个有效位，合计20位。因此，数据 Cache 的总容量应为∶8×（64＋20/8）B=532B。 （2）数组 a 在主存的存放位置及其与Cache 之间的映射关系如下图所示： 数组按行优先方式存放，首地址为 320，数组元素占四个字节。a[0][31]所在的主存块对应的Cache行号为： (320+31×4)DIV64=6; a[1][1]所在的主存块对应的Cache 行号为： (320+256×4＋1×4) DIV64 MOD 8=5。 （3）编译时 i、j、sum 均分配在寄存器中，故数据访问命中率仅考虑数组 a 的情况。 ① 该程序的特点是数组中的每一个元素仅被使用一次。数组a按行优先存放，数据 Cache 正好放下数组半行中的全部元素，即元素的存储顺序与使用次序高度的吻合，每个字块的 16个 int 型元素中，除访问的第一个不会命中，接下来的 15个都会命中。访问全部字块都符合这一规律，故命中率为15/16，即程序A 的数据访问命中率是93.75%。 ②程序 B按照数组的列执行外层循环，在执行内层循环的过程中，将连续访问不同行的同一列的数据，不同行的同一列数组使用的是同一个 Cache 单元，每次都不会命中，故命中率是0 由于从 Cache 读数据比从主存读数据快很多，所以程序A 的执行比程序B快得多。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）数据 Cache有8个 Cache 行，每个 Cache 行大小为64B，Cache 中每个字块的 Tag 字段的位数是28一9 =19位，此外还需使用一个有效位，合计20位。因此，数据 Cache 的总容量应为∶8×（64＋20/8）B=532B。 （2）数组 a 在主存的存放位置及其与Cache 之间的映射关系如下图所示： 数组按行优先方式存放，首地址为 320，数组元素占四个字节。a[0][31]所在的主存块对应的Cache行号为： (320+31×4)DIV64=6; a[1][1]所在的主存块对应的Cache 行号为： (320+256×4＋1×4) DIV64 MOD 8=5。 （3）编译时 i、j、sum 均分配在寄存器中，故数据访问命中率仅考虑数组 a 的情况。 ① 该程序的特点是数组中的每一个元素仅被使用一次。数组a按行优先存放，数据 Cache 正好放下数组半行中的全部元素，即元素的存储顺序与使用次序高度的吻合，每个字块的 16个 int 型元素中，除访问的第一个不会命中，接下来的 15个都会命中。访问全部字块都符合这一规律，故命中率为15/16，即程序A 的数据访问命中率是93.75%。 ②程序 B按照数组的列执行外层循环，在执行内层循环的过程中，将连续访问不同行的同一列的数据，不同行的同一列数组使用的是同一个 Cache 单元，每次都不会命中，故命中率是0 由于从 Cache 读数据比从主存读数据快很多，所以程序A 的执行比程序B快得多。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！