第5章 存储系统计算机组成与结构.PPT

《第5章 存储系统计算机组成与结构.PPT》由会员分享，可在线阅读，更多相关《第5章 存储系统计算机组成与结构.PPT（165页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1*/16*/16第5章 存储系统2 2*/16*/165.1存储系统的基本知识5.2Cache基本知识5.3降低Cache不命中率5.4减少Cache不命中开销5.5减少命中时间5.6并行主存系统5.7虚拟存储器5.8实例：AMD Opteron的存储器层次结构3 3*/16*/161.计算机系统结构设计中关键的问题之一：如何以合理的价格，设计容量和速度都满足计算机系统要求的存储器系统？2.人们对这三个指标的要求 容量大、速度快、价格低3.三个要求是相互矛盾的q速度越快，每位价格就越高；速度越快，每位价格就越高；q容量越大，每位价格就越低；容量越大，每位价格就越低；q容量越大，速度越慢。

2、容量越大，速度越慢。5.1 存储系统的基本知识5.1.1 存储系统的层次结构 4 4*/16*/165.1 存储系统的基本知识4.解决方法：采用多种存储器技术，构成多级存储层次结构。程序访问的局部性原理：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。(局部性原理局部性原理)程序访问的局部性包含两个方面 q时间局部性时间局部性：程序马上将要用到的信息很可能就是现：程序马上将要用到的信息很可能就是现在正在使用的信息。在正在使用的信息。q空间局部性空间局部性：程序马上将要用到的信息很可能与现在：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的

3、。正在使用的信息在存储空间上是相邻的。5 5*/16*/165.1 存储系统的基本知识5.存储系统的多级层次结构 演示演示多级存储层次多级存储层次6 6*/16*/165.1 存储系统的基本知识假设第i个存储器Mi的访问时间为Ti，容量为Si，平均每位价格为Ci，则q访问时间：访问时间：T1 T2 Tnq容量：容量：S1 S2 C2 Cn 整个存储系统要达到的目标：从CPU来看，该存储系统的速度接近于M1的，而容量和每位价格都接近于Mn的。q存储器越靠近存储器越靠近CPU，则，则CPU对它的访问频度越高，对它的访问频度越高，而且最好大多数的访问都能在而且最好大多数的访问都能在M1完成。完成。7

4、 7*/16*/165.1 存储系统的基本知识下面仅考虑由M1和M2构成的两级存储层次：pM M1 1的参数：的参数：S S1 1，T T1 1，C C1 1pM M2 2的参数：的参数：S S2 2，T T2 2，C C2 25.1.2 存储层次的性能参数8 8*/16*/165.1 存储系统的基本知识1.存储容量S一般来说，整个存储系统的容量即是第二级存储器M2的容量，即S=S2。2.每位价格C当当S1S2时，时，CC2。9 9*/16*/165.1 存储系统的基本知识3.命中率H 和不命中率F命中率：CPU访问存储系统时，在M1中找到所需信息的概率。qN N1 1 访问访问M M1 1的

5、次数的次数qN N2 2 访问访问M M2 2的次数的次数 不命中率：F1H1010*/16*/165.1 存储系统的基本知识4.平均访问时间TA T TA A HTHT1 1（1 1H H）（）（T T1 1T TM M）T T1 1（1 1H H）T TM M 或或 T TA A T T1 1FTFTM M分两种情况来考虑CPU的一次访存：q当命中时，访问时间即为当命中时，访问时间即为T T1 1（命中时间命中时间）q当不命中时，情况比较复杂。当不命中时，情况比较复杂。不命中时的访问时间为：不命中时的访问时间为：T T2 2T TB BT T1 1T T1 1T TM M T TM M T

6、 T2 2T TB Bn不命中开销不命中开销T TM M：从向：从向M M2 2发出访问请求到把整个数发出访问请求到把整个数据块调入据块调入M M1 1中所需的时间。中所需的时间。n传送一个信息块所需的时间为传送一个信息块所需的时间为T TB B。1111*/16*/165.1 存储系统的基本知识 三级存储系统qCache（高速缓冲存储器）（高速缓冲存储器）q主存储器主存储器q磁盘存储器（辅存）磁盘存储器（辅存）可以看成是由“Cache主存”层次和“主存辅存”层次构成的系统。5.1.3 三级存储系统1212*/16*/165.1 存储系统的基本知识 从主存的角度来看q“CacheCache主存

7、主存”层次：弥补主存层次：弥补主存速度的不足速度的不足q“主存辅存主存辅存”层次：层次：弥补主存弥补主存容量的不足容量的不足1.“Cache主存”层次主存与CPU的速度差距“Cache-主存”层次2.“主存辅存”层次1313*/16*/165.1 存储系统的基本知识19801980年以来存储器和年以来存储器和CPUCPU性能随时间而提高的情况性能随时间而提高的情况 （以（以19801980年时的性能作为基准）年时的性能作为基准）1414*/16*/165.1 存储系统的基本知识两种存储层次两种存储层次1515*/16*/165.1 存储系统的基本知识存储层次存储层次CPU对第二级的对第二级的访

8、问方式访问方式比较项目比较项目目的目的存储管理实现存储管理实现 访问速度的比值访问速度的比值(第一级和第二级第一级和第二级)典型的块典型的块(页页)大小大小不命中时不命中时CPU是否切换是否切换“Cache 主存主存”层次层次“主存辅存主存辅存”层次层次为了弥补主存速度的不足为了弥补主存速度的不足 为了弥补主存容量的不足为了弥补主存容量的不足主要由专用硬件实现主要由专用硬件实现主要由软件实现主要由软件实现几比一几比一几万比一几万比一几十个字节几十个字节几百到几千个字节几百到几千个字节可直接访问可直接访问均通过第一级均通过第一级不切换不切换切换到其他进程切换到其他进程“CacheCache主存主

9、存”与与“主存辅存主存辅存”层次的区别层次的区别1616*/16*/165.1 存储系统的基本知识1.当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映像规则）映像规则）2.当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）（查找算法）3.当发生不命中时，应替换哪一块？（替换算法）（替换算法）4.当进行写访问时，应进行哪些操作?（写策略）写策略）5.1.4 存储层次的四个问题1717*/16*/161.存储空间分割与地址计算2.Cache和主存分块Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。q主存块地址（块号）主

10、存块地址（块号）用于查找该块在用于查找该块在Cache中的位置。中的位置。q块内位移块内位移用于确定所访问的数据在该块中的位置。用于确定所访问的数据在该块中的位置。5.2 Cache基本知识 5.2.1基本结构和原理 3.Cache的基本工作原理示意图 1919*/16*/165.2.2映像规则 全相联映像 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。举例对比：阅览室位置 随便坐特点：空间利用率最高，冲突概率最低，实现最复杂。5.2 Cache基本知识2020*/16*/165.2 Cache基本知识2121*/16*/165.2 Cache基本知识2.直接映像 直接映像：主

11、存中的每一块只能被放置到Cache中唯一的一个位置。举例（循环分配）（循环分配）对比：阅览室位置 只有一个位置可以坐特点：空间利用率最低，冲突概率最高，实现最简单。对于主存的第i 块，若它映像到Cache的第j 块，则:ji mod(M)（M为Cache的块数）2222*/16*/16设M=2m，则当表示为二进制数时，j实际上就是i的低m位:ji：m位位5.2 Cache基本知识2323*/16*/165.2 Cache基本知识3.组相联映像 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。举例组相联是直接映像和全相联的一种折中2525*/16*/165.2 Cac

12、he基本知识组的选择常采用位选择算法q若主存第若主存第i i 块映像到第块映像到第k k 组，则组，则:k ki i modmod（G G）（G G为为CacheCache的组数）的组数）q设设G G2 2g g，则当表示为二进制数时，则当表示为二进制数时，k k 实际上就是实际上就是i i 的低的低 g g 位位:低g位以及直接映像中的低m位通常称为索引。ki：g位位2626*/16*/165.2 Cache基本知识n 路组相联：每组中有n个块(nM/G)。n 称为相联度。相联度越高，相联度越高，CacheCache空间的利用率就越高，块冲突空间的利用率就越高，块冲突概率就越低，不命中率也就

13、越低。概率就越低，不命中率也就越低。绝大多数计算机的Cache:n 4想一想：想一想：相联度一定是越大越好？相联度一定是越大越好？全相联全相联直接映像直接映像组相联组相联n n(路数路数)G G(组数组数)M MM M1 11 11 1n nM M1 1G GM M2727*/16*/165.2 Cache基本知识当CPU访问Cache时，如何确定Cache中是否有所要访问的块？若有的话，如何确定其位置？1.通过查找目录表来实现目录表的结构q主存块的块地址的高位部分，称为主存块的块地址的高位部分，称为标识标识。q每个主存块能唯一地由其标识来确定每个主存块能唯一地由其标识来确定5.2.3 查找算

14、法2828*/16*/165.2 Cache基本知识只需查找候选位置所对应的目录表项2.并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块)（前瞻执行）（前瞻执行）3.并行查找的实现方法相联存储器q目录由目录由2g个相联存储区构成，每个相联存储区的大小个相联存储区构成，每个相联存储区的大小为为n（h+log2n）位。位。q根据所查找到的组内块地址，从根据所查找到的组内块地址，从Cache存储体中读出存储体中读出的多个信息字中选一个，发送给的多个信息字中选一个，发送给CPU。2929*/16*/165.2 Cache基本知识3030*/16*/165.2 Cache基本知识单体多字存储器

15、比较器 q举例：举例：路组相联并行标识比较路组相联并行标识比较（比较器的个数及位数）（比较器的个数及位数）q路组相联路组相联Cache的查找过程的查找过程q直接映像直接映像Cache的查找过程的查找过程q优缺点优缺点n不必采用相联存储器，而是用按地址访问的存不必采用相联存储器，而是用按地址访问的存储器来实现。储器来实现。n所需要的硬件为：大小为所需要的硬件为：大小为2g nh位的存储器和位的存储器和n个个h位位的比较器。的比较器。n当相联度当相联度n增加时，不仅比较器的个数会增加，增加时，不仅比较器的个数会增加，而且比较器的位数也会增加。而且比较器的位数也会增加。3131*/16*/165.2

16、 Cache基本知识3232*/16*/165.2 Cache基本知识例子：DEC的Alpha AXP21064中的内部数据Cache1.简介容量：8KB块大小：32B块数：256映像方法：直接映像写缓冲器大小：4个块5.2.4 Cache的工作过程2.结构图3434*/16*/165.2 Cache基本知识3.工作过程“读”访问命中（完成（完成4步需要步需要2个时钟周期个时钟周期）pCache的容量与索引的容量与索引index、相联度、块大小之间、相联度、块大小之间的关系的关系 Cache的容量的容量=2index相联度相联度块大小块大小 p把容量为把容量为8192、相联度为、相联度为1、块

17、大小为、块大小为32（字节）（字节）代入：代入：索引索引index：8位位 标识：标识：29821位位 “写”访问命中3535*/16*/165.2 Cache基本知识设置了一个写缓冲器 （提高（提高“写写”访问的速度）访问的速度）q按字寻址的，它含有按字寻址的，它含有4个块，每块大小为个块，每块大小为4个字。个字。q当要进行写入操作时，如果写缓冲器不满，那么就把当要进行写入操作时，如果写缓冲器不满，那么就把数据和完整的地址写入缓冲器。对数据和完整的地址写入缓冲器。对CPU而言，本次而言，本次“写写”访问已完成，访问已完成，CPU可以继续往下执行。由写缓冲可以继续往下执行。由写缓冲器负责把该数

18、据写入主存。器负责把该数据写入主存。q在写入缓冲器时，要进行写合并检查。即检查本次写在写入缓冲器时，要进行写合并检查。即检查本次写入数据的地址是否与缓冲器内某个有效块的地址匹配。入数据的地址是否与缓冲器内某个有效块的地址匹配。如果匹配，就把新数据与该块合并如果匹配，就把新数据与该块合并。3636*/16*/165.2 Cache基本知识发生读不命中与写不命中时的操作q读不命中：读不命中：向向CPU发出一个暂停信号，通知它等待，发出一个暂停信号，通知它等待，并从下一级存储器中新调入一个数据块（并从下一级存储器中新调入一个数据块（32字节）。字节）。q写不命中：将使数据写不命中：将使数据“绕过绕过

19、”Cache，直接写入主存。，直接写入主存。对比：Alpha AXP 21264的数据Cache结构容量：64KB 块大小：64字节 LRU替换策略 主要区别q采用采用2路组相联路组相联q采用写回法采用写回法 没有写缓冲器3838*/16*/165.2 Cache基本知识1.替换算法所要解决的问题：当新调入一块，而Cache又已被占满时，替换哪一块？q直接映像直接映像Cache中的替换很简单中的替换很简单 因为只有一个块，别无选择。因为只有一个块，别无选择。q在组相联和全相联在组相联和全相联Cache中，则有多个块供选择。中，则有多个块供选择。主要的替换算法有三种q随机法随机法 优点：优点：实

20、现简单实现简单q先进先出法先进先出法FIFO5.2.5 替换算法3939*/16*/165.2 Cache基本知识最近最少使用法LRUq选择近期最少被访问的块作为被替换的块。选择近期最少被访问的块作为被替换的块。（实现比较困难）（实现比较困难）q实际上：实际上：选择最久没有被访问过的块作为被替换的块。选择最久没有被访问过的块作为被替换的块。q优点：优点：命中率较高命中率较高LRU和随机法分别因其不命中率低和实现简单而被广泛采用。q模拟数据表明，对于容量很大的模拟数据表明，对于容量很大的Cache，LRU和随机法和随机法的命中率差别不大。的命中率差别不大。4040*/16*/165.2 Cach

21、e基本知识2.LRU算法的硬件实现 堆栈法 q用一个堆栈来记录组相联用一个堆栈来记录组相联Cache的同一组中各块被访的同一组中各块被访问的先后次序。问的先后次序。q用堆栈元素的物理位置来反映先后次序用堆栈元素的物理位置来反映先后次序n栈底记录的是该组中最早被访问过的块，次栈栈底记录的是该组中最早被访问过的块，次栈底记录的是该组中第二个被访问过的块，底记录的是该组中第二个被访问过的块，栈顶记录的是刚访问过的块。栈顶记录的是刚访问过的块。n当需要替换时，从栈底得到应该被替换的块当需要替换时，从栈底得到应该被替换的块（块地址）。（块地址）。4141*/16*/165.2 Cache基本知识4242

22、*/16*/165.2 Cache基本知识q堆栈中的内容必须动态更新堆栈中的内容必须动态更新 n当当Cache访问命中访问命中时，通过用块地址进行相联查找，时，通过用块地址进行相联查找，在堆栈中找到相应的元素，然后把该元素的上面的所在堆栈中找到相应的元素，然后把该元素的上面的所有元素下压一个位置，同时把本次访问的块地址抽出有元素下压一个位置，同时把本次访问的块地址抽出来，从最上面压入栈顶。而该元素下面的所有元素则来，从最上面压入栈顶。而该元素下面的所有元素则保持不动。保持不动。n如果如果Cache访问不命中访问不命中，则把本次访问的块地址从最，则把本次访问的块地址从最上面压入栈顶，堆栈中所有原

23、来的元素都下移一个位上面压入栈顶，堆栈中所有原来的元素都下移一个位置。如果置。如果Cache中该组已经没有空闲块，就要替换一中该组已经没有空闲块，就要替换一个块。这时从栈底被挤出去的块地址就是需要被替换个块。这时从栈底被挤出去的块地址就是需要被替换的块的块地址。的块的块地址。4343*/16*/165.2 Cache基本知识q堆栈法所需要的硬件堆栈法所需要的硬件n需要为每一组都设置一个项数与相联度相同的小堆栈，需要为每一组都设置一个项数与相联度相同的小堆栈，每一项的位数为每一项的位数为log2n位。位。q硬件堆栈所需的功能硬件堆栈所需的功能n相联比较相联比较n能全部下移、部分下移和从中间取出一

24、项的功能能全部下移、部分下移和从中间取出一项的功能q速度较低，速度较低，成本较高成本较高（只适用于相联度较小的（只适用于相联度较小的LRU算法）算法）比较对法 q基本思路基本思路 让各块两两组合，构成比较对。每一个比较对用一个让各块两两组合，构成比较对。每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的触发器的状态来表示它所相关的两个块最近一次被访问的远近次序，再经过门电路就可找到远近次序，再经过门电路就可找到LRU块块。4444*/16*/165.2 Cache基本知识 例如：例如：假设有假设有A、B、C三个块，可以组成三个块，可以组成3对：对：AB、AC、BC。每一对中块

25、的访问次序分别用。每一对中块的访问次序分别用“对触发器对触发器”TAB、TAC、TBC表示。表示。pTAB为为“1”，表示，表示A比比B更近被访问过；更近被访问过；pTAB为为“0”，表示，表示B比比A更近被访问过。更近被访问过。pTAC、TBC也是按这样的规则定义。也是按这样的规则定义。显然，当显然，当TAC1且且TBC1时，时，C就是最久没有被访问过了。就是最久没有被访问过了。（A比比C更近被访问过、且更近被访问过、且B比比C也是更近被访问过）也是更近被访问过）即：即：CLRU=TACTBC 同理可得：同理可得：用触发器和与门实现上述逻辑的电路：用触发器和与门实现上述逻辑的电路：4545*

26、/16*/165.2 Cache基本知识用比较对法实现用比较对法实现LRULRU算法算法 4646*/16*/165.2 Cache基本知识q比较对法所需的硬件量比较对法所需的硬件量n与门与门 有多少个块，就要有多少个与门；有多少个块，就要有多少个与门；每个与门的每个与门的输入端要连接所有与之相关的触发器。输入端要连接所有与之相关的触发器。对于一个具有对于一个具有P块的组中的任何一个块来说，由块的组中的任何一个块来说，由于它可以跟除了它自己以外的所有其他的块两两组合，于它可以跟除了它自己以外的所有其他的块两两组合，所以与该块相关的比较对触发器个数为所以与该块相关的比较对触发器个数为P1，因而其

27、，因而其相应的与门的输入端数是相应的与门的输入端数是P1。n触发器触发器 所需要的触发器的个数与两两组合的比较对的所需要的触发器的个数与两两组合的比较对的数目相同。数目相同。比较对触发器个数、与门的个数、与门的输入端数与块数比较对触发器个数、与门的个数、与门的输入端数与块数P P的关系的关系 组内块数组内块数3481664256P触发器个数触发器个数3628120201632640与门个数与门个数3481664256P与门输入端个数与门输入端个数2371563255P-14848*/16*/165.2 Cache基本知识n块数少时，所需要的硬件较少，块数少时，所需要的硬件较少，n随着组内块数随

28、着组内块数P的增加，所需的触发器的个数会以平方的关的增加，所需的触发器的个数会以平方的关系迅速增加，门的输入端数也线性增加。系迅速增加，门的输入端数也线性增加。（硬件实现的成本很高）（硬件实现的成本很高）q当组内块数较多时，可以用多级状态位技术减少所需的硬件量。当组内块数较多时，可以用多级状态位技术减少所需的硬件量。例如例如：在：在IBM 3033中中 组内块数为组内块数为16，可分成群、对、行，可分成群、对、行3级。级。先分成先分成4群，每群两对，每对两行。群，每群两对，每对两行。选选LRU群需群需6个触发器；个触发器；每群中选每群中选LRU对需要一个触法器，对需要一个触法器，4个群共需要个

29、群共需要4个触发器；个触发器；4949*/16*/165.2 Cache基本知识每行中选每行中选LRU块需要一个触发器，块需要一个触发器，8个行共需要个行共需要8个触发器。个触发器。所需的触发器总个数为：所需的触发器总个数为：6（选群）（选群）4（选对）（选对）8（选行）（选行）=18（个）（个）以牺牲速度为代价的。以牺牲速度为代价的。5050*/16*/165.2 Cache基本知识1.“写”在所有访存操作中所占的比例 统计结果表明，对于一组给定的程序：ql loadoad指令：指令：2626qs storetore指令：指令：9 9“写”在所有访存操作中所占的比例：9 9/(100/(10

30、026269 9)7)7“写”在访问Cache操作中所占的比例：9 9/(26/(269 9)25)255.2.6 写策略5151*/16*/165.2 Cache基本知识2.“写”操作必须在确认是命中后才可进行3.“写”访问有可能导致Cache和主存内容的不一致4.两种写策略写策略是区分不同Cache设计方案的一个重要标志。写直达法（也称为存直达法）q执行执行“写写”操作时，不仅写入操作时，不仅写入CacheCache，而且也写入下，而且也写入下一级存储器。一级存储器。写回法（也称为拷回法）q执行执行“写写”操作时，只写入操作时，只写入CacheCache。仅当。仅当CacheCache中相

31、应中相应的块被替换时，才写回主存。的块被替换时，才写回主存。(设置设置“修改位修改位”)5252*/16*/165.2 Cache基本知识5.两种写策略的比较写回法的优点：速度快，所使用的存储器带宽较低。写直达法的优点：易于实现，一致性好。6.采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。减少写停顿的一种常用的优化技术：采用写缓冲器采用写缓冲器5353*/16*/165.2 Cache基本知识7.“写”操作时的调块按写分配(写时取)写不命中时，先把所写单元所在的块调入写不命中时，先把所写单元所在的块调入CacheCache，再行写入。再行写入。

32、不按写分配(绕写法)写不命中时，直接写入下一级存储器而不调块。写不命中时，直接写入下一级存储器而不调块。8.写策略与调块写回法 按写分配写直达法 不按写分配5454*/16*/165.2 Cache基本知识1.不命中率与硬件速度无关容易产生一些误导2.平均访存时间平均访存时间 命中时间不命中率不命中开销5.2.7 Cache的性能分析3.程序执行时间CPUCPU时间（时间（CPUCPU执行周期数执行周期数+存储器停顿周期数）存储器停顿周期数）时钟周期时间时钟周期时间其中：其中：存储器停顿时钟周期数存储器停顿时钟周期数“读读”的次数的次数读不命中率读不命中率读不读不命中开销命中开销“写写”的次数

33、的次数写不命中率写不命中率写不命中开销写不命中开销存储器停顿时钟周期数访存次数存储器停顿时钟周期数访存次数不命中率不命中率不命中开销不命中开销 CPU时间（CPU执行周期数+访存次数不命中率不命中开销）时钟周期时间=IC（CPIexecution每条指令的平均访存次数不命中率 不命中开销）时钟周期时间5656*/16*/165.2 Cache基本知识 例例5.15.1 用一个和用一个和Alpha AXPAlpha AXP类似的机器作为第一个例子。假类似的机器作为第一个例子。假设设CacheCache不命中开销为不命中开销为5050个时钟周期，当不考虑存储器停顿时，个时钟周期，当不考虑存储器停顿

34、时，所有指令的执行时间都是所有指令的执行时间都是2.02.0个时钟周期，访问个时钟周期，访问CacheCache不命中率为不命中率为2%2%，平均每条指令访存，平均每条指令访存1.331.33次。试分析次。试分析CacheCache对性能的影响。对性能的影响。解解 CPU时间时间有有cacheIC（CPIexecution每条指令的平均访存次数每条指令的平均访存次数 不命中率不命中率不命中开销）不命中开销）时钟周期时间时钟周期时间 IC（2.01.332%50）时钟周期时间时钟周期时间 IC 3.33 时钟周期时间时钟周期时间5757*/16*/165.2 Cache基本知识考虑考虑Cache

35、Cache的不命中后，性能为：的不命中后，性能为：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=1.67(倍倍)CPUCPU时间也增加为原来的时间也增加为原来的1.671.67倍。倍。但若不采用但若不采用Cache,Cache,则：则：CPICPI2.02.050501.331.3368.568.55858*/16*/165.2 Cache基本知识4.Cache不命中对于一个CPI较

36、小而时钟频率较高的CPU来说，影响是双重的：CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。在计算CPI时，不命中开销的单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。因此Cache对于低CPI、高时钟频率的CPU来说更加重要。例例5.25.2 考虑两种不同组织结构的考虑两种不同组织结构的CacheCache：直接映像：直接映像CacheCache和两和两路组相联路组相联CacheCache，试问它们对，试问它们对CPUCPU的性能有何影响？先求平均访存的性能有何影响？先求平均访

37、存时间，然后再计算时间，然后再计算CPUCPU性能。分析时请用以下假设：性能。分析时请用以下假设：(1)(1)理想理想CacheCache（命中率为（命中率为100%100%）情况下的）情况下的CPICPI为为2.02.0，时钟周，时钟周期为期为2ns2ns，平均每条指令访存，平均每条指令访存1.31.3次。次。(2)(2)两种两种CacheCache容量均为容量均为64KB64KB，块大小都是，块大小都是3232字节。字节。(3)(3)在组相联在组相联CacheCache中，中，由于多路选择器的存在而使由于多路选择器的存在而使CPU的时的时钟周期增加到原来的钟周期增加到原来的1.10倍。这是

38、因为对倍。这是因为对Cache的访问总是处于的访问总是处于关键路径上，对关键路径上，对CPU的时钟周期有直接的影响。的时钟周期有直接的影响。(4)(4)这两种结构这两种结构CacheCache的不命中开销都是的不命中开销都是70ns70ns。（在实际应。（在实际应用中，应取整为整数个时钟周期）用中，应取整为整数个时钟周期）(5)(5)命中时间为命中时间为1 1个时钟周期，个时钟周期，64KB64KB直接映像直接映像CacheCache的不命的不命中率为中率为1.4%1.4%，相同容量的两路组相联，相同容量的两路组相联CacheCache的不命中率为的不命中率为1.0%1.0%。6060*/16

39、*/165.2 Cache基本知识 解解 平均访存时间为：平均访存时间为：平均访存时间命中时间不命中率平均访存时间命中时间不命中率不命中开销不命中开销 因此，两种结构的平均访存时间分别是：因此，两种结构的平均访存时间分别是：平均访存时间平均访存时间1 1路路2.02.0（0.0140.0147070）2.98ns2.98ns 平均访存时间平均访存时间2 2路路2.02.01.101.10（0.0100.0107070）2.90ns2.90ns 两路组相联两路组相联CacheCache的平均访存时间比较低。的平均访存时间比较低。CPU时间时间IC（CPIexecution每条指令的平均访存次数每

40、条指令的平均访存次数 不命中率不命中率不命中开销）不命中开销）时钟周期时间时钟周期时间 IC（CPIexecution 时钟周期时间每条指令的时钟周期时间每条指令的 平均访存次数平均访存次数不命中率不命中率不命中开销不命中开销时钟周期时间）时钟周期时间）6161*/16*/165.2 Cache基本知识因此：因此：CPUCPU时间时间1 1路路 ICIC(2.0(2.02 2(1.3(1.30.0140.01470)70)5.275.27ICICCPUCPU时间时间2 2路路 ICIC(2.0(2.02 21.101.10(1.3(1.30.0100.01070)70)5.315.31ICIC

41、直接映像直接映像CacheCache的平均性能好一些。的平均性能好一些。6262*/16*/165.2 Cache基本知识1.平均访存时间命中时间不命中率不命中开销2.可以从三个方面改进Cache的性能：降低不命中率减少不命中开销减少Cache命中时间3.下面介绍17种Cache优化技术q8 8种种用于降低不命中率用于降低不命中率q5 5种种用于减少不命中开销用于减少不命中开销q4 4种种用于减少命中时间用于减少命中时间 5.2.8 改进Cache的性能6363*/16*/161.三种类型的不命中(3C)强制性不命中(Compulsory miss)q当第一次访问一个块时，该块不在当第一次访问

42、一个块时，该块不在CacheCache中，需从下中，需从下一级存储器中调入一级存储器中调入CacheCache，这就是强制性不命中。，这就是强制性不命中。(冷启动冷启动不命中，首次访问不命中）不命中，首次访问不命中）容量不命中(Capacity miss)q如果程序执行时所需的块不能全部调入如果程序执行时所需的块不能全部调入CacheCache中，则中，则当某些块被替换后，若又重新被访问，就会发生不命当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。中。这种不命中称为容量不命中。5.3 降低Cache不命中率5.3.1 三种类型的不命中6464*/16*/165.3

43、降低Cache不命中率冲突不命中(Conflict miss)q在组相联或直接映像在组相联或直接映像CacheCache中，若太多的块映像到中，若太多的块映像到同一组同一组(块块)中，则会出现该组中某个块被别的块替中，则会出现该组中某个块被别的块替换换(即使别的组或块有空闲位置即使别的组或块有空闲位置)，然后又被重新访，然后又被重新访问的情况。这就是发生了冲突不命中。问的情况。这就是发生了冲突不命中。(碰撞不命中，干扰不命中碰撞不命中，干扰不命中)2.三种不命中所占的比例 图示I(绝对值)图示(相对值)6565*/16*/165.3 降低Cache不命中率6666*/16*/165.3 降低C

44、ache不命中率6767*/16*/165.3 降低Cache不命中率可以看出：q相联度越高，冲突不命中就越少；相联度越高，冲突不命中就越少；q强制性不命中和容量不命中不受相联度的影响；强制性不命中和容量不命中不受相联度的影响；q强制性不命中不受强制性不命中不受CacheCache容量的影响，但容量不命中容量的影响，但容量不命中却随着容量的增加而减少。却随着容量的增加而减少。6868*/16*/165.3 降低Cache不命中率减少三种不命中的方法q强制性不命中：强制性不命中：增加块大小，预取增加块大小，预取（本身很少）（本身很少）q容量不命中：容量不命中：增加容量增加容量（抖动现象）（抖动现

45、象）q冲突不命中：冲突不命中：提高相联度提高相联度（理想情况：全相联）（理想情况：全相联）许多降低不命中率的方法会增加命中时间或不命中开销6969*/16*/165.3 降低Cache不命中率1.不命中率与块大小的关系对于给定的Cache容量，当块大小增加时，不命中率开始是下降，后来反而上升了。原因：q一方面它减少了强制性不命中；一方面它减少了强制性不命中；q另一方面，由于增加块大小会减少另一方面，由于增加块大小会减少CacheCache中块的数目，中块的数目，所以有可能会增加冲突不命中。所以有可能会增加冲突不命中。Cache容量越大，使不命中率达到最低的块大小就越大。2.增加块大小会增加不命

46、中开销5.3.2 增加Cache块大小7070*/16*/165.3 降低Cache不命中率不命中率随块大小变化的曲线不命中率随块大小变化的曲线 7171*/16*/165.3 降低Cache不命中率各种块大小情况下Cache的不命中率 块大小（字节）Cache容量（字节）1K 4K 16K 64K 256K 16 15.05%8.57%3.94%2.04%1.09%32 13.34%7.24%2.87%1.35%0.70%64 13.76%7.00%2.64%1.06%0.51%128 16.64%7.78%2.77%1.02%0.49%256 22.01%9.51%3.29%1.15%0.

47、49%7272*/16*/165.3 降低Cache不命中率1.最直接的方法是增加Cache的容量缺点:q增加成本增加成本q可能增加命中时间可能增加命中时间2.这种方法在片外Cache中用得比较多 5.3.3 增加Cache的容量7373*/16*/165.3 降低Cache不命中率1.采用相联度超过8的方案的实际意义不大。2.2:1 Cache经验规则 容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。3.提高相联度是以增加命中时间为代价。5.3.4 提高相联度7474*/16*/165.3 降低Cache不命中率1.多路组相联的低不命中率和直接

48、映像的命中速度2.伪相联Cache的优点命中时间小不命中率低5.3.5 伪相联 Cache(列相联 Cache)优点优点缺点缺点直接映像直接映像组相联组相联命中时间小命中时间大不命中率高不命中率低3.基本思想及工作原理 （动画演示）在逻辑上把直接映像在逻辑上把直接映像CacheCache的空间上下平分为两个区。对于任何的空间上下平分为两个区。对于任何一次访问，伪相联一次访问，伪相联CacheCache先按直接映像先按直接映像CacheCache的方式去处理。若命中，的方式去处理。若命中，则其访问过程与直接映像则其访问过程与直接映像CacheCache的情况一样。若不命中，则再到另一的情况一样。

49、若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。一级存储器。7676*/16*/165.3 降低Cache不命中率 5.缺点：多种命中时间快速命中与慢速命中 要保证绝大多数命中都是快速命中。不命中开销不命中开销7777*/16*/165.3 降低Cache不命中率1.指令和数据都可以预取2.预取内容既可放入Cache，也可放在外缓冲器中。例如：指令流缓冲器例如：指令流缓冲器3.指令预取通常由Cache之外的硬件完成4.预取效果Joppi的研究结果q指令预取指令预取 (4KB(4KB，直接映像

50、，直接映像CacheCache，块大小，块大小1616字节字节)n1 1个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获15152525的不命中的不命中n4 4个块的指令流缓冲器：个块的指令流缓冲器：捕获捕获5050n1616个块的指令流缓冲器：捕获个块的指令流缓冲器：捕获72725.3.6 硬件预取 7878*/16*/165.3 降低Cache不命中率q数据预取数据预取 (4KB,(4KB,直接映像直接映像Cache)Cache)n1 1个数据流缓冲器：捕获个数据流缓冲器：捕获2525的不命中的不命中n还可以采用多个数据流缓冲器还可以采用多个数据流缓冲器Palacharla和Kessler