计算机组成4章

1、1第第4章章 存储系统存储系统 西安电子科技大学计算机学院西安电子科技大学计算机学院有哪些存储设备有哪些存储设备特性特性工作电路工作电路工作过程工作过程(实验实验)74LS13824.1 存储系统概述存储系统概述l4.1.1 存储系统层次结构存储系统层次结构lDesign problem We want a memory unit that:lCan keep up with the CPUs processing speedlHas enough capacity for programs and datalIs inexpensive, reliable, and energy-effic

2、ient3解决存储系统解决存储系统大容量、大容量、高速度、低成本高速度、低成本相互制相互制约的矛盾！约的矛盾！4.1.1 存储系统层次结构存储系统层次结构44.1.2 存储器分类存储器分类 l按在计算机中的用途分类（所处位置）按在计算机中的用途分类（所处位置） l内部存储器内部存储器 l寄存器寄存器l高速缓冲存储器高速缓冲存储器Cachel主存（主存（main） l外部存储器外部存储器l联机：硬盘联机：硬盘l脱机：光盘，磁带，存储卡，脱机：光盘，磁带，存储卡，U盘等盘等l控制存储器控制存储器 l按照存储信息介质分类按照存储信息介质分类 l 半导体器件半导体器件l 磁性器件：磁盘（磁带）存储器磁

3、性器件：磁盘（磁带）存储器 l 光学器件：光盘存储器光学器件：光盘存储器54.1.2 存储器分类存储器分类l按存放信息的易失（挥发）性分类按存放信息的易失（挥发）性分类 l易失存储器易失存储器 l非易失存储器非易失存储器l按存取方式分类按存取方式分类 l随机存取存储器随机存取存储器 l顺序存取存储器顺序存取存储器 l按存储器的读写功能分类按存储器的读写功能分类 l读写存储器读写存储器 l只读存储器只读存储器 64.1.3 存储器的性能指标存储器的性能指标 l存储存储容量容量 存储容量存储容量=存储字数存储字数字长字长=存储单元数存储单元数单元位数单元位数l存储器的存储器的速度速度l存取时间存取

4、时间 l存取周期存取周期TM（存取时间存取时间 ） l存储器带宽存储器带宽BM BM = W/TM ；W为存储器读写的数据宽度为存储器读写的数据宽度l可靠性可靠性 l功耗功耗 l成本（价格）成本（价格） c(每位价格每位价格) =C(总成本总成本)/S(总容量总容量)74.2 内部存储器内部存储器 l主存的构成主存的构成l高速缓存高速缓存l虚拟存储器虚拟存储器 RAMROMDRAM其他存储器其他存储器84.2.1 随机读写存储器随机读写存储器RAM lSRAM (cache), DRAM (main), and flash (nonvolatile)l内部译码结构内部译码结构 l常规常规RAM

5、芯片，其外部有芯片，其外部有地址地址引线、引线、数据数据引线引线和和控制控制信号引线。信号引线。l地址地址引线在芯片内部译码，引线在芯片内部译码，选中选中芯片内部的相芯片内部的相应存储单元。应存储单元。l某静态某静态RAM芯片上有芯片上有n条地址线时，地址线上条地址线时，地址线上所能表示的地址编码就有所能表示的地址编码就有2n种。这就意味着该种。这就意味着该芯片内部有芯片内部有2n个存储单元。个存储单元。 94.2.1 随机读写存储器随机读写存储器RAMA0A1An-1地址译码器01232n-22n-1行地址译码器012n-1列地址译码器012m-1A0A0An-1Am-1（a）（b）图4.2

6、 RAM芯片内部的两种译码方式一维译码一维译码二维译码二维译码104.2.1 随机读写存储器随机读写存储器RAMlDRAM vs. SRAM Memory Cell ComplexitySingle-transistor DRAM cell, which is considerably simpler than SRAM cell, leads to dense, high-capacity DRAM memory chips.114.2.1 随机读写存储器随机读写存储器RAMl存储器时序存储器时序 地址数据WR地址数据WRCS（a）（b）图4.5 CPU写内存（a）及内存写（b）的时序CPU

7、周期M写周期12Example: Access all 4 banks in parallel134.2.1 RAM主存储器的组成及接口主存储器的组成及接口 D0D7A0A12OEWECS图4.6 SRAM芯片引线 A0A12为为13条地址信号线条地址信号线 D0D7为为8条双向数据线条双向数据线 CS片选信号的引线。所有片选信片选信号的引线。所有片选信号同时有效时，才能选中该芯片。号同时有效时，才能选中该芯片。 OE为输出允许信号。当为输出允许信号。当OE=0时，时，允许某单元数据送到允许某单元数据送到D0D7上。上。 WE是写允许信号。是写允许信号。当当WE=0时，允许将数据写入芯片；时，

8、允许将数据写入芯片；当当WE=1时，允许芯片的数据读出。时，允许芯片的数据读出。 l主存与主存与CPU通过通过总线总线连接连接l用存储芯片构成主存用存储芯片构成主存144.2.1 随机读写存储器随机读写存储器RAMlDRAM PackagingTypical DRAM package (DIP) housing a 4M 4 memory.154.2.3 动态读写存储器动态读写存储器DRAM l动态存储器芯片的引线动态存储器芯片的引线 A0A7为地址输入端为地址输入端 DIN和和DOUT是芯片上的数据线是芯片上的数据线 RAS为行地址锁存信号为行地址锁存信号 CAS为列地址锁存信号为列地址锁存

9、信号 WE为写允许信号为写允许信号 164.2.3 动态读写存储器动态读写存储器DRAMl标准标准DRAM的工作过程（时序）的工作过程（时序） 行地址RASCASWED0D7图4.13 DRAM的读出过程列地址有效数据174.2.3 动态读写存储器动态读写存储器DRAM行地址RASCASWED0D7图4.14 DRAM 的写入过程列地址写入数据184.2.3 动态读写存储器动态读写存储器DRAMl刷新（时序）刷新（时序） 19SRAM与与DRAMlSRAMl用稳态电路存信息，不需刷新用稳态电路存信息，不需刷新l相对于相对于DRAM，速度快、集成度低、功耗大、成本高，速度快、集成度低、功耗大、成

10、本高lDRAMl用暂态电路（电容）存信息，需刷新用暂态电路（电容）存信息，需刷新l地址采用复用技术，分行列两次加载，地址采用复用技术，分行列两次加载，l相对于相对于SRAM，速度慢、集成度高、功耗小、成本低，速度慢、集成度高、功耗小、成本低l刷新（再生）方法：集中式、分散式、异步式刷新（再生）方法：集中式、分散式、异步式l刷新控制电路：刷新计数器、刷新刷新控制电路：刷新计数器、刷新/访存裁决、刷新控制访存裁决、刷新控制逻辑，是逻辑，是CPU和和DRAM的接口的接口CASRAS 、204.2.1 随机读写存储器随机读写存储器RAMl连接（内存接口）连接（内存接口）芯片惟一地占据从芯片惟一地占据从

11、F0000H到到F1FFFH这这8KB内存空间内存空间 MEMRMEMW21随机读写存储器随机读写存储器RAMl内存的字扩展内存的字扩展 22随机读写存储器随机读写存储器RAMl内存的位扩展内存的位扩展 234.2.1 随机读写存储器随机读写存储器RAMl80X86内存的连接内存的连接 244.2.1 随机读写存储器随机读写存储器RAM254.2.1 随机读写存储器随机读写存储器RAMlPentium处理器的内存组织处理器的内存组织 Pentium处理器有几百条引线，其中与访问处理器有几百条引线，其中与访问内存有关的是地址信号内存有关的是地址信号A3A31、体选择信号、体选择信号BE0BE7、

12、64位数据信号位数据信号D0D63、及控制、及控制信号信号M/IO、D/C和和W/R。 264.2.2 只读存储器只读存储器ROMl掩膜工艺掩膜工艺ROM l可一次编程可一次编程ROM（PROM或或OTP） l可擦去重写的可擦去重写的PROMlEPROMlEEPROMlFlash 274.2.2 只读存储器只读存储器ROMlNonvolatile MemoryRead-only memory organization, with thefixed contents shown on the right.284.2.2 只读存储器只读存储器ROMl闪速存储器（闪速存储器（Flash Memory

13、） EEPROM or Flash memory organization. Each memory cell is built of a floating-gate MOS transistor.29l外存平均访问时间外存平均访问时间ms级：级：l硬盘：硬盘：910msl光盘：光盘：80120msl内存平均访问时间内存平均访问时间ns级：级：lSRAM Cache：15nslSDRAM内存内存：715nslDDR SDRAM： lEDO内存：内存：6080nslEPROM存储器：存储器：100400ns各种存储器访问时间比较各种存储器访问时间比较DRAM是动态存储器是动态存储器(Dynami

14、c RAM)，SDRAM是是SynchronousDRAM，即同步，即同步动态存储器。动态存储器。SDRAM是在现有的标准是在现有的标准动态存储器中加入同步控制逻辑动态存储器中加入同步控制逻辑(一个状一个状态机态机)，利用一个单一的系统时钟同步所，利用一个单一的系统时钟同步所有的地址、数据和控制信号。使用有的地址、数据和控制信号。使用SDRAM能提高系统表现，简化设计，能提高系统表现，简化设计，提供高速数据传输，且需时钟进行刷新。提供高速数据传输，且需时钟进行刷新。SDRAM是一种改善了结构的增强型是一种改善了结构的增强型DRAM。DDR SDRAM (Double Date Rate Syn

15、chronous Dynamic Random Access Memory) 为双倍数据传输率之为双倍数据传输率之SDRAM。DDR在一个内存在一个内存时钟周期的上升沿和下时钟周期的上升沿和下降沿各做一次操作降沿各做一次操作，可以完成，可以完成SDRAM两个周期才能完成的任务。两个周期才能完成的任务。 DDR SDRAM最早由三星公司最早由三星公司1996年提出，年提出，内存规格由日本电气、三菱、富士通、内存规格由日本电气、三菱、富士通、东芝、日立、德州仪器、三星及现代等东芝、日立、德州仪器、三星及现代等八家公司协议订立，得到八家公司协议订立，得到AMD、VIA与与SiS等主要芯片组厂商支持。

16、等主要芯片组厂商支持。 EDO RAM(Extended Data Output RAM)为扩展数据输出内存，是为扩展数据输出内存，是Micron公司的专利技术，有公司的专利技术，有72线和线和168线之分，线之分，5V电压，带宽电压，带宽32bit，基本速率，基本速率40ns以上。以上。 EDO RAM 是传统是传统 FPRAM (Fast Page RAM) 的改进，运作上假定下一次存取的改进，运作上假定下一次存取地址是与上一次连续的，这样能把地址是与上一次连续的，这样能把 memory throughput 由由 FPRAM 的最高的最高 176MB/s 提升到提升到 EDO RAM 的

17、最高的最高 264MB/s。1993 年后年后 EDO RAM 便开始便开始取代取代 FPRAM 的位置。的位置。304.2.4 主存储器校验主存储器校验l主存的奇偶校验主存的奇偶校验 RDRD314.2.4 主存储器校验主存储器校验l交叉校验交叉校验l当存储或传送数个字节时，对数据块进行纵横两个方向当存储或传送数个字节时，对数据块进行纵横两个方向上的奇（偶）校验，故称为上的奇（偶）校验，故称为交叉校验交叉校验。四个字节的数据块，分别加上横向、纵向奇校验表示如下：四个字节的数据块，分别加上横向、纵向奇校验表示如下： A0 A1 A2 A3 A4 A5 A6 A7 横向奇校验位横向奇校验位 第第

18、1字节字节 1 0 0 1 1 0 0 1 1 第第2字节字节 0 0 1 1 0 1 0 0 0 第第3字节字节 1 1 1 0 0 1 1 1 1 第第4字节字节 0 1 1 1 1 1 1 0 1纵向校验位纵向校验位 1 1 0 0 1 0 1 1 l这种校验方式，可以这种校验方式，可以发现并纠正发现并纠正数据块中的数据块中的1位错误位错误。l该方法可以该方法可以发现发现2位同时出错位同时出错，但无法确定出错的位置，但无法确定出错的位置，因而无法纠正因而无法纠正2位错误。位错误。 32P0D6 D4 D3 D1 D0 H0P1D6 D5 D3 D2 D0 H1P2D7 D3 D2 D1

19、H2P3D7 D6 D5 D4 H34.2.4 主存储器校验主存储器校验l内存的海明码校验及纠错内存的海明码校验及纠错RDRDCSRDWRD0D7D0D711111111035679101112P0P3H0H0H3D6D1D0D3D4D6D5D3D2D0D7D3D2D1D7D6D5D4H1H2H3P0P1P2P374LS28074LS28074LS28074LS280CSWRRAMD0D7CSWRH0H1H2H3D0D774LS154图4.18 8位数据诲明码纠错电路双向三态控制1133提高主存工作速度的技术提高主存工作速度的技术l芯片芯片技术技术l快速快速DRAMl快速页式快速页式DRAM（

20、FPM DRAM）l增强数据输出增强数据输出DRAM （EDO DRAM）l同步型同步型DRAM （SDRAM）l双倍速率双倍速率SDRAM（DDR SDRAM ）l相联存储器相联存储器l结构结构技术技术l多端口存储器多端口存储器l多模块存储器多模块存储器l宽字（单体多字）存储器宽字（单体多字）存储器l多体交叉存储器多体交叉存储器344.2.5 其他存储器其他存储器多端口存储器多端口存储器l用于用于提高访存速度提高访存速度l多端口：多端口：时间并行时间并行l结构特点结构特点l具有多具有多(两两)组独立的读写端组独立的读写端口口l允许多允许多(两两)个个CPU或控制器或控制器从多从多(两两)个端

21、口同时异步访个端口同时异步访问存储单元问存储单元l访问冲突访问冲突l从多从多(两两)个端口同时写同一个端口同时写同一个存储单元，发生冲突个存储单元，发生冲突l解决方法：芯片内电路裁决解决方法：芯片内电路裁决WEA354.2.5 其他存储器其他存储器多模块存储器多模块存储器lBridging the CPU-Memory Speed GapIdea: Retrieve more data from memory with each accessTwo ways of using a wide-access memory to bridge the speed gap between the pr

22、ocessor and memory.(b)36多模块存储器多模块存储器l用于用于提高访存速度提高访存速度l多模块：多模块：空间并行空间并行l单体多字单体多字l结构特点结构特点：多模块构成单一存储体：多模块构成单一存储体l访问方式访问方式：一次访存并行读写：一次访存并行读写m个字（数据总线个字（数据总线/寄存器宽度寄存器宽度为为m字，字， m个顺序地址分配在个顺序地址分配在m个存储模块的相同存储单元个存储模块的相同存储单元上）上）l效率效率：访问的内容在存储体同一行，频带是单体单字存储器：访问的内容在存储体同一行，频带是单体单字存储器的的m倍，否则，并行效率大为降低倍，否则，并行效率大为降低l

23、多体交叉多体交叉l结构特点结构特点：多个存储模块可并行独立工作：多个存储模块可并行独立工作l访问方式访问方式：一次访存对：一次访存对m个存储模块的不同存储单元并行个存储模块的不同存储单元并行（或流水）读写（或流水）读写m个字（数据总线个字（数据总线/寄存器宽度为寄存器宽度为1字）字）l效率效率：频带是单体单字存储器的：频带是单体单字存储器的m倍倍l实现实现374.2.5 其他存储器其他存储器多体交叉存储器多体交叉存储器 l实现实现 总总线线384.2.5 其他存储器其他存储器多体交叉存储器多体交叉存储器 lMemory InterleavingInterleaved memory is mor

24、e flexible than wide-access memory in that it can handle multiple independent accesses at once. 读写读写n个字用时：个字用时：T交叉交叉=TM+(n-1)tB，tB=TM/m394.2.5 其他存储器其他存储器相联存储器相联存储器 l相联存储器相联存储器l依据内容依据内容决定内容的地址或者寻找与其相关的内容。决定内容的地址或者寻找与其相关的内容。l用于许多领域，如高速缓冲存储器及虚拟存储器中。用于许多领域，如高速缓冲存储器及虚拟存储器中。 404.3 高速缓冲存储器高速缓冲存储器(Cache) l工

25、作原理工作原理 l对大量程序执行情况分析：在一段较短的时间间隔内对大量程序执行情况分析：在一段较短的时间间隔内,程序集中在某一较小的内存地址空间执行，这就是程程序集中在某一较小的内存地址空间执行，这就是程序执行的序执行的时间时间和和空间空间的的局部性原理局部性原理。同样，对数据的。同样，对数据的访问也会存在局部性现象。访问也会存在局部性现象。(Temporal and Spatial Localities)l基于程序及数据访问的局部性原理，基于程序及数据访问的局部性原理，在在CPU和主存之和主存之间间，尽量靠近，尽量靠近CPU的地方设置一种容量比较小而速度的地方设置一种容量比较小而速度高的存储

26、器，将当前高的存储器，将当前正在执行的程序和正在访问的数正在执行的程序和正在访问的数据放在其中据放在其中。l在程序运行时，不需要从慢速的主存中取指令和数据，在程序运行时，不需要从慢速的主存中取指令和数据，而是而是直接访问这种高速小容量的存储器直接访问这种高速小容量的存储器，从而可以提，从而可以提高高CPU的程序执行速度，这种存储器就称为的程序执行速度，这种存储器就称为高速缓冲高速缓冲存储器（存储器（Cache） 。41lSmall amount of fast memorylSits between normal main memory and CPUlMay be located on CP

27、U chip or moduleCache424.3 高速缓冲存储器高速缓冲存储器(Cache)lCache的构成的构成 43Cache/Main Memory StructurelMemory has 2n addressable wordslMemory is accessed in blockslK words per blocklTotal 2n/K blocks.lE.g.ln=24, we have 224=16M address spacelIf K=4, we have 224/22 = 222 memory blockslSo the block address is the

28、 first 22 bits of word address44可以加可以加1 1位块有效位位块有效位Cache/Main Memory StructurelCache contains cache C lineslEach line has a block, or K wordslIt has a tag to indicate which block in memory is in cachelTo uniquely identify a cache line, we need h bits, if C=2h.45Cache Design IssueslSize of CachelBloc

29、k SizelLevels of Cache,l1, 2 or 3 levels ?lMapping FunctionlDirectlAssociativelSet AssociativelCache Replacement Algorithm: what to keep in cache ?lLeast recent used (LRU),lFirst In First Out (FIFO),lLeast Freq Use (LFU),lRandomlWrite PolicylWrite thrulWrite back46Cache SizelCostlCache is expensive,

30、 compared with memory, in dollar per bitslSpeedlCache size too big not good for fast accesslMore gates and logic needed for addressinglChecking cache for data takes time474.3 高速缓冲存储器高速缓冲存储器(Cache)lComparison of Cache Sizes484.3.2 地址映射地址映射全相联映射全相联映射l在在Cache工作过程中，工作过程中，需要将主存的信息拷贝需要将主存的信息拷贝到到Cache中，这就是

31、主中，这就是主存地址到存地址到Cache地址的地址的“地址映射地址映射”。l在程序执行中，如果命在程序执行中，如果命中，就从中，就从Cache中存取中存取信息。这就需要将主存信息。这就需要将主存地址转换为地址转换为Cache的地的地址，才能对址，才能对Cache进行进行访问。将主存地址转换访问。将主存地址转换为为Cache地址称为地址称为“地地址变换址变换”。l地址映射与变换有地址映射与变换有三种三种基本方式基本方式。 主存第0块第1块第16382块第16383块块号000001010011111110101100Cache图4.26 全相联地址映射494.3.2 地址映射地址映射全相联映射全

32、相联映射504.3.2 地址映射地址映射直接映射直接映射块 号000001010011111110101100Cache主 存第 0块第 7块第0块第7块第 0区第 0块第 7块第 1区第2047区图 4.28 直 接 映 射 方 式 示 意 图514.3.2 地址映射地址映射直接映射直接映射52全相联与直接映射的比较全相联与直接映射的比较全相联全相联N行高速缓存：行高速缓存：lN个标记比较器，标记个标记比较器，标记可存储于相联存储器。可存储于相联存储器。l存储单元存储单元A可能会被缓可能会被缓存在存在N个高速缓存行的个高速缓存行的任何一个中；没有产生任何一个中；没有产生“冲突冲突”的可能性。

33、的可能性。l在将新字装载到高速缓在将新字装载到高速缓存中时，使用替换策略存中时，使用替换策略（比如，（比如，LRU）来挑选）来挑选所要使用的那一行。所要使用的那一行。直接映射直接映射N行高速缓存：行高速缓存：l1个标记比较器，标记可存个标记比较器，标记可存储于静态随机存储器。储于静态随机存储器。l存储单元存储单元A会被缓存在由会被缓存在由其地址确定的特定高速缓其地址确定的特定高速缓存行中；有可能存在地址存行中；有可能存在地址“冲突冲突”。l不需要使用替换策略：每不需要使用替换策略：每个字只能缓存在某个特定个字只能缓存在某个特定的高速缓存行中。的高速缓存行中。534.3.2 地址映射地址映射组相

34、联映射组相联映射544.3.2 地址映射地址映射组相联映射组相联映射55三种映射的比较三种映射的比较直接映射直接映射N路组相联路组相联全相联全相联问题：替换策略问题：替换策略地址地址地址地址地址地址l只用一个标记来只用一个标记来比较地址比较地址l存储单元存储单元A可以可以精确地存储在某精确地存储在某个高速缓存行中个高速缓存行中n同时用同时用N个标记来个标记来比较地址比较地址n存储单元存储单元A可以精可以精确地存储在某个组确地存储在某个组中，但中，但N个高速缓个高速缓存行中的任何一个存行中的任何一个都属于该组都属于该组n同时用每个标同时用每个标记来比较地址记来比较地址n存储单元存储单元A可可以存

35、储在任何以存储在任何高速缓存行中高速缓存行中组内组内1 1块块组数为组数为1 1564.3.3 替换算法替换算法 l随机替换算法（随机替换算法（RAND）l不存在因不存在因“病态病态”访问而导致的最坏结果；访问而导致的最坏结果；l使用伪随机发生器来得到可再生的行为；使用伪随机发生器来得到可再生的行为；l利用真实的随机性来防止逆向工程！利用真实的随机性来防止逆向工程！l先进先出算法（先进先出算法（FIFO）l廉价的选择方案：替换最旧的条目廉价的选择方案：替换最旧的条目(按访问时间来确定日期按访问时间来确定日期)；l在每个组中：保持某个计数器来指向被替换的行。在每个组中：保持某个计数器来指向被替换

36、的行。l近期最少使用算法（近期最少使用算法（LRU）l将最经常使用的存储单元保存在高速缓存中将最经常使用的存储单元保存在高速缓存中;l需要保持按顺序排列的需要保持按顺序排列的N个条目列表个条目列表N!种排序种排序 O(log2N!) = O(N log2N) “LRU位位”+复杂逻辑。复杂逻辑。 l最不经常使用算法（最不经常使用算法（LFU） l最优替换算法（最优替换算法（OTP）：）：利用先验的替换信息利用先验的替换信息 开销是开销是O(Nlog2N)位位/组组开销是开销是O(log2N)位位/组组开销是开销是O(log2N)位位/组组!574.3.3 替换算法替换算法l假定程序在主存为假定

37、程序在主存为5块，块，Cache为为3块，全相联映射。块，全相联映射。lCPU执行程序的顺序为：执行程序的顺序为：P2、P3、P2、P1、P5、P2、P4、P5、P3、P2、P5、P2。l画出画出FIFO算法算法(a)和和LRU算法算法(b)的命中情况如图所示。的命中情况如图所示。图（图（a）是利用）是利用FIFO算法的执行结果。图中用表示命中情况，命中率为算法的执行结果。图中用表示命中情况，命中率为3/12=25图（图（b）是利用）是利用LRU算法的执行结果。图中用表示命中情况，命中率为算法的执行结果。图中用表示命中情况，命中率为5/12=4222333333332 2222 2224 4

38、4 445555551 1122353333332 2555 5254 4 2 242222551 11（ a）（ b）图 4.34 两 种 替 换 算 法 的 比 较58替换策略与缺失率的比较替换策略与缺失率的比较l一般而言，一般而言，FIFO算法要比随机算法或者算法要比随机算法或者LRU算法稍逊一算法稍逊一筹。筹。l对于尺寸较大的高速缓存来说，随机算法与对于尺寸较大的高速缓存来说，随机算法与LRU算法之间算法之间的差别甚小。的差别甚小。相联度相联度2路路 4路路 8路路大小大小 LRU算法算法 随机算法随机算法 LRU算法算法 随机算法随机算法 LRU算法算法 随机算法随机算法59有效位有

39、效位问题：问题：忽略那些不包含任何值的高速缓存行。例如忽略那些不包含任何值的高速缓存行。例如l启动；启动；l从磁盘中装载程序。从磁盘中装载程序。解决方案：解决方案：利用有效位来扩展每个标记。利用有效位来扩展每个标记。l对于命中的高速缓存行来说，必须设置好有效位；对于命中的高速缓存行来说，必须设置好有效位；l在开机在开机/重启时：清除所有的有效位；重启时：清除所有的有效位；l在高速缓存行首次在高速缓存行首次被替换被替换时，应该设置有效位；时，应该设置有效位；l高速缓存控制特性：在程序高速缓存控制特性：在程序/外部控制下，通过清除所外部控制下，通过清除所有的有效位来冲洗高速缓存。有的有效位来冲洗高

40、速缓存。有效位有效位 标记标记 数据数据CPU主存储器主存储器604.3.4 主存主存Cache内容一致性问题内容一致性问题 l写回法写回法 写回法是当写回法是当CPU写写Cache命中时，只将数据写命中时，只将数据写入入Cache而不立即写入主存。只有当被而不立即写入主存。只有当被CPU写写入修改的块被替换出去时才写回到主存中。入修改的块被替换出去时才写回到主存中。 Average cache update is 15%, but for vector computing, 33%, matrix transposition, 50%. l写直达法写直达法 写直达法是当写直达法是当CPU写写

41、Cache命中时，在将数据命中时，在将数据写入修改写入修改Cache的同时写入修改主存，较好地的同时写入修改主存，较好地保证了主存与保证了主存与Cache内容的一致性。内容的一致性。 61l表表4.1列出了针对采用不同写策略的列出了针对采用不同写策略的Cache，在，在不同操作状况下产生的对存储器的访问时间。不同操作状况下产生的对存储器的访问时间。l设设TC为访问为访问Cache时间，时间，TM为访问内存时间，为访问内存时间，TB为为Cache块调入时间。块调入时间。表表4.1 采用采用Cache的访存操作的访存操作Cache类型类型操作操作访存操作访存操作访存时间访存时间写直达写直达Cach

42、e读命中读命中只读只读CacheTC写命中写命中写写Cache，同时写内存，同时写内存TC（隐藏（隐藏TM）读不命中读不命中调入调入Cache块，再读块，再读CacheTB + TC写不命中写不命中只写内存只写内存(no-write-allocate)TM写回写回Cache读命中读命中只读只读CacheTC写命中写命中只写只写CacheTC读不命中读不命中调入调入Cache块，再读块，再读CacheTB + TC写不命中写不命中调入调入Cache块，再写块，再写Cache(write-allocate)TB + TC624.3.5 Cache性能分析性能分析 l命中率命中率HH=(nc/n)1

43、00% nc为为CPU在在Cache中访问到所需信息的次数中访问到所需信息的次数 n为为CPU的总访问次数的总访问次数 不命中率（缺失率、脱靶率）为：不命中率（缺失率、脱靶率）为：1-H l平均访问时间平均访问时间 假设假设Cache的访问周期为的访问周期为TC，主存的访问周期为，主存的访问周期为TM，数据块，数据块调入调入Cache的块传输时间的块传输时间(或称块访问时间或称块访问时间)为为TB ，则，则Cache系统的平均访问时间系统的平均访问时间T(average access time)可表示为：可表示为： T =HTC +(1H)TM 或或 =HTC +(1H)(TB + TC) 或

44、或 =HTC +(1H)(TM + TC)= TC +(1H)TM lHTC: time to directly access cachel(1H)(TM+TC)in time of miss, time to load the data into cache, and access it. TM TC634.3.5 Cache性能分析性能分析 l访问效率访问效率e l加速比加速比 Cache系统的系统的加速比加速比SP定义为：定义为：SP = TM /T=1/(1-H+H/r)l成本成本 假设计算机中的主存与假设计算机中的主存与Cache的容量分别为的容量分别为S1和和S2。显然。显然，S1

45、S2。若主存与。若主存与Cache的单位价格分别为的单位价格分别为C1和和C2，而且而且C1一定是低的。则存储器的平均价格一定是低的。则存储器的平均价格C由下式决定：由下式决定：C=（C1S1+C2S2）/（S1+S2） CMMCCCTTrHrrrHHTHHTTTTe)1 (1)1 (1)1 (644.3.5 Cache性能分析性能分析TCTMTC +TMl命中率与平均访问时间的关系命中率与平均访问时间的关系 654.3.5 Cache性能分析性能分析l命中率与命中率与Cache容量的关系容量的关系 H1S图 4.35 命 中 率 H 与 容 量 S 关 系664.3.5 Cache性能分析性

46、能分析l命中率与块大小的关系命中率与块大小的关系 H1B图4.36 命中率H与块大小B的关系674.3.5 Cache性能分析性能分析l块大小与访问时间的关系块大小与访问时间的关系l平均访问时间平均访问时间1（缺失率）（缺失率）*(缺失损失缺失损失)。l假设缺失损失（从存储器中读取块所需要的时间）为：假设缺失损失（从存储器中读取块所需要的时间）为：40个个周期的等待时间，然后每周期的等待时间，然后每2个周期读取个周期读取16字节。字节。平均访平均访问时间问时间(周期周期)块大小块大小(字节字节)高速缓存大小高速缓存大小(字节字节)684.3.5 Cache性能分析性能分析l块大小与缺失率的关系

47、块大小与缺失率的关系l局部性：块越大局部性：块越大缺失率就会减小直到某个点！缺失率就会减小直到某个点！l固定的高速缓存大小：块越大，固定的高速缓存大小：块越大，l高速缓存中的行数就会越少。高速缓存中的行数就会越少。l缺失率就会越高，特别是在小型高速缓存中更是如此。缺失率就会越高，特别是在小型高速缓存中更是如此。l冒一定风险的预取操作有其局限性冒一定风险的预取操作有其局限性并且需要花费成本！并且需要花费成本！缺失率缺失率(%)(%)块大小块大小(字节字节)高速缓存大小高速缓存大小(字节字节)694.3.5 Cache性能分析性能分析l相联度与缺失率的关系相联度与缺失率的关系l8路（几乎）与全相联

48、等效。路（几乎）与全相联等效。l拇指法则：拇指法则：N行直接映射行直接映射=N/2行行2路组相联。路组相联。1路路(直接映射直接映射)2路路4路路8路路全相联全相联相联度相联度缺失率缺失率(%)(%)高速缓存大小高速缓存大小(字节字节)704.3.5 Cache性能分析性能分析l两级两级Cache 为了克服为了克服CPU和主存间的性能差距，使两者更好的匹配，目前和主存间的性能差距，使两者更好的匹配，目前均在原有的均在原有的Cache和主存之间增加另一级和主存之间增加另一级Cache，构成两、三，构成两、三级级Cache系统。总失效率系统。总失效率=(失效率失效率)第一级第一级 (失效率失效率)

49、第二级第二级 714.3.6 Pentium的的Cache 指 令 池 （ 重 组 缓 冲 器 R O B ）退 回 单 元指 令 读 取 与执 行 单 元分 派 与 执行 单 元L1数 据 C ache（ 8 16K ）L1指 令 C ache（ 8 16K ）L2C ache（ 256K 1M ）总 线 接 口 单 元图 4.37 Pentium 结 构 框 图主存系统总线 72lPentium 4 Cache L1 caches：64 byte lines，4 way set associative L2 cache：128 byte lines，8 way set associativ

50、e L3 cache ：on chip734.4 虚拟存储器虚拟存储器4.4.1 虚拟存储器的概念虚拟存储器的概念l虚拟存储技术是在主存与辅存之间，增加软件及必虚拟存储技术是在主存与辅存之间，增加软件及必要的硬件，使主、辅存之间的信息交换，程序的再要的硬件，使主、辅存之间的信息交换，程序的再定位，地址的转换都能自动进行，使两者形成一个定位，地址的转换都能自动进行，使两者形成一个有机的整体。有机的整体。l由于程序员可以用到的空间远远大于主存的实际空由于程序员可以用到的空间远远大于主存的实际空间，但实际并不存在这么大的主存，故称间，但实际并不存在这么大的主存，故称“虚拟存虚拟存储器储器”（Virt

51、ual Memory）简称）简称VM。主存MM辅助软硬设备虚存VMCPU图2.36 虚拟存储器原理744.4 虚拟存储器虚拟存储器 4.4.1 虚拟存储器的概念虚拟存储器的概念l虚拟存储器是由价格比较贵、虚拟存储器是由价格比较贵、容量不太大、速度相对比较容量不太大、速度相对比较高的高的主存储器主存储器和价格很低、和价格很低、容量非常大、速度慢的容量非常大、速度慢的外部外部（辅助）存储器（辅助）存储器，在，在操作系操作系统统及及辅助硬件辅助硬件的管理下，构的管理下，构成了像一个单一的、可直接成了像一个单一的、可直接访问的超大容量的主存储器。访问的超大容量的主存储器。l解决主存容量与价格的矛盾，解

52、决主存容量与价格的矛盾，使速度接近主存速度而容量使速度接近主存速度而容量和价格又接近外存。和价格又接近外存。 高速缓存Cache主存MM辅助硬件、软件辅助硬件CPU外（辅）存图4.38 虚拟存储器的构成75The Limits of Physical AddressingCPUMemoryA0-A31A0-A31D0-D31D0-D31“Physical addresses” of memory locations DataAll programs share one address space: The physical address spaceNo way to prevent a pr

53、ogram from accessing any machine resourceMachine language programs must beaware of the machine organization Programming the Apple .76Solution: Add a Layer of IndirectionCPUMemoryA0-A31A0-A31D0-D31D0-D31DataUser programs run in an standardizedvirtual address spaceAddress Translation hardware managed

54、by the operating system (OS)maps virtual address to physical memory“Physical Addresses”AddressTranslationVirtualPhysical“Virtual Addresses”Hardware supports “modern” OS features:Protection, Translation, Sharing774.4.2 页式虚拟存储器页式虚拟存储器 l地址变换地址变换 实 页 号页 表 基 址 寄 存 器主 存 中 的 页 表页 表 基 地 址虚 页 号页 内 地 址虚 拟 地 址

55、实 页 号控 制 位页 内 地 址主 存 物 理 地 址图 4.39 页 式 虚 拟 存 储 器 的 地 址 变 换78Page tables encode virtual address spacesA machine usually supportspages of a few sizes(MIPS R4000):PhysicalMemory SpaceA valid page table entry codes physical memory “frame” address for the pageA virtual address spaceis divided into blocks

56、of memory called pagesframeframeframeframeA page table is indexed by a virtual addressvirtual address Page Table(One per ASID)OS manages the page table for each ASID79Two-level Page TablesPage tables may not fit in memory!A table for 4KB pages for a 32-bit address space has 1M entries Each process n

57、eeds its own address space!P1 indexP2 indexPage Offset3112 110212232 bit virtual addressTop-level table wired in main memorySubset of 1024 second-level tables in main memory; rest are on disk or unallocated 80虚拟存储器虚拟存储器l虚拟存储器的工作过程虚拟存储器的工作过程 在实际进行虚在实际进行虚实地址变换中，必须考虑地实地址变换中，必须考虑地址变换的速度，还有程序的调入调出处理，除址变换

58、的速度，还有程序的调入调出处理，除了页表外，还有以下了页表外，还有以下3个部件：个部件：l快表快表TLB若虚拟存储器采用页式管理若虚拟存储器采用页式管理,表格式表格式与页表相同，先查快表，不命中时查页表（慢表）与页表相同，先查快表，不命中时查页表（慢表）l帧页表帧页表帧页表记录当前内存使用情况，用来对帧页表记录当前内存使用情况，用来对主存进行管理。它位于主存。帧页表格式见表主存进行管理。它位于主存。帧页表格式见表1l外页表外页表外页表用来登记程序虚页号与辅存地址外页表用来登记程序虚页号与辅存地址的对应关系，如表的对应关系，如表2所示所示81主存实页号主存实页号占用位占用位程序号程序号虚页号虚页

59、号其他其他01n-1表表1 1 帧页表帧页表虚页号虚页号辅存地址辅存地址柱面号柱面号盘面号盘面号扇区号扇区号装入位装入位01m-1表表2 2 外页表外页表824.4.2 页式虚拟存储器页式虚拟存储器l以一个多用户、页式管理的虚拟存储器为例说以一个多用户、页式管理的虚拟存储器为例说明虚拟存储器的工作过程明虚拟存储器的工作过程内页表(b) 更新帧页表快表实存页地址页内地址实地址(b) 页表命中(c) 内页表不命中(a) 快表命中快表不命中辅存实地址外页表内页表不命中(a)用户名虚存页号页内地址虚地址主存实地址替换算法主存已满主存未满(c)辅存I/O通道(d)主存装入页替换页图 2 . 4 1页式虚

60、拟存储器工作示意图(c)(e)更新(e)更新(e)更新834.4.2 页式虚拟存储器页式虚拟存储器l优点优点主存的利用率高。由于页的容量很小，每一用主存的利用率高。由于页的容量很小，每一用户程序只有不到一页的浪费，故形成的主存碎户程序只有不到一页的浪费，故形成的主存碎片很小。片很小。地址表的内容比较简单。地址表的内容比较简单。地址映像与地址变换速度比较快。地址映像与地址变换速度比较快。l缺点缺点程序的模块性差。因为页的大小是固定的，无程序的模块性差。因为页的大小是固定的，无法与程序模块保持一致。法与程序模块保持一致。页表很长。如前面的例子可以看到页表长达页表很长。如前面的例子可以看到页表长达1