某计算机的主存地址空间大小为 256MB，按字节编址。指令 Cache 和数据 Cache 分离，均有 8 个 Cache 行，每个 Cache 行大小为 64B，数据 Cache 采用直接映射方式。现有两个功能相同的程序 A 和 B，其伪代码如下所示：
// 程序 A
int a[256][256];
.....
int sum_array1()
{
int i, j, sum=0;
for (i=0; i<256; i++)
for (j=0; j<256; j++)
sum += a[i][j];
return sum;
}
// 程序 B
int a[256][256];
.....
int sum_array2()
{
int i, j, sum=0;
for (j=0; j<256; j++)
for (i=0; i<256; i++)
sum += a[i][j];
return sum;
}
假定 int 类型数据用 32 位补码表示，程序编译时 i，j，sum 均分配在寄存器中，数组 a 按行优先方式存放，其首地址为 320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。
(1) 若不考虑用于 cache 一致性维护和替换算法的控制位，则数据 Cache 的总容量为多少？
(2) 数组元素 a[0][31] 和 a[1][1] 各自所在的主存块对应的 Cache 行号分别是多少（Cache 行号从 0 开始）？
(3) 程序 A 和 B 的数据访问命中率各是多少？哪个程序的执行时间更短？
[tag_link]
1）每个 Cache 行对应一个标记项，如下所示：| 有效位 | 脏位 | 替换控制位 | 标记位 |不考虑用于 Cache 一致性维护和替换算法的控制位。地址总长度为 28 位（228=256 M），块内地址 6 位（26=64），Cache 块号 3 位（23=8），故 Tag 的位数为 28-6-3=19 位，还需使用一个有效位，故题中数据 Cache 行的结构如下图所示。
数据 Cache 共有 8 行，因此数据 Cache 的 总容量为8×(64+20/8)B= 532B。
2）数组 a 在主存的存放位置及其 与 Cache 之间的映射关系如下图所示。
数组按行优先方式存放，首地址为 320，数组元素占 4 字节。a[0][31] 所在的主存块对应的 Cache 行号为(320+31×4)/64=6；a[1][1] 所在的主存块对应的 Cache 行号为(320+256×4+1×4)/64%8=5。
3）数组 a 的大小为256×256×4B=218 B, 占用218/64=212个主存块，按行优先存放，程序A逐行访问数组，共需访问的次数为216次，未命中次数为212次（即每个字块的第一个数未命中），因此程序A的命中率为(216−212)/216×100%=93.75%。【另解】数组 a 按行存放，程序 A 按行存取。每个字块中存放 16 个 int 型数据，除访问的第一个不命中，随后的 15 个全都命中，访问全部字块都符合这一规律，且数组大小为字块大小的整数倍，故程序 A 的命中率为 15/16=93.75%。程序 B 逐列访问数组 a，Cache 总容量为 64Bx8=512B，数组 a 一行的大小为 1KB，正好是 Cache 容量的 2 倍，可知不同行的同一列数组元素使用的是同一个 Cache 单元，故逐列访问每个数据时，都会将之前的字块置换出，也即每次访问都不会命中，命中率为 0。由于从 Cache 读数据比从主存读数据快很多，所以程序 A 的执行比程序 B 快得多。注意：本题考查 Cache 容量计算，直接映射方式的地址计算，以及命中率计算（注意：行优先遍历与列优先遍历命中率差别很大）。