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

高速缓冲存储器Cache和虚拟存储器TLB5.5高速缓冲存储器CacheCache二五三四一Cache的基本原理主存与Cache的地址映射方式替换算法写策略Cache的多层次设计一、Cache的基本原理Cache的工作原理Cache的特点Cache的命中率1231、Cache的特点Cache是指位于CPU和主存之间的一个高速小容量的存储器，一般由SRAM构成。Cache功能：用于弥补CPU和主存之间的速度差异，提高CPU访问主存的平均速度。设置Cache的理论基础，是程序访问的局部性原理。Cache的内容是主存部分内容的副本，Cache的功能均由硬件实现，对程序员是透明的。Cache存储器工作原理（局部性工作原理）对大量典型程序的运行情况进行分析得到：在一个较短的时间间隔内，由程序产生的地址往往集中在地址空间的很小范围内。原因：程序地址的分布一般是连续的，再加上循环程序、子程序等要重复执行多次。因此对程序地址的访问自然具有相对集中的倾向。数据分布不如指令明显，但对数组的存储和访问使存储器地址相对集中。2、Cache的工作原理程序的簇聚性(局部性)指在每一小段时间内，程序所要用到的指令或数据的地址往往集中在一个局部区域内，因而对局部范围内的存储器地址频繁访问，而对此范围外的地址则访问甚少的现象。两种局部性：时间局部性：最近被访问的信息很可能还要被访问。将最近被访问的信息项装入到Cache中。空间局部性：最近被访问的信息临近的信息也可能被访问。将最近被访问信息项附近的信息一起装入到Cache中。如果能把正在执行的指令地址附近的一部分指令或数据从主存成批调入一个能高速访问的小容量存储器(Cache)

，供CPU在一段时间内随时使用，从而大大减少CPU访问主存的次数，加快程序的运行速度。Cache的速度比主存快5－10倍。Cache、主存与CPU的关系Cache的原理图Cache的读写操作CPU在读写存储器时，Cache控制逻辑首先要依据地址来判断这个字是否在Cache中，若在Cache中，则称为“命中”；若不在，则称为“不命中”。针对命中/不命中、读/写操作，Cache的处理是不同的：读命中：立即从Cache读出送给CPU。读不命中：通常有两种解决方法：(1)将主存中该字所在的数据块复制到Cache中，然后再把这个字传送给CPU。(2)把此字从主存读出送到CPU，同时，把包含这个字的数据块从主存中读出送到Cache中。Cache的读写操作写不命中：直接将该字写入主存中，且不再调入Cache；写命中：通常也有两种方法进行处理：写贯穿方法：同时对Cache和主存进行写操作；写回：只写Cache，仅当此Cache块被替换时，才将该块写入主存3、Cache的命中率命中率指CPU访问主存数据时，命中Cache的次数，占全部访问次数的比率。失效率就指不命中Cache的次数，占全部访问次数的比率。命中率h取决于程序的行为、Cache的容量、组织方式、块大小。在一个程序执行期间，设Nc表示Cache完成存取的总次数，Nm表示主存完成存取的总次数，则命中率：若tc表示Cache的访问时间，tm表示主存的访问时间，则Cache/主存系统的平均访问时间ta为：Cache/主存系统的访问效率e:二、主存与Cache的地址映射方式讨论前提：Cache的数据块称为行，主存的数据块称为块，行与块是等长的；主存容量为2m块，Cache容量为2c行，每个字块中含2b字。主存中只有一小部分块的内容可放在Cache中。Cache存储单元的组成部分:数据字段：保存从主存单元复制过来的数据。标志字段：保存相应主存单元的地址信息。有效位字段：标识数据字段和标志字段的是否有效。讨论的问题：如何根据主存地址，判断Cache有无命中并变换为Cache的地址，以便执行读写。有三种地址映射方式：直接映射全相联映射组相联映射1、直接映射直接映射是一种多对一的映射关系：主存的第i块一定映射到Cache的第j行，且：

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

j＝(imod2c’)*2r+k其中0≤k≤2r-1组相联映像方式特点：组间为直接映像，组内为全相联映像。大大增加了映射的灵活性，主存中一块可映射到Cache的2r块，提高了命中率。每次比较只是进行2r路比较，r较小时，硬件开销不是很大。集中了两个方式的优点。成本也不太高。组相联映像通常采用2路、4路和8路比较，即取r=1,r=2,r=3。组相联硬件实现举例三种映像方式比较全相联映射主存中的一块可以映射到Cache中任何一个位置直接映像主存中的一块只能映射到Cache中唯一的一个位置定位时，不需要判断，只需替换多路组相联映射主存中的一块可以选择映射到Cache中多个位置全相联映射和多路组相联映射的失效处理从主存中取出新块为了腾出Cache空间，需要替换出一个Cache块不唯一，则需要判断应替出哪块三、替换算法1、随机替换算法2、先进先出算法（FIFO）3、最近最少使用算法（LRU）该算法统计哪一个Cache行是近段时间使用次数最少的Cache行，需替换时就将它替换出去。LRU替换算法可以通过为每个Cache行设置一个计数器来实现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.1μs，主存的访问时间为1μs，问CPU访问内存的平均时间是多少？解：cache的块数=16/4=4块。

根据Cache块号=主存地址/4(mod4)

可得到下表：块0块1块2块3Cache中最后的内容如下：主存地址范围块号0—304—718—11212--15316—19020—23124--27228—31332-35036—39140--43244—47348—51052—55156--592序号12345678910111213141516地址14852017195691144356917块号0121100222121120命中0001001001001100块0块1块2块3地址17地址6地址9空命中率=5/16=31.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法。

写回策略（WriteBack）当CPU写Cache命中时，写操作只是对Cache进行，而不修改主存的相应内容，仅当此Cache行被换出时，相应的主存内容才被修改；当CPU写Cache不命中时，先将该数据所在块拷贝到Cache的某行，余下操作与Cache写命中时相同。为了区别Cache行是否被改写过，应为每个Cache行设置一个修改位，CPU修改Cache行时，标记其修改位，当此Cache行被换出时，判别此Cache行的修改位，从而决定是否将Cache行数据写回主存相应单元。

3、两种写策略比较写贯穿策略保证了主存数据总是有效，写回策略可能导致Cache和主存数据不一致；写回策略的效率高于写贯穿策略；写回策略的控制比写贯穿策略的控制复杂。五、Cache的多层次设计设计Cache主要考虑五个问题：容量Cache中行的大小Cache的组织（地址映射方式）指令和数据共用同一个Cache还是分享不同CacheCache的层次统一Cache和分离Cache统一Cache：只有一个Cache，指令和数据混放。分离Cache：分为指令Cache和数据Cache。它消除了流水线中指令处理器和执行单元间的竞争，因此，特别适用于PentiumⅡ和PowerPC这样的超标量流水线中；是Cache结构发展的趋势。单级Cache与两级Cache一级Cache（）和二级Cache采用两级Cache结构可以提高性能Cache一致性问题

MESI协议的状态图RH——读命中；RMS——读不命中，共享；RME——读不命中，专有；WH——写命中；WM——写不命中；SHR——读监听命中；SHW——写监听命中或读是用于修改；+——无效处理；↑——Cache行填入；↓——无效行拷回；×——读用于修改CACHE使用中的几个问题CACHE的重要技术指标：命中率影响CACHE命中率的因素CACHE的容量，大一些好CACHE与主存储器每次交换信息的单位量(CacheLineSize)适中CACHE不同的组织方式，多路组相联更好CACHE的多级组织可提高命中率CACHE装满后的替换算法cache的容量与命中率的关系CacheSizeinKBHitRatecachelinesize与缺失率的关系多级的cache结构与命中率的关系

为增加cache容量，可以在已有的cache(第一级)存储器系统之外，再增加一个容量更大的cache(第二级)。第二级cache的容量比第一级cache的容量要大得多，在第一级cache中保存的信息也一定保存在第二级cache中。当CPU访问第一级cache出现缺失情况时，就去访问第二级cache。若第一级、第二级cache的命中率为90%，则它们合起来后的命中率为1-(1-90%)×(1-90%)=99%，而不会是81%。5.6虚拟存储器虚拟存储器的实现方式有三种：段式、页式或段页式页式虚拟存储器

页式虚拟存储器中逻辑地址与物理地址的转换关系5.6虚拟存储器段式虚拟存储器段式虚拟存储器中逻辑地址与物理地址的转换关系5.6虚拟存储器段页式虚拟存储器段页式虚拟存储器中逻辑地址与物理地址的转换关系5.9IA32架构的存储系统举例

P6微架构下的Cache

IntelNetBurst微架构下的Cache

IntelCore微架构的多核高效内存管理技术

一二三一、P6微架构下的CachePentiumⅡ处理器框图一、P6微架构下的CacheL1级数据Cache的结构二、IntelNetBurst微架构下的CachePentium4的简化图三、IntelCore微架构的多核高效内存管理技术IntelCore的微架构的两个核心IntelCore微架构在一个芯