精华内容
参与话题
问答
  • 主存到Cache直接映射、全相联映射和组相联映射

    万次阅读 多人点赞 2016-11-29 14:30:46
    为了把信息放到Cache中,必须应用某种函数把主存地址定位到Cache中,这称为地址映射。---- 在信息按这种映射关系装入Cache后,CPU执行程序时,会将程序中的主存地址变换成Cache地址,这个变换过程叫做地址变换。...

    ---- Cache的容量很小,它保存的内容只是主存内容的一个子集,且Cache与主存的数据交换是以块(cache line)为单位的。为了把信息放到Cache中,必须应用某种函数把主存地址定位到Cache中,这称为地址映射

    ---- 在信息按这种映射关系装入Cache后,CPU执行程序时,会将程序中的主存地址变换成Cache地址,这个变换过程叫做地址变换。

    Cache的地址映射方式有直接映射全相联映射组相联映射

    假设某台计算机主存容量为1MB,被分为2048块,每个Block为512B;Cache容量为8KB,被分为16块,每块也是512B。

    下面以此为例介绍三种基本的地址映射方法。

    1. 直接映射

    ---- 一个内存地址能被映射到的Cache line是固定的。就如每个人的停车位是固定分配好的,可以直接找到。缺点是:因为人多车位少,很可能几个人争用同一个车位,导致Cache淘汰换出频繁,需要频繁的从主存读取数据到Cache,这个代价也较高。

    直接映射的Cache组织如图(1)所示。主存中的一个块只能映射到Cache的某一特定块中去。例如,

    主存的第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.

      

                                              图(1)

    直接映射是最简单的地址映射方式,它的硬件简单,成本低,地址变换速度快,而且不涉及替换算法问题。但是这种方式不够灵活,Cache的存储空间得不到充分利用,每个主存块只有一个固定位置可存放,容易产生冲突,使Cache效率下降,因此只适合大容量Cache采用。例如,如果一个程序需要重复引用主存中第0块与第16块,最好将主存第0块与第16块同时复制到Cache中,但由于它们都只能复制到Cache的第0块中去,即使Cache中别的存储空间空着也不能占用,因此这两个块会不断地交替装入Cache中,导致命中率降低。

    2. 全相联映射

    ---- 主存中的一个地址可被映射进任意cache line,问题是:当寻找一个地址是否已经被cache时,需要遍历每一个cache line来寻找,这个代价很高。就像停车位可以大家随便停一样,停的时候简单,找车的时候需要一个一个停车位的找了。

    图(2)是全相联映射的Cache组织,主存中任何一块都可以映射到Cache中的任何一块位置上。

      

                                             图(2)

    全相联映射方式比较灵活,主存的各块可以映射到Cache的任一块中,Cache的利用率高,块冲突概率低,只要淘汰Cache中的某一块,即可调入主存的任一块。但是,由于Cache比较电路的设计和实现比较困难,这种方式只适合于小容量Cache采用。

    3. 组相联映射

    ---- 组相联映射实际上是直接映射和全相联映射的折中方案,其组织结构如图(3)所示。

    主存和Cache都分组,主存中一个组内的块数与Cache中的分组数相同,组间采用直接映射,组内采用全相联映射。也就是说,将Cache分成2^u组,每组包含2^v块,主存块存放到哪个组是固定的,至于存到该组哪一块则是灵活的。即主存的某块只能映射到Cache的特定组中的任意一块。主存的某块b与Cache的组k之间满足以下关系:k=b%(2^u).

    例如,Cache分为8组(u=3),每组2块(v=1),主存分为128个区,每个区16块。

     

                                                      图(3)

    主存中的各块与Cache的组号之间有固定的映射关系,但可自由映射到对应Cache组中的任何一块。例如:

    --主存的第0块、第2^u块、第2×(2^u)块、…第255x(2^u)即255x8=2040块等256块均映射于Cache的第0组,但可映射到其中的第0块或第1块

    --主存的第1块、第2^u+1块、第3^(2^u)+1块、…第255x(2^u+1)即2041块等均映射于Cache的第2组,但可映射到Cache第2组中的任意一块;

    --主存的第2块、第2^u+2块、第(2^u)x2+2块、…第2042块等均映射于Cache的第3组,但可映射到Cache第3组中的任意一块;

    --主存的第7块、第2^u+7块、第2^(u+1)+7块、…第2047块等均映射于Cache的第8组,但可映射到Cache第8组中的第14块或第15块。

    常采用的组相联结构Cache,每组内有2、4、8、16块,称为2路、4路、8路、16路组相联Cache。以上为2路组相联Cache。组相联结构Cache是前两种方法的折中方案,适度兼顾二者的优点,尽量避免二者的缺点,因而得到普遍采用。

    实例分析:

    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有u组,每组有v块,即u = 16,v = 4,Cache大小:64块×128B = 8KB

    主存大小:4096×128B = 2^12*2^7 = 2^19,即主存地址有19位。4096/64= 2^6主存区号为6位。

    2.某 32 位计算机的 cache 容量为 16KB,cache 块的大小为 16B,若主存与 cache 的地址映射采用直接映射方式,则主存地址为 1234E8F8(十六进制)的单元装入的 cache 地址为__C__。

    A. 00 0100 0100 1101 (二进制)
    B. 01 0010 0011 0100 (二进制)
    C. 10 1000 1111 1000 (二进制)
    D. 11 0100 1110 1000 (二进制)

    :Cache大小为16KB,块大小为16B,所以Cache被分成16KB/16B=1024块,因210=1024故需要10位来表示块数

    24=16故块内地址需要4位来表示。所以Cache的地址线位置为14位。

    由于采用直接映像的方式,所以主存的后14位就是要装入的到Cache中的位置。故选 C.

    个人见解:Cache的容量是16KB = 16×1024B = 16384B,主存的地址为0x1234E8F8/(16×1024B)= 18643. 该地址对应的是主存的第18643块。

    根据公式:cache的块地址i = 主存的块地址 % 16384 = 1234E8F8 - 1234C000 = 0x28F8 选C

     

     

    展开全文
  • cpu的执行速度很快,cpu从memory读取数据速度很慢,导致cpu需要等memory,为了提高cpu的效率,根据程序的局部性原理(现在访问的数据很有可能以后还会访问),引入了读写比较快的memory cache,cache用来存放刚刚访问...

    cpu的执行速度很快,cpu从memory读取数据速度很慢,导致cpu需要等memory,为了提高cpu的效率,根据程序的局部性原理(现在访问的数据很有可能以后还会访问),引入了读写比较快的memory cache,cache用来存放刚刚访问的memory的数据,这样下次再需要从memory读写数据时,可以直接从cache里面读,速度快了很多,提高了cpu的效率。

    cache比memory速度快,但是也比memory价钱贵,所以cache一般比较小,比如memory可能有4G、但cache只有64k。既然cache不能存放所有的memory数据,那memory中的数据应该存放在cache的什么位置呢?希望达成的效果是最近经常访问的数据都在cache里面,并且查找也要快速。

    考虑下面一个程序,假设这个程序在memory中的存放如下图1,这个时候在运行程序的时候肯定是希望code和data都被cache。为了达到这个目标,有3种方案可以选择,图2直接映射,图3全相联映射,图4组相联映射。

    int a = 0;
    
    int main()
    {
        while(a < 100) {a++;}
    }

     

                                                       图1 程序的内存分布

                                                       图2 直接映射

    假设cache有4个cache line,memory比较多,另外各图的方框表示的空间大小相同,即一个memory的方框和一个cache的方框(cache line)大小相同。

    直接映射,就是把memory按照cache line的数量分组,有4个cache line,那么memory每4个一组,每一组直接对应cache的相应line。memory第一组的0-3分别映射到cache的line 0-3。第二组的4-7分别映射到cache的line 0-3。

    通过直接映射,code被放到了cache line 0和1,data也被映射到了cache line 0。这个时候的问题是,执行代码的时候命中cache,读写数据的时候不命中,然后更新cache,把cache的内容换为data。再执行的代码的时候发现code被从cache中移除了,导致cache不命中,然后又更新cache,换成code。读写数据的时候就又会cache不命中,更新cache;然后又代码cache不命中....嗯,需要尝试一下其他的映射方式了

                                                       图3 全相联映射

    全相联映射,不规定memory在cache中的位置了,随意放。比如memory 0可以放在任意的cache line。其他memory也是,所有的cache line都可以放。

    通过全相联映射,可能的结果是1)code放在了cache line 0 & 1,data放在了cache line 2,也可能2)code 0放在cache line 3,code 1放在cache line 2,data放在cache line 0。至少都在cache里面了。存在的问题是,当cpu拿着内存地址来找是否在cache中时,就会比较费力了。只拿着一个内存地址来找cache的话,只能把cache遍历一遍了,不太好。嗯,再考虑另外一种映射方案吧

                                                       图4 组相联映射(每组2个为例)

    组相联映射,希望可以把程序都放在cache,同时希望查找要方便。回想直接映射的时候,因为memory 0和memory 4都映射到了cache line 0,所以导致频繁的cache不命中/更新。如果cache line 0可以同时把memory 0和memory 4都保存了,就会一直cache命中了……

    但是一个cache line只能存放一个memory方框的内容(因为一个cache line的大小等于一个memory方框的大小),怎么办呢?考虑把cache line 0和cache line 1当成一个大的cache line吧,也就是把两个相邻的cache line当作一组、组成一个大的cache line,然后采用直接映射。

    这样,之前的4个cache line变成了2个大的cache line,按照直接映射的规则,把memory按照cache line的数量分组,有2个大的cache line,那么memory每2个一组,每一组直接对应cache的相应line。这样memory第一组的0-1分别映射到大cache line 0-1(组0和组1),第二组的2-3分别映射到大cache line 0-1,第三组的4-5分别映射到大cache line 0-1。

    映射到大的cache line之后需要决定具体放到哪个小的cache line,这个时候是随意的,哪个都可以。比如memory 0映射到组0(大的cache line 0)后,放在cache line 1;memory 1映射到组1(大的cache line 1)后,放在cache line 2;memory 4映射到组0(大的cache line 0)后,放在cache line 0。

    这种映射可以把相关的代码数据都放在cache,同时查找也方便点,因为一个组里面的cache line数量比较少。这种方式也算是可以达成最初的期望:最近经常访问的数据都在cache里面,并且查找也要快速。

    展开全文
  • Cache与主存之间的全相联映射、直接映射和组相联映射的区别高速缓冲存储器的功能、结构与工作原理高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得多,...

    Cache与主存之间的全相联映射、直接映射和组相联映射的区别

    高速缓冲存储器的功能、结构与工作原理

    高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得多,接近于CPU的速度。 Cache的功能是用来存放那些近期需要运行的指令与数据。目的是提高CPU对存储器的访问速度。为此需要解决2个技术问题:一是主存地址与缓存地址的映象及转换; 二是按一定原则对Cache的内容进行替换。

    Cache组成与工作原理

    主要由三大部分组成:
    1. Cache存储体:存放由主存调入的指令与数据块。
    2. 地址转换部件:建立目录表以实现主存地址到缓存地址的转换。
    3. 替换部件:在缓存已满时按一定策略进行数据块替换,并修改地址转换部件。

    地址映象与转换

    地址映象是指某一数据在内存中的地址与在缓冲中的地址,两者之间的对应关系。下面介绍三种地址映象的方式。

    全相联方式

    地址映象规则:主存的任意一块可以映象到Cache中的任意一块
    1. 主存与缓存分成相同大小的数据块。
    2. 主存的某一数据块可以装入缓存的任意一块空间中。

    全相联映射方式
    如果Cache的块数为Cb,主存的块数为Mb,则映象关系共有Cb×Mb种。

    目录表存放在相关(联)存储器中,其中包括三部分:数据块在主存的块地址、存入缓存后的块地址、及有效位(也称装入位)。
    由于是全相联方式,因此,目录表的容量应当与缓存的块数相同。

    全相联地址转换

    举例:某机主存容量为1M,Cache的容量为32KB, 每块的大小为16个字(或字节)。 划出主、缓存的地址格式、 目录表格式及其容量。

    全相联地址格式

    容量:与缓冲块数量相同即211=2048(或32K/16=2048)。  
    优点:命中率比较高,Cache存储空间利用率高。
    缺点:访问相关存储器时,每次都要与全部内容比较,速度低,成本高,因而应用少。

    直接相联方式

    地址映象规则: 主存储器中一块只能映象到Cache的一个特定的块中。
    1. 主存与缓存分成相同大小的数据块。
    2. 主存容量应是缓存容量的整数倍,将主存空间按缓存的容量分成区,主存中每一区的块数与缓存的总块数相等。
    3. 主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。
      图2.3.4示出了直接相联映象规则。 可见,主存中各区内相同块号的数据块都可以分别调入缓存中块号相同的地址中,但同时只能有一个区的块存入缓存。由于主、缓存块号相同,因此,目录登记时,只记录调入块的区号即可。

    直接相联映射方式

    图2.3.5示出了主、 缓冲地址格式、目录表的格式及地址变换规则。主、缓存块号及块内地址两个字段完全相同。目录表存放在高速小容量存储器中,其中包括二部分:数据块在主存的区号和有效位。目录表的容量与缓存的块数相同。

    直接相联地址转换

    地址变换过程:用主存地址中的块号B去访问目录存储器, 把读出来的区号与主存地址中的区号E进行比较, 比较结果相等,有效位为1,则Cache命中,可以直接用块号及块内地址组成的缓冲地址到缓存中取数;比较结果不相等,有效位为1, 可以进行替换,如果有效位为0,可以直接调入所需块。

    优点:地址映象方式简单,数据访问时,只需检查区号是否相等即可,因而可以得到比较快的访问速度,硬件设备简单。
    缺点:替换操作频繁,命中率比较低。

    举例:上例中,主存容量为1M, Cache的容量为32KB,每块的大小为16个字(或字节)。划出主、缓存的地址格式、目录表格式及其容量。
    容量:与缓冲块数量相同即211=2048(或32K/16=2048)。

    组相联映象方式

    直接映射虽然简单方便,但是如果程序同时用到了对应于同一个cache行中的两个主存地址,那么就会发生冲突,结果就是导致这个cache行不停的进行替换操作。所以就有了组相联映射。

    将这cache存储器中的256个行分为了4路,每路有64个cache行。这时根据组索引找到的 cache行不再是一个,而是同时找到 4个 cache行,所以才被称为组索引。每路中包含一个cache行。如下图12.7所示,便是一个组相联映射的cache。 因为现在每路中有 64 个 cache 行,所以组索引的宽度变成了6位,而标签域的标签宽度变成了12位。 直接映射中组索引一次只能对应一个cache 行,而现在组相联映射中组索引一次能对应4个cache行,所以现在主存中的一个地址可以存放到4个cache行中的任意一行。 而在直接映射中,主存中的一个地址只能存放到对应的一个cache行中。所以一个cache行被替换的概率减少为原来的四分之一。

    一个4KB四路组相联cache

    组相联映象关系

    优点:块的冲突概率比较低,块的利用率大幅度提高,块失效率明显降低。
    缺点:实现难度和造价要比直接映象方式高。

    Reference

    ARM的cache和写缓存

    展开全文
  • 浅谈cache的直接映射、全相联映射和组相联映射

    千次阅读 多人点赞 2019-06-24 11:27:34
    以下用图书馆坐座位的例子来说一说直接映射、全相联映射和组相联映射。 对于直接映射,每个块在cache中只能有一个位置,非常局限,就好像图书馆里有那么多空位,你却只能坐在一个地方,即使别的地方是空的你也不能坐...

    对于cache的几种映射方式进行一个小总结,方便以后自己不会了来看看

    以下用图书馆坐座位的例子来说一说直接映射、全相联映射和组相联映射。

    对于直接映射,每个块在cache中只能有一个位置,非常局限,就好像图书馆里有那么多空位,你却只能坐在一个地方,即使别的地方是空的你也不能坐

    对于全相联,只要有空位你坐哪儿都行

    对于组相联,是一种折中的方案。假设图书馆有1000个座位,我们把这1000个座位分成10个区(这叫“10路”,也就是ten-way)每个部分都有100个座位(这叫“100个组”)。你去图书馆的时候,你坐在哪个区都行,但是你只能坐在每个区的某一个位置上(块从内存映射到cache的时候,可以选任意一路,但是只能选这一路内的一组)。比如,这个图书馆规定,用自己的学号取模100来选座位,那么你的座位编号就是97。这个图书馆中有10个区,也就有10个编号为97的座位,你可以选择这10个座位中的任意一个(cache有10路,每路都有一个编号为97的块,你可以存入这10个编号为97的块中的任何一块)。如果你很不幸运,所有97号的座位都有人坐了,而你不能选择任何其他编号的座位,所以你只好去找一个97号座位上的人,跟他说“老哥,你起来,让我坐一会儿吧”。那个老哥一定会把座位让给你,因为你们所有人都被要求当受到请求时让出自己的座位。(如果cache中97组的所有块都满了,就只能从所有的97块中选一块淘汰)。

    其实直接映射和全相联是组相联的极端。如果把1000个座位分成1路,这一路中有1000组,那么每一组内只有一个位置可选,这实际上就是直接映射;如果把1000个座位分成1000路,每一路中只有一组,那么这一组内有1000个位置可选,这实际上就是全相联。

    也许理解上还有不对的地方,以后还会完善~
    越努力,越幸运!

    展开全文
  • Cache与主存之间的全相联映射,直接映射和组相联映射的区别1.高速缓冲存储器的功能、结构与工作原理 高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得多...
  • Cache与主存之间的全相联映射,直接映射和组相联映射的区别 1.高速缓冲存储器的功能、结构与工作原理  高速缓冲存储器是存在于主存与CPU之间的一级存储器,由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得...
  • 高速缓冲存储器的功能、结构与工作原理 高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得多, 接近于CPU的速度。 Cache的功能是用来存放那些近期需要运行...
  • 详细介绍了cache缓存与主存之间的三种映射方式及其区别
  • Cache与主存之间的全相联映射,直接映射和组相联映射的区别 1.高速缓冲存储器的功能、结构与工作原理  高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得...
  •  Cache与主存之间的全相联映射,直接映射和组相联映射的区别 1.高速缓冲存储器的功能、结构与工作原理  高速缓冲存储器是存在于主存与CPU之间的一级存储器,由静态存储芯片(SRAM)组成,容量比较小...
  • **注: ...1、一个采用直接映射方式的16KB缓存,假设块长为8个32位的字,则地址为FDA459H的主存单元映射到缓存的第 290 (十进制表示)块内。 直接映射: 内存字地址等于缓存(cache)块内地...
  • Cache与主存之间的全相联映射,直接映射和组相联映射的区别 1.高速缓冲存储器的功能、结构与工作原理  高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得...
  • 容易理解的计算机组成原理中主存与Cache的3种映射方式(直接映射,全相联映射,组相联映射) 一.为了让大家更加方便的理解,我首先设置了两个问题,同时也写了相应的个人所理解的答案 1.为什么引入Cache? 答: ...
  • 某计算机的Cache共有16块,采用2路-组相联映射方式(即每组包括2块)。存储器按字节编址,每个主存块大小为32字节,请问: Cache如何分组、分块? 主存如何分组、分块? 计算129号主存单元所在的主存块应装入到的...
  • 设计一个四路组相联映射(即Cache内每组包含4个字块)的Cache组织方式。 1)求满足组相联映射的主存地址字段中各字段的位数 2)设Cache的初态为空,CPU从主存第0号单元开始连续访问100个字(主存一次读出一个字),重复此...
  • 块在第几 = 块数/总数 取余 先判断号,然后用区号来做标记。 字号:128 7位 区内块号 = cache号 = 64/4 = 16 4位 主存储器一共占 4K * 128 = 19位 区号:主存储器总块数/总数 = 一个有多少块 = 有多少...
  • Cache与主存之间的直接映射,全相联映射项联映射以及其地址变换 首先先解释一些比较基础的东西 1.cache是什么? Cache是高速缓冲储存器,位于CPU和主存之间,比较小,速度比较快。 2.为什么要有cache? Cache类似...
  • 高速缓存-直接映射&全相联&组相联

    千次阅读 2019-06-12 15:58:50
    1⃣️选择 2⃣️行匹配 3⃣️字抽取 选择 从w的地址中抽出s个索引位确定是哪个 行匹配 在直接高速缓存(每一只有一行)中很容易: 标记为有效 && (高速缓存行中的标记位==w地址中的标记位) 字选择 ...
  • 一、通用的高速缓存存储器组织结构 首先让我们了解一下基本结构、 ... ·高速缓存被组织成一个有S=2^s个高速缓存的数组。(即一共有S个) ·每个包含E个高速缓存行。(即一里有E行) ·每一行是包括...
  • 高速缓存存储器的地址映射 信息在主存和Cache中,确定它们的对应关系就需要借助地址映射。 地址映射的定义: 主存地址按某种规律(函数)映射到cache中。 当cpu访问存储器时,它发出...组相联方式 几个概念 ...

空空如也

1 2 3 4 5 ... 8
收藏数 153
精华内容 61
关键字:

组相联映射