计算机组成原理chap课件.ppt

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

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

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

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

5、，所以读出后不能立即进行下一次访问。）。因此，TMC比TA大。最大数据传输率R：连续访问时每秒钟从存储器入出的信息量。单位：位/秒(bps)或 字节/秒(Bps)。RAM：R=W/TMCMC （假定存储周期是500ns，每次读写一个字(16位),则最大数据传输率为：16b/500ns=32Mbps。)磁表面：TN=TA+N/R (其中TN 为读写N位的平均时间；TA为平均存取时间；N为位数)速度计量单位：毫秒=10-3秒(m s)，微秒=10-6秒(s)，纳秒=10-9秒(ns)南京大学计算机系 多媒体技术研究所 袁春风84.1.2 主要性能指标n价格（每位成本）存储器的价格常用每位(bit)

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

7、义相同的术语是平均无故障时间或平均无差错时间。MTBF的计算公式为：t存储器系统运行的一段时间N(t)系统在0,t时间段内的故障次数南京大学计算机系 多媒体技术研究所 袁春风104.1.2 主要性能指标n其他性能指标 集成度：每个芯片所含的二进制信息量。功耗：发热程度和耗电量。集成度和功耗是矛盾的两个方面。我们希望集成度大而功耗小，但一般集成度越大，功耗也越大。南京大学计算机系 多媒体技术研究所 袁春风114.1.3 存储器分类（1）按工作性质/存取方式分类 随机存取存储器(RAM)：每个单元的读写时间一样，且与各单元所在位置无关。如：内存。顺序存取存储器(SAM)：数据按顺序从存储载体的始端

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

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

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

11、ierarchy传统结构南京大学计算机系 多媒体技术研究所 袁春风164.1.4 存储器分级体系结构Contemporary Memory Hierarchy当代结构开辟一部分内存区，用作“Disk Cache”，用于存放将被送到磁盘上的数据。引入“Disk Cache”的好处：(1)写盘时按“簇”进行，以避免频繁地小块数据写盘。(2)有些中间结果数据在写回盘之前可被快速地再次使用。南京大学计算机系 多媒体技术研究所 袁春风174.2 半导体随机存储器n记忆单元的基本原理n半导体RAM的组织n再生与刷新n只读存储器n存储器的数据检/纠错南京大学计算机系 多媒体技术研究所 袁春风184.2.1

12、记忆单元的基本原理n作为记忆材料的条件：有两种稳态，且是可逆的。在外部信号激励下，两种稳态能进行无限次相互转换。在外部信号激励下，能读出两种稳定状态。长期存储可靠n可用作记忆单元(位元)的材料：磁性材料（磁芯、磁泡、CCD等，用的很少）半导体材料（TTL,ECL,MOS管，大量使用）半导体记忆单元双极型MOS管静态MOS动态MOSSRAMDRAM目前的主流技术南京大学计算机系 多媒体技术研究所 袁春风194.2.1 记忆单元的基本原理（1）速度快，但集成度低、功耗大电路速度主要取决于射极电流“拨动”的速度，而电流变化的快慢，与管子的频率特性有关，晶体管的频率特性可以做得很高，所以双极型记忆单元

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

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

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

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

17、大学计算机系 多媒体技术研究所 袁春风31地址译码器电路示意图南京大学计算机系 多媒体技术研究所 袁春风324.2.2 半导体RAM的组织n读写控制 存储器的基本操作是读操作和写操作。读写控制电路用于接收总线送来的读/写控制信号，控制数据写入记忆单元，或将数据从记忆单元读出。下图是一个二进制位的读写与I/O电路示意图。读写控制电路由门电路1、2组成，“读写命令R/W”接受总线传送过来的读/写命令。当R/W=1时是读操作命令，R/W=0时是写操作。南京大学计算机系 多媒体技术研究所 袁春风33n16M位=4Mb x 4=2048 x 2048 x 4=211x211x4(1)地址线：11根 分时

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

19、x 8=512 x 512 x 8=29 x 29 x 8 所以要8个512 x 512的位片式芯片 每个芯片的地址线为9+9=18。n存储器容量等于芯片的字数，所以只需在位方向上进行扩充。而字方向不需扩充。字：512 x 512=256K(未扩充)位：1位8位。n若需要更大容量的存储器时，则需一个芯片阵列。即芯片在字和位方向都要扩充。南京大学计算机系 多媒体技术研究所 袁春风36举例3：256K字节存储器组织南京大学计算机系 多媒体技术研究所 袁春风374.2.3 DRAM的刷新n什么样的存储芯片要刷新？动态RAM芯片要刷新。n为什么要刷新？因为DRAM芯片是靠电容上存储电荷来暂存信息的。而

20、电容的绝缘电阻不是无穷大，总会有漏电。因而需要定期进行刷新，即对原存信息的电容补充电荷。电荷泄漏程度取决于制造工艺，目前多数DRAM芯片需要在2ms以内全部刷新一遍，若间隔超过2ms，有可能丢失信息。n刷新与再生 刷新是因为记忆电容放电而需要的定时充电操作，因而需要对所有单元定时按行进行；再生则是因为记忆单元被破坏性读出后的充电操作，因而是对个别单元及所在行的其他单元随机进行的。南京大学计算机系 多媒体技术研究所 袁春风384.2.3 DRAM的刷新n如何进行刷新？所有存储芯片同时进行。对每个DRAM芯片来说，按行进行。每次刷新一行，每一行在2ms内必须保证被刷新一次。若某存储器有若干块DRA

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

22、形成一段死区。南京大学计算机系 多媒体技术研究所 袁春风404.2.3 DRAM的刷新n分散刷新方式 将每个存取周期分为两部分，前半期用于正常读写或保持，后半期用于刷新，也就是将各刷新周期分散地安排在读写周期之后。分散刷新方式的优点是时序控制简单，主存没有长的死区；缺点是刷新过于频繁，主存利用率不高，速度大约降低一半。现在，个人计算机主存的存取周期大约为10ns，若采用分散刷新方式，将增至20ns，在2ms内将刷新105次，大大超过行数。因此，分散刷新方式只能用于低速系统之中。南京大学计算机系 多媒体技术研究所 袁春风414.2.3 DRAM的刷新n异步刷新方式 结合集中和分散两种方式。将2m

23、s的刷新时间间隔平均分配到每行。例如：行地址为7位时，共128行，所以行间刷新时间间隔为：2ms/128=15.625s。这样就能保证:对某行而言，在2ms之内必须刷新一次且仅被刷新一次。n透明刷新方式 CPU在指令译码时不访问存储器，因此，存储器可利用这段时间插入刷新操作。这样，刷新过程便不占用CPU时间，对CPU而言是透明的。南京大学计算机系 多媒体技术研究所 袁春风42动态刷新方式时间分配关系图南京大学计算机系 多媒体技术研究所 袁春风434.2.4 只读存储器n特点：信息只能读不能写。非破坏性读出，无需再生。也以随机存取方式工作。信息用特殊方式写入，一经写入，就可长久保存，不受断电影响

24、。故是非易失性存储器。n用途：用来存放一些固定程序。如监控程序、启动程序等。只要一接通电源，这些程序就能自动地运行；可作为控制存储器，存放微程序。还可作为函数发生器和代码转换器。在输入、输出设备中，被用作字符发生器，汉字库等。南京大学计算机系 多媒体技术研究所 袁春风444.2.4 只读存储器n分类：腌膜只读存储器（Mask ROM）-MROM 可编程只读存储器（Programmable ROM）-PROM 可擦除可编程只读存储器（Erasable PROM）-EPROM 电可擦除可编程只读存储器（Electrically EPROM）-EEPROM(E2PROM)闪存（flash memor

25、y）南京大学计算机系 多媒体技术研究所 袁春风454.2.4 只读存储器n掩膜型只读存储器(MROM)类似于字片式RAM，没有写入机构 行、列交叉点的MOS管，在最后一道掩膜工艺，根据特定的编码布局来决定是否行、列互连，接上者为0(或1)，未接上者为1(或0)。特点：(1)存储内容一次写入，不能修改，因而灵活性差。(2)存储内容固定，所以可靠性高。(3)生产周期长，用户和厂家间依赖性大，只适合定型批量生产。南京大学计算机系 多媒体技术研究所 袁春风464.2.4 只读存储器n可编程序只读存储器(PROM)芯片出厂时内容全部为0(半成品)，用户可用专门的PROM写入器将信息写入，所以称为可编程型

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

27、用。但是EPROM采用MOS工艺，速度比较慢。擦除时，芯片中所有信息都会消失，不灵活。因而又引入了一种电可擦除的EPROM（E2PROM）。4.2.4 只读存储器南京大学计算机系 多媒体技术研究所 袁春风484.2.4 只读存储器n电擦除EPROM（E2PROM）也是一种以读为主的可读可写存储器。使用电可擦除技术（加高电压擦除），可擦除个别单元。它采用金属-氮-氧化硅（MNOS）集成工艺，可实现正常的只读不写，在擦除时只需加高压对指定单元产生电流，形成“电子隧道”，将该单元信息擦除，而其它未通电流的单元内容保持不变。写操作比读操作化更多的时间。集成度比EPROM低，而且更贵。南京大学计算机系

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

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

30、ash EEPROM还可能取代DRAM与SRAM。南京大学计算机系 多媒体技术研究所 袁春风514.4 高速缓冲存储器（Cache)n引入高速缓存的目的 解决CPU速度和主存速度匹配问题（另一种方法是采用多模块存储器结构）nCache的工作原理nCache设计的要素 Cache大小 映射方式 替换算法 写策略 块大小 Cache个数n奔腾机的Cache组织南京大学计算机系 多媒体技术研究所 袁春风524.4.1 程序访问的局部化n什么是程序访问的局部化性质？对大量典型程序的运行情况进行分析的结果表明：在一个较短的时间间隔内，由程序产生的地址往往集中在存储器的一个很小的范围内。因为指令地址是连续

31、的，再加上循环程序段或子程序段要重复执行。因此，对这些地址的访问就自然地具有在时间上集中分布的倾向。这种在某一时间段，对局部范围的存储器地址频繁访问的现象就是所谓的程序访问局部性。n基于程序访问的局部性使访存要求快速响应 如果在CPU和主存之间设置一个快速小容量的存储器，其中总是存放最活跃（被频繁访问）的程序块和数据，CPU访问这些程序或数据时，就不必访问主存，而直接从这个高速缓存中取得。这样便使得CPU和主存速度匹配起来了。南京大学计算机系 多媒体技术研究所 袁春风53程序局部性原理图为什么引入Cache能达到快速访问的目的？主要是基于程序访问的局部化性质南京大学计算机系 多媒体技术研究所

32、袁春风544.4.2 Cache的工作原理n在主存-Cache存储体系中，所有的程序和数据都在主存中，Cache中只存放主存一部分程序块和数据的副本。n主存由多达2n个可寻址的字组成，每个字有唯一的n位地址。为了实现映射，我们把这个存储器看成由许多定长的块(block)组成，每块有K个字，即有L=2nK个字块。Cache由M个槽(slot)组成，每个槽有K个字。槽(或称为行line)的数量远远小于主存储器块的数目。在任何时侯，存储器中的几个块驻留在Cache的槽中。如果要读取存储块中的某个字，则整个块被传送到Cache的一个槽中。由于块数多于槽数，所以单个的槽不能久久地被某块专用。因此，每个槽

33、有一个标记(tag)，用来识别当前存储的是哪个块。这个标记通常是主存储器地址的一部分。南京大学计算机系 多媒体技术研究所 袁春风554.4.2 Cache的工作原理南京大学计算机系 多媒体技术研究所 袁春风56南京大学计算机系 多媒体技术研究所 袁春风574.4.2 Cache的工作原理南京大学计算机系 多媒体技术研究所 袁春风58南京大学计算机系 多媒体技术研究所 袁春风59Cache工作原理图南京大学计算机系 多媒体技术研究所 袁春风604.4.2 Cache的工作原理n引入cache后系统的效率估算 假定主存的访问时间为tMM，Cache的访问时间为tC C ，Cache的命中率为p，则

34、CPU访问该存储系统的平均访问速度为：TA A=p tC C+(1-p)tMM=tM M (tMM-tC C )p 所以，采用 Cache后系统的访存速度提高倍数为：tMM/TA A=tMM /(p tC C+(1-p)tM M)=1 /(1-(1-tC C/tMM )p)南京大学计算机系 多媒体技术研究所 袁春风614.4.3 Cache设计要素Cache大小写策略映射功能 写通过（Write Through）直接 回写（Write Back）相联 写一次（Write Once）组相联块大小替换算法Cache数目 最近最少使用 一级或二级 先进先出 统一或分离 最不经常使用 随机南京大学计算

35、机系 多媒体技术研究所 袁春风624.4.3.1 Cache大小n原则上说，Cache的大小选定应使得使用Cache后的位平均价格接近于不使用Cache时主存的平均价格，即Cache应足够小；而使用Cache后的平均访问速度接近于Cache的速度，即Cache应足够大。n一些研究表明，Cache大小取1K512K字是最好的。南京大学计算机系 多媒体技术研究所 袁春风634.4.3.2 映射功能n什么是Cache的映射功能？由于Cache槽比主存块少，因此需要一种算法把主存中的块映射到Cache槽中。这种反映主存块和Cache槽之间对应关系的技术称为映射功能。n通常采用3种映射技术 直接、相联、

36、组相联 为了说明方便起见，假定：数据在主存和Cache之间按块传送，单位为512字。Cache大小：213字=8K字=16槽 x 512字/槽 主存大小：220字=1024K字=2048块 x 512字/块南京大学计算机系 多媒体技术研究所 袁春风644.4.3.2 映射功能-直接映射n是一种最简单的映射技术。n把主存的每一块映射到一个固定的Cache槽中。也称模映射，映射关系为：Cache槽号=主存块号 mod Cache槽数 举例：4=100 mod 16 (说明主存第100块应映射到Cache的第4槽中。)n每个槽有个标志字段，用于指出该槽取自主存的哪个块群。主存共有128个块群。故标志

37、位有7位。n每个块群中的16块与Cache的16个槽一一对应。n主存地址共20位：7位标志、4位槽号、9位字号。高7位标志表示该地址位于主存哪一个块群。南京大学计算机系 多媒体技术研究所 袁春风65直接映射Cache组织示意图南京大学计算机系 多媒体技术研究所 袁春风66n访存过程：CPU给出20位主存地址，根据地址中间4位找到Cache相应的槽，然后取出该槽的标志，与地址中高7位进行比较。若相等，则说明该主存单元所在的块在Cache中，再根据低9位字地址，从Cache的这一槽中取出字地址指出的那个单元送CPU。若不相等，则说明要访问的主存单元所在的那一块不在主存。此时将主存中该块调入Cach

38、e对应的槽中,并将该单元送CPU。n特点：容易实现，但不够灵活，Cache存储空间得不到充分利用。例如，需将主存第0块与第16块同时复制到Cache中时，由于它们都只能复制到Cache第0槽，即使Cache其它槽空闲，也有一个主存块不能写入Cache。这样就会产生频繁的 Cache装入。4.4.3.2 映射功能-直接映射南京大学计算机系 多媒体技术研究所 袁春风674.4.3.2 映射功能-相联映射n每个主存块可装入到Cache的任何一槽中。也称全映射或全相联映射。n每个槽有个标志字段，用于指出该槽取自主存的哪个块。主存共有2048块。故标志位有11位。n主存地址共20位：11位标志、9位字号

39、。高11位表示该地址位于主存哪一块。南京大学计算机系 多媒体技术研究所 袁春风68南京大学计算机系 多媒体技术研究所 袁春风694.4.3.2 映射功能-相联映射n访存过程：CPU给出一个20位主存地址，根据高11位的内容依次与Cache中各槽的标志位进行比较。若能找到相等的槽，则说明要访问的单元在该槽中。再根据后9位字号找到相应的字取到CPU中。若全都不相等，则说明要访问的单元不在Cache中。n特点：比直接映射灵活。采用相联存取技术（按内容访问），实现复杂、速度慢。Cache标志位数增加，比较逻辑成本随之增加。南京大学计算机系 多媒体技术研究所 袁春风704.4.3.2 映射功能-组相联映

40、射n结合了直接映射和相联映射的特点。n将Cache所有槽分组，把主存块映射到Cache固定组的任一槽中。也即：组间模映射、组内全映射。映射关系为：Cache组号=主存块号 mod Cache组数 举例：假定Cache划分为：8K字=8组x2槽/组x512字/槽 4=100 mod 8 (说明主存第100块应映射到Cache的第4组的任意槽中。)n每个槽有个标志字段，用于指出该槽取自主存的哪个组群。主存共有256个组群。故标志位有8位。n每个组群中的8块与Cache的8个组一一对应。n主存地址共20位：8位标志、3位组号、9位字号。高8位标志表示该地址位于主存的哪个组群。南京大学计算机系 多媒体

41、技术研究所 袁春风71组相联映射的Cache组织图南京大学计算机系 多媒体技术研究所 袁春风724.4.3.2 映射功能-组相联映射n访存过程：CPU给出一个20位主存地址，根据中间3位的内容找到对应的Cache组，再将前8位依次与该组中各槽的标志位进行比较。若能找到相等的槽，则说明要访问的单元在该槽中。再根据后9位字号找到相应的字取到CPU中。若全都不相等，则说明要访问的单元不在该组中。n特点：结合了直接映射和相联映射的优点。当Cache的组数为1时，则变为相联映射；当每组只有一个槽时，则变为直接映射。每组两个槽（称为2路组相联）最常用。一般每组4个槽 以上的情况很少用。南京大学计算机系 多

42、媒体技术研究所 袁春风734.4.3.3 替换算法n替换问题的提出：当对应的Cache槽已被占满而需要调入新的主存块时，必须考虑从cache槽中调出一个主存块。例如：组相联映射时，假定第0组的两个槽分别被主存第0和8块占满，此时若需调入主存第16块，根据映射关系，它只能放到Cache第一组，因此，第一组中必须调出一块，那么调出哪一块呢？这就是淘汰策略问题，也称替换算法。n常用替换算法有：先进先出FIFO（first-in-first-out）最近最少用LRU（least-recently used）最不经常用LFU（least-frequently used）随机替换算法（Random）等等南

43、京大学计算机系 多媒体技术研究所 袁春风744.4.3.3 替换算法-先进先出n总是把最先进入的那一块淘汰掉。例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组中，对于同一地址流，考察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槽/组南京大学计算机系 多媒体技术研究所

44、 袁春风754.4.3.3 替换算法-最近最少用n总是把最近最少用的那一块淘汰掉。例：假定主存中的5块1,2,3,4,5同时映射到Cache同一组中，对于同一地址流，考察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槽/组南京大学计算机系 多媒体技术研究所 袁春风764.4.3.3 替换算法-最近最少用n是一种堆栈算法，它的命中率随组的增大而提高。n当分块局部化范围超过了Cache存储容量时，命中率变得很低。极端情况下，假设地址

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

46、值为3的那一槽中的主存块被淘汰，新槽计数器置为0，其余加1。1 2 3 4 1 2 5 1 2 3 4 5 543203211243320112532130125410231254021312542103123410321234032112343210123210121010南京大学计算机系 多媒体技术研究所 袁春风78n最不经常用（LFU）算法：替换掉Cache中引用次数最少的块。LFU也用与每个槽相关的计数器来实现。n随机算法：随机地从候选的槽中选取一个淘汰，与使用情况无关。模拟试验表明，随机替换算法在性能上只稍逊于基于使用情况的算法。4.4.3.3 替换算法-其他算法南京大学计算机系 多

47、媒体技术研究所 袁春风79举例n假定计算机系统有一个容量为32Kx16位的主存，且有一个4K字的4路组相联Cache，主存和Cache之间的数据交换块的大小为64字。假定Cache开始为空，处理器顺序地从存储单元0、1、4351中取数，然后重复9次。设Cache比主存快10倍。采用LRU算法。试分析cache的结构和主存地址的划分。说明采用Cache后速度提高了多少？采用MRU算法后呢？n答：假定主存按字编址。每字16位。主存：32K字=512块x64字/块 Cache：4K字=16组x4槽/组x64字/槽 主存地址划分为：字号标志位组号6454352/64=68，所以处理器的访问过程是对前6

48、8块连续访问10次。南京大学计算机系 多媒体技术研究所 袁春风80举例0组1组2组3组4组15组0 槽1 槽2 槽3 槽0/64/481/65/492/66/503/67/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+1

49、0 x(1-p)=9.5倍南京大学计算机系 多媒体技术研究所 袁春风81举例0组1组2组3组4组15组0 槽1 槽2 槽3 槽0/16/32/481/17/33/492/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字未命中；其余都命

50、中.所以,命中率p为（43520-68-7x4-2 x8）/43520=99.74%速度提高：tm/ta=tm/(ptc+(1-p)tm)=10/(p+10 x(1-p)=9.77倍南京大学计算机系 多媒体技术研究所 袁春风82举例n原版书的解法(对于LRU算法)假定从Cache读64字的时间为T,则从主存读64字的时间为10T。如果某块不在Cache中，那么该块必须先从主存读入Cache，然后再从Cache读入。故时间为11T。不用Cache时,访问时间为：10 x68x10T=6800T 有Cache时,访问时间为：1x(68x11T)+9x(48x1T+20 x11T)=3160T故：速