这都十一篇读书笔记了。漫长啊。。还有好几章没看……

第四章 存储体系

4.3 高速缓冲存储器

4.3.2 地址的映像与变换

对Cache存储器而言:

地址的映像就是将每个主存块按某种规则装入Cache中。

地址的变换就是每次访问Cache时,主存地址如何变成Cache地址。

映像规则的选择除了看所用地址映像和变换硬件是否速度高,价格低,实现方便,块冲突概率是否低,Cache空间利用率是否高。

1.全相联映像和变换

主存中任意一块都可以映像装入到Cache中任意一块位置,为加快主存——Cache地址的变换,不宜采用类似虚拟存储器的页表来实现,一般采用目录表硬件方式来实现。

全相联映像的主存——Cache地址变换过程:

给出主存地址nm访存时,将其主存块号nmb与目录表中所有各项的nmb字段同时相联比较。有相同的,将对应的Cache块号ncb取出,拼接上块的地址nmr形成Cache地址nc,访Cache,无相同表示该主存块未调入Cache发生Cache块失效,由硬件调块。

全相联映像表法优点:块冲突概率最低,只有当Cache全满才可能出现块冲突,所以Cache空间利用率最高。但构成容量为2ncb项相联存储器,代价太大且容量大查表速度很难提高。

全相联映象规则

全相联映象规则

全相联映象的地址变换过程

全相联映象的地址变换过程

 

2.直接影响及其变换

把主存空间按Cache大小等分成区,每区内的各块只能按位置一一对应到Cache的相应块位置上,既主存的第i块只能唯一映像到第i mod 2ncb块位置上。

根据直接映像规则,装入Cache中某块位置的主存可以来自主存不同的去,为区分装入Cache的块来自那个主存区,使用一个按地址访问的表存储器存放Cache中每一块位置目前是被主存中哪个区的块所占用的区号,因此,表存储器为2ncb项,每项区号标志字段为字段,相当于可表示主存中个不同的区号。

直接映像的主存——Cache地址变换过程:

处理机给出主存地址nm,访主存时,截取与nm对应的部分作为Cache地址访问Cache,同时取ncb部分作为地址访问区号标识表存储器,读出原先所存区号与主存地址对应区号作比较,相等,表示Cache命中,让Cache访问继续进行并终止访问,不等于,表示Cache块失效,让Cache访问中止,主存访问继续,由硬件自动将主存中该块调入Cache。

优点:节省硬件,只需容量小的按地址访问的区号标志表存储器和少量外部电路,成本很低。

访问Cahce与访区号表,比较区号是否相等的操作时同时进行的,当Cahce命中时意味着省去了地址变换的时间。

缺点:块冲突率很高(致命),只要有两个及以上经常使用的块恰好被映像到Cache同一块位置时,Cache命中率将急剧下降,即使有大量的空闲块也无法使用,使空间利用率很低。

直接映象规则

直接映象规则

直接映象的地址变换过程

直接映象的地址变换过程

 

3.组相联映像及其变换

组相联映像指的是各组之间是直接映像,组内各块之间是全相联映像。

将Cache空间和主存空间分成组,每组为S块(S=2s),Cache共有个2ncb块。分成Q组(Q=2q)。整个Cache是一区,主存分成为与Cache同样大小的2ncb个区,其地址按区号、组号、组内块号、快内地址分成对应4个字段。

主存地址的组号,组内块号分别为qs'字段表示,它们的宽度和位置与Cache地址的qs是一致的。

组相联映像是介于全相联映像和直接映像访问的,Cache块冲突高铝比直接映像低得多。

只有当某租全满时才会出现冲突,显然组被占满的概率要小的多。

因此,大大降低了块冲突概率,大大提高了Cache空间的利用率,S越大,Cache块冲突概率越低。

S值大小等于Cache块数,S=ncb时,就是全相联映像。

S值小的只有1块(无S字段)就变成直接映像。

在Cache空间大小及块的大小都确定的情况下,Cache总块数就是确定的,但结构设计仍可对SQ值进行选择。

QS的选取主要依据于块冲突概率、块失效率,映像表复杂性和成本、查表速度等之间折中权衡。

组内块数S越多,冲突概率和失效率就越低,映像表越复杂,成本越高,查表速度越慢。

组相联成本比全相联成本低,性能接近全相联,得以广泛应用。

组相联的地址变换:

先由q2q组中选出一组,对该组再用nd+s'进行相联查找。如果在2s行中查找不到相符的,表示主存的该块不在Cache中,如果查到,有相符的,则将表中对对应的s拼接上qnmr就是Cache地址nc

组相联地址映像机构也可以采用按地址访问与按内容访问混合的存储器实现。其存储器总容量应为2ncb行。

办法1:使用单体多字并行存储器,先由q2q中选出一个单元,由该单元同时读出2s个字,分别通过S套外比较电路与主存地址的nd+s'同时比较。将其中相符的s取出,拼接上qnmr就是Cache地址nc

如果都不相符,表示该块不在Cache中,出现块失效,显然,这种方法的S值不能很大。

采用组相联并不是操作系统或存储层次的要求,只是在全相联的速度满足不了要求时才不得已而采用的,以便于实现。尽管会增大Cache冲突概率和降低Cache空间利用率。

组相联映象规则

组相联映象规则

组相联地址变换示意图

组相联地址变换示意图


段相联:

在全相联、直接、组相联基础上变形而来,实质上是组相联的特例,组间全相联、组内直接映像。

段相联映像是把主存和Cache分成具有相同的Z块的若干段,段与段之间采用全相联映像,而段内各块之间却采用直接映像。


段中的第i块可以映像装入

段中的第i块位置。

采用段相联的目的和组相联一样,主要是减小相联目录表的容量,降低成本,提高地址变换速度。

相联目录表由Z个目录表组成,每个目录表的行数由2ncb行减为2ncb/Z行,其块冲突概率比全相联高。

具有每段Z个块的段相联映像

具有每段Z个块的段相联映像

具有每段Z个块的段相联映象

具有每段Z个块的段相联映象


4.3.3 Cache存储器的LRU替换算法的硬件实现

当Cache块失效,将主存块装入Cache又出现Cache块冲突时,就必须按某种替换策略选择Cache中的一块替换出去,Cache存储器的替换算法与虚拟存储器的一样,使用FIFO算法或LRU算法。其中LRU算法最常用。

因Cache调块时间是微秒级,所以只能用硬件实现替换算法。

LRU算法的比较对法:

比较对法的设计思想:让组内各块成对组合,用一个触发器的状态表示该比较内两块访问的远近次序。再经门电路就可找到LRU块。

如有A、B、C 3块,组成AB、AC、BC 3对,各对内块的访问顺序分别用“对触发器”,就有TABTACTBC

TAB为1表示,A比B更近访问过。若TAB为0表示B比A更近访问过。

若C作为最久未被访问块的话,用布尔代数式必有:

同理可得

因此,安全可用与门、触发器等硬件组合实现。

由于每个块均可能作为LRU块,其信号需要与门产生,所以有多少块,就的有多少与门。每个与门接受来自与它有关的比较对触发器的输入。

触发器的个数会随着块数的增多以极快的速度增加,门的输入端数也线性增加。这在工程实现上会带来麻烦。所以比较对法只适用于组内块数较少的组相联映像Cache存储器中。

块数较少的时候容易实现,组内块数超过8个所需的触发器个数就超多了,不过这时可以用多级状态位技术来减少所用的比较对触发器个数。

用比较对法实现LRU算法

用比较对法实现LRU算法


4.3.4 Cache储存器的透明性及性能分析

1.Cache存储器的透明性和性能分析

Cache是主存的一部分副本,主存中某单元的内容可能在一段时间里会与Cahce中对应单元的内容不一致。

解决这个问题的关键是选择好更新主存内容的算法。

写回法与写直达法。

写回法也称为抵触修改法,它是在CPU执行写操作时,信息只写入Cache后是否被修改过的标志,只要修改过,就将该标志位置“1”,这样在快替换时,根据该块的修改为是否“1”,就可以决定替换时是否需要先将该块存回主存。

写直达法也称存直达法,利用Cache存储器在处理机和主存之间的直接通路,当处理机写入Cache时,也通过直接通路写主存,这样块替换时不必先写回主存就可以调取新块。

写回法的开销花在每次要替换的时候,写直达法的开销花在每次写Cache时都要增加一个比写Cache时间长的多的写主存时间。

两种方法都需要少量缓冲器,写回法中缓冲器用于缓存将要写回的块,使之不必等待被替换块写回主存后才开始进行Cache取。写直达法中缓冲器用于缓冲由写Cache所要求的要写回主存的内容,使CPU不必等待这些写主存完成就能往下运行。

缓冲器由要写的数据和要存入的目标地址组成。

缓冲器对Cache和主存是透明的,在设计时,要处理好可能由它们所引起的错误。

写回法是写整个块,但写回法几乎总是使主存的通信量比写直达法要小得多。

处理机的不少写入是暂存中间结果,采用写回法有利于省去将中间结果写入主存的许多无谓开销,但是写回法增加了Cache的复杂性,需要设置修改位,以确定是否需要写回以及控制写回后才调入的执行顺序。而且写回法在块替换前,仍会存在主存内容与Cache内容的不一致。

可靠性

写回法不如写直达法。

写直达法当Cache出错时可以由主存来纠正,因此Cache中只需有一位奇偶校验位,写回法则由于有效的块只在Cache中,因此需要在Cache中采用纠错码。即需要在Cache中增加更多的冗余信息位来提高其内容的可靠性。

采用什么写回法还是写直达法与系统应用有关,单处理机系统,多数用写回法节省成本,共享主存的多处理机系统,一般多用写直达法。

多处理机共享主存交换信息改成共享Cache共享信息,信息的一致性难以保证。

对于共享主存的多CPU系统,绝大多数还是采用各个CPU都有自己的Cache,在这样的系统中由于Cache的透明性,仅采用写直达法并不能保证同一主存单元在各Cache中对应的内容都一致。

解决办法1:

播写法,任何处理机要写入Cache时,不仅写入自己Cache目标块和主存中,还把信息播写到所有Cache有此单元的地方。或者让所有Cache有此单元的块作废,采用作废的方法可以减少播送的信息量。

解决办法2:

控制某些共享信息不得进入Cache

解决方法3:

目录表法,在CPU读、写Cache不命中时,先得查在主存中的目录表,以判定目标块是否在别的Cache内,以及是否正在被修改,然后再决定如何读、写此块。

Cache内容跟不上主存内容变化问题的解决办法是当I/O处理机未经Cache往主存写入新内容时,由操作系统经专用指令清楚整个Cache。

这种方法的缺点是Cache存储器对操作系统和系统程序员不透明。

另一种解决办法是当I/O处理机往主存某个区域写入新内容时,由专用硬件自动将Cache内对应此区域的副本作废,保持了Cache的透明性,CPU、I/O处理机共享同一Cache也是一种解决办法。

每个处理机都有Cache的共享主存多处理机系统

每个处理机都有Cache的共享主存多处理机系统

2.Cache的取算法

Cache所用的取算法基本上是按需取进法,即在Cache块失效时才将要访问的字所在的块取进。适当选择好Cache的容量,块的大小,组相联的族属和组内块数,是可以保证较高的命中率。如再采用在信息块要用之前就预取进Cache的预取算法,还可以进一步提高命中率。

为了便于硬件实现,通常在访问主存第i块时,只预存取顺序的第i+1块。至于何时取进该块,可由恒预取和不命中时预取两种方法。

恒存取是只要访问到主存第i块,无论Cache是否命中,恒预取第i+1块。

不命中时预取则是在访问主存第i块在Cache不命中时,才预取主存的第i+1块。

采取预取法并非一定能提高命中率,它还和块的大小及预取开销的大小有关。

块太小,预取效果不明显,但从需求看,块要尽量大,块太大,就会预取进不用的信息,因Cache容量有限,反而将征用或近期用的信息挤出去。使命中率低。

预取法不应只从命中率的提高来衡量,还应考虑为此所花费的开销是否值得。

3.Cache存储器的性能分析

Cache存储器的性能主要是看命中率的高低,命中率的高低与块的大小、块的总数,采用组相联时组的大小,替换算法以及地址流的簇聚性有关

块的大小及Cache容量增大时都能提高命中率,Cache容量不能太大,否则调块时CPU空等时间太长,块的大小一般取成是多体交叉主存的总宽度。使调块可在一个主存周期内完成,这样,Cache的块数极多,随着块的增大,Cache的不命中率总是呈下降趋势,

绝大多数Cache存储器都采用LRU算法替换。

设tc为Cache的访问时间,tm为主存周期,Hc为放Cache命中率,则Cache存储器的等效存储周期:

与虚拟存储器不同的是,一旦Cache不命中,主存与CPU经直接通路传送。所以CPU对第二级的访问时间是tm。而不是调块时间再加一个访Cache时间。这样,采用Cache存储器比处理机直接访问主存其等效访问速度提高的倍数为:

因为Hc总小于1,可令

带入上式得:

不管Cache本身的速度有多高,只要Cache的命中率有限,那么采用Cache存储器后,等效访问速度能提高的最大值是有限的,不会超过α+1倍。

采用Cache存储器时能使ρ接近所期望的tm/tc

结论:

Cache本身的速度与容量都会映像Cache存储器的等效访问速度,如果对Cache的速度不满意,需改进,应作具体分析。看现在Cache存储器的等效房问速度是否已接近于Cache本身的速度,如果差得远,说明Cache命中率低,这时不适用更高速的Cache芯片来替换现有Cache芯片。而应该以提高Cache命中率着手。如果Cache芯储器的等效速度已经非常接近于Cache本身的速度,但还不能满足速度要求时,就只能更换更高速的Cache芯片。


4.4 三级存储体系

多数计算机既有虚拟存储器又有Cache存储器,程序用虚地址访存,要求速度接近于Cache,容量是辅存的。

4.4.1 物理地址Cache

物理地址Cache是由“Cache——主存”和“主存——辅存”两个独立的存储层次组成。

CPU用程序虚地址访存,经存储管理部件(Memory Management Unit MMU)中的地址变换部件变换成主存物理地址访Cache。如果命中Cache,就访Cache;如果不命中Cache,就将该主存物理地址的字和含该字的主存的一个块与Cache某相应块交换,而所访问的字直接与CPU交换。

这种方式需要将主存物理地址变换Cache地址才能访Cache,这将增大访Cache的时间,至少要增加一个查主存快表的时间,为弥补这个不足,许多系统就改为直接用虚地址访问Cache,这就是虚地址Cache形式。

 

4.4.2 虚地址Cache

虚地址Cache是将Cache——主存——辅存直接构成三级存储层次形式。:

CPU访存时,直接将虚地址送存储管理部件MMU和Cache,如果Cache命中,数据与指令就直接与CPU传送。不命中,由MMU将虚地址变换成主存物理地址访主存,将含该地址的数据块或指令块与Cache交换的同时,将单个指令和数据与CPU之间传送。

虚存采用位选择组相联映像和地址变换方式,为加快地址变换,让虚存的一个页恰好是主存的一个去,直接用虚地址的区内号按地址访问Cache的块表,从块表中读出主存的区号和对应的Cache块块号,这里,主存的区号就是虚页号,在访问Cache块表的同时,用虚地址的虚页号访问快表。

快表命中,从块表中读出主存区号与从快表中的主存实页号进行全等比较,若比较相等,则Cache命中,此时把虚地址中的区内块号直接作为Cache地址中的组号,从块表的相应单元中读出Cache的组内块号,把虚地址中的块内地址直接作为Cache地址中的快内地址。

将上述得到的组号、组内块号、组内地址拼接成Cache地址访问Cache中的字送经CPU。若Cache不命中,则直接用虚地址作为主存实地址访主存将访主存的字送往CPU。同时将含此字的一个块从主存中读出装入到Cache中。

如果Cache已满,还需要Cache替换算法。来将一个不用的块替换到主存中去。

4.4.3 全Cahce

全Cache是最近出现的组织形式,尚不成熟,尚未商品化,他没有主存,只用Cache与辅存中的一部分组成“Cache——辅存”存储体系。

全Cache存储系统的等效访问时间要接近于Cache的,容量是虚地址空间的容量。

由于磁盘辅存基本访问单位基本是物理块,每块512字节。因此,与磁盘存储器连接的局部Cache块容量一般也是512字节,其他Cache块的容量可以小于或大于512字节。但应该是512字节的整数倍。

与本文相关的文章
版权声明
转载保留版权: 大D综合研究院 | 《《计算机系统结构》读书笔记(十一)》
本文链接地址:https://www.dadclab.com/archives/3129.jiecao
转载须知:如果您需要转载本文,请将版权信息,版权授权方式,以及本文的链接地址注明,谢谢合作。
本文被贴上了: , , , , , , 标签