计算机体系结构第章存储层次

计算机体系结构1第五章存储层次本章要点:•存储系统•存储层次•存储系统的性能参数•Cache存储器工作原理•Cache地址映象与变换算法•Cache替换算法及其实现•Cache写操作计算机体系结构2•Cache系统性能的改进方法•主存系统•低位交叉访问存储器•高位交叉访问存储器•虚拟存储器工作原理•段式、页式、段页式存储管理•虚拟存储器地址映象与变换算法•页面替换算法及其实现•缓冲对虚拟存储系统性能的影响•Cache、主存、虚拟存储器的比较计算机体系结构3本章的主要应用问题•Cache性能分析•层次存储器性能分析•Cache地址流分析•虚拟存储器地址流分析•存储器系统设计第五章存储层次45.1存储器的层次结构存储器是计算机的核心部件之一，其性能直接关系到整个计算机系统性能的高低。存储器的三个主要指标是：速度、容量和价格(即每位价格)。如何以合理的价格，设计容量和速度满足计算机系统需求的存储器系统，始终是计算机体系结构设计中的关键问题之一。5.1.1从单级存储器到多级存储器计算机软件设计者和计算机用户总是希望存储器的容量越大越好，而且速度要快，价格也不能太昂贵。而实际情况却是：速度越快，每位价格越高；容量越大，每位价格越低；容量越大，速度越慢。人们对存储器设计的三个指标要求是互相矛盾的。第五章存储层次5解决问题的办法必须切合实际地综合考虑：从实现“容量大、价格”的要去来看，应采用能提供大容量技术的存储器技术；但从满足性能需求的角度来看，又应采用昂贵且容量较小的快速存储器。走出这种困境的唯一方法，就是采用多种存储技术，构成存储器的层次结构，如图5.1所示。第五章存储层次6在多级存储层次中，最靠近CPU的M1速度最快、容量最小、价格最高；而远离CPU的Mn则是速度最慢、容量最大、价格最低。存储系统的设计目标是：M1的速度，Mn的容量和价格。层次存储器设计的依据：程序局部性原理。在层次存储中，靠近CPU的存储器中的数据一般都是其下一层存储器中数据的子集。CPU访存时的基本原则：有近及远，首先是访问M1，若在M1中找不到所要的数据，就要访问M2，将包含所需数据的块或页面调入M1。若在M2中还找不到，就要访问M3，依此类推。如果所有层次中都没有，就出现错误。。第五章存储层次75.1.2存储层次的性能参数研究方法：层次存储器基本问题通过两层存储器结构进行研究。对于由M1和M2构成的两级存储层次结构，假设M1、M2的容量、访问时间和每位价格分别为S1、TA1、C1和S2、TA2、C2。1.存储层次的平均每位价格显然，当S1S2时，CC2。2.命中率H命中率为CPU访问存储系统时，在M1中找到所需信息的概率。访问M1和M2的次数为N1和N2。第五章存储层次8不命中率或失效率F是指CPU访存时在M1找不到所需信息的概率。3.平均访问时间TA分两种情况来考虑CPU的一次访存：（1）当命中时，访问时间即为TA1。TA1常称为命中时间（hit-time）。（2）大多数二级存储层次结构下，当不命中M1时，就必须从M2中访问这个字，并把包含所请求的字的信息块传送到M1，之后CPU才能访问这个字。假设传送一个信息块所需的时间为TB，则不命中时的访问时间为：TA2＋TB＝TA1＋TM其中TM＝TA2＋TB，它为从向M2发出访问请求到把整个数据块调入M1中所需的时间。TM常称为失效开销。第五章存储层次9根据以上分析可知：TA＝HTA1＋(1－H)(TA1＋TM)＝TA1＋(1－H)TM或TA＝TA1＋FTM5.1.3“Cache-主存”和“主存-辅存”层次1.“Cache-主存”层次CPU和主存之间在性能上的差距越来越大，如图5.2所示。现代计算机都采用Cache来解决这个问题。第五章存储层次10“Cache-主存”层次的工作几乎完全由硬件实现，因此它不但对应用程序员是透明的，而且对系统程序员几乎也是透明的。2.“主存-辅存”层次为了弥补主存容量，在主存外面增加一个容量更大、每位价格更低、但速度更慢的存储器(称为辅存，一般是硬盘)。“它们依靠辅助软硬件的作用，构成一个整体，如图5.3所示。主存-辅存”层次常被用来实现虚拟存储器，向编程人员提供大量的程序空间。3.“Cache-主存”层和“主存-辅存”层的简单比较表5.1对“Cache-主存”层和“主存-辅存”层做了一个简单的比较。第五章存储层次115.1.4两级存储层次之间的四个基本问题对于具体存储层次而言，将研究一下四个问题：1.当把一个块调入高一层（靠近CPU）存储器时，可以放到哪些位置上？（映象规则）2.当要访问的块在高一层存储器时，如何找到该块？（查找算法）3.当发生失效时，应替换哪一块？（替换算法）4.当进行写访问时，应进行哪些操作？（写策略）5.2Cache基本知识Cache用于解决上述四个基本问题，即映象规则、查找算法、替换算法以及写策略。第五章存储层次12Cache是按块进行管理的，Cache和主存均被分割成大小不同的块，信息以块为单位调入Cache。CPU的访存地址被分割成块地址和块内地址两部分：主存地址：块地址块内位移主存块地址用于查找在Cache中的位置，块内位移用于确定所访问的数据在该块中的位置。5.2.1映象规则三种映象规则如图5.4所示。1.全相联：主存中的任一块可以被放置到Cache中的任何一个位置的方法。2.直接映象：主存中的每一个块只能被放置到Cache中唯一的一个位置。3.组相联映象：主存中的每一个块可以被放置到Cache中唯一的一个组中的任一个位置。第五章存储层次13全相联映象时，主存中的任一块可以放置到Cache中的任一位置，如图5.4(a)所示，主存中的第9块可以放入Cache中的任意一个位置(带阴影)。图示中画出了Cache大小为8块、主存大小为16块的情况。直接映象情况下，对于主存的第i块(块地址为i)，设它映象到Cache中的第j块，则j＝imod(M)其中，M为Cache的块数。若M＝2m，则当地址表示为二进制数时，Cache的块号j实际上就是主存地址i的m位，如下图所示。因此，可以直接用主存地址的低m位去选择直接映象Cache中的相应块。第五章存储层次14组相联映象是直接映象和全相联映象的一种折衷：首先是映象到唯一的一个组上(直接映象的特征)，然后这个块可以被放入这个组中的任何一个位置(全相联的特征)。若主存第i块映象到Cache的第k组，则k＝imod(G)其中，G为Cache的组数。设G＝2g，则当表示为二进制数时，k实际上就是i的低g位，如图所示。因此，可以直接用主存块地址的低g位去选择Cache中的相应组。这里的低g位以及上述直接映象中的低m位通常称为索引。第五章存储层次15如果每组中有n个块(n=M/G)，则称该映象规则为n路组相联。n的值为相联度。直接相联和全相联是组相联的两种极端情况。表5.2给出了路数n和组数G的取值。表中M为Cache的块数。下面是一般性分析1.相联度越高(即n的值越大)，Cache空间的利用率越高，块冲突(一个主存块要进入已被占用的Cache位置)概率越低，因而Cache的失效率就越低；2.全相联的失效率最低，直接相联的失效率最高；3.增大n值并不一定使整个计算机系统的性能提高，而且还会使Cache的实现复杂度和代价增大。因此，绝大多数计算机都采用直接相联、两路相联或四路相联。特别是直接相联，采用最多。第五章存储层次165.2.2查找方法当CPU访问Cache时，有两个问题要解决：(1)当CPU访问Cache时，如何确定Cache中是否有要访问的块？(2)若有的话，如何确定其位置？这是通过查找目录表来实现的。Cache中设有一个目录表，该表共有m项，每一项对应于Cache中的一个块，称为标识(tag)。在目录表中给每一项设置一个有效位，记录Cache中相应块所包含的信息有效。一个主存块被调入Cache中某一个块位置时，它的标识就被填入目录表中与该Cache块相对应的项中，并且该项的有效位被置“1”，否则置“0”。第五章存储层次17根据映象规则不同，一个主存块可能映象到Cache中的一个或多个Cache块位置。我们称之为候选位置。当CPU访问该主存块时，必须且只需查找它的候选位所对应的目录表项(标识)。如果有与所访问的主存块相同的标识，且其有效值为“1”，则它所对应的Cache块就是所要找的块。为了保证速度，对各候选位置的标识的检查比较应并行进行。直接映象Cache的候选位置只有1个；全相联Cache的候选位置为m个；n路组相联则介于两者之间，为n个。一般采用单体多字存储器和比较器来实现并行查找。n越大，实现查找的机制就越复杂，代价就越高。无论是直接映象还是组相联映象，查找时，只需比较tag。Index无需参加比较。第五章存储层次18如果Cache的容量不变，提高相联度会增加每一组中的块数，从而会减少index的位数和增加tag的位数。图5.5给出了4路组相联并行标识比较。5.2.3替换算法当要从主存调入一块到Cache中时，会出现该块所映象的一组（或一个）Cache块已被占用的情况。这时，必须强迫腾出其中的某一块，已接纳新调入的块。腾出哪一块？这就是替换算法所要解决的问题。直接映象：Cache中的替换很简单，因为只有一个块可选择；组相联和全相联：Cache中有多个块选择，替换算法有随机法、FIFO和LRU三种。评价替换算法的标准：尽可能避免替换马上就要用到的信息。第五章存储层次191.随机法随机地选择被替换的块。优点：简单、易于用硬件实现，且对调试硬件很有帮助。不足：没有考虑Cache块被使用的情况，反映不了程序的局部性。2.先进先出FIFO（First-First-Out）最先装入相应组的块作为被替换的块。优点：容易实现。不足：虽然利用了各块进入Cache的顺序这段“历史”信息，但还是不能正确反映程序的局部性。因为最先进入的块，很可能是经常要用到的块。3.最近最少使用法LRU（LeastRecentlyUsed）选择近期最少被访问的块作为被替换的块。优点：反映程序的局部性原理，因而其失效在上述三种方法中是最低的。不足：LRU比较复杂，硬件实现比较困难，特别是当组的大小增加时，LRU的实现第五章存储层次20代价会越来越高，而且经常只是近似地实现（选择最久没有被访问过块作为被替换的块）。LRU实际上是依据程序局部性原理的一个推论：如果最近刚用过的块很可能就是马上要再用到的块，而最久没用过的块就是最佳的被替换者。表5.3给出了LRU与随机法在失效率方面的比较。第五章存储层次21表中的数据是对于一个VAX地址流(包括用户程序和操作系统程序)，块大小为16B的情况下统计的。在这个例子中，对于大容量Cache，LRU和随机法的失效率几乎没有什么差别。显然，n越大，Cache容量越大，时效率越低。此外，表中虽然没有列出，但是FIFO法的失效率比随机法和LRU都高。5.2.4写策略写需要对存储器和Cache两部分进行操作。写与读的比较：（1）检查标识并不能与写入Cache块并行进行，“写”一般比“读”化肥更多的时间。（2）处理器要写入的数据的宽度不是定长的。(通常为1~8字节)，写入时，只能修改Cache块中相应的第五章存储层次22部分，不能够多修改。而“读”则可以多读出几个字节也没关系。Cache与主存内容一致性问题：Cache内容是主存部分内容的一个副本。“写”访问却可能导致它们内容的不一致。显然，为了保证正确性，主存的内容也必须更新。何时更新主存，是写策略所要解决的问题。写策略是区分不同Cache设计方案的一个重要标志。写策略主要有写直达法和写回法两种。1.写直达法该法也称为存直达法。在执行“写”操作中，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。第五章存储层次23优点：易于实现。下一级存储器中的数据总是最新的。这一个优点对于I/O和多处理机是重要的。问题：写直达法在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，称为CPU写停顿(writestall)。常用的优化