组成原理课件-高速缓冲存储器

1、7 75 5 高速缓冲存储器高速缓冲存储器一、高速缓冲存储器和工作原理一、高速缓冲存储器和工作原理1 1、高速缓冲存储器、高速缓冲存储器 CACHECACHE是一个高速度、小容量的缓冲存储器，存储是一个高速度、小容量的缓冲存储器，存储CPUCPU最经常访问的指令或数据，一般最经常访问的指令或数据，一般用用SRAMSRAM芯片构成芯片构成，其全部功能由其全部功能由硬件硬件实现，对程序员是透明的。实现，对程序员是透明的。 CACHECACHE用于用于解决解决 CPUCPU与主存间的速度匹配问题与主存间的速度匹配问题，其，其理论依据是程序访问的局部性原理。理论依据是程序访问的局部性原理。 在一个较短

2、的时间内，在一个较短的时间内，CPUCPU对局部范围的存储器地址对局部范围的存储器地址频繁访问，而对此址范围外的地址访问很少。频繁访问，而对此址范围外的地址访问很少。程序访问的局部性原理程序访问的局部性原理2 2、工作原理、工作原理 为了使主存与为了使主存与cachecache之间映射，将主存与缓存都分在若之间映射，将主存与缓存都分在若干个块，每个块包含若干个字，并使块的大小相等。干个块，每个块包含若干个字，并使块的大小相等。 将主存将主存n n位地址分为高位地址分为高mm位和低位和低b b位，缓存地址也分成位，缓存地址也分成高高c c位和低位和低b b位。主存的块数位。主存的块数M=2M=2

3、mm远大于缓存的块数远大于缓存的块数C=2C=2c c块。块。 由于缓存的块数远小于主存的块数，一个缓存块不由于缓存的块数远小于主存的块数，一个缓存块不能能唯一、永久地对应一个主存块，每个缓存块需设一个标记，唯一、永久地对应一个主存块，每个缓存块需设一个标记，用来表示当前存放的是哪一个主存块，该标记的内容相当用来表示当前存放的是哪一个主存块，该标记的内容相当于主存块的编号（即主存地址的高于主存块的编号（即主存地址的高mm位）。位）。 CPUCPU读信息时根据主存地址的低位部分，将主存地读信息时根据主存地址的低位部分，将主存地址址的高位部分与缓存块的标记进行比较，以判断所读信息是的高位部分与缓存

4、块的标记进行比较，以判断所读信息是否在缓存中否在缓存中。 主存储器主存储器Cache 主存块号主存块号0122m-1：字块字块0字块字块1字块字块2字块字块M-1字块字块0字块字块1字块字块C-1012c-1标记标记（1 1）CACAHECACAHE命中：命中：CPUCPU访问的数据或指令已存在于访问的数据或指令已存在于CACHECACHE中。中。（2 2）命中时间：在）命中时间：在CACHECACHE命中时的访存时间，它等于命中时的访存时间，它等于CACHECACHE的访的访 问时间。问时间。（3 3）失效时间：）失效时间：CACHECACHE不命中时因访存而增加的访问时间，它等不命中时因访

5、存而增加的访问时间，它等 于对主存的访问时间和将主存中的数据调入于对主存的访问时间和将主存中的数据调入CACHE CACHE 的时间。的时间。M= 2m C = 2c3 3、高速缓冲存储器设计中要考虑的问题、高速缓冲存储器设计中要考虑的问题（1 1）地址映象：主存中的块放入）地址映象：主存中的块放入CACHECACHE中的什么地方。中的什么地方。（2 2）块的替换策略：）块的替换策略：CACHECACHE放满时将哪块数据移去再调入要访问放满时将哪块数据移去再调入要访问 的块。的块。（3 3）块的更新策略：解决）块的更新策略：解决CACHECACHE数据写操作与主存写操作的关系。数据写操作与主存

6、写操作的关系。（4 4）CACHECACHE容量容量16KB 256K16KB 256K和块的容量和块的容量4B128B4B128B。二、地址映象二、地址映象 根据主存的地址来构成根据主存的地址来构成CACHECACHE的地址，即主存地址与的地址，即主存地址与CACHECACHE地址之间的地址之间的 逻辑关系。逻辑关系。 地址映象关系是用地址映象表来表示的，这张表反映了主存地址映象关系是用地址映象表来表示的，这张表反映了主存单元和单元和CACHECACHE单元间的对应关系，这张表是用硬件实现的。单元间的对应关系，这张表是用硬件实现的。 块号块号 块内地址块内地址地址映象表地址映象表块号块号 块

7、内地址块内地址CACHE主存地址主存地址 在访问存储器时，根据主存地址的低位部分在地址映象表中在访问存储器时，根据主存地址的低位部分在地址映象表中查找标志并与主存地址的高位部分进行比较，相同命中，将高速查找标志并与主存地址的高位部分进行比较，相同命中，将高速CACHECACHE中数据送中数据送CPUCPU，不相同从主存调入数据，再送入，不相同从主存调入数据，再送入CPUCPU。 地址变换和替换算法均用硬件实现，地址变换和替换算法均用硬件实现，CACHECACHE对程序员是透明的。对程序员是透明的。主主存存命中？命中？调入？调入？替换机构替换机构CPU访问主存访问主存替换替换CacheNNYY访

8、问主存装入访问主存装入Cache数据直接通路数据直接通路Cache 地址地址数据总线数据总线、1 1、直接映象：一个主存块只能映象到、直接映象：一个主存块只能映象到CACHECACHE中的唯一中的唯一 一个指定块一个指定块 的地址映象方式。的地址映象方式。 第第1块块第第2块块第第3块块第第4块块第第1块块第第2块块第第3块块第第4块块第第5块块第第6块块第第7块块第第8块块第第9块块第第10块块第第11块块第第12块块第第13块块第第14块块第第15块块第第16块块一个块由若干个字节组成，由于主一个块由若干个字节组成，由于主存容存容 量比量比CACHECACHE大得多，所以主存大得多，所以主

9、存有许多块会映射到有许多块会映射到CACHECACHE的同一个的同一个块上，将主存块地址对块上，将主存块地址对CACHECACHE的块的块数取模即得到数取模即得到CACHECACHE中的块地址。中的块地址。主存地址：区号、块号、块内地址主存地址：区号、块号、块内地址区号：作为标志存放在地址映象表区号：作为标志存放在地址映象表 中，用于判断命中与否。中，用于判断命中与否。块号：用于查找地址映象表和在块号：用于查找地址映象表和在 CACHECACHE中的块寻址。中的块寻址。块内地址：用于块内寻址。块内地址：用于块内寻址。 在访存操作时，根据地址中的块号读出块表中的区号并与当前在访存操作时，根据地址

10、中的块号读出块表中的区号并与当前地址的区号进行比较，比较结果相同表示地址的区号进行比较，比较结果相同表示CACHECACHE命中，访问可对命中，访问可对CACHECACHE进行，比较不相同则表示不命中，访问需要对主存进行。进行，比较不相同则表示不命中，访问需要对主存进行。特点：不需采用相联存储器，判断命中的方法简单，也不要替换算特点：不需采用相联存储器，判断命中的方法简单，也不要替换算 法，速度快，可实现大容量的法，速度快，可实现大容量的CACHECACHE。但数据块。但数据块 的冲突率的冲突率高。高。区号区号主存块号主存块号块内地址块内地址块号块号块内地址块内地址比较比较主存区号标志主存区号

11、标志主存地址主存地址Cach地址地址不相等块失效不相等块失效相等相等块表块表按块号查找按块号查找例：有一个例：有一个CACHECACHE的容量为的容量为2K2K字，每个块字，每个块1616个字，求个字，求（1 1）该）该CACHECACHE可容纳多少个块？可容纳多少个块？（2 2）如果主存的容量是）如果主存的容量是256K256K字，则有多少个块？字，则有多少个块？（3 3）主存的地址有多少位？）主存的地址有多少位？CACHECACHE地址有多少位？地址有多少位？（4 4）在直接映象方式下，主存中的第）在直接映象方式下，主存中的第 i i 块映象到块映象到CACHECACHE中哪一个中哪一个块

12、中？块中？（ 5 5）进行地址映象时，存储器的地址分成哪几段？各段分别有多）进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？少位？（1 1）CACHECACHE块数：块数：2K/16=1282K/16=128块块（2 2）主存块数：）主存块数：256K/16=16K256K/16=16K（3 3）主存的地址位数：）主存的地址位数：log 2log 2 256K 256K=18=18位位 CACHECACHE地址位数：地址位数：log 2 log 2 2K2K=11=11位位（4 4）在直接映象方式下，主存中的第）在直接映象方式下，主存中的第 i i 块映象到块映象到CACHECACH

13、E中的中的 i mod 128 i mod 128 个块中个块中（5 5）存储器的地址分成区号、主存块号和块内地址三段）存储器的地址分成区号、主存块号和块内地址三段区号：主存地址位数与区号：主存地址位数与CACHECACHE地址位数之差：地址位数之差：18-11=718-11=7主存块号：块地址长度与主存块号：块地址长度与CACHECACHE的块数有关，的块数有关，CACHECACHE是是128128块，所块，所 以主存块号有以主存块号有 log 2 log 2 128128=7 =7 位位块内地址：每个块由块内地址：每个块由1616个字组成，个字组成， 所以块内地址的位数：所以块内地址的位数

14、： log 2 log 2 16 16 =4 =4 位。位。 2 2、全相联映象：每个主存块可映象到任何、全相联映象：每个主存块可映象到任何CACHECACHE块的地址映象。块的地址映象。 在访问操作时，根据地址中的块号在块表中查找是否有相同的主存在访问操作时，根据地址中的块号在块表中查找是否有相同的主存块号。如果有，则表示块号。如果有，则表示CACHECACHE命中，将对应的命中，将对应的CACHECACHE块号取出并块号取出并对对CACHECACHE进行访问，如果没有，则进行访问，如果没有，则CACHECACHE没有命中，需对主存访没有命中，需对主存访问，在将主存中的块调入问，在将主存中的

15、块调入CACHECACHE中的同时将主存块号写入块表中，中的同时将主存块号写入块表中，以改变地址映象关系。以改变地址映象关系。特点：是最灵活的地址映象方式，地址是映象算法复杂，需要采用特点：是最灵活的地址映象方式，地址是映象算法复杂，需要采用 相联存储器，适合小容量的相联存储器，适合小容量的CACHECACHE，速度慢。，速度慢。 第第0块块第第1块块.第第N-1块块第第0块块第第1块块第第M(N-1)主存块号主存块号块内地址块内地址块号块号块内地址块内地址比较比较主存块号标志主存块号标志CACHE块号块号不相等不相等 块失效块失效相等相等 块表块表 相联查找相联查找0123 3、组相联映象：

16、是将存储空间分成若干组，各组之间是直接映象，、组相联映象：是将存储空间分成若干组，各组之间是直接映象， 而组内各块之间则采用全相联映象。此方式是上而组内各块之间则采用全相联映象。此方式是上述述 两种方式的折衷。两种方式的折衷。 CACHE 0组组 第第0 区区0组组 1组组1组组 0组组 第第M-1区区 1组组第第0块块.第第N-1块块第第0块块.第第N-1块块.第（第（M-1）N.第第MN-1 在访存操作时，根据地址中的组号和块号在块表中的该组对应的在访存操作时，根据地址中的组号和块号在块表中的该组对应的若干项中查找是否有相同的主存区号和组内块号。如果有相同的，若干项中查找是否有相同的主存区

17、号和组内块号。如果有相同的，CACHECACHE命中，将对应的命中，将对应的CACHECACHE组内块号取出以对组内块号取出以对CACHECACHE访问，没访问，没有相同的表示不命中，在对主存进行访问并将主存中的块调入有相同的表示不命中，在对主存进行访问并将主存中的块调入CACHECACHE中的同时将主存区号和组内块号和中的同时将主存区号和组内块号和CACHECACHE的组内块号写入的组内块号写入块块表中，以改变地址映象关系。表中，以改变地址映象关系。特点：适合于容量小，速度较低的场合。特点：适合于容量小，速度较低的场合。区号区号组号组号主存块号主存块号 块内地址块内地址块内地址块内地址块号块

18、号组号组号比较比较主存地址主存地址不相等不相等块失效块失效CACHE相等相等块表块表区号标志区号标志 主存块号标志主存块号标志 CACHE块号块号组内相联查找组内相联查找三、替换策略及更新策略三、替换策略及更新策略（一）替换策略（一）替换策略 在全相联和组相联映象方式下，主存中的数据块写入在全相联和组相联映象方式下，主存中的数据块写入CACHCACH中若干位置，这就有一个选择替换掉哪一个中若干位置，这就有一个选择替换掉哪一个CACHECACHE存储块的问题。存储块的问题。1 1、随机法（、随机法（RANDRAND）：随机地确定替换存储单元，没有根据访存局）：随机地确定替换存储单元，没有根据访存

19、局 部性原理，部性原理， 不能不能 提高系统的命中率。提高系统的命中率。2 2、先进先出法（、先进先出法（FIFOFIFO）：替换最早调入的存储单元。）：替换最早调入的存储单元。3 3、近期最少使用法（、近期最少使用法（LRULRU）：替换出近期用得最少的存储块，利）：替换出近期用得最少的存储块，利用用 了访存局部性的原理，但实现复杂。了访存局部性的原理，但实现复杂。例：设一个容量为例：设一个容量为4 4个块的全相联个块的全相联CACHECACHE，采用，采用FIFOFIFO替换算法，若替换算法，若主存的地址块号序列为主存的地址块号序列为2 2、11 11、2 2、9 9、7 7、6 6、4

20、4、3 3 画出每次访问画出每次访问后后CACHECACHE中的内容中的内容访问顺序访问顺序 1 2 3 4 5 6 7 81 2 3 4 5 6 7 8地址块号地址块号 2 11 2 9 7 6 4 32 11 2 9 7 6 4 3块分配情况块分配情况 22112112119211976119764976437（二）更新策略（写操作策略）（二）更新策略（写操作策略） 由于由于CacheCache的内容只是主存部分内容的复制，它应当的内容只是主存部分内容的复制，它应当和主存内容保持一致。当程序运行时需对某个单元进行写和主存内容保持一致。当程序运行时需对某个单元进行写操作，则会出现操作，则会出

21、现CacheCache和主存中的内容不一致。和主存中的内容不一致。1 1、写操作、写操作CACHECACHE命中时命中时 （1 1）写直达法：写写直达法：写CACHECACHE又写主存。又写主存。 （2 2）写回法：写）写回法：写CACHECACHE不写主存，当不写主存，当CACHECACHE中数据被中数据被 替换出去时才写主存。替换出去时才写主存。2 2、写操作、写操作CACHECACHE不命中时不命中时 （1 1）按写分配法：从主存将块调入）按写分配法：从主存将块调入CACHECACHE。（2 2）不按写分配法：当）不按写分配法：当CACHECACHE写不命中时该地址所对应写不命中时该地址所对应 的数据块不从主存调入的数据块不从主存调入CACHECACHE。四、层次化存储系统四、层次化存储系统 在存储系统中高速、大容量、低成本这三个因素相互制约，相在存储系统中高速、大容量、低成本这三个因素相互制约，相互矛盾。互矛盾。访存局部性规律：程序对存储空间的访存局部性规律：程序对存储空间的90%90%的访问局限于存储空间的的访