问答题
以下是计算两个向量点积的程序段：
float Dotproduct(float x[8], float y[8]){
float sum=0.0;
int i;
for(i=0; i＜8; i++)
sum+=X[i]*y[i];
return sum;
}
请回答下列问题：
问答题
请分析访问数组x和y时的时间局部性和空间局部性?
【正确答案】
【答案解析】数组x和y都按顺序访问，空间局部性都较好，但每个数组元素都只被访问一次，故没有时间局部性。
问答题
假定数据Cache采用直接映射方式，Cache容量为32字节，每个主存块大小为16字节；编译器将变量sum和i分配在寄存器中，内存按字节编址，数组x存放在0000 0040H开始的32字节的连续存储区中，数组y则紧跟在x后进行存放。该程序数据访问的命中率是多少?要求说明每次访问时Cache的命中情况。
【正确答案】
【答案解析】Cache共有32B/16B=2行；4个数组元素占一个主存块(现在的计算机中float型一般为32位，占4B)；数组x的8个元素(共32B)分别存放在主存40H开始的32个单元中，共占有2个主存块，其中x[0]～x[3]在第4块(00H-0FH为第0块，10H-1FH为第1块，以此类推，40H-4FH为第4块，下同)，x[4]～x[7]在第5块中；数组y的8个元素分别在主存第6块和第7块中。所以，x[0]～x[3]和y[0]～y[3]都映射到Cache第0行；x[4]～x[7]和y[4]～y[7]都映射到Cache第1行，如下表所示。因为x[i]和y[i](0≤i≤7)总是映射到同一个Cache行，相互淘汰对方，故每次都不命中，命中率为0。
|
Cache——主存地址
|
40H～5FH
|
60H～7FH
|
|
第0行
|
x[0]～x[3](第四块)
|
y[0]～y[3](第六块)
|
|
第1行
|
x[4]～x[7](第五块)
|
y[4]～y[7](第七块)
|
问答题
将上述上一小题中的数据Cache改用2-路组相联映射方式，块大小改为8字节，其他条件不变，则该程序数据访问的命中率是多少?
【正确答案】
【答案解析】若Cache改用2-路组相联，块大小改为8B，则Cache共有4行，每组2行，共2组。两个数组元素占一个主存块。数组x占4个主存块，数组元素x[0]～x[1]、x[2]～x[3]、x[4]～x[5]、x[6]～x[7]分别在第8～11块中(与上题同理，这里00H～07H为第0块，08H～0FH为第1块，以此类推)；数组y占4个主存块，数组元素y[0]～y[1]、y[2]～y[3]、y[4]～y[5]、y[6]～y[7]分别在第12～15块中，映射关系如下表所示；因为每组有两行，所以x[i]和y[i](0≤i≤7)虽然映射到同一个Cache组，但可以存放到同一组的不同Cache行内，因此，不会发生冲突。每调入一个主存块，装入的2个数组元素中，第2个数组元素总是命中，故命中率为50%。
|
Cache——主存地址
|
40H～4FH
|
50H～5FH
|
60H～6FH
|
70H～7FH
|
|
第一组
|
x[0]～x[1]
|
x[4]～x[5]
|
y[0]～y[1]
|
y[4]～y[5]
|
|
第二组
|
x[2]～x[3]
|
x[6]～x[7]
|
y[2]～y[3]
|
y[6]～y[7]
|
问答题
在上述第二小题中条件不变的情况下，将数组X定义为float[12]，则数据访问的命中率是多少?
【正确答案】
【答案解析】将数组x定义为12个元素后，则x共有48B，使得y从主存第7块开始存放，即x[0]～x[3]在第4块，x[4]～x[7]在第5块，x[8]-x[11]在第6块中；y[0]～y[3]在第7块，y[4]～y[7]在第8块。因而，x[i]和y[i](0≤i≤7)就不会映射到同一个Cache行中，映射关系如下表所示。每调入一个主存块，装入4个数组元素，第一个元素不命中，后面3个总命中，故命中率为75%。
|
Cache——主存地址
|
40H～5FH
|
60H～7FH
|
80H～8FH
|
|
第0行
|
x[0]～x[3](第四块)
|
x[8]～x[11](第六块)
|
y[4]～y[7](第八块)
|
|
第1行
|
x[4]～x[7](第五块)
|
y[0]～y[4](第七块)
|
—
|