计算机体系结构第五章练习题参考解答
。第五章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)0123Cache 块地址流。若 Cache的 4 个块号为 C、C、C和 C ，列出程序执行过程中的(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）根据组相联映象的规则，主存块 07 与 Cache块 0 3 之间的映象关系为：主存块0、 1、 4、 5 与 Cache块 0、1 之间全相联，主存块2、3、6、7 与 Cache 块 2、3 之间全相联。（ 4）根据组相联映象的规则， 该主存块地址流相应的一种 Cache块地址流如下表所示（组内替换算法为 FIFO）。时间： 123456789101112主存块地址流： B 6B 2B4B 1B4B 6B3B 0B4B5BCache块地址流： C 2C 3C0C 1C0C 2C2C 0C0C0C（ 5）组内替换算法采用FIFO 时， Cache块 03 的使用过程如下表所示。时间：12345678910 1112主存块地址流：B 6B 2B4B1B 4B6 B3 B0B4B 5B 7B3Cache 块 044*4*4*4*00*555Cache 块 111111*44*4*4*Cache 块 266*6*6*6*6*33333*3*Cache 块 3222222*2*2*2*7773BC32命中命中命中可见命中三次， Cache 块命中率为 Hi = 3/12 = 0.25。（ 6）组内替换算法采用LRU时， Cache块 0 3 的使用过程如下表所示。-可编辑修改 -。时间：12345678910 11 12主存块地址流：B 6B2B 4B 1B 4B 6B 3B 0B 4B 5B 7B 3Cache 块 044*4444*44*4*4*Cache 块 111*1*1*00*555Cache 块 266*6*6*6*66*6*6*6*77Cache 块 322222*33333*3*命中命中命中命中可见命中四次， Cache 块命中率为 Hi= 4/12 = 0.33。（ 7）全相联映象的规则是主存块0 7 可装入 Cache块 03 的任一块上。当替换算法采用 FIFO 时， Cache块 0 3 的使用过程如下表所示 。时间：12345678910 1112主存块地址流：B 6B2B 4B1B 4 B6B 3B 0B4B5B 7B3Cache块 06666*6*6*33333*3*Cache 块 1222222*00000Cache 块 2444444*4*555Cache 块 31111111*77命中命中命中命中可见命中四次， Cache 块命中率为 Hi= 4/12 = 0.33。当替换算法采用 LRU时， Cache块 03 的使用过程如下表所示。时间：12345678910 1112主存块地址流：B 6B2B 4B1B 4 B6B 3B 0B4B5B 7B3Cache块 06666*6*6666*555Cache 块 122222*3333*77Cache 块 2444444*4444*Cache 块 31111*0000*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 的容量是 2c B，主存是由 m个存储体组成的低位交叉访问存储器，主存总容量是2MB，每一个存储体的字长是 w位，。(1) 画出地址变换图。(2) 写出主存地址和 Cache地址的格式，并标出各字段的长度。(3) 说明目录表的行数、相联比较的位数和目录表的宽度。-可编辑修改 -。解：（ 1）地址变换图见P243 的图 5-20 。（2）采用全相联映象时，主存和Cache地址的格式分别为：主存块号 B块内地址 W组内块号 b块内地址 w主存和 Cache单元数分别为： 8×2M/w、 8× 2c/w ，相应的地址长度分别为：2M22c2w。log （8×2 /w ）=M+3-log w、log（2 /w） =C+3-log块的大小为 m个存储字，则主存和 Cache的块内地址长度均为： log 2 m，所以主存和 Cache2222w）-log22wm。的块号长度分别为：（M+3-log w）-logm = M+3-log wm、（ C+3-logm = C+3-log（ C+3-log2wm）C+3（ 3）相联目录表的行数为 Cache的块数，即b=2 /wm；相联比较的位数为主C=2存块号长度，即 M+3-log 2wm；目录表的宽度（位数）为主存块号长度、Cache 块号长度和有效位的和，即 M+3-log2wm + C+3-log 2wm +1= M+C+6-2 log2wm +1（有效位一位）。5.38 一个采用组相联映像方式的Cache 共有 8 块，分为两组，用硬件比较对法实现 LRU块替换算法。（ 1）共需要多少个触发器和多少个与门 ?（ 2）画出其中一组的逻辑图。2解：（ 1）设组内块数为 p，则触发器的个数为： Cp =p（p-1 ）/2 。Cache有 8 块分为二组，与门的个数为组内块数为p=4，与门输入端数为p-1=3 。（ 2）有效比较对有： AB、AC、AD、BC、BD和 CD，比较对触发器的 TAB=1 表示 A 比 B 更近被访问过， TAB=0 表示 B 比 A 更近被访问过， TAC 、TAD、TBC 、TB
