计算机组成习题答案(清华大学出版社) 下载本文

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];