(新)计算机体系结构第五章练习题参考解答

第 五 章

5.34 在一个采用组相联映象方式的Cache 存储系统中，主存由B 0～B 7共8块组成，Cache 有2组，每组2块，每块大小为16B 。在一个程序执行过程中，访存的主存块地址流为：B 6，B 2，B 4，B 1，B 4，B 6，B 3，B 0，B 4，B 5，B 7，B 3。

(1)写出主存地址的格式，并标出各字段的长度。 (2)写出Cache 地址的格式，并标出各字段的长度。 (3)指出主存与Cache 之间各个块的映象关系。

(4)若Cache 的4个块号为C 0、C 1、C 2和C 3，列出程序执行过程中的Cache 块地址流。 (5)若采用FIFO 替换算法，计算Cache 的块命中率。 (6)若采用LRU 替换算法，计算Cache 的块命中率。 (7)若改为全相联映象方式，再做(5)和(6)。

(8)若在程序执行过程中，每从主存装入一块到Cache ，平均要对这个块访问16次，计算在这种情况下的Cache 命中率。

解：（1）（2）采用组相联映象时，主存和Cache 地址的格式分别为：

主存按Cache 的大小分区，现主存有8个块，Cache 有2×2=4个块，则主存分为8/4=2

个区，区号E 的长度为1位。又每区有2个组，则组号G 、g 的长度都为1位。而每组有2个块，则块号B 、b 的长度又都为1位。每块大小为16个存储字，故块内地址W 、w 的长度都为4位。

（3）根据组相联映象的规则，主存块0～7与Cache 块0～3之间的映象关系为：主存块0、1、4、5与Cache 块0、1之间全相联，主存块2、3、6、7与Cache 块2、3之间全相联。 （4）根据组相联映象的规则，该主存块地址流相应的一种Cache 块地址流如下表所示（组内替换算法为FIFO ）。

时间： 1 2 3 4 5 6 7 8 9 10 11 12

主存块地址流： B 6 B 2 B 4 B 1 B 4 B 6 B 3 B 0 B 4 B 5 B 7 B 3 Cache 块地址流： C 2 C 3 C 0 C 1 C 0 C 2 C 2 C 0 C 0 C 0 C 3 C 2

（5）组内替换算法采用FIFO 时，Cache 块0～3的使用过程如下表所示。

时间： 1 2 3 4 5 6 7 8 9 10 11 12

主存块地址流： B 6 B 2 B 4 B 1 B 4 B 6 B 3 B 0 B 4 B 5 B 7 B 3 Cache 块0 Cache 块1 Cache 块2 Cache 块3

命中 命中 命中

可见命中三次，Cache 块命中率为H i = 3/12 = 0.25。

（6）组内替换算法采用LRU 时，Cache 块0～3的使用过程如下表所示。

时间： 1 2 3 4 5 6 7 8 9 10 11 12

主存块地址流： B 6 B 2 B 4 B 1 B 4 B 6 B 3 B 0 B 4 B 5 B 7 B 3 Cache 块0 Cache 块1 Cache 块2 Cache 块3

命中 命中 命中 命中

可见命中四次，Cache 块命中率为H i = 4/12 = 0.33。

（7）全相联映象的规则是主存块0～7可装入Cache 块0～3的任一块上。 当替换算法采用FIFO 时，Cache 块0～3的使用过程如下表所示。

时间： 1 2 3 4 5 6 7 8 9 10 11 12

主存块地址流： B 6 B 2 B 4 B 1 B 4 B 6 B 3 B 0 B 4 B 5 B 7 B 3 Cache 块0

Cache 块1 Cache 块2 Cache 块3

命中 命中 命中 命中

可见命中四次，Cache 块命中率为H i = 4/12 = 0.33。

当替换算法采用LRU 时，Cache 块0～3的使用过程如下表所示。

时间： 1 2 3 4 5 6 7 8 9 10 11 12

主存块地址流： B 6 B 2 B 4 B 1 B 4 B 6 B 3 B 0 B 4 B 5 B 7 B 3 Cache 块0

Cache 块1 Cache 块2 Cache 块3

命中 命中 命中

可见命中三次，Cache 块命中率为H i = 3/12 = 0.25。 （8）当命中三次时，Cache 的命中率为H i = （12×16-9）/（12×16）≈1，当命中四次时，Cache 的命中率为H i = （12×16-8）/（12×16）≈1。

5.35 在某采用全相联映象、相联目录表实现地址变换Cache 存储器中，Cache 的容

量是2c B ，主存是由m 个存储体组成的低位交叉访问存储器，主存总容量是2M B ，每一个存储体的字长是w 位，。

(1)画出地址变换图。

(2)写出主存地址和Cache 地址的格式，并标出各字段的长度。 (3)说明目录表的行数、相联比较的位数和目录表的宽度。

解：（1）地址变换图见P243的图5-20。

（2）采用全相联映象时，主存和Cache 地址的格式分别为：

主存和Cache 单元数分别为：8×2M

/w 、8×2c

/w ，相应的地址长度分别为：

log 2（8×2M /w ）=M+3-log 2w 、log 2（2c /w ）=C+3-log 2w 。 块的大小为m 个存储字，则主存和Cache 的块内地址长度均为：log 2m ，所以主存和Cache 的块号长度分别为：（M+3-log 2w ）-log 2m = M+3-log 2wm 、（C+3-log 2w ）-log 2m = C+3-log 2wm 。 （3）相联目录表的行数为Cache 的块数，即C b =2（C+3-log2wm ）=2C+3/wm ；相联比较的位数为主存块号长度，即M+3-log 2wm ；目录表的宽度（位数）为主存块号长度、Cache 块号长度和有效位的和，即M+3-log 2wm + C+3-log 2wm +1= M+C+6-2 log 2wm +1（有效位一位）。

5.38 一个采用组相联映像方式的Cache 共有8块，分为两组，用硬件比较对法实现LRU 块替换算法。

（1）共需要多少个触发器和多少个与门? （2）画出其中一组的逻辑图。

解：（1）设组内块数为p ，则触发器的个数为：C p 2=p （p-1）/2。Cache 有8块分为二组，每组4个块，则每组需要触发器的个数为：4（4-1）/2=6，所以共需要触发器为6×2=12。 与门的个数为组内块数为p=4，与门输入端数为p-1=3。

（2）有效比较对有：AB 、AC 、AD 、BC 、BD 和CD ，比较对触发器的T AB =1表示A 比B 更近被访问过，T AB =0表示B 比A 更近被访问过，T AC 、T AD 、T BC 、T BD 和T CD 也类似定义。 D 最久未被访过的块的逻辑关系为：D LRU = T AD ﹒T BD ﹒T CD C 最久未被访过的块的逻辑关系为：C LRU = T AC ﹒T BC ﹒T CD B 最久未被访过的块的逻辑关系为：B LRU = T AB ﹒T BC ﹒T BD A 最久未被访过的块的逻辑关系为：A LRU = T AB ﹒T AC ﹒T AD

5.40 有一个16KB 4路组相联Cache 的32位微处理器，假定该Cache 的块为4个32位的字。

访问访问访问访问

（1）画出该Cache的结构逻辑图，指出主存地址的不同字段的作用。

（2）主存地址为ABCDE8F8的单元在Cache中的什么位置。

解：（1）Cache的结构逻辑图见P248的图5-26。主存地址有区号、区内组号、组内块号和块内地址四个字段，区内组号是按地址访问映像关系表的地址，区号和组内块号是相联访问映像关系表的特征内容，块内地址是选择块内字的地址。

（2）在Cache存储系统中，主存与Cache的块大小是相同的，由题可知主存与Cache是字节编址的。则块内单元数为：4×32 / 8 = 16；由于24 = 16，则块内地址的位数4；4路组相联则组内块数为4，22= 4，组内块号的位数为2；区内组数为：16KB/4×4×4B（32位）= 256，28 = 256，则区内组号的位数为8。

主存地址为ABCDE8F8

16

的单元，其二进制地址为：1010 1011 1110 1101 1110 1000 1111 1000 (主存字节地址为32位)；16KB 的Cache二进制地址为14位，则主存地址中的高18位为区号：1010 1011 1110 1101 11；次高8位10 1000 11为组号，Cache的组号与主存区内组号不变；最低4位1000为块内地址，Cache的块内地址与主存块内地址也不变；次低2位11为组内块号，由于全相联，则Cache的组内块号可以是00或01或10或11。因此，主存地址为ABCDE8F8的单元在Cache中的位置为：10 1000 11 00或01或10或11 1000。

5.44 在一个Cache存储系统中，Cache的访问周期为10ns，主存储器的访问周期为60ns，每个数据在Cache中平均重复使用4次。当块的大小为1个字时，存储系统的访问效率只有0.5，现在要通过增加块大小，使存储系统的访问效率达到0.94.

（1）当存储系统的访问效率为0.5时，计算命中率和等效访问周期。

（2）为了使存储系统的访问效率达到0.94，命中率和等效访问周期应该提高到多少？

（3）为了使存储系统的访问效率从0.5提高到0.94，块的大小至少增加到几个字？

解：（1）e = T

C /（H×T

C

＋ (1-H)T

m

），由题意可知：T

C

=10ns，T

m

=60ns，e=0.5，H为命

中率，则有H = 0.8。而等效访问周期Te= H×T

C ＋ (1-H)T

m

= 20ns。

（2）同（1）有H = 0.9872、Te=17.552 ns。

（3）设块的大小为X，由题意可知一个块的访问次数为4X，访问效率达到0.94的命中率为0.9872，H=(4X-1)/4X，则X=19.53≈20，即块的大小至少增加到20个字。

5.57 假设在3000次访存中，第一级Cache不命中110次，第二级Cache不命中55次。试问：在这种情况下，该Cache系统的局部不命中率和全局不命中率各是多少？

解：局部不命中率 = 该级Cache的不命中次数/到达该级Cache的访存次数。

不命中率

L1 = 110/3000 = 0.0367，不命中率

L2

= 55/110 = 0.50。

全局不命中率

L1 =不命中率

L1

= 0.0367，

全局不命中率

L2 = 不命中率

L1

×不命中率

L2

= 0.0367×0.50 = 0.0184。