第五章存储层次
知识点汇总
存储器层次结构、存储层次性能参数(平均每位价格、命中率、平均访存时间)、存储层次4个问题、CPU 访存地址分割、全相联映像、直接映像、组相联映像、查找方法、替换算法(随机、先进先出、最近最少使用法)、写直达法、写回法、按写分配、不按写分配、Cache性能分析、3C失效(强制失效、容量失效、冲突失效)、Victim Cache、伪相联映像Cache、硬件预取、编译器优化(数组合并、外循环交换、循环融合、分块)、写缓冲合并、单字宽存储器、多字宽存储器、多体交叉存储器、存储体、虚拟存储器(页式、段式)、快表(TLB)
简答题
1.单级存储器的主要矛盾是什么?通常采取什么方法来解决?(知识点:多级存储器)
答:主要矛盾:
(1) 速度越快,每位价格就越高。
(2) 容量越大,每位价格就越低。
(3) 容量越大,速度越慢。
采取多级存储层次方法来解决。
2.“Cache-主存”和“主存-辅存”层次的主要区别是什么?(知识点:存储层次)
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)假设该程序加载到存的地址上,给出该循环退出前每个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组0块 对应主存区号标识为 001 100 0组1块 对应主存区号标识为 001 010 1组0块
对应主存区号标识为 001 010
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 块号
(2)循环20次地址分别为0,1,2,3,4,0,1,2,3,4,0,1,2,……
命中率=(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)不命中,整块调入
f CPUR=5%×75%×4×1=0.15MBps
CPU写时,(1)命中,写直达,访存
f CPUW1=95%×25%×1×1=0.2375MBps
(2)不命中,不按写分配,访存
f CPUW2=5%×25%×1×1=0.0125MBps
f CPU=f CPUR+f CPUW1+f CPUW2=0.4MBps
所以,主存频带使用率为f CPU/f MEM 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 两路组相联的平均访问时间比较低
CPU time =(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
相对性能比:
=--1way
time 2way time CPU CPU 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 两路组相联的平均访问时间比较低
CPU time =(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)C PU发出访存请求的速率为109字/s;
(4)25%的访存为写访问;
(5)存储器的最大流量为109字/s(包括读和写);
(6)主存每次只能读或写一个字;
(7)在任何时候,Cache中有30%的块被修改过;
(8)写失效时,Cache采用按写分配法。
现欲给该计算机增添一台外设,为此首先想知道主存的频带已用了多少。试对于以下两种情况计算主存频带的平均使用比例。
(1)写直达Cache;
(2)写回法Cache。
(知识点:直接映像、组相联映像、平均访存时间、CPU性能)
答:采用按写分配
(1)写直达cache访问命中,有两种情况:
读命中,不访问主存;
写命中,更新cache和主存,访问主存一次。
访问失效,有两种情况:
读失效,将主存中的块调入cache中,访问主存两次;
写失效,将要写的块调入cache,访问主存两次,再将修改的数据写入cache和主存,访问
一次访存请求最后真正的平均访存次数=(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块中,访问主存两次;
如果被替换的块修改过,则首先将修改的块写入主存,需要访问主存两次;然后将主存中的块调
所以:
一次访存请求最后真正的平均访存次数=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 访存地址分割、全相联映像、直接映像、组相联映像)