第五-章__存储系统cache要点课件.ppt

5.3 并行主存储器,所谓并行主存储器，是指在一个主存周期内可以并行读取多个数据字的主存储器。通常采用单体多字和交叉存取方式。寻址方式有单体多字寻址方式、多体存储器的寻址方式和多体交叉寻址方式。,下一页,上一页,当并行的存储器共用一套地址寄存器和地址译码电路时称为单体方式，其结构原理图如下。,下一页,上一页,单体多字寻址方式,多个并行存储器与同一地址寄存器连接，所以同时被一个单元地址驱动，一次访问读出的是沿n个存储器顺序排列的n个字，故也称单体多字方式。与单体单字结构的存储器相比，单体多字寻址方式在存取速度方面有明显的优点，因为，单体单字存储器的每一个主存周期只能读出一条指令或一个数据，在取指和读取数据的周期内，CPU处于等待状态，因此工作效率低。在本例所示的单体4字的寻址方式中，一次能读出4个字长为w位的数据或指令，然后再以单字长的形式送给CPU执行。当然，若处理的数据不是连续地存放在主存中，或者在程序中经常使用转移指令，单体多字寻址方式的效果就不显著了。,下一页,上一页,下一页,上一页,多体存储器的寻址方式,下图是多体存储器原理图,下一页,上一页,计算机系统中的大容量主存是由多个存储体组成的，每个存储体都有自己的读写线路、地址寄存器和数据寄存器，能以同等的方式与CPU交换信息，每个存储体容量相等，它们既能同时工作又独立编址。图中MAR为模块地址寄存器，MDR为模块数据寄存器，主存地址寄存器的高位表示模块号，低位表示块内地址。这种结构的寻址方式有利于并行处理，能够实现多个分体的并行操作，一次访问并行处理的n个字，不像单体方式那样一定是沿存储器顺序排列的存储单元内容，而是分别由各分体的地址寄存器指示的存储单元的内容。因为各分体工作独立，因此，只要进行合理的调度，就能实现并行处理，两个存储体可以同时进行不同的操作。例如一个存储体被CPU访问时，另一个存储体可用来与外部设备进行直接存储器存取（DMA）操作。,多体交叉是多体存储器的另一种组织形式，下面以一个四体交叉存储器的组织形式为例，来说明多体交叉存储器的工作原理。下图是四体交叉原理图。,下一页,上一页,多体交叉寻址方式,多体交叉寻址方式与多体存储器寻址方式不同，多体存储器是以高位地址作为模块号，低位地址作为体内地址，每个模块体内地址是连续的；多体交叉寻址方式是以低位地址作为模块号，高位地址作为体内地址，各模块间地址编号采用交叉方式。上图所示的4个模块M0、M1、M2、M3的编址如下表所示。框内序号表示存储单元的地址编号J=0，1，2。,下一页,上一页,地址连续的两个单元分布在相邻的两个模块中，地址按模块号方向顺序编号。同一模块内相邻的两个单元地址之差等于n。例如在四体交叉存储器结构方式下，两个单元地址之差等于4。任何一个存储单元的二进制地址编号的末2位正好指示该单元所属模块的编号，访问主存时只要判断这几位就能决定访问的是那个存储模块。在四体交叉存储器结构方式下，M0模块的每个单元地址的二进制编码最后两位都是00，M1模块的每个单元地址最后两位都是01，M2模块的每个单元地址最后两位都是02，M3模块的每个单元地址最后两位都是03。同一模块内每个单元地址除去模块号后的高位地址正好是模块内单元的顺序号，由此就可决定访问单元在模块中的位置。,下一页,上一页,n体交叉寻址方式的规则满足以下4点,5.5 Cache存储器,5.5.1 多级存储体系结构,5.5.2 Cache工作原理,5.5.3 主存与Cache的地址映射和地址变换,5.5.4 Cache的替换策略及写操作策略,5.5.1 多级存储体系结构,为解决存储容量、存取速度和价格之间的矛盾,通常将各种不同存储容量、不同存取速度的存储器,按一定的体系结构组织起来,形成一个统一整体.,典型的三级存储系统:,图5.25 三级存储系统示意图,Cache-主存层次,Cache一般由SRAM构成,容量小,存取速度快，依据程序局部性原理,存放的是主存中当前最需要执行的信息副本.,目的：主存容量不足的问题.,利用辅助硬件和操作系统中的存储管理软件,将 主存和辅存构成一个整体.,目的：解决CPU和主存速度不匹配的问题.,主存-辅存层次,总体效果：存取速度接近Cache,而存储容量接 近于辅存,整体价格也较合理.,5.5 Cache存储器,5.5.1 多级存储体系结构,5.5.2 Cache工作原理,5.5.3 主存与Cache的地址映射和地址变换,5.5.4 Cache的替换策略及写操作策略,1.问题的提出,避免 CPU“空等”现象,CPU 和主存（DRAM）的速度差异,容量小速度高,容量大速度低,字,块,主存块 调入 缓存,主存块与缓存块 建立 了对应关系,标记记录 与某缓存块建立了对应关系的 主存块号,命中,未命中,主存块与缓存块 未建立 对应关系,主存块 未调入 缓存,2.Cache的命中率,命中率,CPU 欲访问的信息在 Cache 中的 比率,命中率 与 Cache 的 容量 与 块长 有关,命中率,CPU 欲访问的信息在 Cache 中的 比率,命中率 与 Cache 的 容量 与 块长 有关,Cache 主存系统的效率,效率 e 与 命中率 有关,设 Cache 命中率 为 h，访问 Cache 的时间为 tc，访问 主存 的时间为 tm,3.Cache 的 读 操作,4.Cache 的基本结构,Cache替换机构,Cache存储体,主存Cache地址映像变换机构,由CPU完成,5.5.2 Cache工作原理,Cache的工作机制,Cache工作是以程序访问的局部性原理为基础的,即,一个程序的指令大都顺序存放、顺序执行,与程序相关的数据在存储器中也相对集中.,所以程序运行时,尤其有循环程序段和子程序段时,在较短时间区间内,常会对局部范围的存储器频繁访问,而此范围之外的地址访问甚少.这种现象称为程序访问的局部性.,把局部范围的主存内容从主存放到一个高速小容量存储器中,使CPU在这一段时间内直接访问它,以减少或不去访问慢速的主存,程序运行速度将明显提高.,2.Cache工作原理,例:某机主存容量为1MB,Cache容量为8KB,若以字节编址,每512B为一块,则主存有2048块,Cache有16块.,块0,00000H,00001H,.,001FFH,块2047,FFE00H,FFE01H,FFFFFH,主存,块0,0000H,0001H,.,01FFH,块15,1E00H,1E01H,1FFFH,Cache,块的概念,一般将主存和Cache的存储空间分块,每块大小相同,包括相同数量的存储单元.,Cache构成及工作过程,CPU,主存,主存地址寄存器MAR,主存Cache地址变换机构(块表),Cache存储器,Cache地址寄存器,替换控制部件,AB,DB,单字宽,多字宽,不命中,命中,(块),Cache包括Cache存储器及相应控制部件,全部由硬件组成,速度快,对所有程序员均透明.,CAR,Cache命中率,设Nc为Cache 完成存取的总次数,Nm为主存完成存取的总次数,h为命中率,则有:,设r=tm/tc表示主存慢于Cache的倍率,e表示访问效率,则有:,高速缓存命中率:CPU访存时,信息恰巧在Cache中的概率.,h=Nc/(Nc+Nm),若tc表示命中时的Cache访问时间,tm表示未命中时的主存访问时间,1-h表示未命中率,则Cache/主存系统的平均访问时间ta为:,ta=htc+(1-h)tm,e=tc/ta=tc/htc+(1-h)tm=1/h+(1-h)r=1/r+(1-r)h,例：CPU执行一段程序时,Cache完成存取的次数1900次,主存完成存取的次数为100次,已知Cache的存取周期为1ns,主存存取周期为5ns,求Cache/主存系统的效率和平均访问时间.,解：h=Nc/(Nc+Nm)=1900/(1900+100)=0.95 r=tm/tc=5ns/1ns=5 e=1/r+(1-r)h=1/5+(1-5)X0.95=83.3%ta=tc/e=1ns/0.833=1.2ns,例:某计算机的存储系统由Cache和主存组成,某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是().A.5%B.9.5%C.50%D.95%,影响 Cache命中率的因素 Cache的大小 容量相对较大的Cache,命中率也相应提高,但容量太大,成本会变得不合理.程序的特点 遵循局部性原理的程序在运行时Cache的命中率也会很高,相反,在程序中频繁且无规则地使用Call或JMP命令,将严重影响基于Cache的系统性能.Cache的组织结构 Cache组织结构的好坏,对命中率也会产生较大影响.Cache的组织结构有三种类型:全相联映射、直接映射和组相联映射.,5.5 Cache存储器,5.5.1 多级存储体系结构,5.5.2 Cache工作原理,5.5.3 主存与Cache的地址映射和地址变换,5.5.4 Cache的替换策略及写操作策略,5.5.3 主存与Cache的地址映射和地址变换,1.全相联映射:允许主存中的每一个块可以映射到Cache的任何一块位置上.映射过程如下图所示:,一.全相联映射及其地址变换,二者密切相关-地址变换由地址映射方式决定.,主存-Cache地址变换:程序运行时,根据地址映射把主存地址变换成Cache地址.,主存-Cache地址映射(mapping):把存放在主存中的程序按某种规则装入Cache中,并依此建立主存地址与Cache地址的对应关系,即块表.,块表存放数据或指令在内存中所在单元地址的存储器,用于判断Cache命中以及实现地址映射,其字数等于Cache的块数.,块0,块1,块15,块0,块1,块2047,Cache,主存,全相联映射,2.全相联映射方式下的地址变换,主存块号,块内地址,(1)主存地址格式:,(标志字段),图5.26 全相联映射示意图,例:某机主存容量为1MB,Cache容量为8KB，若以字节编址，每512B为一块,则主存有2048块,Cache有16块。主存地址格式：0000 0000 000 0 0000 0000 0000 0000 000 1 1 1 1 1 1 1 1 1,块号(0块),块内存储单元(0-511),块号(1块),块内存储单元(0-511),0000 0000 001 0 0000 0000,0000 0000 001 1 1 1 1 1 1 1 1 1,块号(2047块),块内存储单元(0-511),1 1 1 1 1 1 1 1 111 0 0000 0000,1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1,Cache块号,块内地址,主存块号转换为Cache块号,块内地址不变,(3)地址变换(将主存地址转换为Cache地址):,(2)Cache地址格式:,块号(0块),块内存储单元(0-511),块号(1块),块内存储单元(0-511),0 00 1 0 0000 0000,0 00 1 1 1 1 1 1 1 1 1 1,块号(15块),块内存储单元(0-511),1 1 1 1 0 0000 0000,1 1 1 1 1 1 1 1 1 1 1 1 1,0 00 0 0 0000 0000,0 00 0 1 1 1 1 1 1 1 1 1,主存块号B(标志字段),块内地址W,Cache块号b,块内地址w,主存块号B,Cache块号b,B,b,比较,命中,MAR,CAR,图5.27 全相联映射的地址变换,块表(块表容量的计算：字数等于高缓块数，字长由主存块数和高缓块数决定),不命中则访问主存,注意:在全相联映射中,主存块号作为识别是否命中的标志,标志位的长度由主存块数决定.,字块0,字块1,字块2C-1,标记,标记,标记,设Cache有2C-1块,主存有2m-1块,即Cache块地址有c位,主存块地址有m位.,字块0,字块1,字块2C-1,字块2m-1,主存地址格式：,主存字块标记,块内地址,m位,图5.28 全相联映射的另一种常见图解,3.全相联映射的优缺点,i=j mod m(m为Cache中总块数),映射规则:主存中任何一组的第i块只能放入Cache 的第i块.主存第j块(大排块数)和Cache第i块有如下函数关系:,1.直接映射:首先,主存在分块的基础上分组,每组大小与Cache的大小相同。,二.直接映射及其地址变换,(2)缺点:块表的查找时间长,速度慢.,(1)优点:块冲突概率最低,只有当Cache中全部装满后,才有可能出现块冲突,块分配灵活；,其中,商为主存第j块所在主存的组数,余数为在该组的块数.,.,.,.,0组,1组,127组,块 0,块 1,块15,块16,块17,块31,块2047,主存,块2032,块2033,图5.29 直接映射示意图,2.直接联映射方式下的地址变换,Cache块号,组号,块内地址,Cache块号,块内地址,组内块号,(2)Cache地址格式:,(1)主存地址格式:,块号(0块),块内存储单元(0-511),块号(1块),块内存储单元(0-511),0000 0000 001 0 0000 0000,0000 0000 001 1 1 1 1 1 1 1 1 1,块号(2047块),块内存储单元(0-511),1 1 1 1 1 1 1 1 111 0 0000 0000,1 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1,主存地址格式：,0000 0000 000 0 0000 0000,0000 0000 000 1 1 1 1 1 1 1 1 1,组号(0-127),组内块号(0-15),(3)地址变换(将主存地址转换为Cache地址):,Cache块号b,组号G(标志字段),MAR,Cache块号b,块内地址w,CAR,命中,不命中访问主存,块内地址W,比较,组号G,Cache地址,根据CAR的内容访问Cache,主存地址中的“组内块号(Cache块号)+块内地址”=Cache地址,注意：在直接映射中,主存组号作为识别是否命中的标志，标志位的长度由主存组数决定.,3.直接映射的优缺点：,块内地址(9位),组内块号(4位),组号(7位),Cache地址格式,块内地址(9位),块号(4位),解:(1)主存地址格式,(1)分别写出主存地址格式和Cache地址格式;(2)画出直接映射及地址变换图;(3)主存地址为0022AH的单元在Cache中什么位置?,例题:某机主存容量为1MB,Cache容量为8KB，每块512B,如果采用直接映射,请回答:,(2)缺点:Cache的空间利用率低,块冲突较多,命中率也低.,(1)优点:硬件实现简单,成本低.,.,.,.,0组,1组,块 0,块 1,块15,块16,块17,块31,块2047,块2032,块2033,127组,主存,7位,4位,9位,组号G,组内块号b,块内地址,主存地址,比较,组号,不命中,访问主存,Cache地址,0,1,b,15,(2)直接映射及地址变换示意图,命中,MAR,CAR,4位,9位,则根据CAR的内容访问Cache,地址映射,地址变换,(3)主存地址为0022AH的单元在Cache中什么位置,组(0组),组内块号(1块),块内地址(42字),另外一种求法:,0022AH=(0000 0000 0010 0010 1010)2,因为主存第j块和Cache第i块有如下函数关系:i=j mod m(m为Cache中总块数)这里,j=1,m=16,所以i=1 mod 16=1,例:设一个Cache中有8个块,访问主存进行读操作的块地址序列为22、26、22、26、16、4、16、18,求每次访问后Cache中的内容.解：,地址,命中与否,地址转换关系,不命中 22 MOD 8=6 不命中 26 MOD 8=2,22 命中,22 MOD 8=6,命中 26 MOD 8=2,16 不命中 16 MOD 8=0,4 不命中 4 MOD 8=4,16 命中 16 MOD 8=0,18 不命中 18 MOD 8=2,直接映象下Cache访问情况,直接映象的块分配情况,访问顺序 1 2 3 4 5 6 7 8地址 22 26 22 26 16 4 16 18块分配 情况,22,操作状态,调进,22,26,调进,22,26,命中,22,26,命中,22,26,16,调进,22,4,16,26,调进,22,16,26,4,命中,22,16,18,4,替换,练习1.设有一个Cache的容量为2K字,每块16字,在直接映象方式下,求:(1)该Cache可容纳多少个块?(2)如果主存的容量为256K字,则有多少个块?(3)主存的地址格式?Cache的地址格式?(4)主存中的第032AB单元映象到Cache中哪一块?,练习2.设计算机的存储器为64K16位,直接地址映射的Cache容量为1K字,每块4字,问:(1)主存中地址的标志字段、块号和块内地址字段分别有多少位？（2）Cache中可装入多少块数据？,三.组相联映射及其地址变换,n路组相联:每组中有n块.,有全相联映射:主存第g组第i块可映射到Cache第i组中任一块的位置.,有直接映射:主存第g组第i块只能映射到Cache第i组.,1.组相联映射:Cache分成大小相等的组,各组再分成大小相等的块.主存在分块的基础上分组,每组块数等于Cache 组数.,映射规则:Cahe分为m组,每组有n块,则有以下关系:i=j mod m 其中,i为Cache组号,j为主存块号(大排).商为主存第j块所在组数,余数为该组所在块数.,块0,块1,块2,块3,块14,块15,0组,1组,7组,Cache,主存,块0,块1,块2,块3,块7,块8,块15,块16,块17,块2047,图5.30 组相联映射示意图,同上例,采用2路组相联,块9,0组,1组,2.组相联映射方式下的地址变换,块内地址,(Cache组号),(1)主存地址格式:,(主存字块标记),(2)Cache地址格式:,块内地址,组号,组内块号,组号,组内块号,(3)地址变换(将主存地址转换为Cache地址):,块内地址,组号,组内块号,块内地址,(Cache组号),(主存字块标记),组号,组内块号,主存字块标记,组号G,块内地址W,MAR,组号g,组内块号b,块内地址w,CAR,比较,不命中,访问主存,命中,主存字块标记,Cache组内块号b,访问Cache,图5.31 组相联映射的地址变换示意图,块表,例:某计算机的Cache共有16块,采用2路组相联(即每组2块).每个主存块大小为32字节,按字节编址.主存129号单元所在主存应装入到得Cache组号是().A.0 B.2 C.4 D.6 例:在下列因素中,与Cache的命中率无关的是().A.Cache块的大小 B.Cache的容量 C.主存的存取时间,例：假设主存容量为512K16位,Cache容量为409616位,块长为4个16位的字,访存地址为字地址.(1)在直接映射方式下,设计主存地址格式.(2)在全相联映射方式下,设计主存地址格式.(3)在2路组相联映射方式下,设计主存地址格式.解:(1)在直接映射方式下,Cache分4096/4=210块,主存分219/4=217块,主存分219/212=27组.故主存地址格式:,主存组数(7位),组内块数(10位),块内地址(2位),(2)在全相联方式下,Cache分4096/4=210块,主存分219/4=217块.故主存地址格式:,主存块数(17位),块内地址(2位),(3)在组相联映射方式下,Cache分4096/4=210块,2块一组,Cache分210/2=29组;主存分219/4=217块,每组分29块,主存分217/29=28组.故主存地址格式:,块内地址,(Cache组号),(主存字块标记),组号(8位),组内块号(9位),(2位),练习1.设有一个Cache的容量为2K字,每块16字,在直接映象方式下,求:(1)该Cache可容纳多少个块?(2)如果主存的容量为256K字,则有多少个块?(3)主存的地址格式?Cache的地址格式?(4)主存中的第032ABH单元映象到Cache中哪一块?,解:(1)Cache可容纳的块数为:2K/16=27=128(块),(2)主存的可容纳的块数为:256K/16=214(块),(3)主存地址格式为:,块内地址(4位),组内块号(7位),组号(7位),Cache地址格式为:,块内地址(4位),组内块号(7位),(4)主存中的032ABH单元:032ABH=(0000 0011 0010 1010 1011)2,6组,42块,11字,另外一种求法:因为主存第j块和Cache第i块有如下函数关系:i=j mod m(m为Cache中总块数),这里,j=29+28+25+23+21=810,m=128,所以i=1 mod m=810 mod 128=42,5.5 Cache存储器,5.5.1 多级存储体系结构,5.5.2 Cache工作原理,5.5.3 主存与Cache的地址映射和地址变换,5.5.4 Cache的替换策略及写操作策略,5.5.4 Cache的替换策略及写操作策略,LRU-Least Recently Used,FIFO-First In First Out,RAND,常用替换算法:,注意:只有全相联和组相联的高速缓存中有替换策略问题.,替换策略(replacement policy):Cache地址变换中一旦发生不命中,需将主存中一个新块调入Cache,如果此时发生块冲突,决定从Cache中选择哪一个数据块,并将其从Cache中移去,将新的数据块写入的方法.,一.Cache的替换策略,1.RAND算法,特点:符合局部性原理,命中率较高.,方法:根据局部性原理选择近期用的最少的数据块作为替换的块.具体做法:为每一块设置一个计数器,当某一块命中时,其计数器清0,其它各块的计数器增1,当需要替换时,将计数值大的块替换出.,3.LRU算法,特点:较简单,但没有体现程序局部性规律,不能提高Cache命中率.,方法:选择最早调入Cache的块进行替换.,2.FIFO算法,方法:随机地确定替换块.特点:容易实现,执行速度快,但没有体现程序局部性规律,不能提高Cache命中率.,二、Cache的写操作策略,Cache内容是主存部分内容的副本,在命中的情况下,如果CPU对Cache写入,改变了Cache(dirty block)的内容,如何保证主存内容与Cache内容一致.,缺点:当CPU向主存写操作时,Cache无高速缓冲功能,降低了Cache的功效.,优点:写主存与写Cache同步.,1.直达法(write through)(通过式写入):每次写入Cache时同时写入主存,使主存与Cache相关块内容始终保持一致.,2.写回法(write back)(标志交换方式):Cache中每一块各作一个标记(清未修改过;浊修改过),命中需将信息写入主存时,暂只写入 Cache,并不写入主存,只有当该块需要从Cache中替换出来时,若其标记为”浊”,再一次性写入主存.,缺点:存在Cache与主存数据不一致的隐患.,优点:减少对主存的写操作次数,工作速度较快.,作业1:某一Cache-主存采用组相联的方法进行地址转换.Cache容量为8KB,每组包括4个块,块大小为128W.主存容量为512KW.要求:(1)画出主存与Cache的地址格式,并说明每个字段由多少位构成;(2)说明CPU访问内存的过程.,作业2:(2003年东大考研题 7分)某Cache-主存系统采用四路组相联映射的方法进行地址转换.块的大小为128W,Cache容量为8KW,主存容量为512KW.设访存地址为字地址.要求画出主存与Cache的地址格式,并确定地址格式中各字段的位数.,作业3：某机主存容量为4MB，Cache容量为16KB，每块包含8B，设计一个四路组相联映射的Cache组织，要求：(1)画出主存地址字段中各段的位数；(2)设Cache的初态为空，CPU依次从主存第0、1、2、99号单元读出100B(主存一次读出一个字节)，并重复按此次序读8次，问命中率是多少？(3)若Cache的速度是主存的6倍，试问有Cache和无Cache相比，速度提高多少倍？,解1)主存容量为4MB，按字节编址，主存地址为22位，地址格式如下：,块内地址(3位),组号(10位),组内块号(9位),(2)由于每块有8个存储单元,所以主存第0、1、2、99号存储单元分别在主存第012块中,采用4路组相联映射将分别映射到Cache第0 12组中.因Cache起始状态为空,所以第一次读时每一块中的第一个单元没有命中,但后面7次每个单元均可以命中.命中率h=Nc/(Nc+Nm)=(100-13+7100)/800=98.4,块0,块1,块2,块3,块511,块512,块1023,块0,块1,块2,块3,块2044,块2045,块2046,块2047,Cache,主存,0组,511组,块219-1,0组,1组,设Cache的存取周期为T，则主存的存取周期为6T。有Cache的平均访问时间=hTc+(1-h)Tm=0.984Tc+(1-0.984)6T=1.08T 无Cache的访存时间为6T 则速度提高倍数=6/1.08=5.56倍,