课件第5章使用

1、1 1/154/1545.15.1存储器的层次结构存储器的层次结构和和虚拟存储器虚拟存储器5.25.2高速缓冲存储器高速缓冲存储器CacheCache 5.35.3降低降低CacheCache失效率的方法失效率的方法5.45.4减少减少CacheCache失效开销失效开销5.55.5减少命中时间减少命中时间5.65.6主存主存5.75.7进程保护和虚存实例进程保护和虚存实例5.95.9Alpha AXP 21064Alpha AXP 21064存储层次存储层次第第5章章 存储层次存储层次2 2/154/154 5.2 高速缓存高速缓存 CACHE 用途：用途：设置在设置在 CPU 和和 主存储

2、器之间，完成高速与主存储器之间，完成高速与 CPU 交换信息，尽量避免交换信息，尽量避免 CPU不必要地多次直接访问慢不必要地多次直接访问慢速的主存储器速的主存储器，从而提高计算机系统的运行效率。从而提高计算机系统的运行效率。 实现：实现：这是一个存储容量很小，但读写速度更快的，这是一个存储容量很小，但读写速度更快的，以关联存储器方式运行、用静态存储器芯片实现的存储以关联存储器方式运行、用静态存储器芯片实现的存储器系统。器系统。 要求：要求：有足够高的命中率，既当有足够高的命中率，既当 CPU需用主存中的需用主存中的数据时，多数情况可以直接从数据时，多数情况可以直接从CACHE中得到，称二者之

3、中得到，称二者之比为命中率。比为命中率。返回返回3 3/154/1544 4/154/1545 5/154/154 存储层次存储层次CPU对第二级的对第二级的访问方式访问方式比较项目比较项目目的目的存储管理实现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小失效时失效时CPU是否切换是否切换“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为了弥补主存速度的不足 为了弥补主存容量的不足为了弥补主存容量的不足主要由专用硬件实现主要由专用硬件实现主要由软件实现主要由软件实现几比一几比一几百比一几百比一几十个字

4、节几十个字节几百到几千个字节几百到几千个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程“Cache“Cache主存主存”与与“主存辅存主存辅存”层次的区别层次的区别6 6/154/154程序的局部性原理1. 程序在一定时间段内通常只访问较小的地址空间2. 两种局部性：时间局部性和空间局部性时间局部性：最近被访问的信息很可能还要被访问。q将最近被访问的信息项装入到将最近被访问的信息项装入到Cache中。中。空间局部性：最近被访问的信息临近的信息也可能被访问。q将最近被访问的信息项临近的信息一起装入到将最近被访问的信息项临近的信息一起装入到Cache中。中

5、。地址空间访问概率7 7/154/154 1.1. 当把一个块调入高一层当把一个块调入高一层( (靠近靠近CPU)CPU)存储器时，存储器时，可以放在哪些位置上可以放在哪些位置上? ? （映像规则）映像规则）2.2. 当所要访问的块在高一层存储器中时，如何当所要访问的块在高一层存储器中时，如何找到该块找到该块? ?（查找算法）（查找算法）3. 当发生失效时，应替换哪一块？当发生失效时，应替换哪一块？（替换算法）（替换算法）4.4. 当进行写访问时，应进行哪些操作当进行写访问时，应进行哪些操作? ? （写策略）写策略）存储存储层次的四个问题：层次的四个问题：8 8/154/1541. 存储空间分

6、割与地址计算存储空间分割与地址计算2.2. CacheCache和主存分块和主存分块 Cache Cache的基本知识的基本知识 Cache是按块进行管理的。是按块进行管理的。Cache和主存均被分割成和主存均被分割成大小相同的块。信息以块为单位调入大小相同的块。信息以块为单位调入Cache。 主存块地址（块号）用于查找该块在主存块地址（块号）用于查找该块在Cache中的位置。中的位置。块内位移用于确定所访问的数据在该块中的位置。块内位移用于确定所访问的数据在该块中的位置。9 9/154/1545.2 Cache的基本知识5.2.15.2.1映象规则映象规则 1. 全相联映象全相联映象 全相联

7、：全相联：主存中的任主存中的任一块可以被放置到一块可以被放置到CacheCache中的任意一个位中的任意一个位置。置。举例举例对比：对比：阅览室位置阅览室位置 随便坐随便坐特点：特点：空间利用率最空间利用率最高，冲突概率最低，高，冲突概率最低，实现最复杂实现最复杂1010/154/1545.2 Cache的基本知识2. 直接映象直接映象 直接映象：直接映象：主存中的每一块只能被放置到主存中的每一块只能被放置到CacheCache中唯一的一个位置。中唯一的一个位置。举例举例（循环分配）（循环分配）对比：对比：阅览室位置阅览室位置 只有一个位置可以坐只有一个位置可以坐特点：特点：空间利用率最低，冲

8、突概率最高，空间利用率最低，冲突概率最高，实现最简单。实现最简单。对于主存的第对于主存的第i i 块，若它映象到块，若它映象到CacheCache的第的第j j 块，块，则则 j ji i mod ( mod (M M ) ) （M M为为CacheCache的块数）的块数）1111/154/154设设M=2M=2m m，则当表示为二进制数时，则当表示为二进制数时，j j实际上就是实际上就是i i的低的低m m位位: : ji：m位位5.2 Cache的基本知识 直接映象方式的地址映象规则直接映象方式的地址映象规则 块块 0 块块 1 区区 0 块块 Cb-1 块块 0 块块 Cb 块块 1

9、块块 Cb+1 区区 1 块块 Cb-1 块块 2Cb-1 Cache 块块 Mb-Cb 块块 Mb-Cb+1 区区 Me-1 块块 Mb-1 主主存存储储器器 1313/154/1545.2 Cache的基本知识3.组相联映象组相联映象 Cache分为分为Gb-1组，组，主存以主存以Gb-1大小分多大小分多个区个区组相联：主存中的每一组相联：主存中的每一块可以被放置到块可以被放置到Cache中唯一的一个组中的任中唯一的一个组中的任何一个位置。何一个位置。 举例举例组相联是直接映象和全组相联是直接映象和全相联的一种折中相联的一种折中主存的块与主存的块与CACHE的的组实现直接映像组实现直接映像

10、主存的块与主存的块与CACHE的的组内块号实现全相联映组内块号实现全相联映象象 块块0 1 区区0 块块0 组组0 Cg-1 Gb-1 Cg Gb Cg+1 组组1 区区1 2Gb-1 2Cg-1 Cb-Gb=CgGb-Gb Cg-1 Cg(Mb-1) Cb-1=CgGb-1 Cg(Mb-1)+1 Cache 区区Me-1 Mb-1=CgMe-1 主主 存存 储储 器器 1515/154/1541616/154/1545.2 Cache的基本知识组的选择常采用位选择算法组的选择常采用位选择算法q若主存第若主存第i i 块映象到第块映象到第k k 组，则组，则 k ki i modmod（G G

11、） （G G为为CacheCache的组数）的组数）q设设G G2 2g g，则当表示为二进制数时，则当表示为二进制数时，k k 实际上就是实际上就是i i 的低的低 g g 位位: : 低低g位位和直接映象中的和直接映象中的低低m位位通常称为通常称为索引。索引。 ki：g位位1717/154/1545.2 Cache的基本知识n n 路组相联：路组相联：每组中有每组中有n n个块个块( (n nM M/ /G G ) )。n n 称为称为相联度。相联度。（M M为为CacheCache的块数）的块数）相联度越高，相联度越高，CacheCache空间的利用率就越高，块冲突空间的利用率就越高，块

12、冲突概率就越低，失效率也就越低。概率就越低，失效率也就越低。 绝大多数计算机的绝大多数计算机的Cache: Cache: n n 44想一想：想一想：相联度一定是越大越好？相联度一定是越大越好？全相联全相联直接映象直接映象组相联组相联n n ( (路数路数) )G G ( (组数组数) )M MM M1 11 11 1n nM M1 1G GM M1818/154/1545.2 Cache的基本知识当当CPUCPU访问访问CacheCache时，如何确定时，如何确定CacheCache中是否有所要中是否有所要访问的块？访问的块？若有，如何确定其位置？若有，如何确定其位置？1. 通过查找目录表来

13、实现通过查找目录表来实现目录表的结构目录表的结构q主存块的块地址的主存块的块地址的高位高位部分，称为部分，称为标识标识 。q每个主存块能唯一地由其标识来确定每个主存块能唯一地由其标识来确定5.2.2 5.2.2 查找算法查找算法 主主存存地地址址： 块块内内位位移移 索索 引引 标标 识识 块块地地址址 1919/154/1545.2 Cache的基本知识只需查找只需查找候选位置候选位置所对应的目录表项所对应的目录表项2. 并行查找与顺序查找并行查找与顺序查找提高性能的提高性能的重要思想：重要思想：主候选位置主候选位置(MRU块块) （前瞻执行）（前瞻执行）3. 并行查找的实现方法并行查找的实

14、现方法相联存储器相联存储器单体多字存储器比较器单体多字存储器比较器 q举例：举例： 路组相联并行标识比较路组相联并行标识比较（比较器的个数及位数）（比较器的个数及位数）q路路组组相联相联CacheCache的查找过程的查找过程q直接映象直接映象CacheCache的查找过程的查找过程2020/154/1545.2 Cache的基本知识2121/154/1542 2、查找方法、查找方法 即如何在候选位置中查找数据块。即如何在候选位置中查找数据块。 * *候选位置：候选位置：直接映像直接映像1 1个；个；组相联映像组相联映像组内块数组内块数n n； 全相联映像全相联映像全部块数全部块数G G。 *

15、 *查找方法：查找方法：按地址查找；按内容查找。按地址查找；按内容查找。(1)(1)按地址查找按地址查找 有串行和并行查找两种方法，基本均采用并行查找方法。有串行和并行查找两种方法，基本均采用并行查找方法。主存块地址主存块地址标识标识r r索引索引s s0 01 1s s有效位有效位 标识标识 其他其他=?=?(a)(a)候选位置为候选位置为1 1个的按地址查找个的按地址查找0 01 1s s有效位有效位 标识标识 有效位有效位 标识标识标识标识r r索引索引s s第第1 1路路 第第2 2路路=?=?+ +=?=?(b)(b)候选位置为多个的按地址查找候选位置为多个的按地址查找回下页 全相联

16、地址变换规则全相联地址变换规则 块块号号 B 块块内内地地址址W 主主存存地地址址 Cache 地地址址 块块号号 b 块块内内地地址址 w 相相联联比比较较 命命中中 B b 主主存存块块号号 B Cache 块块号号 b 有有效效位位 目目录录表表（由由相相联联存存储储器器构构成成，共共 Cb个个字字） 主主存存地地址址 区区号号 E 块块号号 B 块块内内地地址址W Cache 地地址址 块块号号 b 块块内内地地址址 w 块块失失效效 相相等等比比较较 比比较较相相等等且且有有效效为为 1 E 1 访访问问 Cache 区区号号 E（按按地地址址访访问问） 有有效效位位 区区表表存存储

17、储器器 直接映象方式的地址变换规则直接映象方式的地址变换规则 区区号号 E区区内内块块号号 B块块内内地地址址 W 主主存存地地址址 块块失失效效组组号号 g组组内内块块号号 b块块内内 w 与与Cache 地地址址或或相相等等比比较较相相等等比比较较 相相等等比比较较 E b E b E b区区号号E块块号号b e区区号号E块块号号b e区区号号E块块号号b e块块表表(按按地地址址访访问问,读读出出的的多多个个区区号号进进行行相相联联比比较较,e 是是有有效效位位)组相联的地址变换规则组相联的地址变换规则2525/154/154目录表查找示例目录表查找示例11111111111111110

18、00000000000000000000001000000010000010110101111000000000000000001000001111111111111访存地址：访存地址：0001010100010101访存地址：访存地址：000101000101 0101块内地址块内地址块地址块地址256256个字节的主存空间个字节的主存空间6464个数据块的主存空间个数据块的主存空间（块大小（块大小4 4字节）字节）块号块号主存地址主存地址2626/154/1540000000000000010010000008 8个数据块的个数据块的cache:cache:直接映象直接映象（路数为（路数为

19、1 1，组数为，组数为G=8G=8，因此索引为，因此索引为3 3位）位） 0100100000000110110000001001000000001011010000001101100000001111110000006464个数据块的主存空间个数据块的主存空间标识标识数据体数据体2 2tagtagindexindexOffsetOffset3 33 3访存地址：访存地址：XXX XXX 000 000 0000000010010000000100102727/154/1540000000000000001000100008 8个数据块的个数据块的cache:2cache:2路组相联路组相联，

20、（G=4G=4组，因此索引为组，因此索引为2 2位位, ,主存分为主存分为64/4=1664/4=16区，区，每区每区4 4个主存块）个主存块）0010001000000011001100001100110000001101110100001110111000001111111100006464个数据块的主存空间个数据块的主存空间标识标识数据体数据体2 2tagtagindexindex OffsetOffset4 42 2访存地址：访存地址：XXXX XXXX 00 00 2828/154/15400000000000 000001000010 08 8个数据块的个数据块的cache:4ca

21、che:4路组相联路组相联（组数（组数G=2G=2，因此索引位是，因此索引位是1 1位）位）00010000100 000011000110 011100111000 011101111010 011110111100 011111111110 06464个数据块的主存空间个数据块的主存空间标识标识数据体数据体2 2tagtagindexindex OffsetOffset5 51 1访存地址访存地址：XXXXX XXXXX 0 0 2929/154/1540000000000000000010000018 8个数据块的个数据块的cache:cache:全相联（全相联（8 8路路）（组数（组数

22、1 1，索引位为，索引位为0 0位）位）0000100000100000110000111111001111001111011111011111101111101111111111116464个数据块的主存空间个数据块的主存空间标识标识数据体数据体2 2tagtagOffsetOffset6 6访存地址：访存地址：XXXXXXXXXXXX 3030/154/1545.2 Cache的基本知识1.1. 所要解决的问题：所要解决的问题：当新调入一块，而当新调入一块，而CacheCache又已被占又已被占满时，替换哪一块？满时，替换哪一块？直接映象直接映象CacheCache中的替换很简单中的替换很

23、简单 因为只有一个块，别无选择。因为只有一个块，别无选择。在组相联和全相联在组相联和全相联CacheCache中，则有多个块供选择。中，则有多个块供选择。2.主要的替换算法有三种主要的替换算法有三种 （1）随机法）随机法 是由随机数产生需替换的块号。没有考虑信息的历史是由随机数产生需替换的块号。没有考虑信息的历史情况，所以其命中率很低。情况，所以其命中率很低。 优点：优点：实现简单实现简单5.2.3 5.2.3 替换算法替换算法3131/154/1543232/154/1543333/154/1545.2 Cache的基本知识LRULRU和随机法分别因其失效率低和实现简单而被广泛采用。和随机法

24、分别因其失效率低和实现简单而被广泛采用。3434/154/1541. “写写”在所有访存操作中所占的比例在所有访存操作中所占的比例 统计结果表明，对于一组给定的程序：统计结果表明，对于一组给定的程序：ql loadoad指令：指令：2626qs storetore指令：指令：9 9“写写”在所有访存操作中所占的比例：在所有访存操作中所占的比例：9 9/(100/(10026269 9)7)7“写写”在访问在访问CacheCache操作中所占的比例：操作中所占的比例： 9 9/(26/(269 9)25)255.2.4 写策略3535/154/1545.2 Cache的基本知识 由于由于Cach

25、e中保存的只是主存的部分副本，中保存的只是主存的部分副本，那么，这些副本与主存中的内容是否能保持那么，这些副本与主存中的内容是否能保持一致，这是一致，这是Cache能否可靠工作的一个关键能否可靠工作的一个关键问题。问题。 由于以下两个原因，在一段时间内，主存由于以下两个原因，在一段时间内，主存某单元中的内容与某单元中的内容与CacheCache对应单元中的内容对应单元中的内容可能不相同。这样，就造成可能不相同。这样，就造成CacheCache与主存的与主存的不一致问题。不一致问题。5.2.4 写策略3636/154/154(1) (1) 如图如图(a)(a)所示。由于所示。由于CPUCPU写写

26、CacheCache，把，把CacheCache某单元中某单元中的内容从的内容从X X修改成了修改成了XX，而主存对应单元中的内容还仍然，而主存对应单元中的内容还仍然是是X X，没有改变。，没有改变。(2) (2) 如图如图(b)(b)所示。由于输入输出处理机或输入输出设备所示。由于输入输出处理机或输入输出设备修改了主存某单元中的内容，把修改了主存某单元中的内容，把X X修改成了修改成了XX，而，而CacheCache对应单元中的内容还仍然是对应单元中的内容还仍然是X X，没有改变。，没有改变。3737/154/1545.2 Cache的基本知识 当第当第1 1种情况发生时，如果把包括种情况发

27、生时，如果把包括X X在内的主存中的在内的主存中的数据输出到设备去，或者在第数据输出到设备去，或者在第2 2种情况发生时，种情况发生时，CPUCPU读了读了CacheCache中的数据中的数据X X，都可能造成错误。，都可能造成错误。解决解决CacheCache与主存的不一致性问题，首先要选与主存的不一致性问题，首先要选择合适的择合适的CacheCache更新算法。更新算法。 主要有两种主要有两种CacheCache更新算法：更新算法： 写回法写回法WB(Write-Back)WB(Write-Back)，写回法又称为抵触修改，写回法又称为抵触修改法。法。 写直达法，写直达法，写直达法又称为写

28、通过法写直达法又称为写通过法WT(Write- WT(Write- through)through)3838/154/154 写回法：写回法：是指是指CPUCPU在执行写操作时，被写数据只写入在执行写操作时，被写数据只写入CacheCache，不写入主存。，不写入主存。 仅当需要替换时，才把已经修改过的仅当需要替换时，才把已经修改过的CacheCache块写回块写回到主存。在采用这种更新算法的到主存。在采用这种更新算法的CacheCache块表中，一般块表中，一般有一个有一个 修改位修改位 。 当一块中的任何一个单元被修改时，这一块的修改当一块中的任何一个单元被修改时，这一块的修改位就被置位就

29、被置11，否则这一块的修改位仍保持，否则这一块的修改位仍保持00。 在需要替换这一块时，如果对应的修该位为在需要替换这一块时，如果对应的修该位为11，则必须先把这一块写回到主存中去之后，才能再调入则必须先把这一块写回到主存中去之后，才能再调入新的块。如果修改位为新的块。如果修改位为00，则这一块不必写回主存，则这一块不必写回主存，只要用新调入的块覆盖掉这一块即可只要用新调入的块覆盖掉这一块即可。 3939/154/154 写直达法写直达法是指是指CPUCPU在执行写操作时，必须把数据同在执行写操作时，必须把数据同时写入时写入CacheCache和主存。和主存。 在在CacheCache的块表中

30、就不需要的块表中就不需要 修改位修改位 。当某一块需。当某一块需要替换时，也不必把这一块写回到主存中去，新要替换时，也不必把这一块写回到主存中去，新调入的块可以立即把这一块覆盖掉。调入的块可以立即把这一块覆盖掉。4040/154/154n写直达：将数据同时写入主存写直达：将数据同时写入主存n但这样会使写时间更长但这样会使写时间更长ne.g., 没有缺失情况，基本的没有缺失情况，基本的CPI = 1, 10% 的指令的指令是是store指令指令,每次写到内存需要每次写到内存需要100个时钟周期，个时钟周期，n 有效的有效的 CPI = 1 + 0.1100 = 11n解决方法：写缓冲解决方法：写

31、缓冲n数据被放入写缓冲等待写存储器操作完成，之后释数据被放入写缓冲等待写存储器操作完成，之后释放写缓冲放写缓冲nCPU立即继续执行其他指令立即继续执行其他指令n仅当缓冲区满时产生写阻塞仅当缓冲区满时产生写阻塞4141/154/154比较写回法与写直达法的优缺点如下：比较写回法与写直达法的优缺点如下：(1) (1) 可靠性：写直达法要优于写回法。这是可靠性：写直达法要优于写回法。这是因为写直达法能够始终保持因为写直达法能够始终保持CacheCache是主存的正确是主存的正确副本。如果副本。如果CacheCache发生错误，可以从主存得到纠发生错误，可以从主存得到纠正。而写回法当发生正。而写回法当

32、发生 上述两种情况时，在一段上述两种情况时，在一段时间内，时间内，CacheCache并不是主存的正确副本。并不是主存的正确副本。4242/154/154(2) (2) 与主存的通信量：一般情况下，写回法少于写直达法。与主存的通信量：一般情况下，写回法少于写直达法。原因可以从两方面来分析。一方面，由于原因可以从两方面来分析。一方面，由于CacheCache的命中率的命中率一般很高，对于写回法，一般很高，对于写回法，CPUCPU的绝大多数写操作只需写的绝大多数写操作只需写CacheCache，不必写主存。另一方面，当写，不必写主存。另一方面，当写CacheCache发生块失效发生块失效时，可能要

33、写一个块到主存，而写直达法每次只写一个时，可能要写一个块到主存，而写直达法每次只写一个字到主存。而且，即使是读操作，当字到主存。而且，即使是读操作，当CacheCache不命中时，写不命中时，写回法也可能因为发生块替换而要写一块到主存。回法也可能因为发生块替换而要写一块到主存。 写回法的优点是速度快，“写”操作能以 Cache 存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达 Cache ，不到达主存，因而所使用的存储器频带较低。4343/154/1545.2 Cache的基本知识 (3) 控制的复杂性：写直达法比写回法简单。写回法要在块表中为每一块设置

34、一个修改位，而且要对修改位进行管理和判断。而写直达法不需要设置修改位。另外，由于写直达法能够始终保持Cache是主存的正确副本。一旦Cache发生错误，可以从主存得到纠正。因此，Cache通常只需要采用简单的奇偶校验即可。而对于写回法，Cache中的块必须自己独立保证正确性，因此要采用相对比较复杂的纠错码。4444/154/154(4) 硬件实现的代价：写回法要比写直达法好。在写直达法中，因为每次写操作都要写主存，因此为了节省写主存所花费的时间，通常要采用一个高速小容量的缓冲存储器，把要写主存的数据和地址先写到这个缓冲存储器中。在每次读主存时，也要首先判断所读的数据是否在这个缓冲存储器中。而写

35、回法的硬件实现代价相对比较低。4545/154/154 目前，很多单处理机都采用写回法，主要目的是为了减少Cache与主存之间的通信量。也有不少的单处理机采用写直达法，目的是为了硬件的控制比较简单。而几乎所有的多处理机都采用写直达法。例如，IBM 3033、IBM 370/168、VAX-11/780、Honeywell 66/60、Honeywell 66/80 等机器采用写直达法。而Amdahl 的所有机器，IBM 3081等机器采用写回法。 4646/154/1545.2 Cache的基本知识 “写”操作时的调块即当发生写失效时，是否调入相应的块，有两种选择：按写分配(写时取)写失效时，

36、先把所写单元所在的块调入写失效时，先把所写单元所在的块调入CacheCache，然后再进行写入然后再进行写入 不按写分配(绕写法)写失效时，写失效时，直接写入下一级存储器而不将相应的块调入直接写入下一级存储器而不将相应的块调入Cache。写策略与调块：写回法Cache-采用按写分配法（这样以后对那个块的“写”就能被Cache捕获）。写直达法-采用不按写分配法（因为以后对那个块的“写”仍然还要到达下一级存储器）。4747/154/154高速缓冲存储器基本工作原理总结高速缓冲存储器基本工作原理总结(1)(1)存储空间管理存储空间管理 * *信息交换单位：信息交换单位：Cache-CPUCache-

37、CPU间为字、间为字、Cache-Cache-主存间为字块；主存间为字块； CacheCache、主存中字块内字的偏移固定。、主存中字块内字的偏移固定。CacheCache地址表示：地址表示：CacheCache块号块号块内地址块内地址主存地址表示：主存地址表示：主存块号主存块号块内地址块内地址 * *存储空间管理：存储空间管理：按字块按字块( (常称为块，有称行常称为块，有称行) )进行管理。进行管理。 * *管理信息存储：管理信息存储：用目录表用目录表( (每个块每个块1 1行行) )存储块管理信息。存储块管理信息。CacheCache主存主存CPUCPU字字/ /次次( (如如4B)4B

38、)块块/ /次次( (如如32B)32B)按主存地址访问按主存地址访问 块管理信息：块管理信息：对应主存块号对应主存块号有效位有效位与主存块是否一致等与主存块是否一致等4848/154/154(2)(2)完成访问过程完成访问过程按按替换算法替换算法，找出一个块号，找出一个块号i i块块i i被修改过？被修改过？块块i i写回写回主存主存CacheCache有空闲空间？有空闲空间？调进调进目标主存块目标主存块Y YN NY YN N根据根据映像规则映像规则，按，按查找方法查找方法查目录表查目录表命中？命中？块内地址块内地址(CPU(CPU访问的访问的) )主存地址：主存地址：CacheCache

39、块号块号CacheCache地址：地址：根据根据映像规则映像规则, ,进行进行地址变换地址变换按按CacheCache地址访问阵列，完成地址访问阵列，完成CPUCPU访问访问( (字大小字大小) )主存块号主存块号块内地址块内地址Y YN N若若CPUCPU访问为写操作，按访问为写操作，按写策略写策略将该块将该块写回写回主存主存转上页回下页4949/154/1545.2 Cache的基本知识例：例：DECDEC的的Alpha AXP21064Alpha AXP21064中的内部数据中的内部数据CacheCache1.简介简介容量：容量：8 8 KBKB块大小：块大小：3232 B B块数：块数

40、：256256采用采用不按写分配不按写分配映象方法：映象方法：直接映象直接映象 “写写”策略：策略：写直达写直达写缓冲器大小：写缓冲器大小：4 4个块个块5.2.5 Cache5.2.5 Cache的结构的结构5050/154/1542. 结构图5151/163/1637.2 Cache基本知识21064微处理器传送给cache的物理地址为34位Cache的容量与索引index、相联度、块大小之间的关系Cache的容量=2index相联度块大小 把容量为8192=8KB、相联度为1、块大小为32（字节）代入上式：索引index：8位 标识：29821位 于是主存地址格式为： 21 8 5 标识

41、标识 索引索引块内位移块内位移5252/163/163练习：练习：针对针对Alpha AXP21064Alpha AXP21064，请给出映象方法分别为，请给出映象方法分别为4 4路组相联和全相联的主存地址格式路组相联和全相联的主存地址格式5353/154/1543. 21064读数据读数据Cache第一步：地址的分割。第一步：地址的分割。 21064微处理器传送给Cache的物理地址为34位。这个地址被分为两部分：块地址（29位）和块内偏移量（5位）。块地址进一步被分为地址标识（21位）和Cache索引（8位）； 索引从256个Cache块中选择一块，读出数据和标识；标识用于判断要访问的块是

42、否在Cache中（是否命中）；索引的位数由Cache容量、块大小、相联度决定。21064的Cache是直接映象的，所以相联度为1，索引所需的位数满足： 索引为8位，标识为29821位。5454/154/154第二步：按索引选择标识和数据。 在直接映象的Cache中，读出数据并送往CPU与读出标识并进行匹配这两个过程可以并行进行。第三步：标识比较。 标识从Cache中读出来后，就去和CPU送来的物理地址中的标识部分进行比较。为了保证标识信息有效，其相应的有效位必须位“1”，否则比较的结果就是无效的。5555/154/154第四步：CPU从Cache中取数据。 如果标识比较的结果是匹配，且有效位为

43、“1”，那么最后一步就是发信号通知CPU从Cache中取走数据。 其它说明：21064完成这4步骤需要2个时钟周期；在这两个周期中间。指令需要用到本次“读”的结果，这条指令就只好等待。5656/154/1544. 21064写数据写数据Cache 写命中：前三步跟上面是一样的。在确认标识比较为匹配之后，才把数据写入。因为21064使用写直达Cache，所以到此写过程还未结束，还应将数据送往写缓冲器。 21064的写缓冲器有四块，每块大小为4个字，缓冲器是按字寻址的（21064中每个字为8字节）。 写缓冲器为空，就把数据和完整的地址写入缓冲器。对CPU而言，本次“写”访问已完成，可以继续工作，而

44、写缓冲器将负责把该数据写入主存。5757/154/1545. 21064的的Cache失效失效 读失效：Cache向CPU发出一个暂停信号，通知它等待；从下一级存储器中读入32字节数据；21064的Cache和它的下一级存储器之间的数据通路（21064微处理器总线的数据通道）为16字节（128位）。每次数据传送需要5个时钟周期，传送全部32自己数据就需要10个时钟周期。21064的数据Cache是直接映象，所以被替换只有一个；替换一个块意味着更新该块的数据、标识和有效位。 写失效：21064采用不按写分配规则，也就是说CPU将数据“绕过”Cache，直接写入主存。5858/154/1546.混

45、合混合Cache与分离与分离Cache （1） 指令数据混合Cache（称为统一Cache或混合Cache）：同时提供数据和指令，但它有可能会称为瓶颈。例如，当按流水方式工作的处理器执行Load或Store指令时，可能会同时请求一个数据字和一个指令字，导致CPU等待。 解决这个问题的一个简单的方法: 将单一的 Cache 分为两个 Cache ：一个专门存放指令，另一个专门存放数据 5959/154/154（2）分离的Cache：将单一的Cache分为两个Cache，一个专门存放指令，另一个专门存放数据。21064有一个8KB的指令Cache，其结构和8KB数据Cache几乎一样。 提高了系统

46、对存储系统和CPU之间数据通道带宽的要求；能分别对他们进行优化。 结果：指令Cache的失效率比数据Cache的低； 消除了因Cache中的指令块和数据块互相冲突而引起的失效。 表5-4列出了不同容量的指令Cache、数据Cache以及混合Cache在相同条件下的失效率。6060/154/1545.2 Cache的基本知识16 KB16 KB容量容量1 KB1 KB2 KB2 KB4 KB4 KB8 KB8 KB32 KB32 KB指令指令 Cache3.06%5-45-4表表 失失 效效 率率 的的 比比 较较64 KB64 KB128 KB128 KB数据数据 Cache混合混合 Cach

47、e2.26%1.78%1.10%0.64%0.39%0.15%0.02%24.61%20.57%15.94%10.19%6.47%4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%6161/154/154 从表5-4可以看出，指令 Cache 的失效率比数据 Cache 的低。 分离指令 Cache 和数据 Cache 消除了因 Cache 中的指令块和数据块互相冲突而引起的失效，但是这样一来也限定了分配给指令和数据的空间。 究竟哪一方面对失效率的影响更大呢？若要公平地对分离 Cache 和混合 Cache 进行比较，就要求两种 C

48、ache 的总容量相同。例如，分离的1KB指令 Cache 和1KB数据 Cache 就应该和容量为2KB的混合 Cache 相比较。6262/154/154 为了计算分离的指令 Cache 和数据 Cache 的平均失效率，首先必须知道对每种类型的 Cache 进行访问的百分比。 从统计可知：对指令 Cache 的访问占全部访问的100%(100%26%9%)，即大约75%；而对数据 Cache 的访问占全部访问的（26%9%）(100%26%9%)，即大约25%。除改变失效率外，指令 Cache 和数据 Cache 相分离还会影响性能的其他方面，后面将详细介绍这一点。 6363/154/1

49、545.2 Cache的基本知识1. 失效率失效率 失效率与硬件速度无关，用它来评价存储系统失效率与硬件速度无关，用它来评价存储系统的性能非常方便，所以我们经常使用它。但是，的性能非常方便，所以我们经常使用它。但是，它也容易产生一些误导。一种更好的评测存储系它也容易产生一些误导。一种更好的评测存储系统性能的指标是平均访存时间：统性能的指标是平均访存时间： 2. 平均访存时间平均访存时间 平均访存时间平均访存时间 命中时间失效率命中时间失效率失效开销失效开销5.2.6 Cache的性能分析6464/154/1545.2 Cache的基本知识 例例5.1 5.1 假设假设CacheCache的命中

50、时间为的命中时间为1 1个时钟周期，失个时钟周期，失效开销为效开销为5050个时钟周期，在混合个时钟周期，在混合CacheCache中一次中一次loadload或或storestore操作访问操作访问CacheCache的命中时间都要增加的命中时间都要增加1 1个时钟周个时钟周期（因为混合期（因为混合CacheCache只有一个端口，无法同时满足两只有一个端口，无法同时满足两个请求，会导致结构冲突），根据表个请求，会导致结构冲突），根据表5.45.4所列的失效所列的失效率，试问指令率，试问指令CacheCache和数据和数据CacheCache容量均为容量均为16 KB16 KB的分的分离离C

51、acheCache和容量为和容量为32 KB32 KB的混合的混合CacheCache相比，相比，哪种哪种CacheCache的失效率更低？的失效率更低？又假设采用写直达策略，且又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。请有一个写缓冲器，并且忽略写缓冲器引起的等待。请问上述两种情况下平均访存时间各是多少？问上述两种情况下平均访存时间各是多少？6565/154/1545.2 Cache的基本知识解解: : 如前所述，约如前所述，约75%75%的访存为取指令。的访存为取指令。因此，分离因此，分离CacheCache的总体失效率为：的总体失效率为： （75%75%0.64%

52、0.64%）（）（25%25%6.47%6.47%）2.10%2.10%根据表根据表5.45.4，容量为，容量为32 KB32 KB的混合的混合CacheCache的失效率的失效率略低一些，只有略低一些，只有1.99%1.99%。 6666/154/154平均访存时间公式可以分为平均访存时间公式可以分为指令访问指令访问和和数据访问数据访问两部分：两部分： 平均访存时间平均访存时间指令指令所占的百分比所占的百分比（指令命中时间指令失效率（指令命中时间指令失效率失效开销）失效开销） 数据数据所占的百分比所占的百分比（数据命中时间数据失效率（数据命中时间数据失效率失效开销）失效开销）6767/154

53、/1545.2 Cache的基本知识所以，两种结构的平均访存时间分别为：所以，两种结构的平均访存时间分别为： 平均访存时间平均访存时间分离分离75%75%（1+0.64%1+0.64%5050）+25%+25%（1+6.47%1+6.47%5050）（75%75%1.321.32）+ +（25%25%4.3254.325）0.990+1.0590.990+1.0592.052.05 平均访存时间平均访存时间混合混合75%75%（1+1.99%1+1.99%5050）+25%+25%（1+1+1.99%1+1+1.99%5050）（75%75%1.9951.995）+ +（25%25%2.995

54、2.995）1.496+0.7491.496+0.7492.242.24因此，尽管分离因此，尽管分离CacheCache的实际失效率比混合的实际失效率比混合CacheCache的高，但其平均访存的高，但其平均访存时间反而较低。原因：分离时间反而较低。原因：分离CacheCache提供了两个端口，消除了结构冲突。提供了两个端口，消除了结构冲突。6868/154/1545.2 Cache的基本知识3. 程序执行时间程序执行时间CPUCPU时间时间(CPU(CPU执行周期数执行周期数+ +存储器停顿周期数）存储器停顿周期数） 时钟周期时间时钟周期时间其中：其中： 为了简化对各种为了简化对各种 Cac

55、he 设计方案的评价，有时假设所有的访设计方案的评价，有时假设所有的访存停顿都是由存停顿都是由 Cache 失效引起的，这是因为和其它原因引起失效引起的，这是因为和其它原因引起的停顿（如的停顿（如I/O设备使用存储器引起的竞争）相比，设备使用存储器引起的竞争）相比， Cache失失效引起的停顿占了绝大多数。这里也作这种假设，但是请注意，效引起的停顿占了绝大多数。这里也作这种假设，但是请注意，在计算最终的性能时，考虑所有存储器停顿是很重要的。在计算最终的性能时，考虑所有存储器停顿是很重要的。上面的上面的CPU时间公式提出了一个问题，即：时间公式提出了一个问题，即：Cache命中所用的命中所用的时

56、钟周期数应被看作是时钟周期数应被看作是CPU执行的时钟周期数的一部分执行的时钟周期数的一部分，还是，还是存储器停顿时钟周期数的一部分。尽管两种考虑都是合理的，存储器停顿时钟周期数的一部分。尽管两种考虑都是合理的，但使用比较广泛的还是前一种。但使用比较广泛的还是前一种。 6969/154/154存储器停顿时钟周期数存储器停顿时钟周期数“读读”的次数的次数读失效率读失效率读失效开销读失效开销“写写”的次数的次数写失效率写失效率写失效开销写失效开销存储器停顿时钟周期数访存次数存储器停顿时钟周期数访存次数失效失效率率失效开销失效开销7070/154/1545.2 Cache的基本知识3. 程序执行时间

57、程序执行时间CPUCPU时间（时间（CPUCPU执行周期数执行周期数+ +存储器停顿周期数）存储器停顿周期数） 时钟周期时间时钟周期时间其中：其中： 存储器停顿时钟周期数存储器停顿时钟周期数“读读”的次数的次数读失效率读失效率读失读失效开销效开销“写写”的次数的次数写失效率写失效率写失效开销写失效开销存储器停顿时钟周期数访存次数存储器停顿时钟周期数访存次数失效率失效率失效开销失效开销 时钟周期时间失效开销失效率指令数访存次数时间executionCPIICCPU指令数 失效率 访存次数 指令数 失效次数 每条指令的平均失效次数 时钟周期时间指令数存储器停顿周期数时间executionCPIIC

58、CPU其中 IC为指令的条数，“访存次数指令数”为每条指令的平均访存次数。 7171/154/1545.2 Cache的基本知识 例例5.25.2 我们用一个和我们用一个和Alpha AXPAlpha AXP类似的机器作为第一个例子。类似的机器作为第一个例子。假设假设CacheCache失效开销为失效开销为5050个时钟周期，当不考虑存储器停顿时，所个时钟周期，当不考虑存储器停顿时，所有指令的执行时间都是有指令的执行时间都是2.02.0个时钟周期，访问个时钟周期，访问CacheCache失效率为失效率为2%2%，平均每条指令访存平均每条指令访存1.331.33次。试分析次。试分析CacheCa

59、che对性能的影响。对性能的影响。 解解CPU CPU 时间时间ICIC( (CPICPIexeexe ) ) 时钟周期时间时钟周期时间存储器停顿周期数存储器停顿周期数指令数指令数7272/154/1545.2 Cache的基本知识采用采用CacheCache，考虑，考虑CacheCache的失效后，性能为：的失效后，性能为： CPUCPU时间时间有有cachecacheICIC（2.02.01.331.332 %2 %5050）时钟周期时间时钟周期时间 ICIC3.333.33时钟周期时间时钟周期时间实际实际CPI CPI ：3.333.333.33/2.0 = 1.67(3.33/2.0

60、= 1.67(倍倍) ) CPUCPU时间也增加为原来的时间也增加为原来的1.671.67倍。倍。 但若但若不采用不采用CacheCache, ,则：则：CPICPI2.02.050501.331.33100%100%68.568.5 因此，当考虑了因此，当考虑了Cache的失效影响后，的失效影响后，CPI就会增大。本例中就会增大。本例中CPI从理想计算机的从理想计算机的2.0增加到增加到3.33，是原来的，是原来的1.67倍。由于不管有没倍。由于不管有没有有Cache，时钟周期时间和指令数都保持不变，所以，时钟周期时间和指令数都保持不变，所以CPU的时间也的时间也将增加到原来的将增加到原来的