struct pt_color { int c; int m; int y; int k; } struct pt_color square[8][8]; int i, j; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { square[i][j].c = 0; square[i][j].m = 0; square[i][j].y = 1; square[i][j].k = 0; } } struct pt_color { int c; int m; int y; int k; } struct pt_color quare[8][8]; int i, j; for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { square [j] [i].c = 0; square [j] [i].m = 0; square [j] [i].y = 1; square [j] [i].k = 0; } } struct pt_color { int c; int m; int y; int k; } struct pt_color square[8][8]; int i, j; for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) square[i][j].y = 1; for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) { square[i][j].c = 0; square[i][j].m = 0; square[i][j].k = 0; }

程序段A 程序段B 程序段C

假设cache的数据区大小为512B，采用直接映射，块大小为32B，存储器按字节编址，sizeof(int)=4。编译时变量i和j分配在寄存器中，数组square按行优先方式存放在000008C0H开始的连续区域中，主存地址为32位。要求： （1） 对三个程序段A、B、C中数组访问的时间局部性和空间局部性进行分析比较。 （2） 画出主存中的数组元素和cache中行的对应关系图。 （3） 计算三个程序段A、B、C中的写操作次数、写不命中次数和写缺失率。 参考答案：

（1）对于时间局部性来说：

程序段A、B和C中，都是每个数组元素只被访问一次，所以都没有时间局部性； 对于空间局部性来说：

程序段A访问顺序和存放顺序一致，所以，空间局部性好； 程序段B访问顺序和存放顺序不一致，所以，空间局部性不好；

程序段C虽然访问顺序和存放顺序一致，但同一个主存块有两次访问，所以空间局部性不好； （2）cache的行数为512B/32B=16；数组首地址为0000 0C80H，因为0000 0C80H正好是主存第

1100100B（100）块的起始地址。所以数组从主存第100块开始存放，一个数组元素占4×4B=16B，所以每2个数组元素占用一个主存块。8×8的数组共占用32个主存块，正好是cache数据区大小的2倍。

主存中的数组元素与cache行的映射关系图如下：

Cache行号 0# 1# 2# 3# 4# 5#

Square[3][4]/ [3][5] 15#

Square[3][6]/ [3][7] Square[4][0]/ [4][1] Square[0][0]/ [0][1] Square[0][2]/ [0][3] Square[0][4]/ [0][5] Square[0][6]/ [0][7] Square[1][0]/ [1][1] 主存块号 100# 101# 102# 103#

114# 115# 116#

Square[7][0]/ [7][1] Square[7][2]/ [7][3] Square[7][4]/ [7][5] Square[7][6]/ [7][7] 128# 129# 130# 131#

（3）对于程序段A：

每两个数组元素（共涉及8次写操作）装入到一个cache行中，总是第一次访问时未命中，后面7次都命中，所以，总的写操作次数为64 × 4 = 256次，写不命中次数为256×1/8 = 32次，因而写缺失率为12.5%。 对于程序段B：

每两个数组元素（共涉及8次写操作）装入到一个cache行中，但总是只有一个数组元素（涉及4次写操作）在被淘汰之前被访问，并且总是第一次不命中，后面3次命中。即写不命中次数为256×1/4 = 64次，因而写缺失率为25%。 对于程序段C：

第一个循环共64次访问，每次装入两个数组元素，第一次不命中，第二次命中；第二个循环，共访问64×3次，每两个数组元素（共涉及6次写操作）装入到一个cache行中，并且总是第一次不命中，后面5次命中。所以总的写不命中次数为32+(3×64)×1/6 = 64次，因而总缺失率为25%。

17. 假设某计算机的主存地址空间大小为64MB，采用字节编址方式。其cache数据区容量为4KB，采用4

路组相联映射方式、LRU替换和回写（write back）策略，块大小为64B。请问：

（1）主存地址字段如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。 （2）该cache的总容量有多少位？ （3）若cache初始为空，CPU依次从0号地址单元顺序访问到4344号单元，重复按此序列共访问16次。

若cache命中时间为1个时钟周期，缺失损失为10个时钟周期，则CPU访存的平均时间为多少时钟周期？ 参考答案：

（1）cache的划分为：4KB=212B=24组×22行/组×26字节/行，所以，cache组号（组索引）占4位。

主存地址划分为三个字段：高16位为标志字段、中间4位为组号、最低6位为块内地址。 即主存空间划分为：64MB=226B=216组群×24块/组群×26字节/块

（2）cache共有64行，每行中有16位标志、1位有效位、1位修改(dirty)位、2位LRU位，以及数

据64B。故总容量为64×(16+1+1+2+64×8)=34048位。 （3）因为每块为64B，CPU访问的单元范围为0～4344，共4345个单元，4345/64=67.89，所以CPU

访问的是主存前68块（第0～67块），也即CPU的访问过程是对前68块连续访问16次，总访存次数为16×4345=69520。

16次

0 0#

cache共有16组，每组4行，采用LRU算法的替换情况如下图所示： 1 63 64 1#

65 128 2#

4288 67#

4344 4352 68#

根据图中所示可知，第一次循环的每一块只有第一次未命中，其余都命中；以后15次循环中，有20块的第一字未命中，其余都命中。所以命中率p为(69520–68–15×20)/69520=99.47%

平均访存时间为：Hit Time + (1–p) × Miss Penalty

=1+10×(1–p)=1+0.0053×10= 1.053个时钟周期

18. 假定某处理器可通过软件对高速缓存设置不同的写策略，那么，在下列两种情况下，应分别设置成什

么写策略？为什么？

（1）处理器主要运行包含大量存储器写操作的数据访问密集型应用。

（2）处理器运行程序的性质与（1）相同，但安全性要求高，不允许有任何数据不一致的情况发生。 参考答案：

（1）采用write back策略较好，可减少访存次数。

（2）采用write through策略较好，能保证数据的一致性。

19. 已知cache1采用直接映射方式，共16行，块大小为1个字，缺失损失为8个时钟周期；cache2也采用直

接映射方式，共4行，块大小为4个字，缺失损失为11个时钟周期。假定开始时cache为空，采用字编址方式。要求找出一个访问地址序列，使得cache2具有更低的缺失率，但总的缺失损失反而比cache1大。

参考答案：

假设cache1和cache2的缺失次数分别为x和y，根据题意，x和y必须满足以下条件： 11×y > 8×x 且 x > y，显然，满足该条件的x和y有许多，例如，x=4，y=3、x=5，y=4等等。 对于以下的访问地址序列：0，1，4，8，cache1缺失4次，而cache2缺失3次；

对于以下的访问地址序列：0，2，4，8，12，cache1缺失5次，而cache2缺失4次；

对于以下的访问地址序列：0，3，4，8，12，16，20，cache1缺失7次，而cache2缺失6次； 如此等等，可以找出很多。

20. 提高关联度通常会降低缺失率，但并不总是这样。请给出一个地址访问序列，使得采用LRU替换算

法的2-路组相联映射cache比具有同样大小的直接映射cache的缺失率更高。 参考答案：

2-路组相联cache的组数是直接映射cache的行数的一半，所以，可以找到一个地址序列A、B、C，使得：A映射到某一个cache行，B和C同时映射到另一个cache行，并且A、B、C映射到同一个cache组。这样，如果访存的地址序列为A、B、C、A、B、C、A、B、C …，则对于直接映射cache，其命中情况为：miss/miss/miss /hit/miss/miss /hit/miss/miss/… 命中率可达33.3%。

对于组相联cache，因为A、B、C映射到同一个组，每组只有2行，采用LRU替换算法，所以，每个地址处的数据刚调出cache就又被访问到，每次都是miss，命中率为0。 例如：假定直接映射cache为4行×1字/行，同样大小的2-路组相联cache为2组×2行/组×1字/行 当访问序列为：0、2、4、0、2、4、0、2、4、 …（局部块大小为3）时，则出现上述情况。

当访问的局部块大于组的大小时，可能会发生“颠簸”现象：刚被替换出去的数据又被访问，导致缺失率为100%！

21. 假定有三个处理器，分别带有以下不同的cache：

cache1：采用直接映射方式，块大小为1个字，指令和数据的缺失率分别为4%和6%； cache2：采用直接映射方式，块大小为4个字，指令和数据的缺失率分别为2%和4%；

cache3：采用2-路组相联映射方式，块大小为4个字，指令和数据的缺失率分别为2%和3%。

在这些处理器上运行相同的程序，该程序的CPI为2.0，其中有一半是访存指令。若缺失损失为（块大小+6）个时钟周期，处理器1和处理器2的时钟周期都为420ps，带有cache3的处理器3的时钟周期为450ps。请问：哪个处理器因cache缺失而引起的额外开销最大？哪个处理器执行速度最快？ 参考答案：

假设所运行的程序共执行N条指令，每条访存指令仅读写一次内存数据，则在该程序执行过程中各处理器因cache缺失而引起的额外开销和执行时间计算如下。 对于处理器1： 额外开销为：N×(4%+6%×50%)×(1+6)=0.49 N个时钟周期 执行程序所需时间为：(N×2.0+0.49N)×420ps=1045.8N ps 对于处理器2： 额外开销为：N×(2%+4%×50%)×(4+6)=0.40N个时钟周期 执行程序所需时间为：(N×2.0+0.40N)×420ps=1008N ps 对于处理器3： 额外开销为：N×(2%+3%×50%)×(4+6)=0.35N个时钟周期 执行程序所需时间为：(N×2.0+0.35N)×450ps=1057.5N ps

由此可见，处理器1的cache缺失引起的额外开销最大，处理器2的执行速度最快。

22. 假定某处理器带有一个数据区容量为256B的cache，其块大小为32B。以下C语言程序段运行在该处理

器上，sizeof(int)=4，编译器将变量i, j, c, s都分配在通用寄存器中，因此，只要考虑数组元素的访存情况。若cache采用直接映射方式，则当s=64和s=63时，缺失率分别为多少？若cache采用2-路组相联映射方式，则当s=64和s=63时，缺失率又分别为多少？ int i, j, c, s, a[128];