（1）对于数据的访问，几乎没有时间局部性和空间局部性。

（2）对于数据的访问，有很好的时间局部性，但几乎没有空间局部性。 （3）对于数据的访问，有很好的空间局部性，但几乎没有时间局部性。 （4）对于数据的访问，空间局部性和时间局部性都好。 参考答案（略）：

可以给出许多类似的示例。例如，对于按行优先存放在内存的多维数组，如果按列优先访问数组元素，则空间局部性就差，如果在一个循环体中某个数组元素只被访问一次，则时间局部性就差。 10. 假定某机主存空间大小1GB，按字节编址。cache的数据区（即不包括标记、有效位等存储区）有

64KB，块大小为128字节，采用直接映射和全写（write-through）方式。请问： （1）主存地址如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。 （2）cache的总容量为多少位？ 参考答案：

（1）主存空间大小为1GB，按字节编址，说明主存地址为30位。cache共有64KB/128B=512行，因

此，行索引（行号）为9位；块大小128字节，说明块内地址为7位。因此，30位主存地址中，高14位为标志（Tag）；中间9位为行索引；低7位为块内地址。

（2）因为采用直接映射，所以cache中无需替换算法所需控制位，全写方式下也无需修改（dirty）位，

而标志位和有效位总是必须有的，所以，cache总容量为512×(128×8+14+1)=519.5K位。

11. 假定某计算机的cache共16行，开始为空，块大小为1个字，采用直接映射方式。CPU执行某程序时，

依次访问以下地址序列：2，3，11，16，21，13，64，48，19，11，3，22，4，27，6和11。要求： （1）说明每次访问是命中还是缺失，试计算访问上述地址序列的命中率。

（2）若cache数据区容量不变，而块大小改为4个字，则上述地址序列的命中情况又如何？ 参考答案

（1） cache采用直接映射方式，其数据区容量为16行×1字/行=16字；主存被划分成1字/块，所以，

主存块号 = 字号。因此，映射公式为：cache行号 = 主存块号 mod 16 = 字号 mod 16。 开始cache为空，所以第一次都是miss，以下是映射关系（字号-cache行号）和命中情况。 2-2: miss，3-3: miss，11-11: miss，16-0: miss, 21-5: miss，13-13: miss，64-0: miss、replace， 48-0: miss、replace，19-3: miss、replace，11-11: hit, 3-3: miss、replace，22-6: miss， 4-4: miss，27-11: miss、replace，6-6: miss、replace，11-11: miss、replace。

只有一次命中！

（2）cache采用直接映射方式，数据区容量不变，为16个字，每块大小为4个字，所以，cache共有

4行；主存被划分为4个字/块，所以，主存块号 = [字号/4]。因此，映射公式为：cache行号 = 主存块号 mod 4 = [字号/4] mod 4。

以下是映射关系（字号-主存块号-cache行号）和命中情况。

2-0-0: miss，3-0-0: hit，11-2-2: miss，16-4-0: miss、replace，21-5-1、13-3-3: miss， 64-16-0、48-12-0、19-4-0: miss, replace，11-2-2: hit，3-0-0: miss、replace，

22-5-1: hit，4-1-1: miss、replace，27-6-2: miss、replace，6-1-1: hit，11-2-2: miss、replace。

命中4次。

由此可见，块变大后，能有效利用访问的空间局部性，从而使命中率提高！

12. 假定数组元素在主存按从左到右的下标顺序存放。试改变下列函数中循环的顺序，使得其数组元素的

访问与排列顺序一致，并说明为什么修改后的程序比原来的程序执行时间短。 int sum_array ( int a[N][N][N]) {

int i, j, k, sum=0; for (i=0; i < N; i++)

for (j=0; j < N; j++)

for (k=0; k < N; k++) sum+=a[k][i][j];

return sum; }

参考答案：

int sum_array ( int a[N][N][N]) { }

修改后程序的数组元素的访问与排列顺序一致，使得空间局部性比原程序好，故执行时间更短。 13. 分析比较以下三个函数的空间局部性，并指出哪个最好，哪个最差？

# define N 1000 typedef struct { int vel[3]; int acc[3]; # define N 1000 typedef struct { int vel[3]; int acc[3]; # define N 1000 typedef struct { int vel[3]; int acc[3]; int i, j, k, sum=0; for (k=0; k < N; k++)

for (i=0; i < N; i++)

for (j=0; j < N; j++) sum+=a[k][i][j];

return sum;

} point; } point; } point; point p[N]; void clear1(point *p, int n) { } int i, j; for (i = 0; i < n; i++) { } for (j = 0; j<3; j++) for (j = 0; i<3; j++) p[i].acc[j] = 0; p[i].vel[j] = 0; point p[N]; void clear2(point *p, int n) { } int i, j; for (i=0; i

int i, j; for (j=0; j<3; j++) { } for (i=0; i

对于函数clear1，其数组访问顺序与在内存的存放顺序完全一致，因此，空间局部性最好。

对于函数clear2，其数组访问顺序在每个数组元素内跳越式访问，相邻两次访问的单元最大相差3个int型变量（假定sizeof(int)=4，则相当于12B），因此空间局部性比clear1差。若主存块大小比12B小的话，则大大影响命中率。

对于函数clear3，其数组访问顺序与在内存的存放顺序不一致，相邻两次访问的单元都相差6个int型变量（假定sizeof(int)=4，则相当于24B）因此，空间局部性比clear2还差。若主存块大小比24B小的话，则大大影响命中率。 14. 以下是计算两个向量点积的程序段：

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;

要求：

（1）试分析该段代码中数组x和y的时间局部性和空间局部性，并推断命中率的高低。

（2）假定该段程序运行的计算机的数据cache采用直接映射方式，其数据区容量为32字节，每个主

存块大小为16字节。假定编译程序将变量sum和i分配给寄存器，数组x存放在00000040H开始的32字节的连续存储区中，数组y紧跟在x后进行存放。试计算该程序数据访问的命中率，要求说明每次访问的cache命中情况。

（3）将上述（2）中的数据cache改用2-路组相联映射方式，块大小改为8字节，其他条件不变，则

该程序数据访问的命中率是多少？

（4）在上述（2）中条件不变的情况下，如果将数组x定义为float[12]，则数据访问的命中率是多少？ 参考答案：

（1）数组x和y都按存放顺序访问，不考虑映射的情况下，空间局部性都较好，但都只被访问一次，

故没有时间局部性。命中率的高低与块大小、映射方式等都有关，所以，无法推断命中率的高低。

（2）cache采用直接映射方式，块大小为16字节，数据区大小为32字节，故cache共有2行。数组

x的8个元素（共32B）分别存放在主存40H开始的32个单元中，共有2个主存块，其中x[0] ~ x[3]在第4块，x[4] ~ x[7]在第5块中；数组y的8个元素（共32B）分别在主存第6块和第7块中。所以，x[0] ~ x[3]和y[0] ~ y[3]都映射到cache第0行；

x[4] ~ x[7]和y[4] ~ y[7]都映射到cache第1行。 cache 第0行 第1行 不命中，命中率为0.

（3）改用2路组相联，块大小为8B，则cache共有4行，每组两行，共两组。

数组x有4个主存块，x[0] ~ x[1]、x[2] ~ x[3]，x[4] ~ x[5]，x[6] ~ x[7]分别在第8~11块中； 数组y有4个主存块，y[0] ~ y[1]、y[2] ~ y[3]，y[4] ~ y[5]，y[6] ~ y[7]分别在第12~15块中；

cache 第0组 第1组 第0行 x[0-1],x[4-5] x[2-3],x[6-7] 第1行 y[0-1],y[4-5] y[2-3],y[6-7] 第0-3次循环 x[0-3]，y[0-3] 第4-7次循环 x[4-7]，y[4-7] 每调入一块，装入4个数组元素，因为x[i]和y[i]总是映射到同一行，相互淘汰对方，故每次都

每调入一块，装入两个数组元素，第二个数组元素的访问总是命中，故命中率为50%。

（4）若（2）中条件不变，数组x定义了12个元素，共有48B，使得y从第7块开始，因而，x[i]和y[i]

就不会映射到同一个cache行中，即：x[0] ~ x[3]在第4块，x[4] ~ x[7]在第5块，x[8] ~ x[11]在第6块中，y[0] ~ y[3]在第7块，y[4] ~ x[7]在第8块。

cache 第0行 第1行 15. 以下是对矩阵进行转置的程序段： typedef int array[4][4]; void {

int i, j;

for (i = 0; i < 4; i++)

transpose(array dst,

array src)

第0-3次循环 x[0-3] y[0-3] 第4-7次循环 y[4-7] x[4-7] 每调入一块，装入4个数组元素，第一个元素不命中，后面3个总命中，故命中率为75%。

}

for (j = 0; j < 4; j++)

dst[j][i] = src[i][j];

假设该段程序运行的计算机中sizeof(int)=4，且只有一级cache，其中L1 data cache的数据区大小为32B，采用直接映射、写回方式，块大小为16B，初始为空。数组dst从地址0000C000H开始存放，数组src从地址0000C040H开始存放。填写下表，说明数组元素src[row][col]和dst[row][col]映射到cache的哪一行，其访问是命中（hit）还是失效（miss）。若L1 data cache的数据区容量改为128B时，重新填写表中内容。

32B row=0 row=1 row=2 row=3 128B row=0 row=1 row=2 row=3 参考答案：

从程序来看，数组访问过程如下：

src[0] [0]、dst[0] [0]、src[0] [1]、dst[1] [0]、src[0] [2]、dst[2] [0]、src[0] [3]、dst[3] [0] src[1] [0]、dst[0] [1]、src[1] [1]、dst[1] [1]、src[1] [2]、dst[2] [1]、src[1] [3]、dst[3] [1] src[2] [0]、dst[0] [2]、src[2] [1]、dst[1] [2]、src[2] [2]、dst[2] [2]、src[2] [3]、dst[3] [2] src[3] [0]、dst[0] [3]、src[3] [1]、dst[1] [3]、src[3] [2]、dst[2] [3]、src[3] [3]、dst[3] [3]

因为块大小为16B，每个数组元素有4个字节，所以4个数组元素占一个主存块，因此每次总是调入4个数组元素到cache的一行。

当数据区容量为32B时，L1 data cache中共有2行。数组元素dst[0][i]、dst[2][i] 、src[0][i]、src[2][i] (i=0～3)都映射到cache第0行，数组元素dst[1][i]、dst[3][i] 、src[1][i]、src[3][i] (i=0～3)都映射到cache第1行。因此，从上述访问过程来看，src[0][0]所在的一个主存块（即存放src[0][i] (i=0～3)四个数组元素）刚调入cache后，dst[0][0]所在主存块又把src[0][0]替换掉了。……

当数据区容量为128B时，L1 data cache中共有8行。数组元素dst[0][i]、dst[1][i] 、dst[2][i]、dst[3][i]、src[0][i]、src[1][i]、src[2][i]、src[3][i] (i=0～3) 分别映射到cache第0、1、2、3、4、5、6、7行。因此，不会发生数组元素的替换。每次总是第一个数组元素不命中，后面三个数组元素都命中。 16. 通过对方格中每个点设置相应的CMYK值就可以将方格图上相应的颜色。以下三个程序段都可实现对

一个8×8的方格中图上黄色的功能。

col=0 4/miss 5/ miss 6/ miss 7/ miss col=0 0/miss 1/miss 0/miss 1/miss src数组 col=1 0/miss 1/hit 0/miss 1/hit col=1 4/hit 5/hit 6/hit 7/hit col=2 0/hit 1/miss 0/hit 1/miss col=2 4/hit 5/hit 6/hit 7/hit col=3 0/miss 1/hit 0/miss 1/hit col=3 4/ hit 5/hit 6/hit 7/hit col=0 0/miss 1/miss 0/miss 1/miss col=0 0/miss 1/miss 2/miss 3/miss dst数组 col=1 0/miss 1/miss 0/miss 1/miss col=1 0/hit 1/hit 2/hit 3/hit col=2 0/miss 1/miss 0/miss 1/miss col=2 0/hit 1/hit 2/hit 3/hit col=3 0/miss 1/miss 0/miss 1/miss col=3 0/hit 1/hit 2/hit 3/hit src数组 dst数组