存储器层次结构.docx
《存储器层次结构.docx》由会员分享，可在线阅读，更多相关《存储器层次结构.docx（56页珍藏版）》请在冰点文库上搜索。
存储器层次结构
第五章存储器层次结构
存储器是计算机系统的核心组成部分。
本章介绍存储器层次结构（memoryhierarchy）的基本概念和原理，讨论和分析如何利用局部性原理提高Cache/主存存储器层次结构、虚拟存储器（主存/辅存存储层次）的性能。
最后以Alpha机的存储系统为实例综合介绍存储体系的工作过程。
5.1存储器层次结构的基本概念
评价存储器性能的参数主要有三个方面：
容量、速度与价格。
存储器容量用S=W×l×m表示，W为存储器字长，l为存储器字数，m则为存储器体数。
评价存储器的速度一般有以下几个参数：
访问时间（accesstime）Ta：
从存储器接到读请求到所读的字传送到数据总线上的时间间隔。
存储周期Tm：
连续两次访问存储器之间所必需的最小时间间隔。
一般Tm>Ta。
存储带宽Bm：
存储器被连续访问时所提供的数据传输速流，单位是位（或字节）/秒。
存储器的价格通常用单位字节价格来表示。
若总容量为S的存储器的总价格为C，则单位字节价格c＝C/S。
程序设计人员总是希望存储器的速度尽可能的高，以与处理器的速度相匹配；存储器的容量尽可能的大，以装下可能极大的程序；因此，高速度、大容量、低价格始终是存储体系的设计目标。
一方面，经过几十年的发展，存储器的工艺实现技术有了突飞猛进的发展，高速、大容量、低价的存储器件以惊人的速度生产出来。
尽管如此，存储技术的发展证明单一工艺的单一存储器很难同时满足容量、价格、速度三方面的性能要求（见图5.1存储器的速度与价格的关系曲线）。
事实上，对容量与速度、速度与价格、容量与价格的性能要求是相互有矛盾的。
而且，存储器速度的改进始终跟不上CPU速度的提高。
图5.1存储器的速度与价格的关系曲线
另一方面，第一章中我们已介绍了局部性原理，即所有程序都具有这样的行为特性：
程序倾向于再次使用最近刚用过的数据和指令。
这样的局部性反映在空间和时间两个方面。
空间局部性（spatiallocality）（（如果某个数据或指令被引用，那么地址邻近的数据或指令不久很可能也将被引用。
时间局部性（temporallocality）（（如果某个数据或指令被引用，那么不久它可能还将再次被引用。
为了满足对存储器的性能要求，随着存储技术的不断发展，根据程序本身这种局部性的行为特性以及小硬件速度更快的设计原则，基于不同容量和速度的多种存储器所构成的存储器层次结构很自然地就产生了，如图5.2。
一个存储器层次结构由多级不同类型的存储器构成；越靠近CPU的存储器容量越小、速度越快、价格越高，离CPU越远的存储器容量越大、速度越慢、价格越低；第ｉ级存储器存储的信息是第ｉ－１级存储信息的子集（根据时间局部性），相邻两级存储器之间以块为单位进行信息交换（根据空间局部性）；各级存储器借助辅助软硬件构成一个整体，使得该存储体系具有接近于第ｎ级存储器速度、接近于第１级存储器容量和单位字节价格的性能。
图5.2存储器层次结构
存储器层次结构是由多级存储器构成的，但管理是以两级存储器为单位来进行的，而且一般只有在相邻两级存储器之间可以进行信息交换。
下面以两级存储器层次结构（简称存储层次，如图5.3为例介绍存储器层次结构的一些基本概念。
块（block）：
相邻两级存储器之间信息交换的最小单位。
块大小一般是固定的，也可以是可变的。
若块大小固定，则两级存储器的容量为块大小的整数倍。
图5.3两级存储器层次结构
命中率（hitrate）H：
CPU产生的有效地址可以直接在高层存储器中访问到的概率。
失效率（missrate）M：
CPU产生的有效地址直接在高层存储器中访问不到的概率。
M＝１－H。
命中时间（hittime）：
访问高层存储器所需的时间，其中包括本次访问是命中还是失效的判定时间。
失效损失（misspenalty）：
用低层存储器中相应的块替换高层存储器中的块，并将该块传送到请求访问的设备（通常是CPU）的时间。
它又可细分为访问时间和传送时间（transfertime）两部分。
其中前者指访问高层存储器失效时，在低层存储器中访问到块中第一个字的时间，又称访问延迟（accesslatency）。
后者则是传送块内其它字的附加时间。
访问时间与低层存储器的延迟有关，而传送时间则依赖于两级存储器之间的传输带宽和块大小。
由于存储器层次结构的设计目标之一是使其速度接近于高层存储器的速度，因此容易根据命中率的高低来评价存储器层次结构性能的好坏。
由于命中率或失效率与硬件速度无关，因而这样的评价是很片面的。
更好的评价存储器层次结构的性能参数是平均存储访问时间（averagememory-accesstime），其定义如下：
平均存储访问时间＝命中时间＋失效率×失效损失
应该注意的是尽管用平均存储访问时间评价存储器层次结构的速度性能比简单的用命中率来评价要好，平均存储访问时间仍然是性能的一种间接测度，它无法完全替代执行时间这个最准确的性能参数。
图5.4给出了块大小与失效率、失效损失之间的关系曲线（假设高层存储器的容量保持不变）。
图5.4块大小与失效率、失效损失之间的关系
由图5.4（ａ）可见失效率与块大小之间的关系呈现三种不同性质：
（１）当块大小过小时，失效率很高。
随着块大小的增加，由于有效地利用了程序的空间局部性，失效率呈现下降趋势；（２）当高层存储器容量保持不变时，失效率有一最低限值，此时块大小的变化对失效率没有影响；（３）当块大小超过某定值后，（这一定值又称为污染点），失效率呈现随块大小增加而上升的趋势，这是由于在高层存储器容量不变的情况下，增加块大小使高层存储器中的块数减少，对利用程序的时间局部性不利：
有用的信息（不久将再次被使用的信息）被大块中的无用信息替换出去，造成失效率上升。
由于失效损失中的访问延迟部分与块大小无关，传送时间随块大小的增加而线性增长，因此失效损失也将随块大小的增加而线性增长，如图书5.4（ｂ）。
当访问延迟很大时，增加块大小对失效损失的影响不大。
综合考虑块大小对失效率及失效损失的影响后，块大小与平均存储访问时间的关系见图5.5。
图5.5 块大小与平均存储访问时间的关系
设计存储器层次结构的根本目标是为了减少执行时间，因此在确定块大小时，不能以失效率为标准，而应选择使平均访问时间最小的块大小。
处理器的性能是计算机设计的最终依据，所以在选择降低平均存储访问时间的策略时应考虑对CPU性能的影响，保证设计方案不仅能降低平均存储访问时间，还能有益于改进CPU的性能，如同时提高CPI。
下面讨论一下存储器层次结构设计对CPU设计的影响。
在不支持存储器层次结构的系统中，由于所有的存储访问都需要相同的时间，所以处理器的设计相对简单。
而在存储器层次结构中对高层存储器的访问存在失效问题，这意味着CPU必须能够处理可变的存储访问时间。
当失效损失较小，只有几十个时钟周期时，CPU通常采用等待块传输结束的策略。
而当失效损失很大，达到CPU时钟的几千倍时，仍让CPU空闲着等待传输结束就太浪费了。
一般采用中断使CPU切换到其它进程去执行的办法。
但用这种方法来避免失效损失带来的额外开销意味着任何存储访问都可能导致CPU中断。
这样CPU还必须能够恢复引起这种中断的存储地址，使系统在失效处理时知道要传送哪一块。
当存储传送结束时，恢复原来被中断的进程，重新执行引起访问失效的那条指令。
处理器还必须设有一些机制以确定所需信息是否在存储器层次结构的最高层存储器中。
在每次存储访问时都要作这种判定检查，因而会影响命中时间。
为了保证达到可接受的性能，这种检测机制通常用硬件实现。
要实现存储器层次结构，处理机还必须有在相邻两级存储器之间传送信息块的机制。
如果块传送只需几十个时钟周期，那么这种传送机制一般用硬件来控制；如果需要几千个时钟周期，则可以用软件方法实现。
由于所有的存储器层次结构几乎都有相同的设计目标，遵循相同的设计原则，所以在考虑设计某二级存储器构成的存储器层次结构时所需考虑的基本问题是一致的。
下面是存储器层次结构设计中的四大基本问题：
（１）映象方式：
在低层存储器中的块以什么方式与高层存储器中的块相对应，即每个低层存储器的块按什么规则装入高层存储器。
（２）映象机构：
是映象方式的实现。
如果某信息块在高层存储器中，如何识别与查找它。
（３）替换策略：
发生访问失效而高层存储器所有可能对应块中不存在无效的块，此时根据什么规则选择有效信息块将之淘汰出高层存储器，而换之以从低层存储器中传送来的新块。
（４）写策略：
写操作时采用何种策略以保持相邻两级存储器中数据的一致性，发生写操作失效时是否将被写的块从低层存储器取入高层存储器。
我们将从这四个方面来介绍Cache／主存存储器层次结构和虚拟存储器，以及由它们在存储体系中所处的层次所决定的一些特性和性能优化方法。
5.2Cache／主存存储器层次结构
在现代计算机设计中几乎全部采用了Cache技术，这是因为在CPU与主存之间引入Cache，有效地解决了CPU与主存之间的速度匹配问题。
由Cache与主存构成的存储器层次结构具有两级存储器层次结构的一般特点，在５．１．２中介绍的基本概念在此也同样适用，只是在Cache／主存存储器层次结构中块的概念常用行（line）来表示。
有关Cache／主存存储器层次结构的一些基本结构参数的典型范围见表５．１。
表５．１ Cache基本结构参数
5.2.1Cache／主存的映象方式
最基本的Cache／主存映象方式有三种：
（１）直接映象（directmapped）：
这是最简单的一种映象方式。
主存中的一信息块只能对应Cache的一个特定行，如图5.6。
设Cache中共有
行，主存共分为Ｍｂ块，通常按下列规则将主存中的第ｉ块映象到Cache中的第ｊ行：
ｊ＝ｉ ｍｏｄ
图5.6 直接映象
（２）全相关映象（fullyassociative）：
主存中的一信息块可对应Cache中的任意一行，如图5.7所示。
图5.7 全相关映象
（３）组相关映象（setassociative）：
将Cache的行分成若干组，不妨设为Ｓ组，Ｓ＝
，则每组中有ｎ＝
／Ｓ＝
＝
行。
主存中的第ｉ块可以对应Cache中的某一特定组（一般是第（ｉ ｍｏｄ Ｓ）组）中的任意一行。
若组中有ｎ行，则称之为ｎ路组相关映象。
组相关映象方式示意图见图5.8。
图5.8 组相关映象
容易看出，直接映象与全相关映象都是组相关映象方式的特例：
直接映象即１路组相联，而全相关映象为ｍ路组相联（ｍ＝
）。
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地址在Cache中判定其要访问的信息块。
如图5.10，来自CPU的主存物理地址由两部分组成：
居地址高端的块帧地址（block-frameaddress）和低端部分的块内偏移地址（block-offsetaddress）。
其中块内偏移地址用于从块内选取所需字节（设块大小为
字节）；块帧地址（Ｍｂ位）在组相联方式下又分成二部分：
索引（index）用于选取组，标志（tag）用于和Cache中的行标志进行比较。
当CPU给出一地址后，首先由索引确定
组之一，然后地址标志和该组中的所有行标志（共
个，每个Ｍｂ－ｑ位）进行相联比较。
若有相同的且有效位被置位，则表示相应信息块在Cache中，命中Cache后由块内偏移地址确定要访问的具体字节。
否则Cache失效。
图5.10 CPU地址组成
如果Cache的容量、块大小保持不变，增加相联度意味着增加组内行数，此时组数减少，引起索引位数减少而标志位数增加，在图5.10中表现为标志／索引界限向右移动。
极端情况下即为全相联方式的映象机构：
此时参与相联比较的共有
个行标志，标志宽度为Ｍｂ位。
相反，减小相联度则引起索引位数增加而标志位数减少，极端情况下就是直接映象方式的映象机构：
此时参与相联比较的只有一个行标志，宽度为（Ｍｂ－Ｃｂ）位。
易知，在Cache容量、块大小一定的情况下，相联度越高，Cache块冲突率、失效率越低，而映象机构的实现越复杂、成本越高。
从性能折衷权衡考虑，组相关映象方式是一种较好的选择方案。
当然更精确的办法是用典型工作负载作软件模拟，进行量化性能分析，这部分内容将在第
5.2.3Cache／主存的替换策略
当访问Cache失效时，如果相应的组中存在无效数据行（该行的有效位未置），此时不存在替换问题。
否则必须采取某种策略选择一有效数据行将其淘汰出Cache，而换之以从主存送来的数据块。
Cache替换策略非常重要，它将直接影响Cache的命中率。
对于直接映象方式而言，实现替换策略的硬件机制相对较简单。
事实上，此时不存在选择问题，因为参与地址匹配的只有一个行标志，所以发生失效时只能对这一特定行进行替换。
但是，对于全相联和组相关映象，发生Cache失效时，如果组中不存在无效的数据行，就需要在多个有效数据行中进行选择。
基本的替换策略有以下三种：
（1）随机替换策略（RAND）——随机地在候选行中选择一行进行替换。
由于完全随机的选择将给硬件调试带来很大的困难，因此，为使替换行为可再现以利调试，一些系统实际上采用的是伪随机替换策略。
这种策略没有利用数据行的“历史”使用信息，不反映程序行为的局部性。
（2）先进先出策略（FIFO）——在候选块中选择最早送入Cache的那一行进行替换。
它利用了数据行的“历史”使用信息，但不能正确反映程序局部性，因为最早进入Cache的块很可能是经常被引用的块。
（3）最近最少使用策略（LRU）——在候选块中选择最近最少被访问到的那一行进行替换。
这种策略是利用程序局部性原理的必然结果：
因为最近使用过的块很可能不久再次被引用。
为减少可能再次被引用的块替换出去的机会，最佳候选块只能是最近最少使用的块。
要实现LRU策略，就必须记录行被访问的情况。
图5.11给出了在全相关映象的存储器层次结构中，对于某一块帧地址序列，使用LRU策略选择的替换块号。
假设Cache分为4个块，而且开始时最近最少使用的块是块0。
图5.11LRU替换策略示意图
尽管FIFO策略利用了数据块使用的“历史”信息，但实验数据表明RAND策略的性能一般要比FIFO策略要好。
而且RAND最重要的特点是简单，易于用硬件实现。
一般说来，LRU策略的性能要好于RAND，但随着要记录访问情况的块数增多，实现LRU策略的成本迅速增加，此时性能改进却不明显。
表5.2列出了不同Cache容量、不同相联度情况下，使用LRU策略和RAND策略时Cache失效率的对比实验数据。
由图中最后一行数据可知：
当Cache容量达256KB时，采用何种替换策略对失效率几乎没有影响。
因此可见：
与大容量Cache相比，替换策略对小容量Cache的性能影响更大。
表5.2替换策略对Cache失效率的影响
5.2.4Cache/主存的写策略
所有的取指访问是读操作，而大部分指令不对存储器进行写操作,所以，对于Cache的访问主要是读操作。
根据第三章指令使用频度分析数据可知，一般程序的数据传送指令中，取数操作（Load）大约是存数操作（Store）的2倍（？
Fig4.34中，Load指令占18%，Store指令占9%），而且在存储器数据传送（memorytransfer）中，写操作所占比例不到10%。
根据高频事件高速处理的设计原则，在Cache中应尽量优化读操作的能力，同时由Amdahl定律可知，面向高性能的设计不能忽视写操作的速度。
通常，Cache的读操作较易快速实现。
一般，在读取并比较标志的同时就可以读取相应数据行，即一得到来自CPU的块帧地址就可以开始读操作。
如果读命中，则读出的数据行立即送往CPU，而如果读失效，读出的数据作废，这样作既没好处，也没损失。
写操作的情况就不同了。
处理器指定写操作的数据宽度一般在1～8字节之间，即一个写操作仅改变一个数据块某一部分的内容。
通常写操作又细分为三个步骤：
（1）读取源数据块；
（2）修改其中的一部分；（3）写回修改后的数据。
因为修改步骤不能与标志检查并行进行，所以一定要等标志检查确定命中后才能进行修改步骤。
这样，写操作所需的时间通常比读操作长。
在Cache设计中有多种不同的写策略，基本的写策略有如下两种：
（1）直写技术（writethrough）——信息被写入Cache行的同时，利用CPU和主存之间的直接数据通路写入主存的对应块中。
（2）回写技术（writeback）——信息只写入Cache的相应行。
仅当被修改过的行被替换出Cache时，才将它写入主存的相应存储块中。
根据Cache行的信息与对应主存块中的信息相同与否，采用回写技术的Cache行被分为“干净的”或“脏的”两种。
“干净的”行即该数据行在Cache中未被修改过，数据与其主存中的对应块相同。
而“脏的”行即该数据块在Cache中已被修改过。
因此当“干净的”行被替换出Cache时，不必将该行写回主存。
相反，当“脏的”行被替换时，必须将其写回主存。
为区分行是“干净的”还是“脏的”，通常为每个Cache行设置一个称为“脏位”（也称“修改位”）的标志位，指示该Cache行是否曾被修改过。
回写技术和直写技术各有利弊。
回写技术的优点是：
Cache命中时，写操作是以写Cache的速度进行，而且在一个数据块内的多次写操作只需要对低层存储器写一次。
由于每个写操作都不必写主存，因而回写技术有利于降低Cache/主存存储器层次结构对主存带宽的要求。
这一性质使回写技术在多处理器（机）系统设计中颇具吸引力。
对于直写技术，读操作引起的Cache失效不会导致对低层存储器的写操作，而且直写技术的硬件实现更为简单。
直写技术的另一个优点是主存中总是保存着数据的最新拷贝，这一性质对I/O和处理器（机）系统都非常重要，我们将在，在多处理器（机）系统的设计中，既希望利用回写技术减少每个处理器（机）与主存之间的数据传输量，又希望用直写技术保证Cache和主存的一致性。
如果采用直写技术，那么在对低层存储器的写操作期间，CPU必须停下来等待，CPU的这段等待时间被称为写停顿延迟。
通常所用的减少写停顿延迟的办法是设置写缓冲，使CPU在存储器更新期间能继续工作。
但设置写缓冲也不能完全避免写停顿，这一点我们将在
当出现写失效时，无论直写技术还是回写技术都存在是否要将修改的数据块装入Cache的问题，一般有两种选择方案：
（1）写分配（writeallocate）——将要写的数据装入Cache，然后进行和写命中时相同的操作。
这种方法与读失效时的处理方法类似。
（2）无写分配（nowriteallocate）——也称为绕写（writearound）。
直接对低级存储器中的数据块做改写操作，不再将此数据块装入Cache。
虽然这两种方案对直写技术或回写技术都适用，但通常的做法是在采用回写技术时选择写分配，这样对该数据块的后续写操作可以在Cache中进行（时间局部性原理的自然应用）；采用直写技术时一般选择无写分配，因为按直写技术，即使该数据块有后续写操作仍需对主存作改写操作。
5.2.5Cache/主存存储器层次结构实例
本节将以VAX-11/780的Cache为例具体介绍Cache/主存存储器层次结构的结构，并介绍其工作流程。
VAX-11/780的Cache的容量为8KB（8192字节），块大小为8字节，映象方式是2路组相联，采用随机替换策略及直写技术，配有1个字（4字节）的写缓冲，写失效时采用无写分配方法。
VAX-11/780的Cache结构如图5.12所示。
图5.12VAX-11/780的Cache结构
如图5.12，当Cache读命中时，Cache的工作流程可分为五大步骤，这五个步骤是在一个CPU时钟周期内完成的。
（1）来自CPU的地址被分为29位块帧地址和3位块内偏移地址，块帧地址又分成20位标志和9位索引。
（2）根据索引选择Cache中的一个组，读取组内各行标志以判定要访问的数据块是否在Cache中。
图中512组中的0号数据块组成模块0（bank0），而1号数据块组成模块1（bank1）。
索引被同时送往两个模块，读取该组中两个数据行的行标志。
索引的位数是由Cache容量、块大小及相联度决定的，表达式如下：
Cache容量8192
组数=—————————=————=512=29
行大小*相联度8*2
（3）块帧地址的标志域与步骤
（2）中读取的两个行标志作相等比较。
为保证相应行的数据有效，对应的有效位必须是被置位的，否则比较结果无效（被忽略）。
（4）假设有一行标志与块帧地址的标志相匹配，则由2选1多路转换器选取相应的数据行。
二个行标志同时匹配的情况是不可能发生的，因为替换算法保证了一个数据块只有一个行标志。
为减少命中时间，数据读取是与读取行标志同时进行的，所以当多路转换器就绪时，数据也已准备好了。
这一步骤在组相联的Cache中是不可少的，但在直接映象Cache中，因为不必选择数据行，所以本步骤可以省去。
由于多路转换器可能处在关键的定时路径（timingpath）上，因而可能影响（危及）CPU的时钟周期。
在下面的例3中我们将对这种影响作定量分析。
（5）读出的字送往CPU。
读Cache失效时，Cache向CPU发出一个停顿（stall）信号通知CPU等待，并从主存中读入2个字（8字节）。
在VAX-11/780上这需要6个时钟周期（忽略总线干扰（businterference））。
从主存读取的数据块送达时，Cache要选择一个数据行替换出去，VAX-11/780的Cache采用随机替换策略，即当组中二个数据行均为有效行时随机选取一行替换出去。
替换数据块意味着更新该行的数据、地址标志和有效位。
完成这些工作后Cache再经过一个常规的读命中周期，将读取的数据送往CPU。
与其他任何Cache一样，VAX-11/780的写操作比读操作更为复杂。
如果写命中，那么前四步操作与读命中时完全一样，第五步则是修改数据块，并将数据更新部分写入Cache相应行。
由于VAX-11/780在写失效时采用无写分配方法，因而一旦发生写失效，CPU将绕过Cache直接将数据写入低层存储器。
由于VAX-11/78
升级会员 