《计算机组成原理》教程第5章存储器-CACHE2.ppt

5.3 高速缓冲存储器（高速缓冲存储器（Cache）1.Cache-存储器映象存储器映象2.替换算法替换算法问题的提出问题的提出1.CPU和和I/O争抢访问主存争抢访问主存2.主存速度始终跟不上主存速度始终跟不上CPU的发展的发展100MHz的的Pentium处理器平均处理器平均10ns就执行一条指令，就执行一条指令，而而DRAM的典型访问时间是的典型访问时间是60120ns。Cache的出现主要使的出现主要使CPU不直接访问主存，只不直接访问主存，只与高速与高速Cache交换信息。交换信息。程序访问的局部性原理程序访问的局部性原理时间局部性：最近的访问项（指令时间局部性：最近的访问项（指令/数据）很可能在数据）很可能在不久的将来再次被访问（往往会引起对最近使用区域不久的将来再次被访问（往往会引起对最近使用区域的集中访问）的集中访问）空间局部性：一个进程访问的各项其地址彼此很近空间局部性：一个进程访问的各项其地址彼此很近（往往会访问在存储器空间的同一区域）（往往会访问在存储器空间的同一区域）命中、不命中、命中率命中、不命中、命中率Cache命中（命中（hit）CPU欲访问的数据已在缓存中，即可直接访问欲访问的数据已在缓存中，即可直接访问CacheCache不命中（不命中（miss）CPU欲访问的数据不在欲访问的数据不在Cache内，此时需将该内，此时需将该数所在的主存整个子块一次调入数所在的主存整个子块一次调入Cache中。中。命中率命中率是指是指CPU要访问的信息已在要访问的信息已在Cache内的比率。通常用命中率来衡量内的比率。通常用命中率来衡量Cache的的效率。效率。Cache效率效率Cache的的容量容量和和块长块长是影响是影响Cache效率的重效率的重要因素。要因素。Cache容量越大，命中率越高。容量越大，命中率越高。当当Cahce容量达到一定值时，命中率不会因容量容量达到一定值时，命中率不会因容量的增大而明显提高。的增大而明显提高。Cache容量大，成本增加。容量大，成本增加。Cache的命中率与的命中率与cache容量的关系容量的关系1Cache容量容量命中率命中率Cache的读数操作流程的读数操作流程开始开始CPU发出访存地址发出访存地址访问访问Cache取取出信息送出信息送CPU命命中中?结束结束访问主存取出访问主存取出信息送信息送CPU将新的主存块将新的主存块调入调入Cache中中执行替换算执行替换算法腾出空位法腾出空位Cache满满?YNNYCache的写操作的写操作命中命中写直达法（写直达法（Write-through、Store-though）每次写入每次写入Cache的同时，也写入主存。的同时，也写入主存。写回法（写回法（Write-back）：）：执行写操作时，信息只写入执行写操作时，信息只写入Cache；当当Cache块被替换时，先将该块内容写回主存，然后再调入新页。块被替换时，先将该块内容写回主存，然后再调入新页。信息只写入主存，同时将相应的信息只写入主存，同时将相应的Cache块块有效位有效位置置“0”不命中：被修改的单元根本不在不命中：被修改的单元根本不在Cache内，此时写操作内，此时写操作只能对主存进行。只能对主存进行。比较比较写回法的开销是在块替换时的回写时间，而写直达法则在每次写回法的开销是在块替换时的回写时间，而写直达法则在每次写入时，都要附加一个比写写入时，都要附加一个比写Cache长得多的写主存时间。长得多的写主存时间。一般来说，写直达法的开销大一些，但其一般来说，写直达法的开销大一些，但其一致性一致性保持的要好一保持的要好一些。些。关键在于如何使关键在于如何使Cache与主存内容保持一致。与主存内容保持一致。Cache的基本结构的基本结构Cahce存储体、地址映象变换机构、替换机构存储体、地址映象变换机构、替换机构Cahce存储体存储体以块为单位和主存交换信息以块为单位和主存交换信息Cache访存的优先级最高访存的优先级最高地址映象变换机构地址映象变换机构主要是主要是 主存块号和主存块号和Cache块号之间的转换。块号之间的转换。四种映象：直接映象、全相联映象、组相联映象和四种映象：直接映象、全相联映象、组相联映象和段相联映象。段相联映象。替换机构替换机构Cache内容已满时，无法接受来自主存块的信内容已满时，无法接受来自主存块的信息，需由息，需由Cache内的替换机构按一定的内的替换机构按一定的替换算替换算法法来确定从来确定从Cache内移出某个块写回主存。内移出某个块写回主存。Cache主存地址映象主存地址映象由主存地址映象到由主存地址映象到CacheCache地址称为地址映象。地址称为地址映象。直接映象直接映象全相联映象全相联映象组相联影响组相联影响段相连映象段相连映象1.直接映象直接映象CacheCache字块数为：字块数为：C=2C=2c c主存字块数为：主存字块数为：M=2M=2m m映射关系式：映射关系式：i=j mod Ci=j mod C 或或 i=j mod 2i=j mod 2c c字块字块0 0字块字块1 1字块字块2 2c c-1-1字块字块2 2c c字块字块2 2c c+1+1字块字块2 2c+1c+1-1-1字块字块2 2c+1c+1字块字块2 2m m-1-1主存储器主存储器字块字块0 0字块字块1 1字块字块2 2c c-1-1Cache缓存块号缓存块号i主存块号主存块号j00，C，2m-C11，C1，2m-C1C-1C-1，2C-1,，2m-1优点：实现简单，只需利用主存地址的某些位直优点：实现简单，只需利用主存地址的某些位直接判断，就可确定所需字块是否在缓存中。接判断，就可确定所需字块是否在缓存中。缺点：效率低。因为每个主存块固定地对应某个缺点：效率低。因为每个主存块固定地对应某个缓存块（有缓存块（有2t个主存字块对应同一个个主存字块对应同一个Cache字块）字块），如果这，如果这2t个字块中有两个或两个以上的主存字个字块中有两个或两个以上的主存字块要调入块要调入Cache，必然会发生冲突。这时，即使必然会发生冲突。这时，即使Cache中还有很多空闲块也无法占用，使缓存的中还有很多空闲块也无法占用，使缓存的空间得不到充分的利用。空间得不到充分的利用。2.全相联映像全相联映像标记标记标记主存字块标记主存字块标记字块内地址字块内地址主存地址主存地址m=t+c位位b位位m=t+c位位Cache“标记位标记位”增多，比较位数增加；而且访问增多，比较位数增加；而且访问Cache时需要和时需要和Cache的全部的全部“标记标记”进行比较，才能判断出所访问的主存地址的内容是否已在进行比较，才能判断出所访问的主存地址的内容是否已在Cache内。内。2.全相联映像（续全相联映像（续）字块号012345673.组相联映象组相联映象字块0字块1字块2c-r-1字块2c-r字块2c-r+1字块2c-r+1字块2m-1主存储器主存储器标记字块0标记字块1标记字块2标记字块3标记字块2c-2标记字块2c-1Cache（r1）第第0组组第第1组组第第2c-r-1组组主存地址主存地址主存子块标记组地址子块内地址s=t+r位q=c-r位b位m位3.组相联映象（续）组相联映象（续）原理：把Cache分为Q(=2q)组，每组有R(=2r)块，且 i=j mod Q其中，i为缓存的组号，j为主存的块号r0，直接相联；rc，全相联。在主存块和Cache的各组之间，属于直接映象关系；而主存块可以映射到对应组内的任何一块，这又体现出了全相联映象的关系。4.段相联映象段相联映象它将主存和它将主存和Cache都分成若干段，且使得都分成若干段，且使得它们每段包含的块数都相等它们每段包含的块数都相等段之间采用全相联映象，段内块之间采用段之间采用全相联映象，段内块之间采用直接映象直接映象。当段数与当段数与Cache块数相等时（即每段只包块数相等时（即每段只包含一块），便为全相联映象；当段数为含一块），便为全相联映象；当段数为1时，时，便为直接映象。便为直接映象。四种映象方式比较四种映象方式比较直接映象直接映象：优点是实现简单，缺点是不够灵活。：优点是实现简单，缺点是不够灵活。全相联映象全相联映象：实现电路较多：实现电路较多,成本较高，实际的成本较高，实际的Cache还要采用各种措施来减少地址的比较次数。还要采用各种措施来减少地址的比较次数。组相联映象和段相联映象组相联映象和段相联映象：是直接映象和全相联：是直接映象和全相联映象相结合的两种形式。映象相结合的两种形式。替换算法替换算法替换算法先进先出算法（先进先出算法（FIFO）：选择最早装入的选择最早装入的Cache字块替换出来。这种算法实现起来比较字块替换出来。这种算法实现起来比较方便，但不能正确反映程序的局部性。因为最方便，但不能正确反映程序的局部性。因为最先进入的字块也可能是目前经常要用的字块，先进入的字块也可能是目前经常要用的字块，因此，采用这种算法，有可能产生较大的失效因此，采用这种算法，有可能产生较大的失效率。率。近期最少使用算法（近期最少使用算法（LRU）：选择选择“近期最少使近期最少使用用”块作为调出块，这种算法能比较正确反映块作为调出块，这种算法能比较正确反映程序的局部性，因为当前最少使用的块一般来程序的局部性，因为当前最少使用的块一般来说也是未来最少被访问的块。但是它的具体实说也是未来最少被访问的块。但是它的具体实现比现比FIFO要复杂一些。要复杂一些。随机替换随机替换FIFO替换算法替换算法近期最少使用算法近期最少使用算法例：选最近例：选最近4 4次访问期间最少使用次访问期间最少使用CacheCache块作为被替换的块。块作为被替换的块。将内存与外存结合使用，好像有一个容量极大的内存储器，工将内存与外存结合使用，好像有一个容量极大的内存储器，工作速度接近于主存，每位成本又与辅存相近作速度接近于主存，每位成本又与辅存相近.虚拟存储器虚拟存储器工作过程包括6个步骤：中央处理器访问主存的逻辑地址分解成组号中央处理器访问主存的逻辑地址分解成组号a和和组组内地址内地址b，并并对组对组号号a进进行地址行地址变换变换，即将，即将逻逻辑组辑组号号a作作为为索引，索引，查查地址地址变换变换表，以确定表，以确定该组该组信信息是否存放在主存内。息是否存放在主存内。如如该组该组号已在主存内，号已在主存内，则转则转而而执执行行；如果；如果该组该组号不在主存内，号不在主存内，则检查则检查主存中是否有空主存中是否有空闲闲区，如果没有便将某个区，如果没有便将某个暂时暂时不不用的用的组调组调出送往出送往辅辅存，以便将存，以便将这组这组信息信息调调入主存。入主存。从从辅辅存存读读出所要的出所要的组组，并送到主存空，并送到主存空闲闲区，然区，然后将那个空后将那个空闲闲的物理的物理组组号号a和和逻辑组逻辑组号号a登登录录在地在地址址变换变换表中。表中。从地址从地址变换变换表表读读出与出与逻辑组逻辑组号号a对对应应的物理的物理组组号号a。从物理从物理组组号号a和和组组内字内字节节地址地址b得到物理地址。得到物理地址。根据物理地址从主存中存取必根据物理地址从主存中存取必要的信息要的信息。