问答题
屏幕保护程序Sim Aquarium的核心就是一个紧密循环(tight
loop)，它可以计算出256个海藻(algae)的平均位置。在一台具有块大小为16字节(B=16)、整个大小为1024字节的直接映射数据缓存的机器上测量它的高速缓存性能。定义如下：
1 struct algae_position{
2 int
x;
3 int y;
4
};
5
6 struct slgae_position grid
[16][16];
7 int total_x=0，total_y=0;
8 int i, j;
还有如下假设：
·sizeof(int)==4。
·grid从存储器地址0开始。
·这个高速缓存开始时是空的。
·唯一的存储器访问是对数组grid的元素访问。变量i、j、total_x和total_y存放在寄存器中。
确定下面代码的高速缓存性能：
1 for(i=0; i＜16; i++){
2 for(j=0; j＜16; j++){
3
total_x+=grid[i][j].x;
4 }
5 }
6
7 for(i=0; i＜16;
i++){
8 for(j=0; j＜16; j++){
9 total_y+=grid[i][j].y;
10
}
11 }
问答题
不命中率是多少?
【正确答案】块大小为16B，高速缓存大小为1024B，所以高速缓存一共分为64个块。
grid的每个algae_position结构，包含两个int变量，共8B，即每个16B的高速缓存行包含着两个连续的algae_position结构。每个循环按照存储器顺序访问这些结构，每次读一个整数元素。
所以，第一个for语句的每个循环的模式就是不命中→命中→不命中→命中，以此类推。所以对于这个问题，不必实际列举出读和不命中的总数，就能预测出不命中率。
又grid数组在主存中占用128个块，当前64个块换入到高速缓存后，第65个块会将其第1个块驱逐出高速缓存。
所以，第二个for语句访问grid[0][0]时，grid已不在高速缓存中，所以其循环的模式还是不命中→命中→不命中→命中。
综上所述，不命中率为256/512=50%。
【答案解析】
问答题
如果高速缓存有两倍大，那么不命中率是多少?
【正确答案】如果高速缓存有两倍大，第一个for语句跟1)相同(128次不命中)，但第二个for语句全部命中。因为高速缓存能够保存整个grid数组，第二个for语句开始循环时，这个grid数组都已经在高速缓存中了，所以全部命中。
综上所述，不命中率为128/512=25%。
【答案解析】
问答题
高速缓存大小不变情况下，通过修改代码，是否能降低不命中率?如果能，请写出具体代码，并给出新代码的不命中率。
【正确答案】通过修改代码可以降低不命中率。因为两个for循环的步长为2，且一个algae_position结构拥有两个int变量，但每个for循环却只访问其中的一个int变量。正确的代码应该是步长为1的。代码如下：
1 for(i=0; i＜16; i++){
2 for(j=0; j＜16; j++){
3 total_x+=grid[i][j].x;
4 total_y+=grid[i][j].y;
5 }
6 }
for语句的循环模式就是不命中、命中、命中、命中，以此类推，所以不命中率为128/512=25%。
【答案解析】