计算机组成原理 [袁春风]chap4.ppt

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

2、式：对存储体中各存储单元进行编号的方式。 按字节编址 按字编址 按半字编址 存储器地址寄存器（MAR）：用于存放主存单元地址的寄存器。 存储器数据寄存器（MDR）：用于存放主存单元中的数据的寄存器。,南京大学计算机系 多媒体技术研究所 袁春风,5,4.1 .1 基本术语,存储字、编址单位和传输单位 机器字长：运算器中参加运算的寄存器的位数。 存储字：存储器按机器字长组织的一个“自然”单位。它的长度一般应等于一个数或指令的位数。但大多数机器并不是这样。存储芯片中的一个读写单位。 编址单位：一个存储单元的位数。有的按字编址，有的按字节编址，等等。 传输单位：对主存而言，指一次从存储器读出或写入的数

3、的位数，它可以不等于存储字的长度，也可不等于编址单位。对外存而言，数据通常按块传输。 （例如：386/486等，其编址单位为字节、字长为32位，单字位数为16位，但传输单位可以是8/16/24/32位。）,南京大学计算机系 多媒体技术研究所 袁春风,6,4.1.2 主要性能指标,存储容量 ：存储器能够容纳的二进制信息量。,存储器的存储容量越大，能存储的信息就越多。存储容量常用存储单元数与每个单元的位数的乘积表示，或用字节数表示。如PDP-11/23计算机主存容量为64K字，字长为16位，则可表示为64K*16位，或128K字节，记为128KB（Byte）。现代计算机的主存容量要大得多，一般以字

4、节为单位表示。如以Pentium为CPU的微型计算机，主存的配置一般为32256MB。,通常用2的整数幂来计算存储容量，计量单位有K，M，G，T等。这些计算单位之间的换算如下： 1K=210=1024 1G=230=1024M 1M=220=1024K 1T=240=1024G,南京大学计算机系 多媒体技术研究所 袁春风,7,4.1.2 主要性能指标,存取速度 存取时间TA；存储器接到读/写命令后到被读数据稳定在MDR的输出端或数据被写入某单元为止的时间间隔。也称读写时间。 存储周期TMC：连读两次访问存储器所需的最小时间间隔，它应等于存取时间加上下一存取开始前所要求的附加时间（ 因为存储器由

5、于读出放大器、驱动电路等都有一段稳定恢复时间，所以读出后不能立即进行下一次访问。 ）。因此，TMC比TA大。 最大数据传输率R：连续访问时每秒钟从存储器入出的信息量。单位： 位/秒(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),南京大学计算机系 多媒体技术研究所 袁春风,8,

6、4.1.2 主要性能指标,价格（每位成本） 存储器的价格常用每位(bit)的价格来衡量。 它不仅包含了存储元件本身的价格，也包括为该存储器操作服务的外围电路的价格。 一般来说，用来组成主存的存储器价格较高，如半导体存储器（双极型和MOS型存储器）。辅助存储器（如磁盘、磁带、光盘）的价格则低得多。 速度很高的存储器往往价格较贵，容量也不可能很大。因此容量、速度、价格三个指标是互相制约的。,南京大学计算机系 多媒体技术研究所 袁春风,9,4.1.2 主要性能指标,可靠性,存储器可靠性用平均故障时间间隔MTBF（Mean Time Between Failures）来衡量。 MTBF可以理解为两次故

7、障之间的平均时间间隔。它的值越大表示存储器的可靠型越高，可连续运行时间就越长。与MTBF意义相同的术语是平均无故障时间或平均无差错时间。 MTBF的计算公式为：,t存储器系统运行的一段时间,N(t) 系统在0, t时间段内的故障次数,南京大学计算机系 多媒体技术研究所 袁春风,10,4.1.2 主要性能指标,其他性能指标 集成度：每个芯片所含的二进制信息量。 功耗：发热程度和耗电量。 集成度和功耗是矛盾的两个方面。我们希望集成度大而功耗小，但一般集成度越大，功耗也越大。,南京大学计算机系 多媒体技术研究所 袁春风,11,4.1.3 存储器分类,（1）按工作性质/存取方式分类 随机存取存储器(R

8、AM) ：每个单元的读写时间一样，且与各单元所在位置无关。如：内存。 顺序存取存储器(SAM)：数据按顺序从存储载体的始端读出或写入，因而存取时间的长短与信息所在位置有关。例如：磁带。 直接存取存储器：利用一个共享读写机制，直接定位到要读写的数据块，在读写某个数据块时按顺序进行。例如：磁盘。 相联存取存储器：按内容检索到存储位置进行读写。例如：快表。,依据不同的特性有多种分类方法,南京大学计算机系 多媒体技术研究所 袁春风,12,4.1.3 存储器分类,（2）按存储介质分类,半导体存储器 双极型，静态MOS型，动态MOS型 磁表面存储器 磁盘，磁带，磁鼓 光存储器 CD，CD-ROM，MO，D

9、VD 磁芯存储器 电荷耦合器件(CCD) 磁泡存储器,南京大学计算机系 多媒体技术研究所 袁春风,13,4.1.3 存储器分类,（3）按信息的可更改性分类,读写存储器（Read/Write Memory)：可读可写。 只读存储器（Read Only Memory)：只能读不能写。,（4）按断电后信息的可保存性分类,非易失性存储器 ：信息可一直保留，不需电源维持。如 ： ROM，磁表面存储器。 易失性存储器：电源关闭时信息自动丢失。如：RAM 。,南京大学计算机系 多媒体技术研究所 袁春风,14,4.1.3 存储器分类,（5）按功能/容量/速度/所在位置分类 寄存器：封装在CPU内，用于存放当前

10、正在执行的指令和使用的数据。 Cache：位于CPU内部或附近，用来存放当前要执行的局部程序段和数据。速度可与CPU匹配，容量小。 内存储器（主存储器）：位于CPU之外，用来存放已被启动的程序及所用的数据。容量较大，速度较快。 外存储器（辅助存储器）：位于主机之外，用来存放暂不运行的程序和数据。容量大而速度慢。 从使用和维护角度来说，计算机最好使用一个容量极大而速度极快的存储器。但往往做不到。因而采用一种分级体系结构，使各种不同功能/容量/速度/价格的存储器相互协调以构成最佳性能的存储系统。,南京大学计算机系 多媒体技术研究所 袁春风,15,4.1.4 存储器分级体系结构,五层金字塔形分层系统

11、从上到下的特点： 1，每位价格降低 2，容量增大 3，存取时间增大 4，访问频度降低,Traditional Memory Hierarchy,传统结构,南京大学计算机系 多媒体技术研究所 袁春风,16,4.1.4 存储器分级体系结构,Contemporary Memory Hierarchy,当代结构,开辟一部分内存区，用作“Disk Cache”，用于存放将被送到磁盘上的数据。 引入“Disk Cache”的好处： (1)写盘时按“簇”进行，以避免频繁地小块数据写盘。 (2)有些中间结果数据在写回盘之前可被快速地再次使用。,南京大学计算机系 多媒体技术研究所 袁春风,17,4.2 半导体随

12、机存储器,记忆单元的基本原理 半导体RAM的组织 再生与刷新 只读存储器 存储器的数据检/纠错,南京大学计算机系 多媒体技术研究所 袁春风,18,4.2.1 记忆单元的基本原理,作为记忆材料的条件： 有两种稳态，且是可逆的。 在外部信号激励下，两种稳态能进行无限次相互转换。 在外部信号激励下，能读出两种稳定状态。 长期存储可靠 可用作记忆单元(位元)的材料： 磁性材料（磁芯、磁泡、CCD等，用的很少） 半导体材料（TTL,ECL,MOS管，大量使用）,目前的主流技术,南京大学计算机系 多媒体技术研究所 袁春风,19,4.2.1 记忆单元的基本原理,（1）速度快，但集成度低、功耗大 电路速度主要

13、取决于射极电流“拨动”的速度，而电流变化的快慢，与管子的频率特性有关，晶体管的频率特性可以做得很高，所以双极型记忆单元速度是很快的。 （2）非破坏性读出，也无需刷新。 信息读出后，原来的信息状态不变，而且稳定。 主要用作高速小容量的Cache。 对于大容量的主存储器一般用功耗小、集成度高，但速度较慢的MOS管电路。,双极型记忆单元电路的特点,南京大学计算机系 多媒体技术研究所 袁春风,20,4.2.1 记忆单元的基本原理,静态六管MOS有以下三个特点： 非破坏性读出，不需重写或刷新； 结构简单，可靠性高，具有一定速度； 电路元件较多，占硅片面积大， 故功耗大，集成度不高。,南京大学计算机系 多

14、媒体技术研究所 袁春风,21,动态单管MOS记忆单元电路图,南京大学计算机系 多媒体技术研究所 袁春风,22,动态单管记忆单元读出电压,MOS电路中，数据线本身存在分布电容C0 ，故在读出时，读出线上的电荷在串接的两电容C0和CS中间分配，使得读出电压下降，如果原存储在CS上的电压为VS则读出电压VR为：,一般C0CS般,故读出电压信号很微弱，通常需用放大电路。,南京大学计算机系 多媒体技术研究所 袁春风,23,4.2.2 半导体RAM的组织,存储器芯片：存储体+外围电路(地址译码和读写控制),记忆单元的组织：,存储体： 由记忆单元(位元)构成的存储阵列,记忆单元,存储器芯片,内存条（存储器模

15、块）,南京大学计算机系 多媒体技术研究所 袁春风,24,4.2.2 半导体RAM的组织,存储器芯片的种类（由存储体结构来分） 字片式（单方向译码，一维地址驱动） 阵列中的位元排列与存储器中字的逻辑排列相同。 存储体的每一行构成多位的一个存储字，一起被读写。 每列由相同位构成，共用一个读写电路，有多个读写电路。 在位方向上便于扩充。 位片式（双方向译码，二位地址驱动） 芯片阵列由行和列排列而成，每次只能读写行、列交叉处的一位数据。 每个芯片只有一位读写电路。 在字和位方向上都能扩充，但需有片选信号。,南京大学计算机系 多媒体技术研究所 袁春风,25,字片式存储体阵列组织,X 向译码器,一维地址译

16、码系统,地址驱动线,南京大学计算机系 多媒体技术研究所 袁春风,26,位片式存储体阵列组织,南京大学计算机系 多媒体技术研究所 袁春风,27,位片式芯片框图,南京大学计算机系 多媒体技术研究所 袁春风,28,字扩展为芯片字数的4倍,位扩展为芯片位数的16倍,南京大学计算机系 多媒体技术研究所 袁春风,29,半导体随机存储器基本结构图,主存储器,南京大学计算机系 多媒体技术研究所 袁春风,30,4.2.2 半导体RAM的组织,地址译码（驱动）器 用于将总线上传输过来的地址信息进行译码，在所有字线中选择一根字线，使其驱动为高电平。 地址线有n条时，译码器输出2n条字线，能驱动2n个存储单元中任一个

17、。,问题：对于一个具有2n个单元的位片式芯片（即：采用二维地址译码的存储器芯片），其地址驱动（选择）线的条数为多少？ 2n/2 +2n/2,南京大学计算机系 多媒体技术研究所 袁春风,31,地址译码器电路示意图,南京大学计算机系 多媒体技术研究所 袁春风,32,4.2.2 半导体RAM的组织,读写控制 存储器的基本操作是读操作和写操作。读写控制电路用于接收总线送来的读/写控制信号，控制数据写入记忆单元，或将数据从记忆单元读出。 下图是一个二进制位的读写与I/O电路示意图。读写控制电路由门电路1、2组成，“读写命令R/W”接受总线传送过来的读/写命令。当R/W=1时是读操作命令，R/W=0时是写

18、操作。,南京大学计算机系 多媒体技术研究所 袁春风,33,16M位=4Mb x 4=2048 x 2048 x 4=211x211x4 (1) 地址线：11根 分时复用,由RAS和CAS提供控制时序。 采用分时复用技术使得每出现新一代存储器芯片，容量至少 提高四倍。（因为每增加一根地址线，行和列各扩大2倍， 总的扩大4倍） (2) 这个DRAM芯片的存储字是4位，所以还需将多个这样的芯 片连接到DRAM控制器，才能在总线上读写相应的位数。 (3) 所有DRAM芯片都同时刷新，由刷新计数器自动计数、按行 刷新（只产生行地址），对CPU透明。,举例2：典型的16M位DRAM（4M*4）,南京大学计

19、算机系 多媒体技术研究所 袁春风,34,举例2：典型的16M位DRAM（4M*4）,南京大学计算机系 多媒体技术研究所 袁春风,35,举例3：256K字节存储器组织,256KB=256Kb x 8=512 x 512 x 8=29 x 29 x 8 所以要8个512 x 512的位片式芯片 每个芯片的地址线为9+9=18。 存储器容量等于芯片的字数，所以只需在位方向上进行扩充。而字方向不需扩充。 字：512 x 512 =256K (未扩充) 位：1位8位。 若需要更大容量的存储器时，则需一个芯片阵列。 即芯片在字和位方向都要扩充。,南京大学计算机系 多媒体技术研究所 袁春风,36,举例3：2

20、56K字节存储器组织,南京大学计算机系 多媒体技术研究所 袁春风,37,4.2.3 DRAM的刷新,什么样的存储芯片要刷新？ 动态RAM芯片要刷新。 为什么要刷新？ 因为DRAM芯片是靠电容上存储电荷来暂存信息的。而电容的绝缘电阻不是无穷大，总会有漏电。因而需要定期进行刷新，即对原存信息的电容补充电荷。电荷泄漏程度取决于制造工艺，目前多数DRAM芯片需要在2ms以内全部刷新一遍，若间隔超过2ms，有可能丢失信息。 刷新与再生 刷新是因为记忆电容放电而需要的定时充电操作，因而需要对所有单元定时按行进行； 再生则是因为记忆单元被破坏性读出后的充电操作，因而是对个别单元及所在行的其他单元随机进行的。

21、,南京大学计算机系 多媒体技术研究所 袁春风,38,4.2.3 DRAM的刷新,如何进行刷新？ 所有存储芯片同时进行。 对每个DRAM芯片来说，按行进行。 每次刷新一行，每一行在2ms内必须保证被刷新一次。 若某存储器有若干块DRAM芯片，每个芯片的行数为128，则在2ms之中至少应刷新128次，故在15.625 s内至少刷新一行。（ 2ms128= 15.625 s ） 刷新地址（行号）由存储器控制逻辑逐行自主循环产生，它不依赖外部的访问，所以刷新对CPU是透明的。 常用的刷新方式有四种： 集中、分散、异步、透明,南京大学计算机系 多媒体技术研究所 袁春风,39,4.2.3 DRAM的刷新,

22、集中刷新方式 在2ms间隔内集中对所有行进行刷新，每行的刷新时间等于一个存取周期。 由一个定时器每2ms请求刷新一次，由刷新计数器控制一个计数循环，逐行刷新一遍。 优点是主存利用率高，控制简单； 缺点是在连续、集中的这段刷新期间，CPU不能使用存储器，因而形成一段死区。,南京大学计算机系 多媒体技术研究所 袁春风,40,4.2.3 DRAM的刷新,分散刷新方式 将每个存取周期分为两部分，前半期用于正常读写或保持，后半期用于刷新，也就是将各刷新周期分散地安排在读写周期之后。 分散刷新方式的优点是时序控制简单，主存没有长的死区； 缺点是刷新过于频繁，主存利用率不高，速度大约降低一半。 现在，个人计

23、算机主存的存取周期大约为10ns，若采用分散刷新方式，将增至20ns，在2ms内将刷新105次，大大超过行数。因此，分散刷新方式只能用于低速系统之中。,南京大学计算机系 多媒体技术研究所 袁春风,41,4.2.3 DRAM的刷新,异步刷新方式 结合集中和分散两种方式。将2ms的刷新时间间隔平均分配到每行。 例如：行地址为7位时，共128行，所以行间刷新时间间隔为：2ms/128=15.625s。这样就能保证:对某行而言，在2ms之内必须刷新一次且仅被刷新一次。 透明刷新方式 CPU在指令译码时不访问存储器，因此，存储器可利用这段时间插入刷新操作。这样，刷新过程便不占用CPU时间，对CPU而言是

24、透明的。,南京大学计算机系 多媒体技术研究所 袁春风,42,动态刷新方式时间分配关系图,南京大学计算机系 多媒体技术研究所 袁春风,43,4.2.4 只读存储器,特点： 信息只能读不能写。 非破坏性读出，无需再生。 也以随机存取方式工作。 信息用特殊方式写入，一经写入，就可长久保存，不受断电影响。故是非易失性存储器。 用途： 用来存放一些固定程序。如监控程序、启动程序等。只要一接通电源，这些程序就能自动地运行； 可作为控制存储器，存放微程序。 还可作为函数发生器和代码转换器。 在输入、输出设备中，被用作字符发生器，汉字库等。,南京大学计算机系 多媒体技术研究所 袁春风,44,4.2.4 只读存

25、储器,分类： 腌膜只读存储器（Mask ROM）-MROM 可编程只读存储器（Programmable ROM）- PROM 可擦除可编程只读存储器（Erasable PROM）-EPROM 电可擦除可编程只读存储器（Electrically EPROM）-EEPROM (E2PROM) 闪存（flash memory）,南京大学计算机系 多媒体技术研究所 袁春风,45,4.2.4 只读存储器,掩膜型只读存储器(MROM) 类似于字片式RAM，没有写入机构 行、列交叉点的MOS管，在最后一道掩膜工艺，根据特定的编码布局来决定是否行、列互连，接上者为0(或1) ，未接上者为1(或0) 。 特点：

26、 (1)存储内容一次写入，不能修改，因而灵活性差。 (2)存储内容固定，所以可靠性高。 (3) 生产周期长，用户和厂家间依赖性大，只适合定型批量生产。,南京大学计算机系 多媒体技术研究所 袁春风,46,4.2.4 只读存储器,可编程序只读存储器 (PROM) 芯片出厂时内容全部为0(半成品)，用户可用专门的PROM写入器将信息写入，所以称为可编程型。 写入不可逆，某位写入1后，就不能再变为0，因此称为一次编程型。 有两种工艺：熔丝型和反向二极管型 熔丝型较常用，在行列交点处连接一段熔丝，存入0。若该位需写入1，则让它通过较大电流，使熔丝烧断。 反向二极管型在行列交点处有一对反向的二极管，它们因

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

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

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

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

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

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

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

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

35、存速度提高倍数为： tM / TA=tM / (p tC+(1-p)tM ) =1 / (1 - (1- tC / tM ) p),南京大学计算机系 多媒体技术研究所 袁春风,61,4.4.3 Cache设计要素,南京大学计算机系 多媒体技术研究所 袁春风,62,4.4.3.1 Cache大小,原则上说，Cache的大小选定应使得使用Cache后的位平均价格接近于不使用Cache时主存的平均价格，即Cache应足够小；而使用Cache后的平均访问速度接近于Cache的速度，即Cache应足够大。 一些研究表明，Cache大小取1K512K字是最好的。,南京大学计算机系 多媒体技术研究所 袁春风

36、,63,4.4.3.2 映射功能,什么是Cache的映射功能？ 由于Cache槽比主存块少，因此需要一种算法把主存中的块映射到Cache槽中。这种反映主存块和Cache槽之间对应关系的技术称为映射功能。 通常采用3种映射技术 直接、 相联、组相联 为了说明方便起见，假定： 数据在主存和Cache之间按块传送，单位为512字。 Cache大小：213字=8K字=16槽 x 512字/槽 主存大小： 220字=1024K字=2048块 x 512字/块,南京大学计算机系 多媒体技术研究所 袁春风,64,4.4.3.2 映射功能-直接映射,是一种最简单的映射技术。 把主存的每一块映射到一个固定的Ca

37、che槽中。 也称模映射，映射关系为： Cache槽号=主存块号 mod Cache槽数 举例：4=100 mod 16 (说明主存第100块应映射到Cache的第4槽中。) 每个槽有个标志字段，用于指出该槽取自主存的哪个块群。主存共有128个块群。故标志位有7位。 每个块群中的16块与Cache的16个槽一一对应。 主存地址共20位：7位标志、4位槽号、9位字号。高7位标志表示该地址位于主存哪一个块群。,南京大学计算机系 多媒体技术研究所 袁春风,65,直接映射Cache组织示意图,南京大学计算机系 多媒体技术研究所 袁春风,66,访存过程： CPU给出20位主存地址，根据地址中间4位找到C

38、ache相应的槽，然后取出该槽的标志，与地址中高7位进行比较。 若相等，则说明该主存单元所在的块在Cache中，再根据低9位字地址，从Cache的这一槽中取出字地址指出的那个单元送CPU。 若不相等，则说明要访问的主存单元所在的那一块不在主存。此时将主存中该块调入Cache对应的槽中,并将该单元送CPU。 特点： 容易实现，但不够灵活，Cache存储空间得不到充分利用。例如，需将主存第0块与第16块同时复制到Cache中时，由于它们都只能复制到Cache第0槽，即使Cache其它槽空闲，也有一个主存块不能写入Cache。这样就会产生频繁的 Cache装入。,4.4.3.2 映射功能-直接映射,

39、南京大学计算机系 多媒体技术研究所 袁春风,67,4.4.3.2 映射功能-相联映射,每个主存块可装入到Cache的任何一槽中。也称全映射或全相联映射。 每个槽有个标志字段，用于指出该槽取自主存的哪个块。主存共有2048块。故标志位有11位。 主存地址共20位：11位标志、9位字号。 高11位表示该地址位于主存哪一块。,南京大学计算机系 多媒体技术研究所 袁春风,68,南京大学计算机系 多媒体技术研究所 袁春风,69,4.4.3.2 映射功能-相联映射,访存过程： CPU给出一个20位主存地址，根据高11位的内容依次与Cache中各槽的标志位进行比较。 若能找到相等的槽，则说明要访问的单元在该

40、槽中。再根据后9位字号找到相应的字取到CPU中。 若全都不相等，则说明要访问的单元不在Cache中。 特点： 比直接映射灵活。 采用相联存取技术（按内容访问），实现复杂、速度慢。 Cache标志位数增加，比较逻辑成本随之增加。,南京大学计算机系 多媒体技术研究所 袁春风,70,4.4.3.2 映射功能-组相联映射,结合了直接映射和相联映射的特点。 将Cache所有槽分组，把主存块映射到Cache固定组的任一槽中。也即：组间模映射、组内全映射。映射关系为： Cache组号=主存块号 mod Cache组数 举例：假定Cache划分为：8K字=8组x2槽/组x512字/槽 4=100 mod 8

41、(说明主存第100块应映射到Cache的第4组的任意槽中。) 每个槽有个标志字段，用于指出该槽取自主存的哪个组群。主存共有256个组群。故标志位有8位。 每个组群中的8块与Cache的8个组一一对应。 主存地址共20位：8位标志、3位组号、9位字号。高8位标志表示该地址位于主存的哪个组群。,南京大学计算机系 多媒体技术研究所 袁春风,71,组相联映射的Cache组织图,南京大学计算机系 多媒体技术研究所 袁春风,72,4.4.3.2 映射功能-组相联映射,访存过程： CPU给出一个20位主存地址，根据中间3位的内容找到对应的Cache组，再将前8位依次与该组中各槽的标志位进行比较。 若能找到相

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

43、映射关系，它只能放到Cache第一组，因此，第一组中必须调出一块，那么调出哪一块呢？这就是淘汰策略问题，也称替换算法。 常用替换算法有： 先进先出FIFO （first-in-first-out） 最近最少用LRU （ least-recently used） 最不经常用LFU （ least-frequently used） 随机替换算法（Random） 等等,南京大学计算机系 多媒体技术研究所 袁春风,74,4.4.3.3 替换算法-先进先出,总是把最先进入的那一块淘汰掉。 例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组中，对于同一地址流，考察3槽/组、 4槽/组的情况。

44、,由此可见，FIFO不是一种堆栈算法，即命中率并不随组的增大而提高。,1*,1*,4,2,3,1*,4,4,2*,1,3*,4*,5,1*,1*,2,3,5,5*,2*,3,4,1 2 3 4 1 2 5 1 2 3 4 5,2,3,1,2,2,5,1*,2,5,5*,3,4, ,3槽/组,1*,1*,4,2,3,1*,4,4,2,4,3*,1*,5,1,2*,3*,1,5*,4,2,1*,2,2,3,2,3,3,5,1,2,5,4,5,2*, ,1*,2,1*,4*,3,3,3,4槽/组,南京大学计算机系 多媒体技术研究所 袁春风,75,4.4.3.3 替换算法-最近最少用,总是把最近最少用

45、的那一块淘汰掉。 例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组中，对于同一地址流，考察3槽/组、 4槽/组、 5槽/组的情况。,3,1,2,2,1,1,3,1,4,3,3,3,2,5,2,2,4,2,3,4,1,3,2,2,2,1,4,1,5,1,5,2,5,4,3, ,4,4,1,4,5,1,2,1 2 3 4 1 2 5 1 2 3 4 5,3,1,3,4,5,1,3槽/组 4槽/组 5槽/组,南京大学计算机系 多媒体技术研究所 袁春风,76,4.4.3.3 替换算法-最近最少用,是一种堆栈算法，它的命中率随组的增大而提高。 当分块局部化范围超过了Cache存储容量时，

46、命中率变得很低。极端情况下，假设地址流是1,2,3,4,1 2,3,4,1,，而Cache每组只有3槽，那么，不管是FIFO，还是LRU算法，其命中率都为0。这种现象称为颠簸(Thrashing)。 该算法具体实现时，并不是通过移动块来实现的，而是通过给每槽设定一个计数器，根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位。 具体实现,南京大学计算机系 多媒体技术研究所 袁春风,77,4.4.3.3 替换算法-最近最少用,计数器变化规则： 每组4槽时，计数器有2位。计数值越小则说明越被常用。 命中时，被访问的那个槽的计数器置0，比其低的计数器加1，其余不变。 未命中且该组未满时，新槽

47、计数器置为0，其余全加1。 未命中且该组已满时，计数值为3的那一槽中的主存块被淘汰，新槽计数器置为0，其余加1。,1 2 3 4 1 2 5 1 2 3 4 5,5,4,3,2,0,3,2,1,1,2,4,3,3,2,0,1,1,2,5,3,2,1,3,0,1,2,5,4,1,0,2,3,1,2,5,4,0,2,1,3,1,2,5,4,2,1,0,3,1,2,3,4,1,0,3,2,1,2,3,4,0,3,2,1,1,2,3,4,3,2,1,0,1,2,3,2,1,0,1,2,1,0,1,0,南京大学计算机系 多媒体技术研究所 袁春风,78,最不经常用（LFU）算法： 替换掉Cache中引用次

48、数最少的块。LFU也用与每个槽相关的计数器来实现。 随机算法： 随机地从候选的槽中选取一个淘汰，与使用情况无关。模拟试验表明，随机替换算法在性能上只稍逊于基于使用情况的算法。,4.4.3.3 替换算法-其他算法,南京大学计算机系 多媒体技术研究所 袁春风,79,举例,假定计算机系统有一个容量为32Kx16位的主存，且有一个4K字的4路组相联Cache，主存和Cache之间的数据交换块的大小为64字。假定Cache开始为空，处理器顺序地从存储单元0、1、4351中取数，然后重复9次。设Cache比主存快10倍。采用LRU算法。试分析cache的结构和主存地址的划分。说明采用Cache后速度提高了

49、多少？采用MRU算法后呢？ 答：假定主存按字编址。每字16位。 主存：32K字=512块x64字/块 Cache：4K字=16组x4槽/组x64字/槽 主存地址划分为：,字号,4352/64=68，所以处理器的访问过程是对前68块连续访问10次。,南京大学计算机系 多媒体技术研究所 袁春风,80,举例,0组 1组 2组 3组 4组 15组,0 槽,1 槽,2 槽,3 槽,0/64/48 1/65/49 2/66/50 3/67/51 4 15组,16/0/64 17/1/65 18/2/66 19/3/67 20 31,32/16 33/17 34/18 35/19 36 47,48/32 4

50、9/33 50/34 51/35 52 63,LRU算法：第一次循环,对于每一块只有第一字未命中,其余都命中; 以后9次循环,有20块的第一字未命中,其余都命中. 所以,命中率p为（43520-68-9x20）/43520=99.43% 速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)=9.5倍,南京大学计算机系 多媒体技术研究所 袁春风,81,举例,0组 1组 2组 3组 4组 15组,0 槽,1 槽,2 槽,3 槽,0/16/32/48 1/17/33/49 2/18/34/50 3/19/35/52 4 15组,16/32/48/64 17/33/4

51、9/65 18/34/50/66 19/35/51/67 20 31,32/48/64/0 33/49/65/1 34/50/66/2 35/51/67/3 36 47,48/64/0/16 49/65/1/17 50/66/2/18 51/67/3/19 52 63,MRU算法：第一次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)=9.77倍,南京大学计算机系 多媒体技术

52、研究所 袁春风,82,举例,原版书的解法(对于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倍。,南京大学计算机系 多媒体技术研究所 袁春风,83,举例,对两种解法的分析 结论：我们给出解法更精确。 为什么？ 考察访存过程： 不使用Cache时，

53、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倍。,南京大学计算机系 多媒体技术研究所 袁春风,84,4.4.3.4 写策略（Cache一致性问题）,一致性问题的提出： 因为Cache中的内容是主存块的副本，当对Cache中的内容进行更新时，就存在Cache和主存如何保持一

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