问答题 某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：
程序A：
int a[256][2S6];
…
int sum_array 1 ( )
{
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_array 2 ( )
{
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(十进制)。请回答下列问题，要求说明理由或给出计算过程。
问答题 若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少?
【正确答案】Cache结构如下。
V … TAG Data
　　此处的行即为块(Block)。直接映射下，每块的Cache结构一般分为4个部分，其中，
　　V：1位，表示所在的块是否有效。
　　…：表示用于Cache一致性维护和替换算法的控制位。
　　TAG：地址转换标记。
　　如果不计算“…”部分，则Cache的大小由V、TAG和Data(数据)3部分组成。在直起射中，可以将地址分为如下3个部分：
TAG 块索引 块内
本题中，总的寻址位数为28位(228=256M)；块内位为6位(26=64)，5～0位；块索引为3位(23=8)，8～6位。因此，TAG=28-6-3=19位，即27～9位。
每行(块)的大小=V+TAG+数据=1+19+64×8位。
数据Cache有8行，总容量为(1+19+64×8)×8/8=532B。
【答案解析】
问答题 数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少(Cache行号从0开始)?
【正确答案】由于数组在存储器中按行优先方式存放，因此每个数组元素占4B。数组首地址为320，因此可知： a[0][31]在存储器中的地址为320+31×4=444=0001 1011 1100B a[1][1]在存储器中的地址为：320+(256+1)×4=1348=0101 0100 0100B 按直接映射方式，地址分为3部分，块索引在地址的8～6位，因此两地址所对应的块索引分别为6(110B)、5(101B)。
【答案解析】
问答题 程序A和B的数据访问命中率各是多少?哪个程序的执行时间更短?
【正确答案】数组a中每个数据只用了一次，如果程序没有命中，则从主存中读入一块，大小64B，相当于16个整数。对于程序A，如果是按行连续存放的，那么从主存读入一块到Cache(一次失配)后，随后的15次便都Cache命中，读一次管16次，因此命中率为
[(216-212)/216]×100%=93.75%
程序B随列访问数组a，由于Cache的容量太小，读入的数据块留不到下次用便又被替换，因此每次都失败，命中率为0%。
另一种算法是，由于数组a一行的数据量为1KB＞64B，因此访问第0行时，每个元素都不命中，由于数组有256列，数据Cache仅有8行，故访问数组后续列元素仍然不命中，于是程序B的数据访问命中率为0%。
由于从Cache读数据比从内存读数据快很多，因此程序A的执行时间更短。
分析：
1)V、TAG、Data是每个Cache块(行)的必要组成。为了提高效率或者实行替换算法，每个块还需要一些控制位，这些位根据不同的设计要求而定。
2)本题中计算两个数组元素的地址是关键。
3)命中率的计算是本问题的关键。注意数组访问与数组在内存中的存储方式，以及命中率的定义。
【答案解析】