1、计 算 机 组 成 原 理,2024年2月16日,存储系统,通过本章的学习，要求掌握高速缓冲存储器cache的工作原理和理解虚拟存储器的工作原理，能够分析cahce和虚拟存储器的命中情况。通过对命中情况的分析，对cahce和虚拟存储器的工作原理有深入的理解。本章教学内容：1、存储系统基本概念 2、cache存储器 3、虚拟存储器 本章重点：存储系统基本概念，Cache的工作原理及其地址映射方式，LRU替换策略。本章难点：Cache的工作原理及其地址映射方式，虚拟存储器的工作原理。,存储系统,1存储容量：要求大容量。,2价格：要求价格低,主存速度的提高始终跟不上CPU的发展。据统计，CPU的速度
2、平均每年提高60%，而组成主存的DRAM的速度平均每年只改进7%。由SRAM组成的高速缓冲存储器的运行速度则接近甚至等于CPU的速度。,1、存储层次概述,存储器性能指标,3速度:高速度带宽,实际：速度、容量、价格存在巨大的矛盾,希望：高速度、大容量、低价格,存储体系：把各种不同存储容量、不同存取速度、不同价格的存储器，组成层次结构，并通过管理软件和辅助硬件将不同性能的存储器组合成有机的整体，称为计算机的存储层次或存储体系。,存储器系统的层次结构如下图所示：,为了解决对存储器要求容量大，速度快，成本低三者之间的矛盾，目前通常采用多级存储器体系结构，即高速缓冲存储器、虚拟存储器。,较低级：与处理器
3、较远的存储级 容量较大、速度较慢、使用较廉价的技术工艺,存储器系统的层次结构的特点：,在任何指定时间，数据只能在相邻的两级之间拷贝：,较高级：与处理器较近的存储级 容量较小、速度较快、使用较昂贵的技术工艺,2、程序访问的局部性原理,CPU访问存储器时，无论是取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。,时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。(程序循环、堆栈),空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。(指令顺序执行、数组存放),这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少
4、的现象就称为程序访问的局部性原理。,int aMN;for(i=0;i M;i+)for(j=0;j N;j+)sum+=aij;,int aMN;for(j=0;j N;j+)for(i=0;i M;i+)sum+=aij;,哪个程序具有更好的局部性,程序地址的分布是连续的，加上循环程序段和子程序段要重复执行多次，因此，对程序地址的访问具有相对集中的倾向。,程序访问的局部性主要表现：,数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。,其它原因：,优先考虑最近经常被访问的代码,最近可能被访问的数据放在小的但高速存储器里,容量小、离CPU近的
5、高速存储器存放最近要访问的数据。,在高速机器中，信号传输是延迟的一个重要原因。而大的存储器因地址译码级数多，信号延迟会更大。,相同器件条件下，小容量存储器比大容量存储器快。,根据局部性原理，可以在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，在程序运行时，不必从主存储器取指令和取数据，只需访问这个高速存储器，以提高程序运行速度。这个存储器称作高速缓冲存储器Cache。Cache由高速的SRAM组成，它的工作速度数倍于主存，全部功能由硬件实现，并且对程序员是透明的。,cache基本原理,cache的基本结构,它由cache存储体、地址映象变换
6、机构、cache替换机构几大模块组成。,Cache概念：（1）CPU与主存储器之间的一种高速缓冲装置（2）Cache-主存层次结构：由硬件地址变换和控制调度。Cache具有如下特点：位于CPU与主存之间，是存储器层次结构中级别最高的一级；容量比主存小，目前一般有数到数；速度一般比主存快倍,通常由存储速度高的双极型三极管或SRAM组成；其内容是主存的部分副本；其用途可用来存放指令，也可用来存放数据；快存的功能全部由硬件实现，并对程序员透明。,(2)当比较结果不相等时，说明需要的数据尚未调入Cache，那 么就要把该数据所在的整个字块从主存一次调进来。前一种情况称为访问Cache命中，后一种情况称
7、为访问Cache不命中。,cache的命中,任何时候都有一些主存块处在Cache中。当CPU发出读请求时，将主存地址s位（或s位中的一部分）与Cache某块的标记相比较，根据其比较结果是否相等而区分出两种情况：(1)当比较结果相等时，说明需要的数据已在Cache中，那么直接访问Cache就行了，在CPU与Cache之间，通常一次传送一个字；,读请求,命中与缺失,命中（HIT）,缺失（MISS）,读请求,Cache,Cache,缺失造成访问速度急剧下降,cache的命中率,命中率指CPU所要访问的信息在Cache中的比率；而将所要访问的信息不在Cache中的比率称为失效率。增加cache的目的，
8、就是在性能上使主存的平均读出时间尽可能接近cache的读出时间。因此,cache的命中率应接近于1。由于程序访问的局部性，这是可能的。在一个程序执行期间：设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有：,若 tc表示命中时的cache访问时间，tm表示未命中时的主存访问时间，1-h表示不命中率，则cache/主存系统的平均访问时间ta为：ta=htc+(1-h)tm,我们追求的目标是：以较小的硬件代价使cache/主存系统的平均访问时间ta越接近tc越好。,设 r=tm/tc表示主存慢于cache的倍率,e表示访问效率，则有:,为提高访问效率：命中率h
9、越接近1越好，r值以510为宜，不宜太大。命中率h与程序的行为、cache的容量、组织方式、块的大小有关。,例：CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。,解：h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=250ns/50ns=5 e=1/(r+(1-r)h)=1/(5+(1-5)0.95)=83.3%ta=tc/e=50ns/0.833=60ns,例:已知Cache存储周期为40ns,主存存储周期为200
10、ns,Cache/主存系统平均访问时间为50ns,求Cache的命中率是多少?解:因为 ta=htc+(1-h)tm 所以 h=(ta-tm)/(tc-tm)=(50-200)/(40-200)=15/16,（1）数据块在Cache中存放在哪个位置？即定位问题（地址映象）。如果一个块存放在某一Cache中，怎样确定并找到该块，即寻址问题（地址变换）。,Cache结构设计必须解决的问题：如何存放，如何访问，如何替换，如何改写？,（3）在写访问时，写入Cache必须在适当的时候写回主存储器，何时写？写操作时采用什么策略保证两级存储器间的数据一致性。写操作失配时是否将访问块取入高层存储器。,（2）不
11、命中时将从主存储器中访问，并将该块调入Cache中，但是如果Cache中已无空闲空间，则势必将Cache中的某一块调出，但应调出那一块，即替换问题。,地址映象 把主存块按照某种规则（函数或方法）装入或定位到Cache中的过程称地址映象。地址变换 信息按这种映象关系装入Cache后，执行程序时，将主存地址变换成 Cache地址的变换过程叫做地址变换。地址映象和变换密切相关。使用Cache的动力在于它的高速，因此也要求这个地址变换过程尽可能地快，故此过程是以硬件完成的。这带来的另一好处是Cache的透明性，除了程序运行速度提高之外，用户包括系统软件编制人员，丝毫未感觉到Cache的存在。,1.地址
12、映象(映射)与地址变换,基本的地址映象方式：直接映象；全相连映象；组相连映象,在高速缓冲存储器中,把Cache和主存机械等分为相同大小的块,每一块是由若干个字(或字节)组成.,由于Cache的块数远小于主存的块数，因此一个Cache不能唯一地、永久地只对应一个贮存块，在Cache中，每一块外加有一个标记，指明它是主存的哪一块的副本(拷贝)。,例：某机主存容量为1MB,划分为2048块,每块512B;Cache容量为8KB,划分为16块,每块512B。,因刚加电时所有标记位都为“0”，开始执行程序时，命中率较低。另外Cache的命中率还与程序本身有关，即不同的程序，其命中率可能不同。,标记的有效
13、位,每个标记设置有一个有效位。机器加电启动时，Reset信号将所有标记的有效位置“0”，即无效。程序执行过程中，Cache不命中时，逐步将指令块或数据块从主存调入Cache中的某一块，并将这一块标记的有效位置“1”，当再次用到这一块中的指令或数据时，可直接从Cache中取指令或数据。,1）直接映射方式,这是一种多对一的映射关系，但一个主存块只能映象到Cache的一个特定块位置上去。Cache的第i块和主存的第j块有如下函数关系：i=j mod m(m为Cache的总块数）i=0,1,2,m-1 j=0,1,2,n-1,在这种映象方式中：主存的第0块，第16块，第32块，只能映象到Cache的第
14、0块；而主存的第1块，第17块，第33块，只能映象到Cache的第1块；,直接映象,主存地址,7位 4位 9 位,11位 9 位,主存地址,7位,优点:硬件简单,成本低 缺点:块冲突率很高,直接映象的地址变换方法,优点:实现简单，只需利用主存地址块号字段直接判断，即可确定所需字块是否已在Cache中。,缺点：不够灵活，主存的多个字块只能对应唯一的Cache字块，因此，即使Cache别的地址空着也不能占用。Cache存储空间得不到充分利用，降低了命中率。,直接映射地址变换,例：设有一个cache的容量为2K字，每个块为16字，求(1)该cache可容纳多少个块？(2)如果主存的容量是256K字，则有多少个块？(3)主存的地址有多少位？cache地址有多少位？(4)在直接映象方式下，主存中的第i块映象到cache中哪一个块中？(5)进行地址映象时，存储器的地址分成哪几段？各段分别有多少位？,