发布时间 : 星期三 文章(新)计算机体系结构第五章练习题参考解答更新完毕开始阅读ec319c0d162ded630b1c59eef8c75fbfc67d948d
所谓的光辉岁月，并不是以后，闪耀的日子，而是无人问津时，你对梦想的偏执。
第 五 章
5.34 在一个采用组相联映象方式的Cache存储系统中，主存由B0～B7共8块组成，Cache有2组，每组2块，每块大小为16B。在一个程序执行过程中，访存的主存块地址流为：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。
(1)写出主存地址的格式，并标出各字段的长度。 (2)写出Cache地址的格式，并标出各字段的长度。 (3)指出主存与Cache之间各个块的映象关系。
(4)若Cache的4个块号为C0、C1、C2和C3，列出程序执行过程中的Cache块地址流。 (5)若采用FIFO替换算法，计算Cache的块命中率。 (6)若采用LRU替换算法，计算Cache的块命中率。 (7)若改为全相联映象方式，再做(5)和(6)。
(8)若在程序执行过程中，每从主存装入一块到Cache，平均要对这个块访问16次，计算在这种情况下的Cache命中率。
解：（1）（2）采用组相联映象时，主存和Cache地址的格式分别为：
区号E 区内组号G 主存组内块号B 块内地址W 组号g 组内块号b 块内地址w 主存按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
主存块地址流： B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 Cache块地址流： C2 C3 C0 C1 C0 C2 C2 C0 C0 C0 C3 C2
（5）组内替换算法采用FIFO时，Cache块0～3的使用过程如下表所示。
时间： 1 2 3 4 5 6 7 8 9 10 11 12
主存块地址流： B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 Cache块0 4 4* 4* 4* 4* 0 0* 5 5 5 Cache块1 1 1 1 1 1* 4 4* 4* 4* Cache块2 6 6* 6* 6* 6* 6* 3 3 3 3 3* 3* Cache块3 2 2 2 2 2 2* 2* 2* 2* 7 7 命中 命中 命中
可见命中三次，Cache块命中率为Hi = 3/12 = 0.25。
（6）组内替换算法采用LRU时，Cache块0～3的使用过程如下表所示。
同是寒窗苦读，怎愿甘拜下风！
1
所谓的光辉岁月，并不是以后，闪耀的日子，而是无人问津时，你对梦想的偏执。
时间： 1 2 3 4 5 6 7 8 9 10 11 12
主存块地址流： B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 Cache块0 Cache块1 Cache块2 Cache块3
6 4 4* 4 1 1* 6* 6* 2 2 4 1* 6 2* 4 1* 6* 3 4* 0 6* 3 4 0* 6* 3 4* 5 6* 3 4* 4* 5 7 5 7 6* 6* 2 2 3* 3* 命中 命中 命中 命中
可见命中四次，Cache块命中率为Hi = 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
主存块地址流： B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 Cache块0
Cache块1 Cache块2 Cache块3
6 6 2 6 2 4 6* 6* 2 4 1 2 4 1 6* 2 4 1 3 2* 4 1 3 0 4* 1 3 0 4* 1 3 0 5 1* 3* 3* 0 5 7 0 5 7 命中 命中 命中 命中
可见命中四次，Cache块命中率为Hi = 4/12 = 0.33。
当替换算法采用LRU时，Cache块0～3的使用过程如下表所示。
时间： 1 2 3 4 5 6 7 8 9 10 11 12
主存块地址流： B6 B2 B4 B1 B4 B6 B3 B0 B4 B5 B7 B3 Cache块0
Cache块1 Cache块2 Cache块3
6 6 2 6 2 4 6* 6* 2 4 1 2 4 1 6 2* 4 1 6 3 4 1* 6 3 4* 0 6* 3 4 0 5 3* 4 0 5 7 4 5 7 4* 0* 3 命中 命中 命中
可见命中三次，Cache块命中率为Hi = 3/12 = 0.25。 （8）当命中三次时，Cache的命中率为Hi = （12×16-9）/（12×16）≈1，当命中四次时，Cache的命中率为Hi = （12×16-8）/（12×16）≈1。
5.35 在某采用全相联映象、相联目录表实现地址变换Cache存储器中，Cache的容
量是2cB，主存是由m个存储体组成的低位交叉访问存储器，主存总容量是2MB，每一个存储体的字长是w位，。
(1)画出地址变换图。
(2)写出主存地址和Cache地址的格式，并标出各字段的长度。 (3)说明目录表的行数、相联比较的位数和目录表的宽度。
同是寒窗苦读，怎愿甘拜下风！
2
所谓的光辉岁月，并不是以后，闪耀的日子，而是无人问津时，你对梦想的偏执。
解：（1）地址变换图见P243的图5-20。
（2）采用全相联映象时，主存和Cache地址的格式分别为：
主存块号B 块内地址W M
c
组内块号b 块内地址w 主存和Cache单元数分别为：8×2/w、8×2/w，相应的地址长度分别为：
log2（8×2M/w）=M+3-log2w、log2（2c/w）=C+3-log2w。 块的大小为m个存储字，则主存和Cache的块内地址长度均为：log2m，所以主存和Cache的块号长度分别为：（M+3-log2w）-log2m = M+3-log2wm、（C+3-log2w）-log2m = C+3-log2wm。 （3）相联目录表的行数为Cache的块数，即Cb=2（C+3-log2wm）=2C+3/wm；相联比较的位数为主存块号长度，即M+3-log2wm；目录表的宽度（位数）为主存块号长度、Cache块号长度和有效位的和，即M+3-log2wm + C+3-log2wm +1= M+C+6-2 log2wm +1（有效位一位）。
5.38 一个采用组相联映像方式的Cache共有8块，分为两组，用硬件比较对法实现LRU块替换算法。
（1）共需要多少个触发器和多少个与门? （2）画出其中一组的逻辑图。
解：（1）设组内块数为p，则触发器的个数为：Cp2=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，比较对触发器的TAB=1表示A比B更近被访问过，TAB=0表示B比A更近被访问过，TAC 、TAD、TBC 、TBD和TCD 也类似定义。 D最久未被访过的块的逻辑关系为：DLRU = TAD ﹒TBD ﹒TCD C最久未被访过的块的逻辑关系为：CLRU = TAC ﹒TBC ﹒TCD B最久未被访过的块的逻辑关系为：BLRU = TAB ﹒TBC ﹒TBD A最久未被访过的块的逻辑关系为：ALRU = TAB ﹒TAC ﹒TAD
B A & & 0 1 0 1 0 1 0 1 T R S T R S T R S T R S 访问A 访问B 访问C 访问D
LRULRUABACADBCCLRU & DLRU & TBD 0 1 R S TCD 0 1 R S 5.40 有一个16KB 4路组相联Cache的32位微处理器，假定该Cache的块为4个32位的字。
同是寒窗苦读，怎愿甘拜下风！
3
所谓的光辉岁月，并不是以后，闪耀的日子，而是无人问津时，你对梦想的偏执。
（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。
主存地址为ABCDE8F816的单元，其二进制地址为：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 = TC/（H×TC ＋ (1-H)Tm），由题意可知：TC=10ns，Tm=60ns，e=0.5，H为命中率，则有H = 0.8。而等效访问周期Te= H×TC ＋ (1-H)Tm = 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。
同是寒窗苦读，怎愿甘拜下风！ 4