第十讲(cache存储器)要点

1、第3章内部存储器iuosfiao6in201 q163. com(phone： 83#,辨主要内容 cache基本原理cache存储器组织替换策略与写操作策略 奔腾pc机的cache,ccache基本原理根据访存局部性原理，可以在主存和cpu之间设置一个高 速的容量相对较小的存储器，如果当前正在执行的程序和数据 存放在这个存储器中，在程序运行时，不必从主存储器取指令 和取数据，只需访问这个高速存储器，以提高程序运行速度。 这个存储器称作高速缓冲存储器cache。cache由高速的sram组成，它的工作速度数倍于主存， 全部功能由硬件实现，并且对程序员是透明的。cach

2、e的基本结构它由cache存储体、地址映象变换机构、cache替换机构cache概念:(1) cpu与主存储器之间的一种高速缓冲装置(2) cache-主存层次结构：由硬件变换地址和控制调度。cache具有如下特点： 位于cpu与主存之间，是存储器层次结构中级别最高的一 级； 容量比主存小，目前一般有数kb到数mb；it 速度一般比主存快5-10倍,通常由存储速度高的sram组成； 其内容是主存的部分副本； 其用途可用来存放指令，也可用来存放数据； 快存的功能全部由硬件实现，并对程序员透明。任何时候都有一些主存块处在cache中。当cpu发出读请求时，将主存地址s位(或s位中的一部分) 与ca

3、che某块的标记相比较，根据其比较结果是否相等而区分 出两种情况： (1)当比较结果相等时，说明需要的数据已在cache中，那么 直接访问cache就行了，在cpu与cache之间，通常一次传送 一个字； 当比较结果不相等时，说明需要的数据尚未调入cache,那么就要把该数据所在的整个字块从主存一次调进来。前一种情况称为访问cache命中，后一种情况称为访问?!?!cache不命中。cache的命中率命中率指cpu所要访问的信息在cache中的比率； 而将所要访问的信息不在cache中的比率称为失效率。增加cache的目的，就是在性能上使主存的平均读出 时间尽可能接近cache的读出时间。因此

4、,cache的命中率应 接近于1。由于程序访问的局部性，这是可能的。在一个程序执行期间：设m表示cache完成存取的总次数， nm表示主存完成存取的总次数， h定义为命中率，则有：h=nc/nc+nm若l表示命中时的cache访问时间，上表示未命中时的主存访问时间，lh表示不命中率，则cache/主存系统的平均访问时间为：ta=htc+(l-h)tm我们追求的目标是:以较小的硬件代价使cache/主存系统的平均访问时间越接近l越好。设r=tn/tc表示主存慢于cache的倍率， e表示访问效率，则有：e=tc/ta=tc/htc+(l-h)tm=l/r+(l-r)h=l/h+(l-h)rit为

5、提高访问效率：命中率h越接近1越好，r值以510为宜，不宜太大。ev命中率h与程序的行为、cache的容量、组织方式、 块的大小有关。e3ea例cpu执行一段程序时，cache完成存取的次数为1900次，主 存完成存取的次数为100次，已知cache存取周期为50ns,主存 存取周期为250ns,求cache/主存系统的效率和平均访问时间。解：h=nc/(nc+nm)=1900/(1900+100)=0.95r=tm/t =250ns/50ns=5in ce=u(r+(l-r)h)=l/(5+(l-5) x 0.95)=83.3%sata=tje=50ns/0.833=60ns例:已知cach

6、e存储周期为40ns,主存存储周期为200ns, cache / 主存系统平均访问时间为50ns,求cache的命中率是多少？解：因为 ta=htc+(l-h)tm所以 h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16cache结构设计必须解决的问题:如何存放，如何访问，如何替换，如何改写?111（1）数据块在cache中存放在哪个位置？即定位问题（地址 映象）o如果一个块存放在某一cache中，怎样确定并找到该 块，即寻址问题（地址变换）。（2）不命中时将从主存储器中访问，并将该块调入cache中，即替换问题。但是如果cache中已无空闲空间，则势必将cac

7、he中的某一块 调出，但应调出那一块（3）在写访问时，写入cache必须在适当的时候写回主存储 器，何时写？写操作时釆用什么策略保证两级存储器间的数据 一致性。写操作失配时是否将访问块取入高层存储器。本讲主要内容 cache基本原理cache存储器组织替换策略与写操作策略 奔腾pc机的cache,c地址映象（映射）与地址变换地址映象把主存块按照某种规则（函数或方法）装入或定位到 cache中的过程称地址映象。地址变换ci信息按这种映象关系装入cache后，执行程序时，将主存 地址变换成cache地址的变换过程叫做地址变换。地址映象和变换密切相关。使用cache的动力在于它的高速，因此也要求这个

8、地址变 换过程尽可能地快，故此过程是以硬件完成的。这带来的另一 好处是cache的透明性，除了程序运行速度提高之外，用户包 括系统软件编制人员，丝毫未感觉到cache的存在。基本的地址映象方式：直接映象；全相连映象；组相连映象在高速缓冲存储器中，把cache和主存机械等分为相同大小的块,每一块是由若干个字（或字节）组成o例：某机主存容量为1mb,划分为2048块，每块512b;cache容量为kb,划分为16块,每块512b。cache标记标记块15块jsz.字 511主存由于cache的块数远小于主存的块数，因此一个cache不能 唯一地、永久地只对应一个贮存块，在cache中，每一块外加有

9、 一个标记，指明它是主存的哪一块的副本（拷贝）。标记的有效位每个标记设置有一个有效位。机 器加电启动时，reset信号将所有标记 的有效位置即无效。程序执行 过程中，cache不命申时，逐步辎指 令块或数据块从主存调入cache中的 某一块，并将这一块标记的有效位置 “1”，当再次用到这一块中的指令或 数据时，可直接从cache中取指令或 数据。标记 cache0 u_ zt, v牙-口字块0字块1ew因刚加电时所有标记位都为开始执行程序时, 命中率较低。另外cache的命中率还与程序本身有关，即 不同的程序，其命中率可能不同。直接映射方式这是一种多对一的映射关系，但一个主存块只能映象到 ca

10、che的一个特定块位置上去。cache的第i块和主存的第j块有如下函数关系：i = j mod mi =0,l,2,.,mlj=0,l,2,.,nl（m为cache的总块数）在这种映象方式中：主存的第0块，第16块，第32块，只能映象到 cache的第0块；iii主存的第1块，第17块，第33块，只能映象到 cache的第1块；块15tag cache主存地址cache地址cache块号块内地址主存地址主存标记包a号）cache块号块内地址iii直接映象的地址变换方法 9位主存标记（组号）cache块号块内地址主存地址主存块31不命中块15块16块17比较块 2047优点:硬件简单,成本低缺点

11、:块冲突率很高ill优点:实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在cache中。缺点:不够灵活，主存的多个字块只能对应唯一的cache字块，因此，即使cache别的地址空着也不 能占用。cache存储空间得不到充分利用，降低 了命中率。例上设有一个cache的容量为2k字，每个块为项字,求(1) 该cache可容纳多少个块？(2) 如果主存的容量是256k字，则有多少个块？(3) 主存的地址有多少位？ cache地址有多少位？ha(4) 在直接映象方式下，主存中的第i块映象到cache中哪一个块 中？(5) 进行地址映象时，存储器的地址分成哪几段？各段分别有 多少

12、位？ 解：(1) cache中有2048/16=128个块。(2) 主存有256k/16=16384个块。(3) cache容量为2k=2n字，所以cache字地址为11位。(4) 主存中的第i块映象到cache中第imod 128个块中。(5) 存储器的字地址分成三段：区号、块号、块内字地址。区号的长度为18.11=7位，块号为7位。块内字地址为4位。允许主存中的每一个字块映象到cache的任何一个字块位置上:灵活但成本】:高的一种方式。31!全相联映象的地址变换方法11位主存块号块内地址主存地址不命中有效位块。有效位块1111有效位块15主存块0块 1.块15块16块17块31. . .块

13、 2047命中这只是一个理想的方案。两个原因使其实际上很少釆用: 标记位数从7位增加到11位，使cache标记容量加大。=1 访问cache时，需要和cache的全部标记进行“比较”才 能判断出所访主存地址的内容是否已在cache中。由于cache 速度要求高，通常由“按内容寻址”的相联存储器完成，所 需硬件逻辑电路很多，以至于无法用于cache中。实际的 cache组织则是釆取各种措施来减少所需比较的地址数目。优点：灵活，块冲突概率小。只有当cache中全部装满后，才 有可能出现块冲突；1=缺点：要作相联搜索，速度慢，代价高。组相联映射方式1、组间全相联，组内直接映像直接 映象和全 相联映象

14、 方袞的一 种折衷方 案。tag标记cache标记块0标记块11.标记块7标记标记块71组v块0块1 块7块8块9 块15.块 2032块 2033 块 2039块 2040 块 2046块 2047。组, 1组、254组255组cache组号块号块内地址1位3位9主存组号块号块内地址注意：当只有一个组并且每组16块时，此时为直接映像; 当有16组并且每组一个块时，则为全相联映像。内存tv块0tv块1tv块2tv块3tvtv块5tv块6tv块7块0块8块1块9 xx 6块7块15 块2040 块2047组相联的地址变换方法8位 3位 9位主存中的一块能对应到cache中一个特定组中的任意一 行

15、上。若组中有n个块，则称其为n路组关联。n个直接映射cache并行工作。直接映象和全相联映象是组相联的特例：直接映象是：1路组相联 全相联是：m路组相联另外一种组相联映射方式2、组内全相联，组间直接映像all!cache与主存均分组，主存中一个组内的块数与cache的分 组数相同，主存中的各块与cache的组号有固定的映象关系，但可自由映象到对应的cache组中任一块。注意：当只有一个组并且每组16块时，此时为全相联映像;当有16组并且每组一个块时，则为直接映像。组相联的地址变换方法主存组号块号块内地址tv组0tv组1tv组2tv组3tv组4tv组5tv组6tv组7组0vt组1vt组2vt组3

16、vt组4vt组5vt组6vt组7vt1不命中比较=命中比较选择器例:设一个cache中有8个块,访问主存进行读操作的块地址序列 为22、26、22、26、16、4、16、18,求每次访问后cache中的 内容解:直接映象下cache访问情况地址22命中与否不命中地址转换关系22 mod 8=62622261616182不命中命中命中不命中不命中命中不命中26 mod 8=222 mod 8=626 mod 8=216 mod 8=04 mod 8=416 mod 8=018 mod直接映象的块分配情况访问顺序12345678操作 调调命命调 调命替状态进进中中进进中换cache容量与命中率ca

17、che的容量和块的大小是影响cache的效率的重要因素。 一般来说，cache的存储容量比主存的容量小得多；twfis容量超过但不能太小，太小会使命中率太低；建離必辭如礬盈髓課畑顺量超过 魂觥将卿颱將髀容量不断增大已由几k 因此，cache容量是总成本价与命中率的折衷值。如：80386的主存最大容量为4g,与其配套的cache容量为 16kb或32kb,其命中率为95%。块长与命中率块长与命中率的关系更为复杂，它取决于程序的局部特 性。块长的最优值很难确定，通常：a每块取4至8个可编址单位（字或字节）较好；也可取一个主存周期所能调出主存的信息长度。例如，cary-1的主存是16个交叉体，每个体

18、为单字宽，其指令cache的块长为16个字；ibm 370/168机主存是4体交叉，每个体宽为64位（8个字），其cache块长为32个字。本讲主要内容 cache基本原理cache存储器组织替换策略与写操作策略 奔腾pc机的cache,c替换策略当一个新的主存块要调入到cache,而允许存放此块的行位 置都被其它主存块占满时，就要产生替换，因为cache工作原理 要求它应尽量保存最新的数据。替换问题与cache的组织方式紧密相关对于釆用直接映射方式的cache来说： 因一个主存块只有一个特定的行位置可存放，所以问题 解决很简单，把此特定行位置上的原主存块妥善处理后，换 出cache即可。(2

19、)对于全相联的cache来说，它的全部行都是可被替换的特 定行；而组相联的cache中同组各路的行都是可被替换的特定 行：这样就要从允许存放新主存块的若干特定行中选取一行 换出。2!如何选取就涉及到替换策略或称替换算法的釆用。以硬件 实现的常用算法主要有以下三种o(1)先进先出(fifo)算法1=1fifo (first in first out)算法是把一组中最先调入 cache的字块替换出去，不需要随时记录各个字块的使用情 况,所以实现容易，开销小。(2) lru与lfu算法lru (least recently used)算法是将最近最少使用的行 换出。需要二维计数，实现复杂，速度慢。r

20、=lfu (least frequently used)算法是将最久未被访问过 的行换出。方法：每行设置一个计数器，cache每命中一次，命中行计数器 清零，其它各行计数器增1,因此它是未访问次数计数器。当 需要替换时，比较各特定行的计数值，将计数值最大的行换出。 这种算法显然保护了刚拷贝进新数据的行，符合cache工作原 因而使cache有较高的命中率。(3)随机替换ii随机替换(random replacement)策略实际上是不要 什么算法，从特定的行位置中随机地选取一行换出即可。这种策略以硬件实现最容易，而且速度也比前两种策 略快。缺点是随意换出的数据很可能马上又要用，从而增加 了映射

21、次数，降低了命中率和cache的工作效率。但这个缺 点可以用增大cache的容量来克服，实验统计表明，随机替 换策略的功效只是稍逊于前两种策略。例：一访cache的地址流为：23215245325 2,假设cache只有3块(?)时间：123456789101112块地址流：2321524532522222555旦333fifo33332225531114444替2调调命调替替替命命替222222223333lfu33旦5555旦551 ,1444222调调命调替命替命替替命命先进先出替换策略访问顺序12345678地址块号2h297643先进先出替换方式下的cache内容变化情况近期最久未使

22、用替换策略访问顺序地址块号块分配情况操作状态调进调进命中调进调进替换替换替换最久未使用替换方式下的cache内容变化情况写操作策略 因为cache的内容是部分主存内容的副本，应该与主存内 容保持一致。而cpu对cache的写入更改了cache内容，如何 与主存内容保持一致就有几种写操作工作方式可供选择，统 称为写策略。写回法(write.back)(1) cpu对cache写命中时当cpu对cache写命中时，只修改cache的内容不立即写入 主存，只当此行被换出时才写回主存。对一cache行的多次写命中都在cache中快速完成修改，只 是需被替换时才写回速度较慢的主存，减少了访问主存的次 数

23、从而提高了效率。方法：每个cache行必须配置一个修改位，以反映此行是否被 cpu修改过。当某行被换出时，根据此行修改位为1还是为0, 决定是将该行内容写回主存还是简单地弃之而不顾。(2) cpu对cache写未命中时对于cache写未命中，写回法的处理是为包含欲写字的主存 块在cache分配一行,将此块整个拷贝到cache后在cache中对其 进行修改；拷贝主存块时虽已读访问到主存，但此时并不对主 存块修改，统一地将主存写修改操作留待换出时进行。(3)优缺点:写cache与写主存分开进行方式可显著减少写主存次数，但 写回法存在cache/主存不一致性的隐患。写直达法(write-throug

24、h )也称全写法。当cache写命中时：cache与主存同时发生写修改。这种策 略显然较好地维护了 cache与主存的内容一致性； (2)当cache写未命中时：直接向主存写。但此时是否将修改过的主存块取到cache,写直达法有两种选 择： 一种是取主存块到cache并为它分配一个行位置，称为wtwa法(writethroughwithwriteallocate )；另一种是不取主存块到cache,称为wtnwa法(write-through-with. no-write-allocate )。(3)优缺点:写直达法是写cache与写主存同步进行，优点是：cache每行无需设置一个修改位以及相

25、应的判测逻辑； 缺点是：cachextcpu向主存的写操作无高速缓存功能，降低了 cache的功效。80486处理器片内cache釆用的就是写直达法。写一次法(writeonce)策略：写一次法是一种基于写回法又结合了写直达法的写策略, 即写命中和写未命中的处理与写回法基本相同，只是第一次写 命中时要同时写入主存。应用: ii这种策略主要用于某些处理器的片内cache,例如pentium 处理器的片内数据cache就釆用的是写一次法。因为片内cache 写命中时，写操作就在cpu内部高速完成，若没有内存地址 及其它指示信号送出，就不便于系统中的其它cache监听(snoop) o在第一次片内cache写命中时，cpu要在总线 上启动一个存储器写周期。其它cache监听到此主存块地址及写信号后，即可把它们各自保存可能有 的该块拷贝及时作废（无效处理）。尔后若有对片 内cache此行的再次或多次写命中，则按回写法处理，无需再送出信号了。这样虽然第一次写命中时花费了一个存储周期，但对维护系统全部cache的一致性有利。而大多的cache写操作不涉及到片外,对指令流水执行有利。本讲主要内容 cache基本原理cache存储器组织替换策略与写操作策略ii奔腾pc机的cache奔腾pc机的cachepentium pc釆用两级cache结构m3m2安装在主板上，其容量