主存和Cache的几种映射方式

更新时间:2023-07-13 12:40:57 阅读: 评论:0

主存和Cache的⼏种映射⽅式
在⼀切开始之前,⾸先最重要的是需要去明⽩和掌握内存的块的定义:内存被分为若⼲块,这些块:1.⼤⼩相等,2.每块由若⼲字组成,3.块的长度成为块长,块的长度是指由⼏个字组成就是多长,⽐如⼀个块由x个字组成,那么块长为x.4.每个块由连续的字组成。在Cache中这种块被某些替换原则替换进⼊Cache之后,称为Cache的⾏(有些书上也称为块,这⾥就⽤⾏表⽰,以免混淆)。有以下⼏个特点:
1.块长(⼀般是取⼀个存取周期内从主存调出的信息长度,和交互存取有关系)与⾏长相等,这点和物理页和逻辑页的页内地址的长度是⼀样的原理类似。
2.Cache中⾏的位数=⾏号+⾏内地址内存中块的位数=块号+块内地址。
3.块内地址的位数由块的长度决定(设块的长度为x,块内地址的位数其实就是⽤⼏位能表⽰x的问题),块号的位数由块的数⽬决定(⽐如块的数⽬是x,块号其实就是⽤⼏位⼆进制数能表⽰x个数的问题),⾏号的位数由⾏数决定。块⾥的内容就是⾏的内容,⾏内地址和块内地址相同。、
副生命线标记位是什么?先记住⼀点,标记位和cache的地址没有⼀点关系。每个⾏对应⼀个标记位。后⾯会进⾏说明
CPU与内存以及Cache之间的交互⽅式
好了,明⽩了块和⾏的定义之后,我们来看看CPU与内存和Cache之间的交互:1.CPU同时(也有可能不是同时,这时事先访问cache cahce⾥⾯没有再对主存进⾏访问,如果缺失的话访存时间会长⼀点)向Cache和内存发出读请求。把地址同时送给Cache和内存。2.Cache控制逻辑(由硬件实现)判断此内存地址是否在Cache中,在则⽴马将此内存的字送给CPU,与此同时,终⽌访问内存。3.若不在Cache中,⽤主存读取周期从主存中将字取出送往CPU,与此同时,把含有这个字的整个数据块通过Cache与主存的直接通路送到Cache 中。(由这个交互过程我们可以看到,主存和Cache与CPU交互的时候传送的是字,但是Cache和主存交互传送的是块)
了解了过程之后我们来看看映射关系是什么,映射关系是CPU在访存时,将主存地址变换成Cache地址的过程。对应第⼆步的判断是否在Cache中的其中⼀部。
三种映射关系。1.直接映射。2.全相联映射。3.组相联映射。
1.全相联映射
将块内地址直接变为Cache的⾏内地址,同时将块号直接放进Cache的标记位(这个时候标记位就是内存地址的块号)⾥去,直接将主存⾥的⼀个快包括内容直接拷贝到Cache⾥的任意⼀⾏⾥去(⼀般是弄成连续的),这样相当于相当于建⽴了⼀个标记位和⾏之间的对应关系表,访问⼀个内存地址上的字,只要从内存地址中取出块号,然后在标记位和⾏之间的对应关系⾥查表,就能找到这个字所在
的⾏,然后⽤快内地址(其实就是快内偏移量)找到⾏中对应的字的地址。
例如,主存现有256个块(得出块号为8位),每个快有256个字(得出块内地址8位),所以内存地址总位数为16位,所以cache块内地址应该有8位,设它有8⾏,⾏号有3位,所以cache地址长度为3 + 8 =11位,标记位为块号。可以随便映射到任意⼀个Cache的⾏,建⽴这个块号(也就是标记位)与映射到的⾏的对应关系,标记位的内容为块号(即内存地址的前⼋位),这个就是简单的全相联映射。此时,主存容量为块数(256)*块长(256)为64K,Cache容量为⾏数(8)*⾏长(256)为2K(不包括标记位)。(为什么是K 不是KB?其实写成64KB 2KB也可以,毕竟表⽰的是容量,写成64K 2K就意味着,有64个字的容量,或者有2K个字的容量,因为有些计算机⼀个字可能不是8位。本例⼦中是⼀个字8位)
如何访问内存中⼀个字怎么找到他对应的cache的地址呢?(由硬件实现),有⼀个⽐较器,1.CPU访问按内存地址,将其块号放到⽐较器中,然后⽐较器将块号和标记位与⾏之间的对应关系表中的标记位⼀个⼀个⽐较,如果有⼀个标记位和块号⼀样,则说明这个字所在的块在Cache⾥,然后⽤地址的低⼋位(快内地址,也叫做快内偏移量)找到⾏中的那个字的地址然后读⼊CPU。2.如果没有标记位和块号⼀样,说明不在Cache⾥,通过16位地址直接访问内存送CPU,同时将这个字所在的块整个搬⼊Cache⾥(硬件实现)。这种⽅法命中率⾼,但是⽐较器电路设计复杂。因为对应关系表中⼀个标记位就要连⼀条线,最简单的⽐较器就是两个数⽐较最简单,所以有了直接映射。
举个例⼦:⽐如 addr1:0010 1101 0010 1110    addr2:1101 1111 1111 1010  cache 有8⾏。
划分内存地址红⾊为标记位,黄⾊为块内偏移量。刚开始cache为空,访问addr1 addr2,不命中,从内存读取块,开始全相联映射,⽐如addr1,他属于块0010 1101 0000 0000 -----0010 1101 1111 1111,随机放⼊⼀⾏中,假设放⼊了101⾏,那么101⾏也就是101 0000 0000 ----- 101 1111 1111这⼀⾏的标记位就为 0010 1101,同理假设addr2放⼊的⾏是111,那么标记位就为 1101 1111,建⽴标记位和⾏的对应关系,相当于打表,表中有两项,0010 1101 对应 101 0000 0000,1101 1111对应 111 0000 0000 .第⼆次访问addr2的时候,遍历这张表,找到标记位与addr2前⼋位相同的表项,取出⾏号111 ,再与其块内偏移量⼀拼,就得到了cache中的地址111 1111 1010,这个地址上就是我们要访问的字。
2.直接映射
指的是主存⾥的⼀个块能通过⼀个式⼦的映射能放在Cache中的⼀个特定的⾏⾥(这个逻辑由硬件实现)Cache的⾏号 i 和主存块号j存在关系 i=j mod n n为总⾏数,⽐如43号
块,cache中有10⾏,说明43 必须放⼊第⾏号为3的那⼀⾏⾏,⽽且23 13 53等都是这样。
例⼦:
内存地址16位,Cache⾏数8⾏,内存地址低⼋位位块内地址,⾼⼋位位块号。这时,块号8位中的低三位,其实是块号除于⼋的余数(000-111),所以可以直接⽤内存地址当中的这三位来表⽰cache的⾏号,都不⽤算 ,结果剩下5位是标记位,内存的块往cache放的时候,内存地址的⾼⼋位中的的低三位是多少就往第⼏⾏放(硬件实现),吧剩下五位当做标记位,建⽴标记位与⾏的映射关系,便于查找。
如何写好字原理。拿到16位地址之后,取出⾼⼋位的低三位确定⾏号去找第⼏⾏。吧这⼀⾏的标记位拿出来通过⽐较器和地址前五位⽐较,如果⼀样,则命中,不⼀样不命中,若命中,再根据块内地址(快内偏移)找到字送给cpu,不命中,访问内存,把包含这个字的整个块放到刚才我们找的那⼀⾏⾥⾯去(硬件实现)
⽐较器简单,只⽤⽐较两个数,但是不灵活,会产⽣抖动,冲突率最⾼,空间利⽤率最低。同时注意不需要替换算法。青钱柳的功效
举个例⼦:⽐如 addr1:0010 1101 0010 1110    addr2:1101 1111 1111 1010
两个内存地址:划分内存地址红⾊为标记位,蓝⾊为⾏号,黄⾊为块内偏移量,cache⼀开始为空的时候访问这个两个地址,不命中,开始直接映射,内存地址划分之后红⾊表⽰的是标记位,蓝⾊表⽰的是组好,黄⾊表⽰的是块内地址,那么addr1就是应该映射到⾏号为101的cache⾏,意思是整块映
射到地址为101 0000 0000 -----101 1111 1111的cache⾏中, addr2 映射到⾏号为111的cache⾏,意思是整块映射到地址为111 0000 0000 ----- 111 1111 1111的⾏中,然后建⽴起标记位和⾏的对应关系,00101 对应101 0000 0000 (相当于把这⼀⾏的起始地址与标记位对应) 11011 对应111 0000 0000 ,当访问addr1的时候获得组号10,查表,通过硬件直接得到 101⾏的标记位00101,命中,然后快内偏移位0010 1110 直接与101 连接起来得到最终要的要访问的字所在的cache地址 101 0010 1110 。吉粮康郡
3.组相联映射
是折中的⽅法,将cache的8⾏分为4组,没组2⾏,这叫做2路组相联,(⼀组4⾏叫做,4路组相联)。然后⽤内存地址的块号处于总组数,余数是⼏就往第⼏组放,组⾥⾯随便放。组内相当于全相联,组间直接映射。
内存地址,16位分隔为3部分:6位(直接作为标记位)+2位(⽤来确定组号)+块内8位。看组号是⼏,就放第⼏组,组⾥⾯随便放。将剩下6位当做cache标记位。⼆路组相联⽐⼀路的组号少⼀位,4路的少⼆位。。。类推
查找过程:获得16位内存地址,由组号是⼏就找第⼏组,将⾥⾯两个⾏的标记位和内存地址的前6位⽐较,如果有⼀个⼀样,说明命中。由块内地址找到字。两号标记位都不⼀样,就
琅岐
在内存中读出数据同时将字所在的整个块放到我们刚才找的那个组⾥⾯去,两⾏随便放(硬件实现)
举个例⼦:⽐如 addr1:0010 1101 0010 1110    addr2:1101 1111 1111 1010
两个内存地址:红⾊表⽰的是标记位,蓝⾊表⽰的是组好,黄⾊表⽰的是块内地址,第⼀次访问addr1 addr2 未命中,将内存块放⼊cache,那么addr1就是应该映射到组号为01的组,也就是第⼀组意思在地址为010 0000 0000 ----- 010 1111 1111的cache⾏和地址为 011 0000 0000  ----- 011 1111 1111的cache⾏中, addr2 映射到组号为11的cache⾏,也就是第3组意思是在地址为110  0000 0000 ----- 110 1111 1111的⾏以及111 0000 0000 ----- 111 1111 1111的⾏中。组内随便放,⽐如addr1 ,他所在的块0010 11 ...... 放⼊的是011 0000 0000 ---- 011 1111 1111的cache⾏中,那么他的这⼀⾏的标记位为0010 11,进建⽴对应关系,下次访问addr1的时候直接得到组号,然后找到组好对应的两个⾏,取出标记位,与红⾊区域进⾏对⽐,然后与块内地址⼀拼接,就得到了字所在的地址。
计算问题
在cache的试题当中,我们会发现很多⼨步难⾏的地⽅,主要的原因还是对于cache的地址的不了接所造成的。⽐如要你求cache的总容量你会怎么求呢。⽐如告诉你cache的总容量为16KB你就会说这么简单,不就是cache的地址是14位吗?的确有道理,因为不管你划分什么⿁标记位,块内地址,甚⾄是什么⽚选信号位,以及页号等等等,其实实质上都是⼀个地址对应⼀个字的数据,⽐如1100 1100 0
011 0101这个地址,你⽆论怎么划分标记位什么的,其实就是相当于给整个存储系统分了⼏个部分。仅此⽽已,所以有道理。但是其实错了,为什么,这下我要告诉你cache的地址的真正构成,这个地⽅是本⼈经过很多题⽬的训练和⽹上寻找答案总结出来的东西,都是⼲货
⼤家都知道cache中的⼀⾏由标记位和块内地址组成,但是⼤家知道吗,其实⼀⾏中,有很多个字节,但是标记位只有⼀个,⽽不是每个字都对应⼀个相同的标记位。什么意思呢?就是cache的总容量⾸先有块内地址的容量,⽐如⼀个⾏长是64B的cahce,他的块内地址的容量就是512bit,这叫做每⾏存储的数据,也叫做数据块的位数但是在这⼀个快中,只有⼀个标记位,这个标记位,其实实质上不属于cache的地址。只是⼀个内容。(详情见王道P119)所以
迢迢牵牛星原文及翻译cache的总容量=(有效位(每个⾏⼀般会加上⼀个有效位)+脏位+替换控制位+标记位的位数+数据块总位数。(⼀般题⽬会要求“若不考虑⽤⾬cache的⼀致性维护和替换算法的控制位”,如果没有这个条件,但是他也没说写策略⽤的是哪个,或者没说替换策略⽤的是哪⼀个,那么久当做只有有效位来处理))X⾏数;
所以,如有上⾯那句话,
cache的总容量=(有效位(每个⾏⼀般会加上⼀个有效位)+标记位位数+数据块总位数)X⾏数。
例:块长(有些书上称⾏为快)为64B(⾏长⼀般是K做单位,表⽰字的个数,但是题⽬有时候会⽤B ,bit KB MB这个意思就是⼀个⾏的有效容量,也就是⼀般所说的容量,还有数据块的位数),主存256MB,按字节编址(⼀般默认是这样,除⾮题⽬说明了按字编址或者说是出现了aMXbB这样的描述内存⼤⼩的⽅式)。有8⾏。求cache总容量和容量(若不考虑⽤⾬cache的⼀致性维护和替换算法的控制位)
第⼀步⼀般求主存地址位数:主存256MB可得,256M=2的28次⽅,所以主存地址位数为28位。
第⼆部⼀般就块内地址位数:很可能⽤到⾏长来反推块长,因为两者相等。所以⾏长=块长=64,所以块内地址为6位。
第三部求标志位数(这个指的是主存地址的标志位,所以不⽤加1):28-⾏号位数(3位)-6(块内地址)=19位。
手动挡离合第四部求出cache⾏标记位的组成:19位+1,⼀定要注意加上有效位。
第五步求总容量=(20+64x8)x8
污泥浓缩池
容量很简单1.块长x⾏数=64Bx8,
注意⼀般为cache的地址就是cache的块内地址。因为这才是他的有效数据位,还有问的是主存的标志位还是cache的标志位,还有就是块号和⾏号以及第⼏块⼀般是从0开始(⼀般题⽬会说,但是也可能不会说)
有⼀种情况就是告诉你cache的容量为16B这下你可以直接得出cache的地址位数为4位,如果是总容量就不⾏
关于最常考的关于c语⾔与cache的映射结合起来的⽅式,就是循环和求缺失率:
⽐如for(in=0;i<100;i++)
a[i]=a[i]+k;
这种就是,这⾥相当于每执⾏⼀次赋值语句,就访问两次a[i],⽐如如果是int类型的数组,⼀个数4B,但是块的长度为16B,就是说⼀个快中有4个a数组的数,这时候他会问你,如果求cache的访问缺失率,主要是⼀点,不要去算总的访问次数和缺失次数或者命中次数,⼀次⾛那个语句的命中率久可以代表所有的命中率或者缺失率,这⾥假设⼀开始cache为空,为直接映射,他访问a[0]时候,未命中,于是到内存⾥将含有这个数的整个块调⼊cache中,所以就把这个数a[0]以及后⾯三个数a[1] a[2] a[3]全部掉⼊了cache⾥,所以每访问四个数,就只有第⼀次访问是缺失的,后⾯的7次都是命中,四个数总共访问8次a数组,所以命中率为1/8.

本文发布于:2023-07-13 12:40:57,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/fan/89/1079843.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:地址   标记   主存   映射   关系
相关文章
留言与评论(共有 0 条评论)
   
验证码:
推荐文章
排行榜
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图