MENU

高速缓冲存储器

November 10, 2018 • Read: 785 • 计算机组成原理

概述

Cache即高速缓存,是用来解决主存与CPU速度不匹配的问题,Cache的出现使得CPU可以不直接访问主存而直接与Cache交换信息。由于程序访问的局部性原理可以很容易设想只要将CPU近期要用到的程序和数据提前从主存送到Cache,那么就可以做到CPU在一定时间内只访问Cache,这样CPU与高速Cache进行通信,就大大提高了计算机的运行速度

程序的局部性原理: 局部性原理又表现为:时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行,则不久之后该指令可能再次被执行;如果某数据被访问,则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元,则不久之后。其附近的存储单元也将被访问。

Cache的工作原理

在Cache与主存的地址映射之前,首先要将主存与Cache都分成若干块,每块又包括若干个字,并使得它们的大小相同(即块内的字数相同,因为Cache与主存之间的数据交互是以行为单位,所以他俩每行存储的字大小必须相同)。

在划分好块后,下面要做的就是将主存块与Cache块形成映射就行了。而这里的映射则是通过块的地址形成映射关系。对于地址映射,首先将主存地址分成两块,高$m$位为主存的快地址,低$b$位为块内地址。(字块中存放的就是真正使用的数据,只是映射时使用地址来映射)

CPU、Cache、主存之间的关系

Cache的读写操作

读
写

Cache命中率

在一个程序执行期间,设Nc表示cache完成存取的次数,Nm表示主存完成存取的次数,h表示cache的命中率,则:

$$ h = \frac{Nc}{Nc+Nm} $$

cache/主存系统的平均访问时间

若$t_c$表示命中时cache的访问时间,$t_m$表示未命中时主存的访问时间,h表示cache的命中率,$t_a$表示平均访问时间,则:

$$ t_a = ht_c+(1-h)t_m $$

访问效率

$$ e = \frac{t_c}{t_a} = \frac{t_c}{ht_c+(1-h)t_m}=\frac{1}{h+(1-h)r} = \frac{1}{r+(1-r)h} $$

其中,$r=\frac{t_m}{t_c}$

关于Cache命中率有一个坑,提前给出来,免得以后犯错。$t_m$的定义是“未命中时主存访问的时间”,所以不能单纯的理解为“主存的存储周期”,比如下面一道题

某计算机的存储系统采用由cache-主存系统构成,cache的存储周期为10ns,主存的存储周期为50ns。若CPU执行一段程序时,cache完成存取的次数为4800次,主存完成存取的次数为200次,cache与主存不能同时访问,求该cache-主存系统的访问效率。

习惯地认为这里“$t_m=50ns$”,但是请注意一句话“cache与主存不能同时访问”,$t_m$的定义是“未命中时主存的访问时间”,既然“未命中”,说明在该题的情景下,先访问了cache,用了10ns,再去访问主存。所以:$t_m=10+50=60ns$

Cache与主存的映射方式

Cache与主存的地址映射方式有很多,有直接映射全相联映射组相联映射

1.直接映射

在这种映射方式下,主存中的任一块只与一个缓存块相对应,映射关系为:$i = j mod C$,其中,$i$为缓存块号,$j$为主存块号,$C$为缓存块数。
直接映射

当缓存接收到CPU发送来的主存地址后,只需根据中间c位字段(假设为00…01)找到缓存块1,然后根据字块1的“标记”是否与主存地址的高t位相符合,若符合且有效位为1(这里的有效位用来识别Cache存储块中的额数据是否有效,因为有时Cache中的数据是无效的,例如,在初始时刻Cache中的额内容为空,是无意义的),则表示该Cache块已和主存中的某块建立了对应关系,则可根据b位块内地址从Cache块中取得对应的字,即找到CPU发来的主存地址在缓存中所对应的信息;若不符合,或者有效位为”0”,则主存读入新的字块来代替旧的字块,同时将信息送往CPU,并修改Cache“标记”。

特点: 不灵活,每个主存块只能按照取模固定地映射到某个缓存块,即使缓存内其他块空着,也不能用来映射。因而如果程序恰好要重复地使用对应同一缓存块的不同主存块,那么久需要不同的替换,这样会降低命中率。

2.全相联映射

全相联映射中,主存任一块可以放到任一缓存块中。这样CPU如果获取主存的内的数据,就需要扫描整个缓存,看当前缓存中是否包含有所需的主存的数据
全相联映射
特点: 全相联映射允许将主存中的每一字块映射到Cache中的任意一块位置上。显然这种映射方式相对于直接映射,更加灵活,命中率也更高,缩小了块冲突。同时也因为这个特点,所需的逻辑电路较多,成本也比较高。

3.组相连映射

针对上述直接映射和全相联映射出现的问题,现在出现一种折中的映射方式,即下面介绍的组相联映射。该映射方式将所有Cache分为Q组,每组有R块,则有关系:$i = j mod Q$,其中$i,j$的含义与直接映射中的含义一致
组相联映射
之所以说是折中,是因为按照直接映射中取模的方式,某个主存块映射到Cache中的组是固定的,但是在组内,又按照全相联映射原则,“随意存放”,即通过主存字块标记可以映射到该组中任意一块Cache块。

这里看似主存地址很复杂,其实只要知道Cache一共有多少组即可确定组地址的位数,字块内地址与前面两种映射方式所说的一致,最后通过总位数减去组地址位数和字块内地址位数即得主存字块标记位数。

常用替换算法

Cache miss不仅意味着需要从主存获取数据,而且还需要将cache的某一块替换出去。常用的算法包括FIFO、LRU、LFU、Random等

FIFO: First in First out

假如依次进入Cache的数据为:1、5、4、3、2,如果此时Cache满了,又有一个新的数据6要进入,此时就会将数据1所在的块清空,把6放进来;如果1这个数据又来了,那么就会将5所在的数据块清空,把1放进来

Radom

这个就是纯粹的玄学随机移除,如果Cache满了,随机移除某一块

LFU

LFU(Least Frequently Used)最近最不常用算法。它是基于如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小的思路

假设缓存大小为3,数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)

则在set(4,4)时对于LFU算法应该淘汰(3,3)

实现思路:每行设置一个计数器,计数器最小的行将被替换

LRU

LRU(Least Recently Used)最近最少使用。它是基于:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。也就是说,当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

注意LFU和LRU算法的不同之处,LRU的淘汰规则是基于访问时间,而LFU是基于访问次数的。

假设缓存大小为3,数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4)

LRU应该淘汰(1,1)

实现思路:每行设置一个计数器,Cache命中相应的计数器清零,其他计数值加1,计数值最大的行将被替换

小结

直接映射:某一主存块只能固定映射到某一缓存块

全相联:某一主存块映射到任一缓存块

组相联:某一主存块只能映射到某一缓存中的任一块

Archives Tip
QR Code for this page
Tipping QR Code