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