问答题 在信号处理和科学的应用中，转置矩阵的行和列是一个很重要的问题。从局部性的角度来看，它也很有趣，因为它的引用模式既是以行为主的，也是以列为主的，例如，考虑下面的转置函数：
1 typedef int array a[2][2];
2
3 void transposel(array dst, array src)
4 {
5 int i, j;
6 for(i=0; i＜2; i++){
7 for(j=0; j＜2j;j++){
8 dst[j][i]=src[i][j];
9 }
10 }
11 }
假设在一台具有如下属性的机器上运行这段代码：
·sizeof(int)==4。
·src数组从地址0开始，dst数组从地址16开始(十进制)。
·只有一个L1数据高速缓存，它是直接映射的、直写、写分配，块大小为8个字节。
·这个高速缓存总的大小为16个数据字节，一始是空的。
·对src和dst数组的访问分别是读和写不命中的唯一来源。
问题如下：
问答题 对每个row和col，指明对src[row][col]和dst[row][col]的访问是命中(h)还是不命中(m)，例如，读src[0][0]会不命中，写dst[0][0]也不命中，并将结果填至下列表格中。
{{B}}dst数组{{/B}}
列0 列1
行0
行1
{{B}}src数组{{/B}}
列0 列1
行0
行1
【正确答案】解决这个问题的关键是想象出如图1所示的关系图。
[*]

关系图(一)

注意：每个高速缓存行只包含数组的一个行，高速缓存正好只够保存一个数组，而且对于所有i，src和dst的行i都映射到同一个高速缓存行(0%2=Q，1%2=1，2%2=0，3%2=1)。因为高速缓存不够大，不足以容纳这两个数组，所以对一个数组的引用总是驱逐出另一个数组的有用的行。具体过程如下：
dst[j][i]=src[i][j]语句先访问src[i][j]再将其存储到dst[j][i]
访问 命中否 访问后Line0中内容 访问后Linel中内容
src[0][0] m src[0]
dst[0][0] m dst[0]
src[0][1] m src[0]
dst[1][0] m src[0] dst[1]
src[1][0] m src[0] src[1]
dst[0][1] m dst[0] src[1]
src[1][1] h dst[0] src[1]
dst[1][1] m dst[0] dst[1]
说明如下： ①访问src[0][0]，不命中，将src[0]调入高速缓存的Line0。 ②访问dst[0][0]，不命中，将dst[0]调入高速缓存的Line0，换出src[0]。 ③访问src[0][1]，不命中，将src[0]调入高速缓存的Line0，换出dst[0]。 ④……
{{B}}dst数组{{/B}}
列0 列1
行0 m m
行1 m m
{{B}}src数组{{/B}}
列0 列1
行0 m m
行1 m h
【答案解析】
问答题 对于一个大小为32数据字节的高速缓存，指明src和dst的访问命中情况，并将结果填至下列表格中。
{{B}}dst数组{{/B}}
列0 列1
行0
行1
{{B}}src数组{{/B}}
列0 列1
行0
行1
【正确答案】当高速缓存为32B时，它足够大，能容纳这两个数组。因此所有不命中都是开始时的冷不命中。关系如图2所示。
[*]

图2 关系图(二)
访问 命中否 Line0 Line1 line2 line3
src[0][0] m src[0]
dst[0][0] m src[0] dst[0]
sre[0][1] h src[0] dst[0]
dst[1][0] m src[0] dst[0] dst[1]
src[1][0] m src[0] src[1] dst[0] dst[1]
dst[0][1] h src[0] src[1] dst[0] dst[1]
src[1][1] h src[0] src[1] dst[0] dst[1]
dst[1][1] h src[0] src[1] dst[0] dst[1]
{{B}}dst数组{{/B}}
列0 列1
行0 m h
行1 m h
{{B}}src数组{{/B}}
列0 列1
行0 m h
行1 m h
【答案解析】