Yo
虑成本，你还这样设计高性能计算机吗？为什么？
参考答案： 不这样做的理由主要有以下两个方面： ① 主存越大越好，主存大，缺页率降低，因而减少了访问磁
盘所需的时间。显然用
片比用 SRAM 芯片构成的主存容量大的多。
② 程序访问的局部性特点使得 cache 的命中率很高，因而，即使主存没有用快速的 片而是用 DRAM 芯片，也不会影响到访问速度。
9. 分别给出具有下列要求的程序或程序段的示例： （1）对于数据的访问，几乎没有时间局部性和空间局部性。
（2）对于数据的访问，有很好的时间局部性，但几乎没有空间局部性。 （3）对于数据的访问，有很好的空间局部性，但几乎没有时间局部性。 （4）对于数据的访问，空间局部性和时间局部性都好。
参考答案（略） ：
可以给出许多类似的示例。例如，对于按行优先存放在内存的多维数组，如果按列优先访问数 组元素，则空间局部性就差，如果在一个循环体中某个数组元素只被访问一次，则时间局部性就差。
10?假定某机主存空间大小 1GB ,按字节编址。CaChe的数据区（即不包括标记、有效位等存储区）有64KB , 块大小
为 128字节，采用直接映射和全写（ （2）CaChe的总容量为多少位？ 参考答案：
（1） 主存空间大小为 1GB ,按字节编址，说明主存地址为
30位。CaChe共有64KB∕128B=512行， 因
此，行索引（行号）为 9 位；块大小 128 字节，说明块内地址为 7 位。因此， 30 位主存地址 中，高 14 位为标志（ Tag ）；中间 9 位为行索引；低 7 位为块内地址。
（2） 因为采用直接映射，所以 CaChe中无需替换算法所需控制位，全写方式下也无需修改（
位，而标志位和有效位总是必须有的，所以，
dirty）
CaChe总容量为512×（128疋+14+1）=519.5K位。
write-through ）方式。请问：
（ 1 ）主存地址如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。
SRAM 芯 DRAM 芯
11?假定某计算机的CaChe共16行，开始为空，块大小为 1个字，采用直接映射方式。
依次访问以下地址序列： 2， 3， 11， 16，
22， 4，
21， 13，
64，
27， 6和11。要求：
CPU执行某程序时， 48， 19， 11， 3，
（1） 说明每次访问是命中还是缺失，试计算访问上述地址序列的命中率。
（2） 若 CaChe 数据区容量不变，而块大小改为 4 个字，则上述地址序列的命中情况又如何？ 参考答案
（1） CaChe采用直接映射方式，其数据区容量为16行×字/行=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个字/块，所以，主存块号 号 = 主存块号 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 ，
=[字号/4]。因此，映射公式为：CaChe行
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])
{
int i, j, k, sum=0; for (k=0; k < N; k++)
for (i=0; i < N; i++)
for (j=0; j < N; j++)
return sum;
}
sum+=a[k][i][j];
修改后程序的数组元素的访问与排列顺序一致，使得空间局部性比原程序好，故执行时间更短。
13. 分析比较以下三个函数的空间局部性，并指出哪个最好，哪个最差？
# define N 1000 typedef StrUCt { in t vel[3]; int acc[3]; } poi nt; poi nt p[N]; void clear1(po int *p, int n) { int i, j; for (i = 0; i V n; i++) { for (j = 0; j<3; j++) p[i].vel[j] = 0; for (j = 0; i<3; j++) p[i].acc[j] = 0; } } # define N 1000 typedef StrUCt { in t vel[3]; int acc[3]; } poi nt; poi nt p[N]; void clear2(po int *p, int n) { int i, j; for (i=0; i 对于函数ClearI ,其数组访问顺序与在内存的存放顺序完全一致，因此，空间局部性最好。 对于函数clear2，其数组访问顺序在每个数组元素内跳越式访问， 相邻两次访问的单元最大相差 clear1差。若主存块大小比 6个 3个int型变量（假定SiZeof（int）=4 ,则相当于12B），因此空间局部性比 12B小的话，则大大影响命中率。 对于函数clear3，其数组访问顺序与在内存的存放顺序不一致， 相邻两次访问的单元都相差 int型变量（假定 SiZeof（int）=4 ,则相当于24B）因此，空间局部性比 24B小的话，则大大影响命中率。 clear2还差。若主存块大小比 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采用直接映射方式，其数据区容量为 主存块大小为16字节。假定编译程序将变量 开始的32字节的连续存储区中，数组 率，要求说明每次访问的 CaChe命中情况。 8字节，其他条件不变， 则该 32字节，每个 SUm和i分配给寄存器，数组X存放在00000040H y紧跟在X后进行存放。试计算该程序数据访问的命中 （3） 将上述（2）中的数据CaChe改用2-路组相联映射方式，块大小改为 程序数据访问的命中率是多少？ (4) 在上述(2)中条件不变的情况下，如果将数组 X定义 为float[12],则数据访问的命中率是多 少？ 参考答案： (1) 低。 (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行 数组X和y都按存放顺序访问， 空间局部性都较好， 但都只被访问一次， 不考虑映射的情况下， 故没有时间局部性。命中率的高低与块大小、映射方式等都有关，所以，无法推断命中率的高 第0-3次循环 x[0-3]，y[0-3] 第4-7次循环 x[4-7]，y[4-7] 每调入一块，装入 4个数组元素，因为 x[i]和y[i]总是映射到同一行，相互淘汰对方，故每次都 不命中，命中率为 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] 50%。 每调入一块，装入两个数组元素，第二个数组元素的访问总是命中，故命中率为 (4) 始，因而，x[i] 若(2)中条件不变，数组 X定义了 12个元素，共有48B ,使得y从第7块开 和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行 第0-3次循环 x[0-3] 第4-7次循环 y[4-7] 75%。 x[4-7] y[0-3] 每调入一块，装入 4个数组元素，第一个元素不命中，后面 3个总命中，故命中率为 15. 以下是对矩阵进行转置的程序段： typedef int array[4][4]; void { int i, j; for (i = 0; i < 4; i++) for (j = 0; j V 4; j++) dst[j][i] = src[i][j]; } 假设该段程序运行的计算机中 tran spose(array dst, array SrC) SiZeof(int)=4，且只有一级CaChe，其中L1 data CaChe的数据区大小为
计算机组成与系统结构课后答案全(清华大学出版社袁春风主编).docx
