计算机系统结构：第5章 存储层次.docx

第五章 存储层次
知识点汇总
存储器层次结构、存储层次性能参数（平均每位价格、命中率、平均访存时间） 、存储层次4个问题、CPU访存地址分割、全相联映像、直接映像、组相联映像、查找方法、替换算法（随机、先进先出、最近最少使用法）、写直达法、写回法、按写分配、不按写分配、Cache性能分析、3C失效（强制失效、容量失效、冲突失效）、Victim Cache、伪相联映像Cache、硬件预取、编译器优化（数组合并、内外循环交换、循环融合、分块）、写缓冲合并、单字宽存储器、多字宽存储器、多体交叉存储器、存储体、虚拟存储器（页式、段式）、快表（TLB）
简答题
1. 单级存储器的主要矛盾是什么？通常采取什么方法来解决？（知识点：多级存储器）
答：主要矛盾：
(1) 速度越快，每位价格就越高。
(2) 容量越大，每位价格就越低。
(3) 容量越大，速度越慢。
采取多级存储层次方法来解决。

2. “Cache-主存”和“主存-辅存”层次的主要区别是什么？（知识点：存储层次）

存储层次
比较项目
“Cache-主存”层次
“主存-辅存”层次
目的
为了弥补主存速度的不足
为了弥补主存容量的不足
存储管理的实现
全部由专用硬件实现
主要由软件实现
访问速度的比值
（第一级比第二级）
几比一
几万比一
典型的块（页）大小
几十个字节
几百到几千个字节
CPU对第二级的访问方式
可直接访问
均通过第一级
不命中时CPU是否切换
不切换
切换到其他进程

3. 在存储层次中应解决哪四个问题？ （知识点：存储层次的四个问题）
答：（1）映像规则：当把一个块调入高一层存储器时，可以放到哪些位置上。
（2）查找算法：当所要访问的块在高一层存储器中时，如何找到该块。
（3）替换算法：当发生失效时，应替换哪一块。
（4）写策略：当进行写访问时，应进行哪些操作。

4. 地址映像方法有哪几种？它们各有什么优缺点？ （知识点：地址映像）
（1）全相联映像。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。
（2）直接映像。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。
（3）组相联映像。组相联是直接映像和全相联的一种折中。

5. Cache的3C失效是哪三种失效？针对每种失效给出一种降低失效率的方法。（知识点：3C失效）
答：强制性失效、容量失效、冲突失效。

6. 简述Cache的两种写策略（知识点：写直达、写回）
写直达法：执行“写”操作时，不仅写入Cache，而且也写入存储器
写回法：执行“写”操作时，只写入Cache，并将对应Dirty Flag位置1。
当任意一个Cache块将要被替换时，若Dirty Flag位为1，则先将该Cache块写回存储器，再进行替换动作；否则不用写回，直接替换。

7. 简述Cache写失效的两种处理方法（知识点：按写分配、不按写分配）
经过cache法(按写分配)：发生写失效时，先把地址对应的内存块调入Cache，再进行写操作。
绕过cache法(不按写分配)：发生写失效时，不把地址对应的内存块调入Cache，而是绕过cache直接将数据写入存储器

选择题
1． 虚拟存储器中，可采用如下映像规则：（ D ）（知识点：映像规则、虚拟存储器）
A． 直接映像；
B． 组相联映像；
C． 全相联映像；
D． 上述三者均可。

2． 衡量一个存储器性能可从( A )方面考虑。（知识点：存储器层次结构）
A． 容量、速度、价格
B． 制造工艺、封装、材料
C． 容量、速度、功耗
D． Cache-主存存储层次、主存-辅存存储层次、辅存-磁带存储层次

3． 当发生Cache写失效时，是否调入相应的块，有哪两种选择？（D ）（知识点：写直达法、写回法、按写分配、不按写分配）
A．按写分配法和写回法
B．按写分配法和写直达法
C．写回法和写直达法
D．按写分配法和不按写分配法

4． 虚拟存储器主要是为了解决（ A ）。（知识点：存储器层次结构、虚拟存储器）
A． 扩大存储系统的容量
B． 提高存储系统的速度
C． 扩大存储系统的容量和提高存储系统的速度
D． 便于程序的访存操作

5． 与全相联映像相比，组相联映像的优点是（ A ）。（知识点：全相联映像、组相联映像）
A． 目录表短，实现成本低
B． 块冲突概率低
C． Cache命中率高
D． 主存利用率高

6． Cache 存储器主要是为了解决（ B ）。（知识点：存储器层次结构）
A． 扩大存储系统的容量
B． 提高存储系统的速度
C． 扩大存储系统的容量和提高存储系统的速度
D． 便于程序的访存操作

7． 容量和块大小均相同的Cache，块冲突概率由高到低的顺序是（ B ）。（知识点：全相联映像、直接映像、组相联映像）
A． 全相联映像、直接映像、组相联映像
B． 直接映像、组相联映像、全相联映像
C． 全相联映像、组相联映像、直接映像
D． 组相联映像、直接映像、全相联映像

8． 容量和块大小均相同的Cache，主存地址中索引位的位数由少到多的顺序是（ C ）。（知识点：全相联映像、直接映像、组相联映像、CPU访存地址分割）
A． 全相联映像、直接映像、组相联映像
B． 组相联映像、直接映像、全相联映像
C． 全相联映像、组相联映像、直接映像
D． 直接映像、组相联映像、全相联映像

9． 以下（B）的值不能从CPU发出的主存地址中直接获得。（知识点：CPU访存地址分割）
A． 主存块地址
B． 主存物理页号
C． 用于选择Cache块/组的索引
D． 用于匹配Cache块的标识

填空题
1. 存储层次中的写策略主要有两种，它们是：（ 写直达 ）和（ 写回 ）。（知识点：写策略）
2. 在全相联映像、直接映像和组相联映像中，块冲突最小的是（ 全相联 ）。Cache存储器的地址映像规则一般不能用（ 全相联 ），否则，主存Cache的地址映像表太大，查表速度太慢，硬件难以实现。（知识点：全相联映像、直接映像、组相联映像）
3. 评价存储层次的主要参数有（存储层次的平均每位价格）、（ 命中率 ）和（ 平均访存时间 ）。（知识点：平均每位价格、命中率、平均访存时间）
4. Cache存储器采用的组相联映像是指组间是（ 全相联 ）映像， 组内各块之间是（ 直接 ）映像。（知识点：组相联映像）
5. “主存-辅存”层次的目的主要是为了弥补主存的（ 容量 ）的不足。（知识点：存储器层次结构）
计算题
1. 某机器主存为2KB，采用直接映像方式，指令cache容量为32B，每个块为16B。在该机器上执行如下循环程序：
FOO： LD F2, 0(R1)
MULTD F4, F2, F0
LD F6, 0(R2)
ADDD F6, F4, F6
SD 0(R2), F6
ADDI R1, R1, #8
ADDI R2, R2, #8
ADDI R3, R1, R2
BEQZ R3, FOO
每条指令长度均为4B，程序执行前，指令cache的内容为空。
（1）假设该程序加载到内存的00000100000地址上，给出该循环退出前每个cache块所对应的标识。
（2）如果该循环执行循环体10次，则指令cache的命中率为多少？
（知识点：Cache和主存映像，命中率）
答：Cache块数=32B/16B=2(块)
主存块数=2KB/16B=211B/24B=27=128(块)
Cache块

(1) 所以，循环退出前每个Cache块所对应标识如下：

(2) 块地址流为0，1，2，0，1，2，0……

所以，循环体执行10次，未命中次数为3＋9×2=21次，命中率=（90－21）／90×100%=76.67%

2. 某计算机主存为1KB，采用两路组相联（2-Way）映像，指令Cache容量为32B，每个块为8B。在该机执行如下循环程序：
OK:
LD
F2，0(R1)

MULTD
F4，F2，F0

LD
F6，0(R2)

ADDD
F6，F4，F6

SD
0(R2)，F6

ADDI
R1，R1，#8

ADDI
R2，R2，#8

SGTI
R3，R1，DONE

BEQZ
R3，OK
每条指令长度均为4B，程序执行前指令Cache的内容为空，Cache采用LRU替换算法。
（1）假设该程序加载道0010100000地址上，试给出该循环推出前每个Cache块所对应的主存区号标识，以及其组内块号；
（2）如果该循环执行20次，则Cache命中率为多少？
（知识点：Cache和主存映像，命中率）
答：（1）
0
1
0
1
0010100000
主存
Cache
I1
I2
I3
I4
I5
I6
I7
I8

I9
0组
1组
001010
001010
001011
001011
001100
0
1
0
1
0
主存区
号标示
Cache
块号

由映像图可见，退出循环前
0组0块
对应主存区号标识为 001 100
0组1块
对应主存区号标识为 001 010
1组0块
对应主存区号标识为 001 010
1组1块
对应主存区号标识为 001 011

（2）循环20次地址分别为0，1，2，3，4，0，1，2，3，4，0，1，2，……

0
1
2
3
4
0
1
2
3
4
0
1
…
0组
0
0
0
0
4
4
4
4
4
4
4
4
…

2
2
2
0
0
2
2
2
0
0
…
1组

1
1
1
1
1
1
1
1
1
1
1
…

3
3
3
3
3
3
3
3
3
…

装入
装入
装入
装入
替换
替换
命中
替换
命中
命中
替换
命中
…
命中率=(9´20-5-2´19)/(9´20)=137/180»76%

3. 假设某台计算机具有如下特性：（1）cache的命中率为95%；（2）cache块大小为4个字，cache失效时整块调入；（3）CPU发出访存请求的速率为1MBps；（4）25%的访存为写访存；（5）CPU每次只能读写一个字；（6）采用写直达cache，写失效时采用不按写分配；（7）主存可支持的最大访问流量为1MBps。问在此情况下主存频带的平均使用率为多少？（知识点：平均访存时间、写直达）

答： 分析，CPU每次只能读写1个字，说明数据字宽是1个字，也就是CPU每秒钟访存1M次。每次访存需要访问内存字数是5%*75%*4+95*25%*1+5%×25%×1

CPU读时，（1）命中，此时不访存
（2）不命中，整块调入
fCPUR=5%×75%×4×1=0.15MBps
CPU写时，（1）命中，写直达，访存
fCPUW1=95%×25%×1×1=0.2375MBps
（2）不命中，不按写分配，访存
fCPUW2=5%×25%×1×1=0.0125MBps
fCPU=fCPUR＋fCPUW1＋fCPUW2=0.4MBps
所以，主存频带使用率为fCPU／fMEM Max=0.4MBps／1MBps=0.4

4. 有三个Cache存储器，每个Cache均由4个块组成，每个块只有一个字。第一个Cache采用全相联映像，第二个Cache采用2-Way组相联映像，第三个Cache采用直接映像。程序执行过程中访问的块地址分别为：
0、8、0、6、8
（1）试计算三种结构的未命中次数；
（2）可得到什么样的结论？
（知识点：全相联映像、直接映像、组相联映像）
答：全相联映像缺页次数是：第1、2、4次，共缺失了3次。
2-Way组相联映像，由于0、6、8都映射在组号0，所以相当于一个2块的全相联映像Cache，缺失的次数是第1、2、4、5次，共缺失了4次。
对于直接映像来说，0、6、8对应映射到第0、2、0块，那么缺失的次数是第1、2、3、4、5次，共缺失了5次。

5. 给定以下的假设:
（1） 理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.1次；
（2） 直接映像和两路组相联映像Cache容量均为128KB，块大小都是32字节；
（3） 组相联映像Cache中的多路选择器使CPU的时钟周期增加了10％；
（4） 这两种Cache的失效开销都是80ns；
（5） 命中时间为1个时钟周期；
（6） 128KB直接映像Cache的失效率为0.010，128KB两路组相联映像Cache的失效率为 0.007。
试计算直接映像Cache和两路组相联映像Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？
（知识点：直接映像、组相联映像、平均访存时间、CPU性能）

答：平均访问时间＝命中时间＋失效率×失效开销
平均访问时间1-路=2.0+0.010*80=2.8ns
平均访问时间2-路=2.0*(1+10%)+0.007*80=2.76ns
两路组相联的平均访问时间比较低
CPUtime=（CPU执行+存储等待周期）*时钟周期
CPU time=IC（CPI执行+总失效次数/指令总数*失效开销） *时钟周期
=IC（（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期））
CPU time 1-way=IC(2.0*2+1.1*0.010*80)＝4.88IC
CPU time 2-way=IC(2.2*2+1.1*0.007*80)＝5.016IC
相对性能比：5.016/4.88=1.028
6. 给定以下的假设，
（1） 理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.5次；
（2） 两种Cache容量均为64KB；
（3） 这两种Cache的失效开销都是80ns；
（4） 命中时间为1个时钟周期；
（5） 64KB直接映象Cache的失效率为1.4％，64KB两路组相联Cache的失效率为1.0％。
（6） 组相联Cache中的多路选择器使CPU的时钟周期增加了10％；
问：（1）试比较直接映象Cache和两路组相联Cache的平均访问时间。(5分)
（2）试比较直接映象Cache和两路组相联Cache的CPU时间。(5分)
（知识点：直接映像、组相联映像、平均访存时间、CPU性能）

答：平均访问时间＝命中时间＋失效率×失效开销
平均访问时间1-路=2.0+1.4% *80=3.12ns
平均访问时间2-路=2.0*(1+10%)+1.0% *80=3.0ns
两路组相联的平均访问时间比较低

CPUtime=（CPU执行+存储等待周期）*时钟周期
CPU time=IC（CPI执行+总失效次数/指令总数*失效开销） *时钟周期
=IC（（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期））
CPU time 1-way=IC(2.0*2+1.5*0.014*80)＝5.68IC
CPU time 2-way=IC(2.2*2+1.5*0.01*80)＝5.60IC

7. 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，64KB的指令Cache的失效率为0.15%，64KB的数据Cache的失效率为3.77%，128KB的混合Cache的失效率为0.95%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为64KB的分离Cache和容量为128KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？
（知识点：直接映像、组相联映像、平均访存时间、CPU性能）

答：（1）根据题意，约75%的访存为取指令。
因此，分离Cache的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%；
容量为128KB的混合Cache的失效率略低一些，只有0.95%。
（2）平均访存时间公式可以分为指令访问和数据访问两部分：
平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间＋数据失效率×失效开销）
所以，两种结构的平均访存时间分别为：
分离Cache的平均访存时间＝75%×（1＋0.15%×50）＋25%×（1＋3.77%×50）
＝（75%×1.075）＋（25%×2.885）＝1.5275
混合Cache的平均访存时间＝75%×（1＋0.95%×50）＋25%×（1＋1＋0.95%×50）
＝（75%×1.475）＋（25%×2.475）＝1.725
因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。

8. 假设一台计算机具有以下特性：
（1） 95％的访存在Cache中命中；
（2） 块大小为两个字，且失效时整个块被调入；
（3） CPU发出访存请求的速率为109字/s；
（4） 25％的访存为写访问；
（5） 存储器的最大流量为109字/s（包括读和写）；
（6） 主存每次只能读或写一个字；
（7） 在任何时候，Cache中有30％的块被修改过；
（8） 写失效时，Cache采用按写分配法。
现欲给该计算机增添一台外设，为此首先想知道主存的频带已用了多少。试对于以下两种情况计算主存频带的平均使用比例。
（1） 写直达Cache；
（2） 写回法Cache。
（知识点：直接映像、组相联映像、平均访存时间、CPU性能）

答：采用按写分配
（1）写直达cache访问命中，有两种情况：
读命中，不访问主存；
写命中，更新cache和主存，访问主存一次。
访问失效，有两种情况：
读失效，将主存中的块调入cache中，访问主存两次；
写失效，将要写的块调入cache，访问主存两次，再将修改的数据写入cache和主存，访问主存一次，共三次。上述分析如下表所示。
访问命中
访问类型
频率
访存次数
Y
读
95%*75%=71.3%
0
Y
写
95%*25%=23.8%
1
N
读
5%*75%=3.8%
2
N
写
5%*25%=1.3%
3

一次访存请求最后真正的平均访存次数=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)＝0.35
已用带宽=0.35×109/10 9 =35.0%
（2）写回法cache访问命中,有两种情况：
读命中，不访问主存；
写命中，不访问主存。采用写回法，只有当修改的cache块被换出时，才写入主存；
访问失效,有一个块将被换出，这也有两种情况：
如果被替换的块没有修改过，将主存中的块调入cache块中，访问主存两次；
如果被替换的块修改过，则首先将修改的块写入主存，需要访问主存两次；然后将主存中的块调入cache块中，需要访问主存两次，共四次访问主存。
访问命中
块为脏
频率
访存次数
Y
N
95%*70%=66.5%
0
Y
Y
95%*30%=28.5%
0
N
N
5%*70%=3.5%
2
N
Y
5%*30%=1.5%
4
所以：
一次访存请求最后真正的平均访存次数=66.5％*0＋28.5%*0+3.5%*2+1.5%*4=0.13
已用带宽＝0.13×10 9/10 9＝13%

9. 假设当按直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）时，需要2个额外的周期，而且不交换两个Cache中的数据。Cache参数如下：
（1） 容量128KB。
（2） 直接映象情况下命中时间为1个时钟周期，失效开销为50个时钟周期。
（3） 直接映象失效率为0.010，两路组相联失效率为0.007。
问：伪相联映象这种组织结构，平均访存时间是多少？
答： ①
首先考虑标准的平均访存时间公式：
平均访存时间伪相联 ＝ 命中时间伪相联＋失效率伪相联×失效开销伪相联
不管我们对命中的情况做了何种改进，失效开销总是相同的。为了确定失效率，需要知道什么时候会发生失效。只要我们总是通过把索引的最高位变反的方法来寻找另一块，在同一“伪相联”组中的两块就是用同一个索引选择得到的，这与在两路组相联 Cache 中所用的方法是一样的，因而它们的失效率相同，即：失效率伪相联＝失效率2路
②
再看命中时间。伪相联 Cache 的命中时间等于直接映象 Cache 的命中时间加上在伪相联查找过程中命中（即伪命中）的百分比乘以该命中所需的额外时间开销，即：
命中时间伪相联＝命中时间1路＋伪命中率伪相联×2
伪相联查找的命中率等于2路组相联Cache的命中率和直接映象Cache命中率之差。
伪命中率伪相联 ＝命中率2路－命中率1路
＝（1－失效率2路）－（1－失效率1路）
＝失效率1路－失效率2路
③
平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×2
＋失效率2路×失效开销1路
平均访存时间伪相联，128 KB＝1＋（0.010－0.007）×2＋（0.007×50）＝1.356

（知识点：直接映像、组相联映像、平均访存时间、CPU性能、伪相联）

10. 在伪相联中，给定如下假设：
（1） 若在直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）时，不对这两个位置的数据进行交换。这时只需要1个额外的周期；
（2） 失效开销为50个时钟周期；
（3） 128KB直接映象Cache的失效率为1.0%，2路组相联的失效率为0.7%。
计算伪相联的平均访存时间。

答：
不管作了何种改进，失效开销相同。不管是否交换内容，在同一“伪相联”组中的两块都是用同一个索引得到的，因此失效率相同，即：失效率伪相联＝失效率2路。
伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。
命中时间伪相联＝命中时间1路＋伪命中率伪相联×1
交换或不交换内容，伪相联的命中率都是由于在第一次失效时，将地址取反，再在第二次查找带来的。
因此 伪命中率伪相联＝命中率2路－命中率1路＝（1－失效率2路）－（1－失效率1路）
＝失效率1路－失效率2路。交换内容需要增加伪相联的额外开销。
平均访存时间伪相联＝命中时间1路＋（失效率1路－失效率2路）×1
＋失效率2路×失效开销1路
将题设中的数据带入计算，得到：
平均访存时间128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353

（知识点：直接映像、组相联映像、平均访存时间、CPU性能、伪相联）

11. 设cache共有8块，每块大小为4B,主存共有64块，请给出直接映像、2路组相联映像、4路组相联映像和全相联映像时的访存地址格式：
标识
索引
块内位移

的具体形式并给出分析过程。

答：
3 3 2
标 识
索 引
块内位移
直接映像：

4 2 2
标 识
索 引
块内位移
2路组相联映像：

5 1 2
标 识
索 引
块内位移
4路组相联映像：

6 2
索 引
块内位移
全相联映像：

（知识点：CPU访存地址分割、全相联映像、直接映像、组相联映像）