计算机组成原理chap课件

1、第四章 存储系统南京大学计算机系多媒体技术研究所袁春风1第四章 内部存储器存储器的基本概念半导体存储器多模块存储器高速缓冲存储器辅助(外部)存储器虚拟存储器2南京大学计算机系 多媒体技术研究所 袁春风4.1 存储器的基本概念基本术语主要性能指标存储器分类存储器分级体系结构3南京大学计算机系 多媒体技术研究所 袁春风4.1 .1 基本术语记忆单元（位元）：具有两种稳态的能够表示二进制数码0和1的物理器件。存储单元：主存中具有相同地址的那些位构成一个存储单元。存储体：若干存储单元构成一个存储体。编址方式：对存储体中各存储单元进行编号的方式。按字节编址按字编址按半字编址存储器地址寄存器（MAR）：用

2、于存放主存单元地址的寄存器。存储器数据寄存器（MDR）：用于存放主存单元中的数据的寄存器。4南京大学计算机系 多媒体技术研究所 袁春风4.1 .1 基本术语存储字、编址单位和传输单位机器字长：运算器中参加运算的寄存器的位数。存储字：存储器按机器字长组织的一个“自然”单位。它的长度一般应等于一个数或指令的位数。但大多数机器并不是这样。存储芯片中的一个读写单位。编址单位：一个存储单元的位数。有的按字编址，有的按字节编址，等等。传输单位：对主存而言，指一次从存储器读出或写入的数的位数，它可以不等于存储字的长度，也可不等于编址单位。对外存而言，数据通常按块传输。 （例如：386/486等，其编址单位为

3、字节、字长为32位，单字位数为16位，但传输单位可以是8/16/24/32位。）5南京大学计算机系 多媒体技术研究所 袁春风4.1.2 主要性能指标存储容量 ：存储器能够容纳的二进制信息量。存储器的存储容量越大，能存储的信息就越多。存储容量常用存储单元数与每个单元的位数的乘积表示，或用字节数表示。如PDP-11/23计算机主存容量为64K字，字长为16位，则可表示为64K*16位，或128K字节，记为128KB（Byte）。现代计算机的主存容量要大得多，一般以字节为单位表示。如以Pentium为CPU的微型计算机，主存的配置一般为32256MB。 通常用2的整数幂来计算存储容量，计量单位有K，

4、M，G，T等。这些计算单位之间的换算如下：1K=210=1024 1G=230=1024M 1M=220=1024K 1T=240=1024G6南京大学计算机系 多媒体技术研究所 袁春风4.1.2 主要性能指标存取速度存取时间TA；存储器接到读/写命令后到被读数据稳定在MDR的输出端或数据被写入某单元为止的时间间隔。也称读写时间。存储周期TMC：连读两次访问存储器所需的最小时间间隔，它应等于存取时间加上下一存取开始前所要求的附加时间（ 因为存储器由于读出放大器、驱动电路等都有一段稳定恢复时间，所以读出后不能立即进行下一次访问。 ）。因此，TMC比TA大。最大数据传输率R：连续访问时每秒钟从存储

5、器入出的信息量。单位： 位/秒(bps) 或 字节/秒(Bps) 。 RAM：R=W/ TMC （假定存储周期是500ns，每次读写一个字(16位),则最大数据传输率为：16b/500ns=32Mbps。) 磁表面： TN =TA+N/R (其中TN 为读写N位的平均时间；TA为平均存取时间；N为位数) 速度计量单位：毫秒= 10-3秒(m s)，微秒=10-6秒( s)，纳秒=10-9秒(ns)7南京大学计算机系 多媒体技术研究所 袁春风4.1.2 主要性能指标价格（每位成本）存储器的价格常用每位(bit)的价格来衡量。它不仅包含了存储元件本身的价格，也包括为该存储器操作服务的外围电路的价格

6、。一般来说，用来组成主存的存储器价格较高，如半导体存储器（双极型和MOS型存储器）。辅助存储器（如磁盘、磁带、光盘）的价格则低得多。速度很高的存储器往往价格较贵，容量也不可能很大。因此容量、速度、价格三个指标是互相制约的。 8南京大学计算机系 多媒体技术研究所 袁春风4.1.2 主要性能指标可靠性存储器可靠性用平均故障时间间隔MTBF（Mean Time Between Failures）来衡量。 MTBF可以理解为两次故障之间的平均时间间隔。它的值越大表示存储器的可靠型越高，可连续运行时间就越长。与MTBF意义相同的术语是平均无故障时间或平均无差错时间。 MTBF的计算公式为：t存储器系统运

7、行的一段时间N(t) 系统在0, t时间段内的故障次数9南京大学计算机系 多媒体技术研究所 袁春风4.1.2 主要性能指标其他性能指标集成度：每个芯片所含的二进制信息量。功耗：发热程度和耗电量。 集成度和功耗是矛盾的两个方面。我们希望集成度大而功耗小，但一般集成度越大，功耗也越大。10南京大学计算机系 多媒体技术研究所 袁春风4.1.3 存储器分类（1）按工作性质/存取方式分类随机存取存储器(RAM) ：每个单元的读写时间一样，且与各单元所在位置无关。如：内存。顺序存取存储器(SAM)：数据按顺序从存储载体的始端读出或写入，因而存取时间的长短与信息所在位置有关。例如：磁带。直接存取存储器：利用

8、一个共享读写机制，直接定位到要读写的数据块，在读写某个数据块时按顺序进行。例如：磁盘。相联存取存储器：按内容检索到存储位置进行读写。例如：快表。依据不同的特性有多种分类方法11南京大学计算机系 多媒体技术研究所 袁春风4.1.3 存储器分类（2）按存储介质分类半导体存储器双极型，静态MOS型，动态MOS型磁表面存储器磁盘，磁带，磁鼓光存储器CD，CD-ROM，MO，DVD磁芯存储器电荷耦合器件(CCD)磁泡存储器12南京大学计算机系 多媒体技术研究所 袁春风4.1.3 存储器分类（3）按信息的可更改性分类读写存储器（Read/Write Memory)：可读可写。只读存储器（Read Only

9、 Memory)：只能读不能写。（4）按断电后信息的可保存性分类 非易失性存储器 ：信息可一直保留，不需电源维持。如 ： ROM，磁表面存储器。易失性存储器：电源关闭时信息自动丢失。如：RAM 。13南京大学计算机系 多媒体技术研究所 袁春风4.1.3 存储器分类（5）按功能/容量/速度/所在位置分类寄存器：封装在CPU内，用于存放当前正在执行的指令和使用的数据。Cache：位于CPU内部或附近，用来存放当前要执行的局部程序段和数据。速度可与CPU匹配，容量小。内存储器（主存储器）：位于CPU之外，用来存放已被启动的程序及所用的数据。容量较大，速度较快。外存储器（辅助存储器）：位于主机之外，用

10、来存放暂不运行的程序和数据。容量大而速度慢。 从使用和维护角度来说，计算机最好使用一个容量极大而速度极快的存储器。但往往做不到。因而采用一种分级体系结构，使各种不同功能/容量/速度/价格的存储器相互协调以构成最佳性能的存储系统。 14南京大学计算机系 多媒体技术研究所 袁春风4.1.4 存储器分级体系结构五层金字塔形分层系统从上到下的特点：1，每位价格降低2，容量增大3，存取时间增大4，访问频度降低Traditional Memory Hierarchy传统结构15南京大学计算机系 多媒体技术研究所 袁春风4.1.4 存储器分级体系结构Contemporary Memory Hierarchy

11、当代结构开辟一部分内存区，用作“Disk Cache”，用于存放将被送到磁盘上的数据。引入“Disk Cache”的好处：(1)写盘时按“簇”进行，以避免频繁地小块数据写盘。(2)有些中间结果数据在写回盘之前可被快速地再次使用。16南京大学计算机系 多媒体技术研究所 袁春风4.2 半导体随机存储器记忆单元的基本原理半导体RAM的组织再生与刷新只读存储器存储器的数据检/纠错17南京大学计算机系 多媒体技术研究所 袁春风4.2.1 记忆单元的基本原理作为记忆材料的条件：有两种稳态，且是可逆的。在外部信号激励下，两种稳态能进行无限次相互转换。在外部信号激励下，能读出两种稳定状态。长期存储可靠可用作记

12、忆单元(位元)的材料：磁性材料（磁芯、磁泡、CCD等，用的很少）半导体材料（TTL,ECL,MOS管，大量使用）半导体记忆单元双极型MOS管静态MOS动态MOSSRAMDRAM目前的主流技术18南京大学计算机系 多媒体技术研究所 袁春风4.2.1 记忆单元的基本原理（1）速度快，但集成度低、功耗大电路速度主要取决于射极电流“拨动”的速度，而电流变化的快慢，与管子的频率特性有关，晶体管的频率特性可以做得很高，所以双极型记忆单元速度是很快的。（2）非破坏性读出，也无需刷新。信息读出后，原来的信息状态不变，而且稳定。主要用作高速小容量的Cache。对于大容量的主存储器一般用功耗小、集成度高，但速度较

13、慢的MOS管电路。 双极型记忆单元电路的特点19南京大学计算机系 多媒体技术研究所 袁春风4.2.1 记忆单元的基本原理静态六管MOS有以下三个特点：非破坏性读出，不需重写或刷新； 结构简单，可靠性高，具有一定速度； 电路元件较多，占硅片面积大， 故功耗大，集成度不高。 20南京大学计算机系 多媒体技术研究所 袁春风动态单管MOS记忆单元电路图21南京大学计算机系 多媒体技术研究所 袁春风动态单管记忆单元读出电压MOS电路中，数据线本身存在分布电容C0 ，故在读出时，读出线上的电荷在串接的两电容C0和CS中间分配，使得读出电压下降，如果原存储在CS上的电压为VS则读出电压VR为：一般C0CS般

14、,故读出电压信号很微弱，通常需用放大电路。22南京大学计算机系 多媒体技术研究所 袁春风4.2.2 半导体RAM的组织存储器芯片：存储体+外围电路(地址译码和读写控制)记忆单元的组织： 位元字线W位线S0位线S1 读写控制Din DoutR/W 位元选择线(字线)数据线(位线)读写控制Din DoutR/W存储体： 由记忆单元(位元)构成的存储阵列记忆单元存储器芯片内存条（存储器模块）23南京大学计算机系 多媒体技术研究所 袁春风4.2.2 半导体RAM的组织存储器芯片的种类（由存储体结构来分）字片式（单方向译码，一维地址驱动）阵列中的位元排列与存储器中字的逻辑排列相同。存储体的每一行构成多位

15、的一个存储字，一起被读写。每列由相同位构成，共用一个读写电路，有多个读写电路。在位方向上便于扩充。 位片式（双方向译码，二位地址驱动）芯片阵列由行和列排列而成，每次只能读写行、列交叉处的一位数据。每个芯片只有一位读写电路。在字和位方向上都能扩充，但需有片选信号。24南京大学计算机系 多媒体技术研究所 袁春风字片式存储体阵列组织X向译码器一维地址译码系统地址驱动线25南京大学计算机系 多媒体技术研究所 袁春风位片式存储体阵列组织26南京大学计算机系 多媒体技术研究所 袁春风位片式芯片框图27南京大学计算机系 多媒体技术研究所 袁春风字扩展为芯片字数的4倍位扩展为芯片位数的16倍28南京大学计算机

16、系 多媒体技术研究所 袁春风半导体随机存储器基本结构图主存储器29南京大学计算机系 多媒体技术研究所 袁春风4.2.2 半导体RAM的组织地址译码（驱动）器用于将总线上传输过来的地址信息进行译码，在所有字线中选择一根字线，使其驱动为高电平。地址线有n条时，译码器输出2n条字线，能驱动2n个存储单元中任一个。 问题：对于一个具有2n个单元的位片式芯片（即：采用二维地址译码的存储器芯片），其地址驱动（选择）线的条数为多少？ 2n/2 +2n/230南京大学计算机系 多媒体技术研究所 袁春风地址译码器电路示意图31南京大学计算机系 多媒体技术研究所 袁春风4.2.2 半导体RAM的组织读写控制 存储

17、器的基本操作是读操作和写操作。读写控制电路用于接收总线送来的读/写控制信号，控制数据写入记忆单元，或将数据从记忆单元读出。 下图是一个二进制位的读写与I/O电路示意图。读写控制电路由门电路1、2组成，“读写命令R/W”接受总线传送过来的读/写命令。当R/W=1时是读操作命令，R/W=0时是写操作。 32南京大学计算机系 多媒体技术研究所 袁春风16M位=4Mb x 4=2048 x 2048 x 4=211x211x4(1) 地址线：11根 分时复用,由RAS和CAS提供控制时序。 采用分时复用技术使得每出现新一代存储器芯片，容量至少 提高四倍。（因为每增加一根地址线，行和列各扩大2倍， 总的

18、扩大4倍）(2) 这个DRAM芯片的存储字是4位，所以还需将多个这样的芯 片连接到DRAM控制器，才能在总线上读写相应的位数。(3) 所有DRAM芯片都同时刷新，由刷新计数器自动计数、按行 刷新（只产生行地址），对CPU透明。 举例2：典型的16M位DRAM（4M*4）33南京大学计算机系 多媒体技术研究所 袁春风举例2：典型的16M位DRAM（4M*4）34南京大学计算机系 多媒体技术研究所 袁春风举例3：256K字节存储器组织256KB=256Kb x 8=512 x 512 x 8=29 x 29 x 8 所以要8个512 x 512的位片式芯片 每个芯片的地址线为9+9=18。存储器容

19、量等于芯片的字数，所以只需在位方向上进行扩充。而字方向不需扩充。 字：512 x 512 =256K (未扩充) 位：1位8位。若需要更大容量的存储器时，则需一个芯片阵列。 即芯片在字和位方向都要扩充。35南京大学计算机系 多媒体技术研究所 袁春风举例3：256K字节存储器组织36南京大学计算机系 多媒体技术研究所 袁春风4.2.3 DRAM的刷新什么样的存储芯片要刷新？ 动态RAM芯片要刷新。为什么要刷新？ 因为DRAM芯片是靠电容上存储电荷来暂存信息的。而电容的绝缘电阻不是无穷大，总会有漏电。因而需要定期进行刷新，即对原存信息的电容补充电荷。电荷泄漏程度取决于制造工艺，目前多数DRAM芯片

20、需要在2ms以内全部刷新一遍，若间隔超过2ms，有可能丢失信息。刷新与再生 刷新是因为记忆电容放电而需要的定时充电操作，因而需要对所有单元定时按行进行； 再生则是因为记忆单元被破坏性读出后的充电操作，因而是对个别单元及所在行的其他单元随机进行的。37南京大学计算机系 多媒体技术研究所 袁春风4.2.3 DRAM的刷新如何进行刷新？所有存储芯片同时进行。对每个DRAM芯片来说，按行进行。 每次刷新一行，每一行在2ms内必须保证被刷新一次。 若某存储器有若干块DRAM芯片，每个芯片的行数为128，则在2ms之中至少应刷新128次，故在15.625 s内至少刷新一行。（ 2ms128= 15.625

21、 s ）刷新地址（行号）由存储器控制逻辑逐行自主循环产生，它不依赖外部的访问，所以刷新对CPU是透明的。常用的刷新方式有四种： 集中、分散、异步、透明38南京大学计算机系 多媒体技术研究所 袁春风4.2.3 DRAM的刷新集中刷新方式在2ms间隔内集中对所有行进行刷新，每行的刷新时间等于一个存取周期。由一个定时器每2ms请求刷新一次，由刷新计数器控制一个计数循环，逐行刷新一遍。优点是主存利用率高，控制简单；缺点是在连续、集中的这段刷新期间，CPU不能使用存储器，因而形成一段死区。39南京大学计算机系 多媒体技术研究所 袁春风4.2.3 DRAM的刷新分散刷新方式将每个存取周期分为两部分，前半期

22、用于正常读写或保持，后半期用于刷新，也就是将各刷新周期分散地安排在读写周期之后。分散刷新方式的优点是时序控制简单，主存没有长的死区；缺点是刷新过于频繁，主存利用率不高，速度大约降低一半。 现在，个人计算机主存的存取周期大约为10ns，若采用分散刷新方式，将增至20ns，在2ms内将刷新105次，大大超过行数。因此，分散刷新方式只能用于低速系统之中。 40南京大学计算机系 多媒体技术研究所 袁春风4.2.3 DRAM的刷新异步刷新方式结合集中和分散两种方式。将2ms的刷新时间间隔平均分配到每行。例如：行地址为7位时，共128行，所以行间刷新时间间隔为：2ms/128=15.625s。这样就能保证

23、:对某行而言，在2ms之内必须刷新一次且仅被刷新一次。透明刷新方式CPU在指令译码时不访问存储器，因此，存储器可利用这段时间插入刷新操作。这样，刷新过程便不占用CPU时间，对CPU而言是透明的。41南京大学计算机系 多媒体技术研究所 袁春风动态刷新方式时间分配关系图42南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器特点：信息只能读不能写。非破坏性读出，无需再生。也以随机存取方式工作。信息用特殊方式写入，一经写入，就可长久保存，不受断电影响。故是非易失性存储器。用途：用来存放一些固定程序。如监控程序、启动程序等。只要一接通电源，这些程序就能自动地运行；可作为控制存储器，存放微程

24、序。还可作为函数发生器和代码转换器。在输入、输出设备中，被用作字符发生器，汉字库等。43南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器分类：腌膜只读存储器（Mask ROM）-MROM可编程只读存储器（Programmable ROM）- PROM可擦除可编程只读存储器（Erasable PROM）-EPROM电可擦除可编程只读存储器（Electrically EPROM）-EEPROM (E2PROM)闪存（flash memory）44南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器掩膜型只读存储器(MROM)类似于字片式RAM，没有写入机构行、列交叉点的

25、MOS管，在最后一道掩膜工艺，根据特定的编码布局来决定是否行、列互连，接上者为0(或1) ，未接上者为1(或0) 。特点： (1)存储内容一次写入，不能修改，因而灵活性差。 (2)存储内容固定，所以可靠性高。 (3) 生产周期长，用户和厂家间依赖性大，只适合定型批量生产。45南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器可编程序只读存储器 (PROM)芯片出厂时内容全部为0(半成品)，用户可用专门的PROM写入器将信息写入，所以称为可编程型。写入不可逆，某位写入1后，就不能再变为0，因此称为一次编程型。有两种工艺：熔丝型和反向二极管型 熔丝型较常用，在行列交点处连接一段熔丝，

26、存入0。若该位需写入1，则让它通过较大电流，使熔丝烧断。 反向二极管型在行列交点处有一对反向的二极管，它们因反向而不导通，称为0。若该位需要写入1，则在相应行列之间加较高电压，将其中反向二极管永久性击穿，留正向可导通的一只二极管。(书中称为P-N结破坏型)46南京大学计算机系 多媒体技术研究所 袁春风可擦除可编程只读存储器(EPROM) 是一种以读为主的可读可写存储器。可用紫外线擦除（每次20分钟），然后重新写入新的信息。EPROM比MROM和PROM灵活与实用。但是EPROM采用MOS工艺，速度比较慢。擦除时，芯片中所有信息都会消失，不灵活。因而又引入了一种电可擦除的EPROM（E2PROM

27、）。4.2.4 只读存储器47南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器电擦除EPROM（E2PROM）也是一种以读为主的可读可写存储器。使用电可擦除技术（加高电压擦除），可擦除个别单元。 它采用金属-氮-氧化硅（MNOS）集成工艺，可实现正常的只读不写，在擦除时只需加高压对指定单元产生电流，形成“电子隧道”，将该单元信息擦除，而其它未通电流的单元内容保持不变。写操作比读操作化更多的时间。集成度比EPROM低，而且更贵。48南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器快闪存储器（闪存、Flash Memory） 八十年代中期，研制出一种快擦写型存储器（

28、Flash Memory）。它具备RAM（随机存储器）与ROM（只读存储器）的所有特点，而且功耗低、集成度高，发展前景非常广阔，这种器件沿用了EPROM的简单结构和浮栅/热电子注入的编程写入方式，又兼备E2PROM的可擦除特点，而且可在计算机内进行擦除和编程写入。因此称为快擦型电可擦除重编程ROM，即Flash EEPROM。功能和价格介于EPROM和EEPROM之间。可按块进行电擦除，而不提供字节级擦除。速度比EPROM快，集成度比EEPROM高。 49南京大学计算机系 多媒体技术研究所 袁春风4.2.4 只读存储器闪存的发展趋势现阶段Flash EEPROM正在取代EPROM和E2PROM

29、。将来可望部分地取代磁盘存储器。 因为这种芯片具有非易失性，当电源断开后仍能长久保存信息，属于非易失性半导体存储器，不需后备电源。从速度上讲，它的读取速度与DRAM芯片相近，是磁盘读取速度的100倍左右；而它的写数据时间（快擦写）则与硬盘相近。因此它适于做成半导体盘，即用半导体存储器当成磁盘使用。由于没有机电运动，可靠性高，也被称为固态盘。这种存储器有可能对传统的磁表面存储器发起挑战，目前的劣势是价格高，价格/位约为硬盘存储器的15倍。在某些应用之中，Flash EEPROM还可能取代DRAM与SRAM。 50南京大学计算机系 多媒体技术研究所 袁春风4.4 高速缓冲存储器（Cache)引入高

30、速缓存的目的解决CPU速度和主存速度匹配问题（另一种方法是采用多模块存储器结构）Cache的工作原理Cache设计的要素Cache大小映射方式替换算法写策略块大小Cache个数奔腾机的Cache组织51南京大学计算机系 多媒体技术研究所 袁春风4.4.1 程序访问的局部化什么是程序访问的局部化性质？ 对大量典型程序的运行情况进行分析的结果表明：在一个较短的时间间隔内，由程序产生的地址往往集中在存储器的一个很小的范围内。因为指令地址是连续的，再加上循环程序段或子程序段要重复执行。因此，对这些地址的访问就自然地具有在时间上集中分布的倾向。这种在某一时间段，对局部范围的存储器地址频繁访问的现象就是所

31、谓的程序访问局部性。基于程序访问的局部性使访存要求快速响应如果在CPU和主存之间设置一个快速小容量的存储器，其中总是存放最活跃（被频繁访问）的程序块和数据，CPU访问这些程序或数据时，就不必访问主存，而直接从这个高速缓存中取得。这样便使得CPU和主存速度匹配起来了。52南京大学计算机系 多媒体技术研究所 袁春风程序局部性原理图为什么引入Cache能达到快速访问的目的？主要是基于程序访问的局部化性质53南京大学计算机系 多媒体技术研究所 袁春风4.4.2 Cache的工作原理在主存-Cache存储体系中，所有的程序和数据都在主存中，Cache中只存放主存一部分程序块和数据的副本。 主存由多达2n

32、个可寻址的字组成，每个字有唯一的n位地址。为了实现映射，我们把这个存储器看成由许多定长的块(block)组成，每块有K个字，即有L=2nK个字块。Cache由M个槽(slot)组成，每个槽有K个字。槽(或称为行line)的数量远远小于主存储器块的数目。在任何时侯，存储器中的几个块驻留在Cache的槽中。如果要读取存储块中的某个字，则整个块被传送到Cache的一个槽中。由于块数多于槽数，所以单个的槽不能久久地被某块专用。因此，每个槽有一个标记(tag)，用来识别当前存储的是哪个块。这个标记通常是主存储器地址的一部分。 54南京大学计算机系 多媒体技术研究所 袁春风4.4.2 Cache的工作原理

33、55南京大学计算机系 多媒体技术研究所 袁春风56南京大学计算机系 多媒体技术研究所 袁春风4.4.2 Cache的工作原理57南京大学计算机系 多媒体技术研究所 袁春风58南京大学计算机系 多媒体技术研究所 袁春风Cache工作原理图59南京大学计算机系 多媒体技术研究所 袁春风4.4.2 Cache的工作原理引入cache后系统的效率估算 假定主存的访问时间为tM，Cache的访问时间为tC ，Cache的命中率为p，则CPU访问该存储系统的平均访问速度为： TA=p tC+(1-p)tM= tM (tM- tC ) p 所以，采用 Cache后系统的访存速度提高倍数为： tM / TA=

34、tM / (p tC+(1-p)tM ) =1 / (1 - (1- tC / tM ) p) 60南京大学计算机系 多媒体技术研究所 袁春风4.4.3 Cache设计要素Cache大小写策略映射功能 写通过（Write Through） 直接 回写（Write Back） 相联 写一次（Write Once） 组相联块大小替换算法Cache数目 最近最少使用 一级或二级 先进先出 统一或分离 最不经常使用 随机61南京大学计算机系 多媒体技术研究所 袁春风4.4.3.1 Cache大小原则上说，Cache的大小选定应使得使用Cache后的位平均价格接近于不使用Cache时主存的平均价格，即C

35、ache应足够小；而使用Cache后的平均访问速度接近于Cache的速度，即Cache应足够大。一些研究表明，Cache大小取1K512K字是最好的。62南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能什么是Cache的映射功能？由于Cache槽比主存块少，因此需要一种算法把主存中的块映射到Cache槽中。这种反映主存块和Cache槽之间对应关系的技术称为映射功能。通常采用3种映射技术 直接、 相联、组相联 为了说明方便起见，假定： 数据在主存和Cache之间按块传送，单位为512字。 Cache大小：213字=8K字=16槽 x 512字/槽 主存大小： 220字=1024

36、K字=2048块 x 512字/块63南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能-直接映射是一种最简单的映射技术。把主存的每一块映射到一个固定的Cache槽中。 也称模映射，映射关系为： Cache槽号=主存块号 mod Cache槽数 举例：4=100 mod 16 (说明主存第100块应映射到Cache的第4槽中。)每个槽有个标志字段，用于指出该槽取自主存的哪个块群。主存共有128个块群。故标志位有7位。每个块群中的16块与Cache的16个槽一一对应。主存地址共20位：7位标志、4位槽号、9位字号。高7位标志表示该地址位于主存哪一个块群。64南京大学计算机系 多媒

37、体技术研究所 袁春风直接映射Cache组织示意图65南京大学计算机系 多媒体技术研究所 袁春风访存过程： CPU给出20位主存地址，根据地址中间4位找到Cache相应的槽，然后取出该槽的标志，与地址中高7位进行比较。 若相等，则说明该主存单元所在的块在Cache中，再根据低9位字地址，从Cache的这一槽中取出字地址指出的那个单元送CPU。 若不相等，则说明要访问的主存单元所在的那一块不在主存。此时将主存中该块调入Cache对应的槽中,并将该单元送CPU。特点：容易实现，但不够灵活，Cache存储空间得不到充分利用。例如，需将主存第0块与第16块同时复制到Cache中时，由于它们都只能复制到C

38、ache第0槽，即使Cache其它槽空闲，也有一个主存块不能写入Cache。这样就会产生频繁的 Cache装入。4.4.3.2 映射功能-直接映射66南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能-相联映射每个主存块可装入到Cache的任何一槽中。也称全映射或全相联映射。每个槽有个标志字段，用于指出该槽取自主存的哪个块。主存共有2048块。故标志位有11位。主存地址共20位：11位标志、9位字号。 高11位表示该地址位于主存哪一块。67南京大学计算机系 多媒体技术研究所 袁春风68南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能-相联映射访存过程： CPU

39、给出一个20位主存地址，根据高11位的内容依次与Cache中各槽的标志位进行比较。 若能找到相等的槽，则说明要访问的单元在该槽中。再根据后9位字号找到相应的字取到CPU中。 若全都不相等，则说明要访问的单元不在Cache中。特点：比直接映射灵活。采用相联存取技术（按内容访问），实现复杂、速度慢。Cache标志位数增加，比较逻辑成本随之增加。 69南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能-组相联映射结合了直接映射和相联映射的特点。将Cache所有槽分组，把主存块映射到Cache固定组的任一槽中。也即：组间模映射、组内全映射。映射关系为： Cache组号=主存块号 mod

40、 Cache组数 举例：假定Cache划分为：8K字=8组x2槽/组x512字/槽 4=100 mod 8 (说明主存第100块应映射到Cache的第4组的任意槽中。)每个槽有个标志字段，用于指出该槽取自主存的哪个组群。主存共有256个组群。故标志位有8位。每个组群中的8块与Cache的8个组一一对应。主存地址共20位：8位标志、3位组号、9位字号。高8位标志表示该地址位于主存的哪个组群。70南京大学计算机系 多媒体技术研究所 袁春风组相联映射的Cache组织图71南京大学计算机系 多媒体技术研究所 袁春风4.4.3.2 映射功能-组相联映射访存过程： CPU给出一个20位主存地址，根据中间3

41、位的内容找到对应的Cache组，再将前8位依次与该组中各槽的标志位进行比较。 若能找到相等的槽，则说明要访问的单元在该槽中。再根据后9位字号找到相应的字取到CPU中。 若全都不相等，则说明要访问的单元不在该组中。特点：结合了直接映射和相联映射的优点。 当Cache的组数为1时，则变为相联映射；当每组只有一个槽时，则变为直接映射。每组两个槽（称为2路组相联）最常用。一般每组4个槽 以上的情况很少用。72南京大学计算机系 多媒体技术研究所 袁春风4.4.3.3 替换算法替换问题的提出： 当对应的Cache槽已被占满而需要调入新的主存块时，必须考虑从cache槽中调出一个主存块。例如：组相联映射时，

42、假定第0组的两个槽分别被主存第0和8块占满，此时若需调入主存第16块，根据映射关系，它只能放到Cache第一组，因此，第一组中必须调出一块，那么调出哪一块呢？这就是淘汰策略问题，也称替换算法。常用替换算法有：先进先出FIFO （first-in-first-out）最近最少用LRU （ least-recently used）最不经常用LFU （ least-frequently used）随机替换算法（Random）等等73南京大学计算机系 多媒体技术研究所 袁春风4.4.3.3 替换算法-先进先出总是把最先进入的那一块淘汰掉。例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组

43、中，对于同一地址流，考察3槽/组、 4槽/组的情况。由此可见，FIFO不是一种堆栈算法，即命中率并不随组的增大而提高。1*1*4231*442*13*4* 51*1*2355*2*34 1 2 3 4 1 2 5 1 2 3 4 5 23122 51*2 55*34 3槽/组1*1*4231*44243*1* 512*3*15*421*223233 512 5452* 1*21*4*3334槽/组74南京大学计算机系 多媒体技术研究所 袁春风4.4.3.3 替换算法-最近最少用总是把最近最少用的那一块淘汰掉。例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组中，对于同一地址流，考

44、察3槽/组、 4槽/组、 5槽/组的情况。3 1 2211 3143332 522423413222141 515 2543 4414512 1 2 3 4 1 2 5 1 2 3 4 5 3134513槽/组4槽/组5槽/组75南京大学计算机系 多媒体技术研究所 袁春风4.4.3.3 替换算法-最近最少用是一种堆栈算法，它的命中率随组的增大而提高。当分块局部化范围超过了Cache存储容量时，命中率变得很低。极端情况下，假设地址流是1,2,3,4,1 2,3,4,1,，而Cache每组只有3槽，那么，不管是FIFO，还是LRU算法，其命中率都为0。这种现象称为颠簸(Thrashing)。该算法

45、具体实现时，并不是通过移动块来实现的，而是通过给每槽设定一个计数器，根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位。 具体实现76南京大学计算机系 多媒体技术研究所 袁春风4.4.3.3 替换算法-最近最少用计数器变化规则：每组4槽时，计数器有2位。计数值越小则说明越被常用。命中时，被访问的那个槽的计数器置0，比其低的计数器加1，其余不变。未命中且该组未满时，新槽计数器置为0，其余全加1。未命中且该组已满时，计数值为3的那一槽中的主存块被淘汰，新槽计数器置为0，其余加1。 1 2 3 4 1 2 5 1 2 3 4 5 543203211243320112532130125410

46、23125402131254210312341032123403211234321012321012101077南京大学计算机系 多媒体技术研究所 袁春风最不经常用（LFU）算法： 替换掉Cache中引用次数最少的块。LFU也用与每个槽相关的计数器来实现。随机算法： 随机地从候选的槽中选取一个淘汰，与使用情况无关。模拟试验表明，随机替换算法在性能上只稍逊于基于使用情况的算法。4.4.3.3 替换算法-其他算法78南京大学计算机系 多媒体技术研究所 袁春风举例假定计算机系统有一个容量为32Kx16位的主存，且有一个4K字的4路组相联Cache，主存和Cache之间的数据交换块的大小为64字。假定

47、Cache开始为空，处理器顺序地从存储单元0、1、4351中取数，然后重复9次。设Cache比主存快10倍。采用LRU算法。试分析cache的结构和主存地址的划分。说明采用Cache后速度提高了多少？采用MRU算法后呢？答：假定主存按字编址。每字16位。 主存：32K字=512块x64字/块 Cache：4K字=16组x4槽/组x64字/槽 主存地址划分为：字号标志位组号6454352/64=68，所以处理器的访问过程是对前68块连续访问10次。79南京大学计算机系 多媒体技术研究所 袁春风举例0组1组2组3组4组15组0 槽1 槽2 槽3 槽0/64/481/65/492/66/503/67

48、/51415组16/0/6417/1/6518/2/6619/3/67203132/1633/1734/1835/19364748/3249/3350/3451/355263LRU算法：第一次循环,对于每一块只有第一字未命中,其余都命中;以后9次循环,有20块的第一字未命中,其余都命中.所以,命中率p为（43520-68-9x20）/43520=99.43%速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)=9.5倍80南京大学计算机系 多媒体技术研究所 袁春风举例0组1组2组3组4组15组0 槽1 槽2 槽3 槽0/16/32/481/17/33/492/

49、18/34/503/19/35/52415组16/32/48/6417/33/49/6518/34/50/6619/35/51/67203132/48/64/033/49/65/134/50/66/235/51/67/3364748/64/0/1649/65/1/1750/66/2/1851/67/3/195263MRU算法：第一次68字未命中；第2,3,4,6,7,8,10次各有4字未命中；第5,9次各有8字未命中；其余都命中.所以,命中率p为（43520-68-7x4-2 x8）/43520=99.74%速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)

50、=9.77倍81南京大学计算机系 多媒体技术研究所 袁春风举例原版书的解法(对于LRU算法)假定从Cache读64字的时间为T,则从主存读64字的时间为10T。如果某块不在Cache中，那么该块必须先从主存读入Cache，然后再从Cache读入。故时间为11T。 不用Cache时,访问时间为： 10 x68x10T=6800T 有Cache时,访问时间为： 1x(68x11T)+9x(48x1T+20 x11T) =3160T故：速度提高6800T/ 3160T=2.15倍。82南京大学计算机系 多媒体技术研究所 袁春风举例对两种解法的分析结论：我们给出解法更精确。为什么？考察访存过程：不使用

51、Cache时，64个字的访问时间为：64x10T/64=10T。使用Cache时, (1)若第一字命中,则64字访问时间为：64xT/64=1T。 (2)若第一字未命中,则64字访问时间约为：10T/64+1T=74T/64所以按原版书的解法，应该为：有Cache时,访问时间约为：(68+9x20)74T/64+9x48xT=719T故：速度提高6800T/ 719T=9.5倍。83南京大学计算机系 多媒体技术研究所 袁春风4.4.3.4 写策略（Cache一致性问题）一致性问题的提出：因为Cache中的内容是主存块的副本，当对Cache中的内容进行更新时，就存在Cache和主存如何保持一致性

52、的问题。以下情况也会出现“Cache一致性问题”当多个设备都允许访问主存时 例如：I/O设备可直接读写内存时，如果Cache中的内容被修改，则I/O设备读出的对应主存单元的内容无效；若I/O设备修改了主存单元的内容，则对应Cache槽中的内容无效。当多个CPU都带有各自的Cache而共享主存时 某个CPU修改了自身Cache中的内容，则对应的主存单元和其他CPU中对应的Cache槽的内容都变为无效。84南京大学计算机系 多媒体技术研究所 袁春风4.4.3.4 写策略（Cache一致性问题）写策略方式：Write back(一次性写、写回法) 先暂时只写入Cache有关单元，并用标志予以注明，直到该块内容需从Cache中替换出来时，才一次写入主存。这种方式不在快速写入Cache中插入慢速的写主存操作，可以保持程序运行的快速性；但在写回主存前，主存中内容失效，主存与Cache 内容不一致，有可能导致工作失误。Write through(通过式写、写直达法) 即每次写入Cache时也同时写入主存，主存与Cache始终保持一致性。这种方式比较简单，能保持主存与Cache副本的一致性，但要插入慢速访