(结合看过的几篇文章整理笔记)
什么是Cache地址映射
Cache的容量很小,它保存的内容只是主存内容的一个子集,且Cache与主存的数据交换是以块为单位的。主存每个块的大小和Cache每个块的大小相等(主存块大小=Cache块大小)。
为了把信息放到Cache中,必须应用某种函数把主存地址定位到Cache中,这称为地址映射。
在信息按这种映射关系装入Cache后,CPU执行程序时,会将程序中的主存地址变换成Cache地址,这个变换过程叫做地址变换。
Cache的地址映射方式有:直接映射、全相联映射和组相联映射。
假设某台计算机主存容量为1MB,被分为2048块,每块512B;
Cache容量为8KB,被分为16块,每块也是512B。
下面以此为例介绍三种基本的地址映射方法。
直接映射
直接映射是最简单粗暴的办法:
(块地址)mod(cache中的块数)
映射规则为:Cache line index = (主存(Page)的line数)%(cache中 cache line的总数)
一个内存块地址始终映射到一个固定的Cache 地址。就如每个人的停车位是固定分配好的,可以直接找到。
主存中的一个块只能映射到Cache的某一特定块中去。
下图中主存被分为了0-2047个内存块,缓存块或者说Cache line有16块。
例如,主存的第0块、第16块、第32块、第48块、…、第2032块等128块,只能映射到Cache的第0块;
主存的第1块、第17块、第33块、第49块、…、第2033块等128块,只能映射到Cache的第1块;
以此类推,主存的第15块、第31块、第47块、…、第2047块等128块,只能映射到Cache的第15块中。
映射完毕,Cache总共有0~15即16块,主存中的每128(2048/16)块,只能映射到Cache中的某一个块中。
即映射规则为cache line index = (主存(Page)的line数)%(cache中 cache line的总数)
主存的line数是0~2047,cache中cache line的总数是16.
那么第0,16,n*16块因为mod16都为0,所以他们对应到的Cache行号都为0。
知道了映射方法,那么如何规定主存地址呢?
其实对于取模运算,我们只需要取低位字节就可以了。
在十进制里面如果对16取余,那么结果定是两位数以内,并且不会大于15。
比如说Cache有16行,16是2的4次方,那么我们就可以直接取主存块号的低四位作为Cache行号。
17对应的cache行号就是1.
但当我们读取某一个缓存行时,我们怎么知道他是0块群的还是其他块群的呢?
其实正如主存块号中包含了Cache行号一样,其低四位之前的高位就可以作为区分的Tag(主存标记)使用。最后一点就是,CPU读取数据只是要读取它需要的字(Word)而已,那么这个字具体是在Cache line的哪里,我们还需要一个偏移量来纪录它。
所以直接映射的主存地址应该由三部分组成:主存子块标记,Cache子块标记,字块内地址。
现在我们来自己动手做一做:假设数据在主存和Cache间的传送单位为512B,Cache大小为2^13B,主存大小为2^20B。
因为主存大小为2^20B,且以512B为传送单位。那么2^20B=2048块 * 512B/块,主存可以划分为2048块,主存地址为20位二进制数。因为我们需要确定要取的是块中的哪个字,又512=2^9,所以需要9位作为偏移量,或者说字块内地址。 Cache可以划分出16行(2^13=16行 * 512B/行),也就是说划出4位作为行号标记,或者说Cache字块地址。剩下的7位自然就作为主存字块标记啦。
优缺点:
电路实现简单,命中时间短无需考虑替换问题Cache的存储空间没有得到充分使用,命中率低
缺点通俗理解:因为人多车位少,很可能几个人争用同一个车位,导致Cache淘汰换出频繁,需要频繁的从主存读取数据到Cache,这个代价也较高。
全相联映射
针对直接映射Cache空间利用率低的问题,我们有一种简单粗暴的办法提升空间的利用率。
那就是主存中的任意一块都可以映射到Cache中的任意一个位置。
有空车位你就停,随意,映射位置不在固定,停的时候简单,找车的时候需要一个一个停车位找。
全相联映射方式比较灵活,主存的各块可以映射到Cache的任一块中,Cache的利用率高,块冲突概率低,只要淘汰Cache中的某一块,即可调入主存的任一块。
那么我们唯一要做的就是知道Cache中是对应主存中的哪一块和字块内地址就行。因为是随便映射,所以我们把直接映射中的Cache字块标记合并到主存字块标记中。
全相联映射主存地址只有两部分:主存字块标记,字块内地址。
优缺点:
不存在冲突缺失,命中率高电路复杂,速度慢
由于Cache比较电路的设计和实现比较困难,这种方式只适合于小容量Cache采用。
需要存储tag来区分,tag可以理解为主存块的index,方便查找。
组相联映射
综合前两种方法的就是组相联映射,组相联映射实际上是直接映射和全相联映射的折中方案,组织结构如下图。(两级结构,内存块→缓存组)
具体做法是:主存和Cache都分组,主存中一个组内的块数与Cache中的分组数相同,组间采用直接映射,组内采用全相联映射。也就是说,将Cache分成u组,每组v块,主存块存放到哪个组是固定的,至于存到该组哪一块则是灵活的。例如,主存分为256组,每组8块,Cache分为8组,每组2块。
Cache组号=主存块号 mod Cache组数
举例:
将Cache空间划分成2^q组,每组2^s页(称为2s路相联),将主存空间分成2^m区,每个区2^q页,主存中的某区允许映射到固定组内的任意项。某区的第0页可以调入Cache0组的中的任意一页,第1页可以调入Cache1组的中的任意一页。
现在设q=7,则Cache中有0 - 127,共128组,s = 1,每组2页(称为2路相联),每页32个字节,Cache容量为8KB。主存地址32位,m = 20,最大可分为2^20个区,每区128(2^q)页,每页32个字节。
(引入“区”的概念,三级结构,内存【区,组】→缓存组,原理一致)
组相联的映象规则:
(1)主存和Cache按同样大小划分成块。
(2)主存和Cache按同样大小划分成组。
(3)主存容量是缓存容量的整数倍,将主存空间按缓冲区的大小分成区,主存中每一区的组数与缓存的组数相同。
(4)当主存的数据调入缓存时,主存与缓存的组号应相等,也就是各区中的某一块只能存入缓存的同组号的空间内,但组内各块地址之间则可以任意存放,即从主存的组到Cache的组之间采用直接映象方式;在两个对应的组内部采用全相联映象方式。
图2.3.6示出了组相联的映象关系,图中缓存共分Cg个组,每组包含有Gb块;主存是缓存的Me倍,所以共分有Me个区,每个区有Cg组,每组有Gb块。那么,主存地址格式中应包含4个字段:区号、区内组号、组内块号和块内地址。而缓存中包含3个字段:组号、组内块号、块内地址。主存地址与缓存地址的转换有两部分,组地址是按直接映象方式,按地址进行访问,而块地址是采用全相联方式,按内容访问。组相联的地址转换部件也是采用相关存储器实现,见图2.3.7。
二级结构和三级结构原理一致。
简单举例理解如下:缓存8K,一个缓存块大小521B,分16块,分8组,一组2块。内存1MB,一个内存块大小521B,分2048块。
二级结构:主存和Cache都分组,主存中一个组内的块数与Cache中的分组数相同。
则,主存2048块以8块为一组,分为256个组。256个组每个组的第一块都是映射到缓存第0组,即一组缓存(2块)对应256个内存块。
三级结构:(1)主存和Cache按同样大小划分成块。(2)主存和Cache按同样大小划分成组。(3)主存容量是缓存容量的整数倍,将主存空间按缓冲区的大小分成区,主存中每一区的组数与缓存的组数相同。
缓存共分8个组,每组包含有2块;主存是缓存的(1MB/8K=128)倍,所以共分有128个区,每个区有8组,每组有2块。
128个区每一个区的第0组(2块内存块)都映射到缓存的第0组,内存块总数128*2=256块,依旧是一组缓存(2块)对应256个内存块。
两个结构表述不同,但原理是一致的。
那么问题来了怎么确定Cache中的字块是对应主存的那一块呢?首先我们仍需要字块内地址,需要区分组号,那么剩下的地址就可以作为主存字块标记使用。
实例分析1:
容量为64块的Cache,采用组相联方式映像,字块大小为128字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址该如何划分?
因为4096=219,所以主存地址应该为19位,Cache总共有16组,所以需要4位确定组号。又字块大小为128字,128=2^7,所有字块内地址为7位,剩下的19-7-4=8位作为主存字块标记。
实例分析2:
1.容量为64块的Cache采用组相联方式映像,字块大小为128字节,每4块为一组,若主容量为4096块,且以字编址,那么主存地址为(19)位,主存区号为(6)位。
解:组相联的地址构成为:区号+组号+块号+块内地址。
主存的每个分区/组大小与整个Cache大小相等,故此主存需要分的区数为:4096/64=64,因为26=64,因此需要6位来表示区号。
每4块为一组,故共有组数 64/4 = 16 ,因为24=16,因此需要4位表示组号。每组4块,故表示块号需要2位。
块内地址共128字节,27=128,所以块内地需要7位表示。所以:主存地址的位数=6+4+2+7 = 19
主存区号的位数=6
以上两个实例问题相似,但解答不同,我也想不通了,版本不同吧。
优缺点:
电路较简单,速度较快,命中率较高,属于比较理想的方式
常采用的组相联结构Cache,每组内有2、4、8、16块,称为2路、4路、8路、16路组相联Cache。组相联结构Cache是前两种方法的折中方案,适度兼顾二者的优点,尽量避免二者的缺点,因而得到普遍采用。