第五章存储器层次结构

第五章存储器层次结构5-1第五章存储器层次结构存储器是计算机系统的核心组成部分。本章介绍存储器层次结构(memoryhierarchy)的基本概念和原理，讨论和分析如何利用局部性原理提高Cache/主存存储器层次结构、虚拟存储器(主存/辅存存储层次）的性能。最后以Alpha机的存储系统为实例综合介绍存储体系的工作过程。5.1存储器层次结构的基本概念5.1.1存储器的基本性能参数评价存储器性能的参数主要有三个方面：容量、速度与价格。存储器容量用S=W×l×m表示，W为存储器字长，l为存储器字数，m则为存储器体数。评价存储器的速度一般有以下几个参数：访问时间(accesstime)Ta：从存储器接到读请求到所读的字传送到数据总线上的时间间隔。存储周期Tm：连续两次访问存储器之间所必需的最小时间间隔。一般TmTa。存储带宽Bm：存储器被连续访问时所提供的数据传输速流，单位是位(或字节）/秒。存储器的价格通常用单位字节价格来表示。若总容量为S的存储器的总价格为C，则单位字节价格c＝C/S。5.1.2存储器层次结构的基本原理程序设计人员总是希望存储器的速度尽可能的高，以与处理器的速度相匹配；存储器的容量尽可能的大，以装下可能极大的程序；因此，高速度、大容量、低价格始终是存储体系的设计目标。一方面，经过几十年的发展，存储器的工艺实现技术有了突飞猛进的发展，高速、大容量、低价的存储器件以惊人的速度生产出来。尽管如此，存储技术的发展证明单一工艺的单一存储器很难同时满足容量、价格、速度三方面的性能要求（见图5.1存储器的速度与价格的关系曲线）。事实上，对容量与速度、速度与价格、容量与价格的性能要求是相互有矛盾的。而且，存储器速度的改进始终跟不上CPU速度的提高。图5.1存储器的速度与价格的关系曲线另一方面，第一章中我们已介绍了局部性原理，即所有程序都具有这样的行为特性：程序倾向于再次使用最近刚用过的数据和指令。这样的局部性反映在空间和时间两个方面。空间局部性(spatiallocality)((如果某个数据或指令被引用，那么地址邻近的数据或指令不久很可能也将被引用。时间局部性(temporallocality)((如果某个数据或指令被引用，那么不久它可能还将再次被引用。为了满足对存储器的性能要求，随着存储技术的不断发展，根据程序本身这种局部性的行为特性以及小硬件速度更快的设计原则，基于不同容量和速度的多种存储器所构成的存储器层第五章存储器层次结构5-2次结构很自然地就产生了，如图5.2。一个存储器层次结构由多级不同类型的存储器构成；越靠近CPU的存储器容量越小、速度越快、价格越高，离CPU越远的存储器容量越大、速度越慢、价格越低；第ｉ级存储器存储的信息是第ｉ－１级存储信息的子集（根据时间局部性），相邻两级存储器之间以块为单位进行信息交换（根据空间局部性）；各级存储器借助辅助软硬件构成一个整体，使得该存储体系具有接近于第ｎ级存储器速度、接近于第１级存储器容量和单位字节价格的性能。图5.2存储器层次结构存储器层次结构是由多级存储器构成的，但管理是以两级存储器为单位来进行的，而且一般只有在相邻两级存储器之间可以进行信息交换。下面以两级存储器层次结构（简称存储层次，如图5.3为例介绍存储器层次结构的一些基本概念。块(block)：相邻两级存储器之间信息交换的最小单位。块大小一般是固定的，也可以是可变的。若块大小固定，则两级存储器的容量为块大小的整数倍。图5.3两级存储器层次结构命中率(hitrate)H：CPU产生的有效地址可以直接在高层存储器中访问到的概率。失效率(missrate)M：CPU产生的有效地址直接在高层存储器中访问不到的概率。M＝１－H。命中时间(hittime)：访问高层存储器所需的时间，其中包括本次访问是命中还是失效的判定时间。失效损失(misspenalty)：用低层存储器中相应的块替换高层存储器中的块，并将该块传送到请求访问的设备（通常是CPU）的时间。它又可细分为访问时间和传送时间(transfertime)两部分。其中前者指访问高层存储器失效时，在低层存储器中访问到块中第一个字的时间，又称访问延迟(accesslatency)。后者则是传送块内其它字的附加时间。访问时间与低层存储器的延迟有关，而传送时间则依赖于两级存储器之间的传输带宽和块大小。5.1.3存储器层次结构的性能由于存储器层次结构的设计目标之一是使其速度接近于高层存储器的速度，因此容易根据命中率的高低来评价存储器层次结构性能的好坏。由于命中率或失效率与硬件速度无关，因而这样的评价是很片面的。更好的评价存储器层次结构的性能参数是平均存储访问时间(averagememory-accesstime)，其定义如下：平均存储访问时间＝命中时间＋失效率×失效损失应该注意的是尽管用平均存储访问时间评价存储器层次结构的速度性能比简单的用命中率来评价要好，平均存储访问时间仍然是性能的一种间接测度，它无法完全替代执行时间这个最准确的性能参数。图5.4给出了块大小与失效率、失效损失之间的关系曲线（假设高层存储器的容量保持不变）。图5.4块大小与失效率、失效损失之间的关系第五章存储器层次结构5-3由图5.4（ａ）可见失效率与块大小之间的关系呈现三种不同性质：（１）当块大小过小时，失效率很高。随着块大小的增加，由于有效地利用了程序的空间局部性，失效率呈现下降趋势；（２）当高层存储器容量保持不变时，失效率有一最低限值，此时块大小的变化对失效率没有影响；（３）当块大小超过某定值后，（这一定值又称为污染点），失效率呈现随块大小增加而上升的趋势，这是由于在高层存储器容量不变的情况下，增加块大小使高层存储器中的块数减少，对利用程序的时间局部性不利：有用的信息（不久将再次被使用的信息）被大块中的无用信息替换出去，造成失效率上升。由于失效损失中的访问延迟部分与块大小无关，传送时间随块大小的增加而线性增长，因此失效损失也将随块大小的增加而线性增长，如图书5.4(ｂ)。当访问延迟很大时，增加块大小对失效损失的影响不大。综合考虑块大小对失效率及失效损失的影响后，块大小与平均存储访问时间的关系见图5.5。图5.5块大小与平均存储访问时间的关系设计存储器层次结构的根本目标是为了减少执行时间，因此在确定块大小时，不能以失效率为标准，而应选择使平均访问时间最小的块大小。5.1.4存储器层次结构对CPU设计的影响处理器的性能是计算机设计的最终依据，所以在选择降低平均存储访问时间的策略时应考虑对CPU性能的影响，保证设计方案不仅能降低平均存储访问时间，还能有益于改进CPU的性能，如同时提高CPI。下面讨论一下存储器层次结构设计对CPU设计的影响。在不支持存储器层次结构的系统中，由于所有的存储访问都需要相同的时间，所以处理器的设计相对简单。而在存储器层次结构中对高层存储器的访问存在失效问题，这意味着CPU必须能够处理可变的存储访问时间。当失效损失较小，只有几十个时钟周期时，CPU通常采用等待块传输结束的策略。而当失效损失很大，达到CPU时钟的几千倍时，仍让CPU空闲着等待传输结束就太浪费了。一般采用中断使CPU切换到其它进程去执行的办法。但用这种方法来避免失效损失带来的额外开销意味着任何存储访问都可能导致CPU中断。这样CPU还必须能够恢复引起这种中断的存储地址，使系统在失效处理时知道要传送哪一块。当存储传送结束时，恢复原来被中断的进程，重新执行引起访问失效的那条指令。处理器还必须设有一些机制以确定所需信息是否在存储器层次结构的最高层存储器中。在每次存储访问时都要作这种判定检查，因而会影响命中时间。为了保证达到可接受的性能，这种检测机制通常用硬件实现。要实现存储器层次结构，处理机还必须有在相邻两级存储器之间传送信息块的机制。如果块传送只需几十个时钟周期，那么这种传送机制一般用硬件来控制；如果需要几千个时钟周期，则可以用软件方法实现。5.1.5存储器层次结构设计的基本问题由于所有的存储器层次结构几乎都有相同的设计目标，遵循相同的设计原则，所以在考虑设计某二级存储器构成的存储器层次结构时所需考虑的基本问题是一致的。下面是存储器层次结构设计中的四大基本问题：（１）映象方式：在低层存储器中的块以什么方式与高层存储器中的块相对应，即每个低层存储器的块按什么规则装入高层存储器。第五章存储器层次结构5-4（２）映象机构：是映象方式的实现。如果某信息块在高层存储器中，如何识别与查找它。（３）替换策略：发生访问失效而高层存储器所有可能对应块中不存在无效的块，此时根据什么规则选择有效信息块将之淘汰出高层存储器，而换之以从低层存储器中传送来的新块。（４）写策略：写操作时采用何种策略以保持相邻两级存储器中数据的一致性，发生写操作失效时是否将被写的块从低层存储器取入高层存储器。我们将从这四个方面来介绍Cache／主存存储器层次结构和虚拟存储器，以及由它们在存储体系中所处的层次所决定的一些特性和性能优化方法。5.2Cache／主存存储器层次结构在现代计算机设计中几乎全部采用了Cache技术，这是因为在CPU与主存之间引入Cache，有效地解决了CPU与主存之间的速度匹配问题。由Cache与主存构成的存储器层次结构具有两级存储器层次结构的一般特点，在５．１．２中介绍的基本概念在此也同样适用，只是在Cache／主存存储器层次结构中块的概念常用行(line)来表示。有关Cache／主存存储器层次结构的一些基本结构参数的典型范围见表５．１。表５．１Cache基本结构参数5.2.1Cache／主存的映象方式最基本的Cache／主存映象方式有三种：（１）直接映象(directmapped)：这是最简单的一种映象方式。主存中的一信息块只能对应Cache的一个特定行，如图5.6。设Cache中共有mCb2行，主存共分为Ｍｂ块，通常按下列规则将主存中的第ｉ块映象到Cache中的第ｊ行：ｊ＝ｉｍｏｄ2Cb图5.6直接映象（２）全相关映象(fullyassociative)：主存中的一信息块可对应Cache中的任意一行，如图5.7所示。图5.7全相关映象（３）组相关映象(setassociative)：将Cache的行分成若干组，不妨设为Ｓ组，Ｓ＝2q，则每组中有ｎ＝2Cb／Ｓ＝2()Cqb＝2e行。主存中的第ｉ块可以对应Cache中的某一特定组（一般是第（ｉｍｏｄＳ）组）中的任意一行。若组中有ｎ行，则称之为ｎ路组相关映象。组相关映象方式示意图见图5.8。第五章存储器层次结构5-5图5.8组相关映象容易看出，直接映象与全相关映象都是组相关映象方式的特例：直接映象即１路组相联，而全相关映象为ｍ路组相联（ｍ＝2Cb）。5.2.2Cache／主存的映象机构映象机构的功能是根据CPU送来的有效主存地址确定要访问的信息是否在Cache中，并找到该信息块，也即它是映象方式的具体实现。由于无论采用哪种映象方式，Cache中的某一行总是对应于主存的多个块，即Cache中的某信息行其来源可以是主存中的多个块。因此，Cache中的每行都带有一个标志(tag)以确定该行所对应的主存块。Cache中存放标志的那部分存储器称为标志存储器。每个Cache的标志中可以包含一些特定信息，根据这些特定信息可以检测他们是否和来自CPU的块帧地址相匹配。存放标志的那部分存储器称为标志存储器。由于主存中的某一块可映象到Cache中的多个块（除直接映象外），而且对Cache／主存存储器层次结构来说，速度性能是至关重要的，因而来自CPU的主存地址是和Cache中所有可能对应行的标志同时作相联比较，以快速找出相匹配的块，如图5.9所示。图5.9映象机构示意图为确定Cache行中所含信息是否有效，通常还在行标志中添加一个有效位（validbit)，指明行中信息是否有效。如果未置有效位，则该行的标志不能与主存地址匹配。在估算Cache成本时，标志存储器的成本容易被忽略。因为每个Cache行都带有一个标志，所以增加块大小有益于减少标志成本在Cache总成本中所占的比例。下面，我们考虑如何由CPU地址