湘潭大学第4章 高速缓冲存储器和虚拟存储器

1、高速缓冲存储器Cache和虚拟存储器TLB5.5 高速缓冲存储器Cache Cache的基本原理主存与Cache的地址映射方式替换算法写策略Cache的多层次设计一、Cache的基本原理 Cache的工作原理Cache的特点Cache的命中率1231、Cache的特点 Cache是指位于CPU和主存之间的一个高速小容量的存储器，一般由SRAM构成。 Cache功能：用于弥补CPU和主存之间的速度差异，提高CPU访问主存的平均速度。 设置Cache的理论基础，是程序访问的局部性原理。 Cache的内容是主存部分内容的副本，Cache的功能均由硬件实现，对程序员是透明的。 Cache存储器工作原理

2、（局部性工作原理）对大量典型程序的运行情况进行分析得到：在一个较短的时间间隔内，由程序产生的地址往往集中在地址空间的很小范围内。原因：程序地址的分布一般是连续的，再加上循环程序、子程序等要重复执行多次。因此对程序地址的访问自然具有相对集中的倾向。数据分布不如指令明显，但对数组的存储和访问使存储器地址相对集中。2、Cache的工作原理 程序的簇聚性(局部性)指在每一小段时间内，程序所要用到的指令或数据的地址往往集中在一个局部区域内，因而对局部范围内的存储器地址频繁访问，而对此范围外的地址则访问甚少的现象。 两种局部性：时间局部性：最近被访问的信息很可能还要被访问。 将最近被访问的信息项装入到Ca

3、che中。空间局部性：最近被访问的信息临近的信息也可能被访问。 将最近被访问信息项附近的信息一起装入到Cache中。 如果能把正在执行的指令地址附近的一部分指令或数据从主存成批调入一个能高速访问高速访问的小容量存储器的小容量存储器( (Cache) ，供CPU在一段时间内随时使用，从而大大减少CPU访问主存的次数，加快程序的运行速度。 Cache的速度比主存快510倍。Cache、主存与CPU的关系 CPU主存Cache字传送块传送CPU主存主存相联存储器相联存储器Cache存储体存储体硬件逻辑电路硬件逻辑电路地址总线地址总线数据总线数据总线Cache的原理图Cache的读写操作 CPU在读写

4、存储器时，Cache控制逻辑首先要依据地址来判断这个字是否在Cache中，若在Cache中，则称为“命中”；若不在，则称为“不命中”。 针对命中/不命中、读/写操作，Cache的处理是不同的：读命中：立即从Cache读出送给CPU。读不命中：通常有两种解决方法：(1)将主存中该字所在的数据块复制到Cache中，然后再把这个字传送给CPU。(2)把此字从主存读出送到CPU，同时，把包含这个字的数据块从主存中读出送到Cache中。Cache的读写操作写不命中：直接将该字写入主存中，且不再调入Cache；写命中：通常也有两种方法进行处理：写贯穿方法：同时对Cache和主存进行写操作；写回：只写Cac

5、he，仅当此Cache块被替换时，才将该块写入主存3、Cache的命中率 命中率指CPU访问主存数据时，命中Cache的次数，占全部访问次数的比率。 失效率就指不命中Cache的次数，占全部访问次数的比率。 命中率h取决于程序的行为、Cache的容量、组织方式、块大小。 在一个程序执行期间，设Nc表示Cache完成存取的总次数，Nm表示主存完成存取的总次数，则命中率：actte mccNNNh mcath1htt）（ ）（）（cmcatth1htt v若tc表示Cache的访问时间，tm表示主存的访问时间，则Cache/主存系统的平均访问时间ta为：vCache/主存系统的访问效率e:二、主存

6、与Cache的地址映射方式 讨论前提：Cache的数据块称为行，主存的数据块称为块，行与块是等长的；主存容量为2m块，Cache容量为2c行，每个字块中含2b字。主存中只有一小部分块的内容可放在Cache中。 Cache存储单元的组成部分:数据字段：保存从主存单元复制过来的数据。标志字段：保存相应主存单元的地址信息。有效位字段：标识数据字段和标志字段的是否有效。 讨论的问题：如何根据主存地址，判断Cache有无命中并变换为Cache的地址，以便执行读写。有三种地址映射方式：直接映射全相联映射组相联映射1、直接映射 直接映射是一种多对一的映射关系：主存的第i块一定映射到Cache的第j行，且：

7、j=i mod 2c 直接映像方式特点：主存的字块只可以和固定的Cache字块对应，映射方式直接、简单，易实现，利用率低。标志位较短，比较电路的成本低。如果主存空间有2m块，Cache中字块有2c块，则标志位只要有m-c位，且仅需要比较一次。机制不灵活，Cache命中率低。c2DIVik 标记K：直接映像硬件实现举例A d dre ss (sh ow ing b it p ositio ns)2010By teo ffse tV alidT agD a taIn de x01210 2110 2210 23T a gInd exH itD ata20323 1 30 1 3 12 11 2 1

8、 0 注意P358-359与这里讲的区别。书上访问Cache是访问2个字(4字节/字)，这里是用W进行选择，不需要在外面加一个2选择1多路器来选择。2、全相联映射 全相联映射是多对多的映射关系：对于主存的任何一块均可以映射到Cache的任何一行。 特点：主存的字块可以和Cache的任何字块(行)对应，利用率高，方式灵活，命中率高。标志位较长，比较电路的成本太，高难于设计和实现。如果主存空间有2m块，则标志位要有m位。如果Cache有n块，则需要有n个比较电路。全相联硬件实现举例3、组相联映射 组相联映像是将Cache的行分成c=2c-r组，每组2r行。主存的字块存放到Cache中的哪个组是固定

9、的，至于映射到该组哪一行是灵活的，即有如下函数关系： j(i mod 2c)*2r+k 其中 0k2r-1 组相联映像方式特点：组间为直接映像，组内为全相联映像。大大增加了映射的灵活性，主存中一块可映射到Cache 的2r块，提高了命中率。每次比较只是进行2r路比较，r 较小时，硬件开销不是很大。集中了两个方式的优点。成本也不太高。 组相联映像通常采用2路、4路和8路比较，即取r=1,r=2,r=3。组相联硬件实现举例Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData1

10、238910111230310三种映像方式比较 全相联映射主存中的一块可以映射到Cache中任何一个位置 直接映像主存中的一块只能映射到Cache中唯一的一个位置定位时，不需要判断，只需替换 多路组相联映射主存中的一块可以选择映射到Cache中多个位置 全相联映射和多路组相联映射的失效处理从主存中取出新块为了腾出Cache空间，需要替换出一个Cache块不唯一，则需要判断应替出哪块三、替换算法1、随机替换算法2、先进先出算法（FIFO）3、最近最少使用算法（LRU）该算法统计哪一个Cache行是近段时间使用次数最少的Cache行，需替换时就将它替换出去。LRU替换算法可以通过为每个Cache行

11、设置一个计数器来实现LRU替换算法，Cache每命中一次，命中行的计数器被清零，其他行的计数器加1，需要替换的话，就将计数器值最大的行替换出去。LRU算法的平均命中率比FIFO要高，并且当分组容量加大时，能提高LRU替换算法的命中率。如下图。 图 LRU算法替换登记表（数字为块号） 例：假定cache是直接映射的，每块4字。Cache的容量是16字，初始时cache为空。对于下述访问主存地址序列(字地址)： 1,4,8,5,20,17,19,56,9,11,4,43,5,6,9,17。标出每次访问的cache命中情况以及最后cache的内容，并计算命中率。如果Cache访问时间为0.1s，主存

12、的访问时间为1s，问CPU访问内存的平均时间是多少？ 解：cache的块数=16/4=4块。 根据 Cache块号=主存地址/4 (mod 4) 可得到下表：块0块1块2块3Cache中最后的内容如下：主存地址范围块号030471811212-153161902023124-2722831332-3503639140-43244473485105255156-592序号12345678910111213141516地址14852017195691144356917块号0121100222121120命中0001001001001100块0块1块2块3地址17地址6地址9空命中率=5/16=31

13、.25%CPU访问内存的平均时间Ta=H*Tc+(1-H)*Tm =0.3125*0.1+0.6875*1 =0.71875四、写策略 常用的写策略通常有写贯穿和写回两种 写贯穿策略 当CPU写Cache命中时，所有写操作既对Cache也对主存进行；当CPU写Cache不命中时，直接写主存，有两种做法： 不将该数据所在的块拷贝到Cache行，称为WTNWA法； 将该数据所在块拷贝到Cache的某行，称为WTWA法。 写回策略（Write Back） 当CPU写Cache命中时，写操作只是对Cache进行，而不修改主存的相应内容，仅当此Cache行被换出时，相应的主存内容才被修改；当CPU写Ca

14、che不命中时，先将该数据所在块拷贝到Cache的某行，余下操作与Cache写命中时相同。 为了区别Cache行是否被改写过，应为每个Cache行设置一个修改位，CPU修改Cache行时，标记其修改位，当此Cache行被换出时，判别此Cache行的修改位，从而决定是否将Cache行数据写回主存相应单元。 3、两种写策略比较写贯穿策略保证了主存数据总是有效，写回策略可能导致Cache和主存数据不一致；写回策略的效率高于写贯穿策略；写回策略的控制比写贯穿策略的控制复杂。五、Cache的多层次设计 设计Cache主要考虑五个问题：容量Cache中行的大小Cache的组织（地址映射方式）指令和数据共用

15、同一个Cache还是分享不同CacheCache的层次 统一Cache和分离Cache 统一Cache：只有一个Cache，指令和数据混放。 分离Cache：分为指令Cache和数据Cache。它消除了流水线中指令处理器和执行单元间的竞争，因此，特别适用于Pentium 和Power PC这样的超标量流水线中；是Cache结构发展的趋势。 单级Cache与两级Cache 一级Cache（）和二级Cache 采用两级Cache结构可以提高性能 Cache一致性问题 无效专有修改共享+RMSRHRMEWMRHWHWHRHWH无效专有修改共享SHWSHRSHWSHWSHRSHR（A）发起处理器的Ca

16、che行（B）监听Cache行MESI协议的状态图 RH读命中；RMS读不命中，共享；RME读不命中，专有；WH写命中；WM写不命中；SHR读监听命中；SHW写监听命中或读是用于修改；+无效处理；Cache行填入；无效行拷回；读用于修改 CACHE使用中的几个问题 CACHE的重要技术指标：命中率 影响 CACHE 命中率的因素CACHE CACHE 的容量，大一些好的容量，大一些好CACHE CACHE 与主存储器每次交换信息的单位量与主存储器每次交换信息的单位量(Cache Line Size)(Cache Line Size)适中适中CACHE CACHE 不同的组织方式，多路组相联更好

17、不同的组织方式，多路组相联更好CACHE CACHE 的多级组织可提高命中率的多级组织可提高命中率CACHE CACHE 装满后的替换算法装满后的替换算法cache的容量与命中率的关系 Cache Size in KBHit Ratecache line size与缺失率的关系 多级的cache结构与命中率的关系 为增加cache容量，可以在已有的cache(第一级)存储器系统之外，再增加一个容量更大的cache(第二级) 。 第二级cache的容量比第一级cache的容量要大得多，在第一级cache中保存的信息也一定保存在第二级cache中。 当CPU访问第一级cache出现缺失情况时，就去

18、访问第二级cache。 若第一级、第二级cache的命中率为90%，则它们合起来后的命中率为1-(1-90%)(1-90%)=99%，而不会是81%。5.6 虚拟存储器 虚拟存储器的实现方式有三种：段式、页式或段页式 页式虚拟存储器 页式虚拟存储器中逻辑地址与物理地址的转换关系 5.6 虚拟存储器 段式虚拟存储器段式虚拟存储器 段内偏移段号段表基地址段长逻辑地址物理地址段表+ .段首地址 .段号01+段式虚拟存储器中逻辑地址与物理地址的转换关系 5.6 虚拟存储器 段页式虚拟存储器 段号页号页内地址页内地址物理页号逻辑地址物理地址.段表页表+段页式虚拟存储器中逻辑地址与物理地址的转换关系 5.

19、9 IA32架构的存储系统举例 P6P6微架构下的微架构下的CacheCache Intel NetBurstIntel NetBurst微架构下的微架构下的CacheCache Intel CoreIntel Core微架构的多核高效内存管理技术微架构的多核高效内存管理技术 一一二二三三一、P6微架构下的Cache L2 Cache(256KB-1MB)总线接口单元取指令和译码单元派遣和执行单元回收单元指令池（重定序缓冲区-ROB）L1 指令Cache(8KB-16KB)L1 数据Cache(8KB-16KB)取装入存储系统总线Pentium处理器框图 一、P6微架构下的CacheLRU 目

20、录 0目录 1标记状态路0（4KB）路1（4KB）32字节32 字节组0组127.状态目录标记（页面地址）组地址起始字节主存物理地址=3512115 40L1级数据Cache的结构 二、Intel NetBurst微架构下的Cache 指令取指令取/译译码单元码单元踪迹踪迹Cache(12K ops）整数寄存器组整数寄存器组装入装入地址地址单元单元存储存储地址地址单元单元8KB的的L1级数据级数据Cache256KB的的L2级级Cache(8路路)1MB的的L3级级Cache简单简单整数整数ALU简单简单整数整数ALU复杂复杂整数整数ALU浮点寄存器组浮点寄存器组FP/MMX单元单元FP传送传

21、送单元单元乱序执行逻辑乱序执行逻辑256位位64位位系统总线系统总线Pentium4的简化图 三、Intel Core微架构的多核高效内存管理技术 浮点运算单元浮点运算单元运算核心运算核心L1 Cache浮点运算单元浮点运算单元运算核心运算核心L1 CacheL2 Cache前端总线前端总线 Intel Core的微架构的两个核心 Intel Core微架构在一个芯片内封装了两个计算内核，两个核各具有一个8路32KB的L1级指令Cache和32KB的双端口L1级数据Cache。两核共享一个16路、容量为2MB或4MB的L2级Cache 三、Intel Core微架构的多核高效内存管理技术 CACHE管理 L2 CacheL1CacheL1CacheCORE 1CORE 0主主 存存L2 CacheL1CacheL1CacheCORE 1CORE 0主主 存存Core微架构的共享L2级Cache非共享L2级CacheL2 CacheCore微