第十讲(cache存储器)

1、南大科技学院南大科技学院主讲主讲 罗少彬罗少彬Email Email ：PhonePhone：83#83#，1507091260115070912601Cache存储器组织存储器组织 Cache基本原理基本原理替换策略与写操作策略替换策略与写操作策略 奔腾奔腾PC机的机的Cache 根据根据访存局部性原理访存局部性原理，可以在主存和，可以在主存和CPU之间设置一个之间设置一个高高速速的的容量相对较小容量相对较小的存储器，如果当前正在执行的程序和数据的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不必从主存储器取指令存放在这个存储器中，在程序运行时，不必从主存储器取指令和

2、取数据，只需访问这个高速存储器，以提高程序运行速度。和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓冲存储器这个存储器称作高速缓冲存储器Cache。 Cache由高速的由高速的SRAM组成，组成，它的工作速度数倍于主存，它的工作速度数倍于主存，全部功能由全部功能由硬件硬件实现，并且对实现，并且对程序员是透明程序员是透明的。的。cache基本原理基本原理cache的基本结构的基本结构 它由它由cache存储体、地址映象变换机构、存储体、地址映象变换机构、cache替换机构替换机构几大模块组成。几大模块组成。主存块号块内地址地址映象变换机构Cache块号块内地址C Ca

3、ac ch he e主主存存C Ca ac ch he e替替换换策策略略主主存存地地址址C Ca ac ca ah he e地地址址访访问问主主存存替替换换C Ca ac ch he e访访问问主主存存装装入入C Ca ac ch he e已已满满不不命命中中命命中中未未满满块块单单字字到到C CP PU U来来自自C CP PU UCache概念：概念：（1）CPU与主存储器之间的一种高速缓冲装置与主存储器之间的一种高速缓冲装置（2）Cache-主存层次结构：由硬件变换地址和控制调度。主存层次结构：由硬件变换地址和控制调度。Cache具有如下特点：具有如下特点： 位于位于CPU与主存之间，

4、是存储器层次结构中级别最高的一与主存之间，是存储器层次结构中级别最高的一级；级； 容量比主存小，目前一般有数容量比主存小，目前一般有数KB到数到数MB； 速度一般比主存快速度一般比主存快5-10倍倍,通常由存储速度高的通常由存储速度高的SRAM组成；组成； 其内容是主存的部分副本；其内容是主存的部分副本； 其用途可用来存放指令，也可用来存放数据；其用途可用来存放指令，也可用来存放数据； 快存的功能全部由硬件实现，并对程序员透明。快存的功能全部由硬件实现，并对程序员透明。(2)(2)当比较结果不相等时，说明需要的数据尚未调入当比较结果不相等时，说明需要的数据尚未调入Cache，那，那么就要把么就

5、要把该数据所在的整个字块从主存一次调进来该数据所在的整个字块从主存一次调进来。 前一种情况称为访问前一种情况称为访问Cache命中，后一种情况称为访问命中，后一种情况称为访问Cache不命中。不命中。Cache的命中的命中 任何时候都有一些主存块处在任何时候都有一些主存块处在Cache中。中。 当当CPU发出读请求时，将主存地址发出读请求时，将主存地址s位（或位（或s位中的一部分）位中的一部分）与与Cache某块的标记相比较，根据其比较结果是否相等而区分某块的标记相比较，根据其比较结果是否相等而区分出两种情况：出两种情况： (1)当比较结果相等时，说明需要的数据已在当比较结果相等时，说明需要的

6、数据已在Cache中，那么中，那么直接访问直接访问Cache就行了，在就行了，在CPU与与Cache之间，通常一次传送之间，通常一次传送一个字；一个字；Cache的命中率的命中率命中率命中率指指CPU所要访问的信息在所要访问的信息在Cache中的比率；中的比率；而将所要访问的信息不在而将所要访问的信息不在Cache中的比率称为中的比率称为失效率失效率。 增加增加cache的目的，就是在性能上使主存的平均读出的目的，就是在性能上使主存的平均读出时间尽可能接近时间尽可能接近cache的读出时间。因此的读出时间。因此, cache的命中率应的命中率应接近于接近于1。 由于程序访问的局部性由于程序访问

7、的局部性 ，这是可能的。，这是可能的。 在一个程序执行期间：在一个程序执行期间： 设设Nc表示表示cache完成存取的总次数，完成存取的总次数， Nm表示主存完成存取的总次数，表示主存完成存取的总次数， h定义为命中率，则有：定义为命中率，则有：h=Nc/Nc+Nm若若 tc表示命中时的表示命中时的cache访问时间，访问时间， tm表示未命中时的主存访问时间，表示未命中时的主存访问时间， 1-h表示不命中率，表示不命中率，则则cache/主存系统主存系统的平均访问时间的平均访问时间ta为：为：ta=htc+(1-h)tm我们追求的目标是：我们追求的目标是： 以较小的硬件代价使以较小的硬件代价

8、使cache/主存系统主存系统的平均访的平均访问时间问时间ta越接近越接近tc越好。越好。设设 r=tm/tc表示主存慢于表示主存慢于cache的倍率的倍率, e表示访问效率，则有表示访问效率，则有: e=tc/ta=tc/htc+(1-h)tm=1/r+(1-r)h=1/h+(1-h)r为提高访问效率：为提高访问效率： 命中率命中率h越接近越接近1越好，越好，r值以值以510为宜，不宜太大。为宜，不宜太大。 命中率命中率h与程序的行为、与程序的行为、cache的容量、组织方式、的容量、组织方式、块的大小有关。块的大小有关。例：例：CPU执行一段程序时，执行一段程序时，cache完成存取的次数

9、为完成存取的次数为1900次，主次，主存完成存取的次数为存完成存取的次数为100次，已知次，已知cache存取周期为存取周期为50ns，主存，主存存取周期为存取周期为250ns，求，求cache/主存系统的效率和平均访问时间。主存系统的效率和平均访问时间。解：解： h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3% ta=tc/e=50ns/0.833=60ns例例:已知已知Cache存储周期为存储周期为40ns,主存存储周期为主存存储周期为200ns, Cach

10、e /主存系统平均访问时间为主存系统平均访问时间为50ns,求求Cache的命中率是多少的命中率是多少?解解: 因为因为 ta=htc+(1-h)tm 所以所以 h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16 （1）数据块在）数据块在Cache中存放在哪个位置？即定位问题中存放在哪个位置？即定位问题（地址（地址映象）映象） 。如果一个块存放在某一。如果一个块存放在某一Cache中，怎样确定并找到该中，怎样确定并找到该块，即寻址问题块，即寻址问题（地址变换）（地址变换）。（2）不命中时将从主存储器中访问，并将该块调入）不命中时将从主存储器中访问，并将该块调入C

11、ache中，中，但是如果但是如果Cache中已无空闲空间，则势必将中已无空闲空间，则势必将Cache中的某一块中的某一块调出，但应调出那一块，即调出，但应调出那一块，即替换问题替换问题。（3）在写访问时，写入）在写访问时，写入Cache必须在适当的时候写回主存储必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性一致性。写操作失配时是否将访问块取入高层存储器。写操作失配时是否将访问块取入高层存储器。Cache结构设计必须解决的问题：结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？如何存放，如

12、何访问，如何替换，如何改写？Cache存储器组织存储器组织 Cache基本原理基本原理替换策略与写操作策略替换策略与写操作策略 奔腾奔腾PC机的机的Cache地址映象地址映象 把主存块按照某种规则（函数或方法）装入或定位到把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。中的过程称地址映象。地址变换地址变换 信息按这种映象关系装入信息按这种映象关系装入Cache后，执行程序时，将主存后，执行程序时，将主存地址变换成地址变换成 Cache地址的变换过程叫做地址变换。地址的变换过程叫做地址变换。 地址地址映象和变换映象和变换密切相关。密切相关。 使用使用Cache的动力在

13、于它的高速，因此也要求这个地址变的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的。这带来的另一换过程尽可能地快，故此过程是以硬件完成的。这带来的另一好处是好处是Cache的透明性，除了程序运行速度提高之外，用户包的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到括系统软件编制人员，丝毫未感觉到Cache的存在。的存在。地址映象地址映象(映射映射)与地址变换与地址变换基本的地址映象方式：直接映象；基本的地址映象方式：直接映象； 全相连映象；组相连映象全相连映象；组相连映象 在高速缓冲存储器中在高速缓冲存储器中,把把Cache和主存机械等分为

14、和主存机械等分为相同大小相同大小的块的块,每一块是由若干个字每一块是由若干个字(或字节或字节)组成。组成。块块0 0块块1 1块块1515Cache标记标记标记标记标记标记块块0 0块块1 1块块20472047主存主存m m位位 块块字字0 0字字1 1字字511511 由于由于Cache的块数远小于主存的块数，因此一个的块数远小于主存的块数，因此一个Cache不能不能唯一地、永久地只对应一个贮存块，在唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有中，每一块外加有一个标记，指明它是主存的哪一块的副本一个标记，指明它是主存的哪一块的副本(拷贝拷贝)。例：例：某机主存容量为某机主存

15、容量为1MB,划分为划分为2048块块,每块每块512B;Cache容量为容量为8KB,划分为划分为16块块,每块每块512B。 因刚加电时所有标记位都为因刚加电时所有标记位都为“0”0”，开始执行程序时，开始执行程序时，命中率较低。另外命中率较低。另外CacheCache的命中率还与程序本身有关，即的命中率还与程序本身有关，即不同的程序，其命中率可能不同。不同的程序，其命中率可能不同。标记的有效位标记的有效位 每个标记设置有一个有效位。机每个标记设置有一个有效位。机器加电启动时，器加电启动时，Reset信号将所有标记信号将所有标记的有效位置的有效位置“0”，即无效。程序执行，即无效。程序执行

16、过程中，过程中，Cache不命中时，逐步将指不命中时，逐步将指令块或数据块从主存调入令块或数据块从主存调入Cache中的中的某一块，并将这一块标记的有效位置某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或，当再次用到这一块中的指令或数据时，可直接从数据时，可直接从Cache中取指令或中取指令或数据。数据。字块字块0 0字块字块1 1字块字块L Lm-1m-1 . .标记标记CacheCache0 01 12 2r r-1-1 标记标记有效位有效位直接映射方式直接映射方式 这是一种多对一的映射关系，但一个这是一种多对一的映射关系，但一个主存块只能映象到主存块只能映象到Cache

17、的一个特定块位置上去的一个特定块位置上去。 Cache的第的第i块和主存的第块和主存的第j块有如下函数关系：块有如下函数关系： i = j mod m ( m为为Cache的总块数）的总块数） i =0,1,2,m-1 j=0,1,2,n-1在这种映象方式中：在这种映象方式中：主存的第主存的第0块，第块，第16块，第块，第32块，块，只能映象到，只能映象到Cache的第的第0块；块；主存的第主存的第1块，第块，第17块，第块，第33块，块，只能映象到，只能映象到Cache的第的第1块；块；直接映象直接映象Cache地址地址C Ca ac ch he e块块号号块块内内地地址址4位位 9 位位主

18、存地址主存地址块内地址块内地址Cache块号Cache块号主存标记（组号）主存标记（组号）7位位 4位位 9 位位主主存存块块号号块块内内地地址址11位位 9 位位主存地址主存地址块块0块块1块块15C Ca ac ch he e标标记记标标记记标标记记标标记记标标记记标标记记.0 0 组组块块0块块1块块 15块块 16块块 17块块 31块块 2047主主存存T Ta ag g1 1 组组1 12 27 7组组7位位.0 0 组组块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存1 1 组组127127组组块内地址块内地址Cache块号Cache块号主存标记（组号）

19、主存标记（组号）标记标记标记标记标记标记标记标记标记标记标记标记块块 0块块 1块块 15有效位有效位有效位有效位: :有效位有效位7位 4位 9位7位 4位 9位比较比较命中命中数据数据主存地址主存地址不命中不命中优点优点:硬件简单硬件简单, ,成本低成本低 缺点缺点:块冲突率很高块冲突率很高直接映象的地址变换方法直接映象的地址变换方法优点优点: 实现简单，只需利用主存地址按某些字段直实现简单，只需利用主存地址按某些字段直接判断，即可确定所需字块是否已在接判断，即可确定所需字块是否已在Cache中。中。缺点：缺点： 不够灵活，主存的多个字块只能对应唯一的不够灵活，主存的多个字块只能对应唯一的

20、Cache字块，因此，即使字块，因此，即使Cache别的地址空着也不别的地址空着也不能占用。能占用。Cache存储空间得不到充分利用，降低存储空间得不到充分利用，降低了命中率。了命中率。例：例：设有一个设有一个cache的容量为的容量为2K字，每个块为字，每个块为16字，求字，求(1) 该该cache可容纳多少个块？可容纳多少个块？(2) 如果主存的容量是如果主存的容量是256K字，则有多少个块？字，则有多少个块？(3) 主存的地址有多少位？主存的地址有多少位？cache地址有多少位？地址有多少位？(4) 在直接映象方式下，主存中的第在直接映象方式下，主存中的第i块映象到块映象到cache中哪

21、一个块中哪一个块中？中？(5) 进行地址映象时，存储器的地址分成哪几段？各段分别有进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？多少位？解：解：(1) cache中有中有2048/16=128个块。个块。(2) 主存有主存有256K/16=16384个块。个块。(3) cache容量为容量为2K=211字，所以字，所以cache字地址为字地址为11位。位。(4) 主存中的第主存中的第i块映象到块映象到cache中第中第 i mod 128个块中。个块中。(5) 存储器的字地址分成三段：区号、块号、块内字地址。存储器的字地址分成三段：区号、块号、块内字地址。 区号的长度为区号的长度为

22、18-11=7位，块号为位，块号为7位。块内字地址为位。块内字地址为4位。位。块块 0块块 1块块 15CacheCache标记标记标记标记标记标记标记标记标记标记标记标记.块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存TagTag全相联映象方式全相联映象方式C Ca ac ch he e块块号号块块内内地地址址Cache地址地址4位位 9 位位主主存存块块号号块块内内地地址址11位位 9 位位主存地址主存地址11位位 允许主存中的每一个字块映象到允许主存中的每一个字块映象到Cache的任何一个字块的任何一个字块位置上最灵活但成本最高的一种方式。位置上最灵活但成本最

23、高的一种方式。.块块0块块1块块 15块块 16块块 17块块 31块块 2047主存主存标记标记标记标记标记标记标记标记标记标记标记标记块块 0块块 1块块 15有效位有效位有效位有效位: :有效位有效位11位 9位11位 9位比较所有的标记比较所有的标记命中命中数据数据主存地址主存地址不命中不命中主存块号主存块号块内地址块内地址全相联映象的地址变换方法全相联映象的地址变换方法 这只是一个理想的方案。这只是一个理想的方案。两个原因使其两个原因使其实际上很少采用：实际上很少采用：(1) 标记位数从标记位数从7位增加到位增加到11位，使位，使Cache标记容量加大。标记容量加大。(2) 访问访问

24、Cache时，需要和时，需要和Cache的全部标记进行的全部标记进行“比较比较”才才能判断出所访主存地址的内容是否已在能判断出所访主存地址的内容是否已在Cache中。由于中。由于Cache速度要求高，通常速度要求高，通常由由“按内容寻址按内容寻址”的相联存储器的相联存储器完成，所完成，所需硬件逻辑电路很多，以至于无法用于需硬件逻辑电路很多，以至于无法用于cache中。实际的中。实际的Cache组织则是采取各种措施来减少所需比较的地址数目。组织则是采取各种措施来减少所需比较的地址数目。优点：优点：灵活，块冲突概率小。只有当灵活，块冲突概率小。只有当Cache中全部装满后中全部装满后,才才有可能出

25、现块冲突；有可能出现块冲突；缺点：缺点：要作相联搜索，速度慢，代价高。要作相联搜索，速度慢，代价高。1 1、组间全相联，组内直接、组间全相联，组内直接映像映像块块 0块块 1块块C Ca ac ch he e标标记记标标记记标标记记标标记记标标记记标标记记.块块0块块1块块 7块块 8块块 9块块 2032块块 2039主主存存T Ta ag g254组块块 0块块 1块块7标标记记标标记记标标记记标标记记标标记记标标记记标标记记70组1组块块 2033块块 15.块块 2047块块 2046.块块 2040255组0组1组8位位 3位位 9 位位主存组号块号块内地址8位位1位位 3位位 9

26、位位Cache组号块号块内地址组相联映射方式组相联映射方式 直接直接映象和全映象和全相联映象相联映象方式的一方式的一种折衷方种折衷方案。案。注意：当只有一个组并且每组注意：当只有一个组并且每组1616块时，此时为直接映像；块时，此时为直接映像； 当有当有1616组并且每组一个块时组并且每组一个块时, ,则为全相联映像。则为全相联映像。块块0 0块块1 1块块2 2块块3 3块块4 4块块5 5块块6 6块块7 7块块0 0块块1 1块块2 2块块3 3块块4 4块块5 5块块6 6块块7 7V VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT

27、 TV VT TV VT TV VT TV VT TV VT TV VT TV VT TX XX X块块0 0块块1 1块块7 7块块8 8块块9 9块块1 15 5. . . .块块2 20 04 40 0块块2 20 04 47 7. . . . . . . . . . . . .0组 1组 内存组相联组相联的地址变换方法的地址变换方法8 8 位位3 3 位位9 9 位位主存组号块号块内地址块块0 0块块1 1块块2 2块块3 3块块4 4块块5 5块块6 6块块7 7块块0 0块块1 1块块2 2块块3 3块块4 4块块5 5块块6 6块块7 7V VT TV VT TV VT TV V

28、T TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT T块块0 0块块1 1块块7 7块块8 8块块9 9块块1 15 5. . . .块块2 20 04 40 0块块2 20 04 47 7. . . . . . . . . . . . .比较选择器比较命中数据不命中直接映象是：直接映象是：1路组相联路组相联全相联是：全相联是： m路组相联路组相联 主存中的一块能对应到主存中的一块能对应到Cache中一个特定组中的任意一中一个特定组中的任意一行上。若组中有行上。若组中有n个块，则称其为个块，则称其为

29、 n路组关联路组关联。 N个直接映射个直接映射cache并行工作。并行工作。 直接映象和全相联映象是组相联的特例：直接映象和全相联映象是组相联的特例：块块0块块1块块C Ca ac ch he e标标记记标标记记标标记记标标记记标标记记标标记记.0 0 组组块块0块块1块块 7块块 8块块 9块块 2040块块 2047主主存存T Ta ag g1 1 组组127组块块4块块5块块 14标标记记标标记记标标记记标标记记标标记记标标记记标标记记块块23标标记记块块 150组1组2组7组块块 2041块块 15另外一种组相联映射方式另外一种组相联映射方式 Cache与主存均分组与主存均分组,主存中

30、一个组内的块数与主存中一个组内的块数与Cache 的的分组数相同分组数相同,主存中的各块与主存中的各块与Cache的组号有固定的映象关系的组号有固定的映象关系,但可自由映象到对应的但可自由映象到对应的Cache组中任一块。组中任一块。2 2、组内全相联，组间直接、组内全相联，组间直接映像映像注意：当只有一个组并且每组注意：当只有一个组并且每组1616块时，此时为全相联映像；块时，此时为全相联映像； 当有当有1616组并且每组一个块时组并且每组一个块时, ,则为直接映像。则为直接映像。组相联组相联的地址变换方法的地址变换方法8 8 位位3 3 位位9 9 位位主存组号块号块内地址组组0 0组组1

31、 1组组2 2组组3 3组组4 4组组5 5组组6 6组组7 7组组0 0组组1 1组组2 2组组3 3组组4 4组组5 5组组6 6组组7 7V VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT TV VT T块块0 0块块1 1块块7 7块块8 8块块9 9块块1 15 5. . . .块块2 20 04 40 0块块2 20 04 47 7. . . . . . . . . . . . .比较选择器比较命中数据不命中例例:设一个设一个Cache中有中有8个块个块,访

32、问主存进行读操作的块地址序列访问主存进行读操作的块地址序列为为22、26、22、26、16、4、16、18，求每次访问后，求每次访问后Cache中的中的内容。内容。解：解：地址地址命中与否命中与否地址转换关系地址转换关系22 不命中不命中 22 MOD 8=626 不命中不命中 26 MOD 8=2 22 命中命中 22 MOD 8=626 命中命中 26 MOD 8=216 不命中不命中 16 MOD 8=04 不命中不命中 4 MOD 8=4 16 命中命中 16 MOD 8=0 18 不命中不命中 18 MOD 8=2 直接映象下直接映象下Cache访问情况访问情况直接映象的块分配情况直

33、接映象的块分配情况访问顺序访问顺序 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 地址地址 22 26 22 26 16 4 16 1822 26 22 26 16 4 16 18块分配块分配情况情况 22操作操作状态状态调调进进2226调调进进2226命命中中2226命命中中222616调调进进2241626调调进进2216264命命中中2216184替替换换 Cache的容量和块的大小是影响的容量和块的大小是影响Cache的效率的重要因素。的效率的重要因素。 一般来说，一般来说，Cache的存储容量比主存的容量小得多的存储容量比主存的容量小得多; 但不能太小，太小会使命中

34、率太低；但不能太小，太小会使命中率太低； 也没有必要过大，过大不仅会增加成本，而且当容量超过一也没有必要过大，过大不仅会增加成本，而且当容量超过一 定值后，命中率随容量的增加将不会有明显地增长。定值后，命中率随容量的增加将不会有明显地增长。 但随着芯片价格的下降，但随着芯片价格的下降，Cache的容量不断增大，已由几的容量不断增大，已由几K发展到几十发展到几十K，甚至到几百，甚至到几百K字节。字节。 因此，因此，cache容量是总成本价与命中率的折衷值。容量是总成本价与命中率的折衷值。 如：如：80386的主存最大容量为的主存最大容量为4G，与其配套的，与其配套的cache容量为容量为 16K

35、B或或32KB，其命中率为，其命中率为95%。Cache容量与命中率容量与命中率块长与命中率块长与命中率 块长与命中率的关系更为复杂，它取决于程序的局部特块长与命中率的关系更为复杂，它取决于程序的局部特性。块长的最优值很难确定，通常：性。块长的最优值很难确定，通常：每块取每块取4至至8个可编址单位（字或字节）较好；个可编址单位（字或字节）较好；也可取一个主存周期所能调出主存的信息长度。也可取一个主存周期所能调出主存的信息长度。 例如，例如，CARY-1的主存是的主存是16个交叉体，每个体为单字宽，个交叉体，每个体为单字宽， 其指令其指令cache的块长为的块长为16个字；个字； IBM 370

36、/168机主存是机主存是4体交叉，每个体宽为体交叉，每个体宽为64位位 （8个字），其个字），其cache块长为块长为32个字。个字。Cache存储器组织存储器组织 Cache基本原理基本原理替换策略与写操作策略替换策略与写操作策略 奔腾奔腾PC机的机的Cache替换策略替换策略 当一个新的主存块要调入到当一个新的主存块要调入到cache，而允许存放此块的行位，而允许存放此块的行位置都被其它主存块占满时，就要产生替换，因为置都被其它主存块占满时，就要产生替换，因为cache工作原理工作原理要求它应尽量保存最新的数据。要求它应尽量保存最新的数据。(1)对于采用对于采用直接映射方式直接映射方式的的

37、cache来说：来说： 因一个主存块只有一个特定的行位置可存放，所以问题因一个主存块只有一个特定的行位置可存放，所以问题解决很简单，把此特定行位置上的原主存块妥善处理后，换解决很简单，把此特定行位置上的原主存块妥善处理后，换出出Cache即可。即可。(2)对于对于全相联全相联的的cache来说，它的全部行都是可被替换的特定来说，它的全部行都是可被替换的特定行；而行；而组相联组相联的的cache中同组各路的行都是可被替换的特定行：中同组各路的行都是可被替换的特定行： 这样就要从允许存放新主存块的若干特定行中选取一行这样就要从允许存放新主存块的若干特定行中选取一行换出。换出。替换问题与替换问题与c

38、ache的组织方式紧密相关的组织方式紧密相关 如何选取就涉及到如何选取就涉及到替换策略替换策略或称或称替换算法替换算法的采用。以硬件的采用。以硬件实现的常用算法主要有以下三种。实现的常用算法主要有以下三种。 FIFO（First In First Out）算法算法是把一组中最先调入是把一组中最先调入Cache的字块替换出去，不需要随时记录各个字块的使用情的字块替换出去，不需要随时记录各个字块的使用情况，所以实现容易，开销小。况，所以实现容易，开销小。（1）先进先出（）先进先出（FIFO）算法）算法 LRU （Least Recently Used）算法是将最近最少使用的行算法是将最近最少使用的

39、行换出。需要二维计数，实现复杂，速度慢。换出。需要二维计数，实现复杂，速度慢。 LFU （Least Frequently Used）算法是将最久未被访问过算法是将最久未被访问过的行换出。的行换出。方法：方法： 每行设置一个计数器，每行设置一个计数器，cache每命中一次，命中行计数器每命中一次，命中行计数器清零，其它各行计数器增清零，其它各行计数器增1，因此它是，因此它是未访问次数计数器未访问次数计数器。当。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。需要替换时，比较各特定行的计数值，将计数值最大的行换出。这种算法显然保护了刚拷贝进新数据的行，符合这种算法显然保护了刚拷贝进新数

40、据的行，符合cache工作原工作原理，因而使理，因而使cache有较高的命中率。有较高的命中率。（2）LRU与与LFU算法算法 随机替换随机替换（Random Replacement）策略实际上是不要策略实际上是不要什么算法，从特定的行位置中随机地选取一行换出即可。什么算法，从特定的行位置中随机地选取一行换出即可。 这种策略以硬件实现最容易，而且速度也比前两种策这种策略以硬件实现最容易，而且速度也比前两种策略快。略快。 缺点缺点是随意换出的数据很可能马上又要用，从而增加是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和了映射次数，降低了命中率和cache 的工作效率。但这个缺

41、的工作效率。但这个缺点可以用增大点可以用增大cache的容量来克服，实验统计表明，随机替的容量来克服，实验统计表明，随机替换策略的功效只是稍逊于前两种策略。换策略的功效只是稍逊于前两种策略。（3）随机替换）随机替换 例：例：一访一访Cache的地址流为：的地址流为：2 3 2 1 5 2 4 5 3 2 5 2，假设，假设Cache只有只有3块块(?)时间：时间： 1 2 3 4 5 6 7 8 9 10 11 12块地址流：块地址流： 2 3 2 1 5 2 4 5 3 2 5 2FIFO2 调调23 调调23 命命231调调531替替521替替524替替524命命324替替324命命354

42、替替352替替3LFU2 调调23 调调23命命231调调251替替251命命254替替254命命354替替352替替352命命352命命5先进先出替换策略先进先出替换策略访问顺序访问顺序 1 2 3 4 5 6 7 8地址块号地址块号 2 11 2 9 7 6 4 3块分配情况块分配情况操作状态操作状态 调进调进 调进调进 命中命中 调进调进 调进调进 替换替换 替换替换 替换替换先进先出替换方式下的先进先出替换方式下的cache 内容变化情况内容变化情况2-211-211-2119-211976119764976437近期最久未使用替换策略近期最久未使用替换策略访问顺序访问顺序 1 2 3

43、 4 5 6 7 8地址块号地址块号 2 11 2 9 7 6 4 3块分配情况块分配情况操作状态操作状态 调进调进 调进调进 命中命中 调进调进 调进调进 替换替换 替换替换 替换替换最久未使用替换方式下的最久未使用替换方式下的cache 内容变化情况内容变化情况2*-211*-2*11-2119 *-21197*26*974*697463*7写操作策略写操作策略 因为因为cache的内容是部分主存内容的副本，应该与主存内的内容是部分主存内容的副本，应该与主存内容保持一致。而容保持一致。而CPU对对cache的写入更改了的写入更改了cache内容，如何内容，如何与主存内容保持一致就有几种写操

44、作工作方式可供选择，统与主存内容保持一致就有几种写操作工作方式可供选择，统称为称为写策略写策略。写回法（写回法（write-back） 当当CPU对对cache写命中时，只修改写命中时，只修改cache的内容不立即写入的内容不立即写入主存，只当此行被换出时才写回主存。主存，只当此行被换出时才写回主存。 对一对一cache行的多次写命中都在行的多次写命中都在cache中快速完成修改，只中快速完成修改，只是需被替换时才写回速度较慢的主存，减少了访问主存的次是需被替换时才写回速度较慢的主存，减少了访问主存的次数从而提高了效率。数从而提高了效率。(1) CPU对对cache写命中时写命中时方法：方法：

45、每个每个cache行必须配置一个修改位，以反映此行是否被行必须配置一个修改位，以反映此行是否被CPU修改过。当某行被换出时，根据此行修改位为修改过。当某行被换出时，根据此行修改位为1还是为还是为0，决定是将该行内容写回主存还是简单地弃之而不顾。决定是将该行内容写回主存还是简单地弃之而不顾。(2) CPU对对cache写未命中时写未命中时 对于对于cache写未命中，写回法的处理是为包含欲写字的主存写未命中，写回法的处理是为包含欲写字的主存块在块在cache分配一行，将此块整个拷贝到分配一行，将此块整个拷贝到Cache后在后在cache中对其中对其进行修改；拷贝主存块时虽已读访问到主存，但此时并

46、不对主进行修改；拷贝主存块时虽已读访问到主存，但此时并不对主存块修改，统一地将主存写修改操作留待换出时进行。存块修改，统一地将主存写修改操作留待换出时进行。(3) 优缺点：优缺点： 写写cache与写主存分开进行方式可显著减少写主存次数，但与写主存分开进行方式可显著减少写主存次数，但写回法存在写回法存在cache/主存不一致性的隐患。主存不一致性的隐患。写直达法（写直达法（write-through） 也也称全写法。称全写法。(1)当当cache写命中时：写命中时：cache与主存同时发生写修改。这种策与主存同时发生写修改。这种策略显然较好地维护了略显然较好地维护了cache与主存的内容一致性

47、；与主存的内容一致性；(2)当当cache写未命中时：写未命中时：直接向主存写。直接向主存写。 但此时是否将修改过的主存块取到但此时是否将修改过的主存块取到cache，写直达法有两种选，写直达法有两种选择：择： 一种是取主存块到一种是取主存块到cache并为它分配一个行位置，并为它分配一个行位置， 称为称为WTWA法法(Write-Through-with-Write-Allocate）；）； 另一种是不取主存块到另一种是不取主存块到cache, 称为称为WTNWA法法 （Write-Through-withNO-Write-Allocate）。）。写直达法是写写直达法是写cache与写主存同

48、步进行，与写主存同步进行，优点是：优点是： cache每行无需设置一个修改位以及相应的判测逻辑；每行无需设置一个修改位以及相应的判测逻辑；缺点是：缺点是： cache对对CPU向主存的写操作无高速缓存功能，降低了向主存的写操作无高速缓存功能，降低了cache的功效。的功效。 80486处理器片内处理器片内cache采用的就是写直达法。采用的就是写直达法。(3) 优缺点：优缺点：写一次法（写一次法（write-once）策略：策略：写一次法是一种基于写回法又结合了写直达法的写策略，写一次法是一种基于写回法又结合了写直达法的写策略，即写命中和写未命中的处理与写回法基本相同，只是第一次写即写命中和写

49、未命中的处理与写回法基本相同，只是第一次写命中时要同时写入主存。命中时要同时写入主存。应用：应用： 这种策略主要用于某些处理器的片内这种策略主要用于某些处理器的片内cache，例如，例如Pentium处理器的片内数据处理器的片内数据cache就采用的是写一次法。因为片内就采用的是写一次法。因为片内cache写命中时，写操作就在写命中时，写操作就在CPU内部高速完成，若没有内存地址内部高速完成，若没有内存地址及其它指示信号送出，就不便于系统中的其它及其它指示信号送出，就不便于系统中的其它cache监听监听（snoop）。）。 在第一次片内在第一次片内cache写命中时，写命中时， CPU要在总线

50、要在总线上启动一个存储器写周期。其它上启动一个存储器写周期。其它cache监听到此主监听到此主存块地址及写信号后，即可把它们各自保存可能有存块地址及写信号后，即可把它们各自保存可能有的该块拷贝及时作废（无效处理）。尔后若有对片的该块拷贝及时作废（无效处理）。尔后若有对片内内cache此行的再次或多次写命中，则按回写法处此行的再次或多次写命中，则按回写法处理，无需再送出信号了。这样虽然第一次写命中时理，无需再送出信号了。这样虽然第一次写命中时花费了一个存储周期，但对维护系统全部花费了一个存储周期，但对维护系统全部cache的的一致性有利。而大多的一致性有利。而大多的cache写操作不涉及到片外，

51、写操作不涉及到片外，对指令流水执行有利。对指令流水执行有利。 Cache存储器组织存储器组织 Cache基本原理基本原理替换策略与写操作策略替换策略与写操作策略 奔腾奔腾PC机的机的Cache奔腾奔腾PC机的机的CacheL2 安装在主板上，其容量是安装在主板上，其容量是256 KB或或512KB，采用的两路，采用的两路组相联映射方式，每行可以是组相联映射方式，每行可以是32，64或或128字节。字节。L1 集成在集成在CPU内，其容量是内，其容量是16KB，采用的也是两路组相联，采用的也是两路组相联映射方式，每行是映射方式，每行是32字节。字节。 L2的内容是的内容是432MB容量主存的子集，容量主存的子集，L1又是又是L2的子集，从而的子集，从而使使L1未命中处理时间大为缩短，为未命中处理时间大为缩短，为L1的高速使用提供了支持。的高速使用提供了支持。L L2 2L L1 1Pentium PC采用两级采用两级cache结构结构CPU中的中的L1分立为各分立为各8KB的指令的指令cache