计算机组成原理-课件cache

3.4高速存储器单机系统中，主存与CPU速度的不匹配是高速计算的瓶颈。提高存储系统性能的主要措施采用更高速的主存和加长存储器的字长采用并行操作的双端口存储器采用多模块交叉存储器采用高速缓冲存储器P97应用：虚拟存储器中存放段表、页表和快表高速缓存中存入cache行地址相联存储器普通存储器是以地址为检索项来进行存取。相联存储器（CAM）的基本原理可将某一存储项的内容作为检索项来存取和检索信息的存储器。物理地址职工号姓名出生年月工资数N800张明1940.22000N+1540王芳1960.11200N+2920李萍1942.51500N+3750赵虹1945.21400普通存储器的检索项相联存储器的检索项3.5高速缓冲存储器工作原理基于程序局部性原理短时间内，CPU对存储器的访问总是局限在某个较小区域内cache与主存分成大小相同的块当CPU读取一个字时，便发出此字的内存地址到cache和主存。控制逻辑判断此字当前是否在cache中若在，立即传送给CPU若不在，则把此字从主存读到CPU，同时，把含有该字的数据块从主存送cache。CPU相联存储器主存LRU管理逻辑cacheDBABCache的命中率Cache始终保存主存最活跃的局部区域的副本，使CPU的访存操作大多数针对Cache，提高整个程序的执行速度。命中率，越接近1越好。Nc——Cache完成存取的总次数Nm——主存完成存取的总次数h——命中率系统平均访问时间越接近cache访问时间越好。tc——命中时，cache访问时间tm——未命中时，主存访问时间ta——系统平均访问时间Cache的命中率系统访问效率r——Tm/Tc，比值不宜太大，以5~10较好。e——系统访问效率【例5】CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/(r+(1-r)h)=1/(5+(1-5)×0.95)=83.3%ta=htc+(1-h)tm=tc/e=50ns/0.833=60ns主存与Cache的地址映射地址映射应用某种函数，将主存地址映像到Cache中定位，从而可以将内存地址变换成Cache地址，完成CPU的访问。全相联映射直接映射组相联映射地址映射过程对程序员来说是完全透明的由硬件控制实现，程序员不需要编程介入全相联映射主存中任一块都可以映射到Cache中任一行上。例：内存容量64KB，分为256块，每块256B，Cache容量2KB，分为8行，每行也是256B。优点：比较灵活Cache利用率高块冲突概率低使用淘汰算法缺点：Cache标记太长比较电路难于设计和实现M255…7块…1块0块块号…块号块号7行…1行0行Cache标记8位全相联映射检索过程块号块内地址内存地址8位8位7行块号……2行块号1行块号0行块号标记块内容量Cache比较命中0块1块2块…L-1块L块L+1块…255M未命中8位直接映射主存分区，每区内块数与Cahce内行数相同。主存中每一个块只能映射到Cache中某一个固定的行。i=jmodmi：Cache的行号j：主存的块号m：Cache的总行数例：0=8mod8（主存第8块映像到Cache的第0行）31区255…249248…15块…9块8块7块…1块0块M0区1区…区号…区号区号7行…1行0行Cache标识5位不灵活块冲突概率高特点地址变换速度快无需替换算法直接映射检索过程内存地址区号区内块号块内地址5位3位8位7行区号……2行区号1行区号0行区号标记块内容量Cache7块…1块0块…7块…1块0块7块…1块0块M0区1区31区…比较命中未命中组相联映射主存分区，Cache分组，主存每个区的块数与Cache的分组数相同。组间采用直接映射组内采用全相联映射特点：是全相联映像与直接映像的折衷。较直接映像灵活较全相联映像标记位短，速度快255254253252…7块6块5块4块3块2块1块0块M0区1区63区…区号区号区号区号区号1行0行1行0行Cache…1行…0组1组3组0行标识6位区号组相联映射检索过程区号区内块号Cache组号块内地址区号3块2块1块0块…3块2块1块0块3块2块1块0块区号区号区号区号1行0行1行0行CacheM0区1区63区…区号…1行…0组1组3组0行比较命中未命中6位2位8位标识6位块内容量Cache地址映射练习一个四路组相联映射的Cache，由64行构成。主存包含4096个存储块，每块由128字组成。一个主存地址有多少位？主存地址格式中区号、组号和块内地址位数？1)19位，4096*128=2192)区号8位，组号4位，块内地址7位15组区号4095…40814080…31块…17块16块15块…1块0块区号区号区号区号3行2行1行0行CacheM0区1区255区…区号…63行…0组62行区号区号61行60行高速缓存替换算法替换算法：当Cache中的可用位置已被占满时，需要利用某种算法，将旧的行用新的行来代替。最不经常使用（LFU）算法将一段时间内使用次数最少的行淘汰。近期最少使用（LRU）算法最近一段时间，使用机会最少的行被淘汰。随机算法简单地根据一个随机数，指定需要替换出去的旧块。Cache的读写策略读操作：CPU发出读命令后若Cache命中，直接对Cache进行读操作未命中，访问内存，同时将内存信息调入Cache若Cache已满，采用替换算法，换掉原来的某块写操作：CPU发出写命令后写回法:先暂时写入Cache，并用标记注明，直到该块从Cache中替换出来时，才一次写入内存。全写法:同时写入内存和Cache。写一次法:是写回法与全写法的结合。基本同于写回法，但第一次写命中时要同时写入主存。3.6虚拟存储器虚拟存储系统建立在内存——外存层次上的需要辅助硬软件的支持将内存与外存空间统一编址形成一个庞大的存储空间用户可在这个虚拟的庞大空间里编程，而不必考虑实际内存的大小虚拟地址（逻辑地址）：用户编程时使用的地址，在程序真正执行时，在辅助软硬件支持下，虚拟地址将映射为内存的物理地址。实际地址（物理地址）：内存的实际的地址编号。页表页式虚拟存储器内存空间和虚存空间都划分成若干个大小相等的页。设置地址变换机构——页表。页表由多个页表项构成。每个页表项包含实页号、装入位等。实页号页内地址虚页号页内地址虚地址实地址页表项地址1装入位1：该页在内存0：不在内存，调入页表起始地址页表基址寄存器页式虚拟存储器页表的改进——快表快速小容量的存储器保存当前最常用的页表项是慢表的副本页表虚拟存储的特点页大小相等，地址变换简单存在页零头页的划分不具有逻辑性，程序处理复杂段式虚拟存储器内存空间按程序逻辑结构分段，段长度各异。地址变换机构——段表。段表包括多个段表项。每个段表项包含段号、段起点、段长、装入位等。2K1202441K1919233K161202011K110000段长装入位段起点段号段表段0段1段2段3段41K2K3K1K2K程序空间段0段4段2内存实空间1000202440716120919210215段3段式虚拟存储器段表起始地址段表基址寄存器段号段内地址段表虚地址段表项地址实地址内存地址+优点：段的分界与程序逻辑性相符，便于程序管理。缺点：段长不一，主存空间分配麻烦，存在段间零头。段页式虚拟存储器程序按逻辑结构先分段，段内再划分为若干大小相等的页，内存也划分为同样大小的页。地址变换机构——段表、页表段表：每个程序一个页表：每段一个优点兼备页式和段式系统的优点缺点地址映射过程中需要多次查表多道程序的段页式地址变换SASBSC基址寄存器逻辑地址12dC基号段号页号页内地址+b程序C段表SA+0SA+1SA+2SA+3程序A段表SC+0SC+1SC+2…ca+b+0b+1b+210页表a段b段c段a+0a+1c+0c+178物理地址10物理页号d页内地址虚拟存储器的页面替换算法当产生页面失效时，需要进行页面替换，区别于Cache的替换至少要访问外存一次，速度慢。由操作系统软件实现页面替换选择余地大，属于一个进程的页面都可替换。虚拟存储器中的替换策略LRU算法LFU算法FIFO算法虚拟存储器的页面替换算法【例7】假设主存只有a,b,c三个页框，组成a进c出的FIFO队列，进程访问页面的序列是0，1，2，4，2，3，0，2，1，3，2号。若采用①FIFO算法，②FIFO算法+LRU算法，用列表法分别求两种替换策略情况下的命中率。命中

命中

命中

120