第五 章-存储系统cache

1、5.3 并行主存储器 所谓并行主存储器，是指在一个主存周期内可以并行读取多个数据字的主存储器。通常采用单体多字和交叉存取方式。 寻址方式有单体多字寻址方式、多体存储器的寻址方式和多体交叉寻址方式。下一页上一页 当并行的存储器共用一套地址寄存器和地址译码电路时称为单体方式，其结构原理图如下。下一页上一页单体多字寻址方式 多个并行存储器与同一地址寄存器连接，所以同时被一个单元地址驱动，一次访问读出的是沿n个存储器顺序排列的n个字，故也称单体多字方式。与单体单字结构的存储器相比，单体多字寻址方式在存取速度方面有明显的优点，因为，单体单字存储器的每一个主存周期只能读出一条指令或一个数据，在取指和读取数

2、据的周期内，CPU处于等待状态，因此工作效率低。在本例所示的单体4字的寻址方式中，一次能读出4个字长为w位的数据或指令，然后再以单字长的形式送给CPU执行。当然，若处理的数据不是连续地存放在主存中，或者在程序中经常使用转移指令，单体多字寻址方式的效果就不显著了。下一页上一页下一页上一页多体存储器的寻址方式下图是多体存储器原理图下一页上一页 计算机系统中的大容量主存是由多个存储体组成的，每个存储体都有自己的读写线路、地址寄存器和数据寄存器，能以同等的方式与CPU交换信息，每个存储体容量相等，它们既能同时工作又独立编址。图中MAR为模块地址寄存器，MDR为模块数据寄存器，主存地址寄存器的高位表示模

3、块号，低位表示块内地址。这种结构的寻址方式有利于并行处理，能够实现多个分体的并行操作，一次访问并行处理的n个字，不像单体方式那样一定是沿存储器顺序排列的存储单元内容，而是分别由各分体的地址寄存器指示的存储单元的内容。因为各分体工作独立，因此，只要进行合理的调度，就能实现并行处理，两个存储体可以同时进行不同的操作。例如一个存储体被CPU访问时，另一个存储体可用来与外部设备进行直接存储器存取（DMA）操作。 多体交叉是多体存储器的另一种组织形式，下面以一个四体交叉存储器的组织形式为例，来说明多体交叉存储器的工作原理。下图是四体交叉原理图。下一页上一页多体交叉寻址方式 多体交叉寻址方式与多体存储器寻

4、址方式不同，多体存储器是以高位地址作为模块号，低位地址作为体内地址，每个模块体内地址是连续的；多体交叉寻址方式是以低位地址作为模块号，高位地址作为体内地址，各模块间地址编号采用交叉方式。上图所示的4个模块M0、M1、M2、M3的编址如下表所示。框内序号表示存储单元的地址编号J=0，1，2。下一页上一页 地址连续的两个单元分布在相邻的两个模块中，地址按模块号方向顺序编号。 同一模块内相邻的两个单元地址之差等于n。例如在四体交叉存储器结构方式下，两个单元地址之差等于4。 任何一个存储单元的二进制地址编号的末2位正好指示该单元所属模块的编号，访问主存时只要判断这几位就能决定访问的是那个存储模块。在四

5、体交叉存储器结构方式下，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的替换策略及写操作策略中央处理器主存外存cacheCPUM1M2M3辅助硬件辅助软硬件5.5.1

6、多级存储体系结构为解决存储容量、存取速度和价格之间的矛盾,通常将各种不同存储容量、不同存取速度的存储器,按一定的体系结构组织起来,形成一个统一整体.典型的三级存储系统:图5.25 三级存储系统示意图 Cache-主存层次 Cache一般由SRAM构成,容量小,存取速度快，依据程序局部性原理,存放的是主存中当前最需要执行的信息副本. 目的：主存容量不足的问题. 利用辅助硬件和操作系统中的存储管理软件,将 主存和辅存构成一个整体.目的：解决CPU和主存速度不匹配的问题. 主存-辅存层次 总体效果：存取速度接近Cache,而存储容量接 近于辅存,整体价格也较合理.5.5 Cache存储器5.5.1

7、多级存储体系结构5.5.2 Cache工作原理5.5.3 主存与Cache的地址映射和地址变换5.5.4 Cache的替换策略及写操作策略1. 问题的提出避免 CPU “空等” 现象CPU 和主存（DRAM）的速度差异缓存CPU主存容量小速度高容量大速度低字块主存块 调入 缓存主存块与缓存块 建立 了对应关系标记记录 与某缓存块建立了对应关系的 主存块号命中未命中主存块与缓存块 未建立 对应关系主存块 未调入 缓存2. Cache的命中率命中率CPU 欲访问的信息在 Cache 中的 比率命中率 与 Cache 的 容量 与 块长 有关 命中率CPU 欲访问的信息在 Cache 中的 比率命中

8、率 与 Cache 的 容量 与 块长 有关 Cache 主存系统的效率效率 e 与 命中率 有关 设 Cache 命中率 为 h，访问 Cache 的时间为 tc ， 访问 主存 的时间为 tm 则 e = 100% tc h tc+ (1h) tm 访问 Cache 的时间 平均访问时间 e = 100%3. Cache 的 读 操作 访问Cache取出信息送CPU 访问主存取出信息送CPU将新的主存块调入Cache中执行替换算法 腾出空位 结束命中？Cache满？CPU发出访问地址 开始是否是否4. Cache 的基本结构Cache替换机构Cache存储体主存Cache地址映像变换机构由

9、CPU完成 5.5.2 Cache工作原理Cache的工作机制 Cache工作是以程序访问的局部性原理为基础的,即, 一个程序的指令大都顺序存放、顺序执行,与程序相关的数据在存储器中也相对集中.所以程序运行时,尤其有循环程序段和子程序段时,在较短时间区间内,常会对局部范围的存储器频繁访问,而此范围之外的地址访问甚少.这种现象称为程序访问的局部性.把局部范围的主存内容从主存放到一个高速小容量存储器中,使CPU在这一段时间内直接访问它,以减少或不去访问慢速的主存 ,程序运行速度将明显提高. 2. Cache工作原理例:某机主存容量为1MB, Cache容量为8KB,若以字节编址,每512B为一块,

10、则主存有2048块, Cache有16块.块000000H 00001H. 001FFH块2047FFE00HFFE01HFFFFFH主存块00000H 0001H.01FFH块151E00H1E01H1FFFH Cache 块的概念一般将主存和Cache的存储空间分块,每块大小相同,包括相同数量的存储单元. Cache构成及工作过程CPU主存主存地址寄存器MAR主存Cache地址变换机构(块表)Cache存储器Cache地址寄存器替换控制部件ABDB单字宽多字宽不命中命中(块) Cache包括Cache存储器及相应控制部件,全部由硬件组成,速度快,对所有程序员均透明.CAR Cache命中率

11、 设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次,已知Cac

12、he的存取周期为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,命中率也相应提

13、高,但容量太大,成本会变得不合理. 程序的特点 遵循局部性原理的程序在运行时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. 全相联映射:允许主存中的每一个

14、块可以映射到Cache的任何一块位置上.映射过程如下图所示: 一.全相联映射及其地址变换 二者密切相关-地址变换由地址映射方式决定.主存-Cache地址变换:程序运行时,根据地址映射把主存地址变换成Cache地址. 主存-Cache地址映射(mapping):把存放在主存中的程序按某种规则装入Cache中,并依此建立主存地址与Cache地址的对应关系,即块表. 块表存放数据或指令在内存中所在单元地址的存储器,用于判断Cache命中以及实现地址映射,其字数等于Cache的块数.块0 块1块15块0块1块2047Cache主存全相联映射 2.全相联映射方式下的地址变换主存块号块内地址 (1) 主存

15、地址格式: (标志字段)图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 00000000 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 0

16、0001 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1Cache块号块内地址 主存块号转换为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

17、 1 1 1 1主存块号B(标志字段)块内地址WCache块号b块内地址w主存块号BCache块号bBb比较命中MARCAR 图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=

18、j mod m (m为Cache中总块数) 映射规则:主存中任何一组的第i块只能放入Cache 的第i块. 主存第j块(大排块数)和Cache第i块有如下函数关系:1.直接映射:首先,主存在分块的基础上分组,每组大小与Cache的大小相同。二. 直接映射及其地址变换 (2) 缺点:块表的查找时间长,速度慢.(1) 优点:块冲突概率最低,只有当Cache中全部装满后, 才有可能出现块冲突,块分配灵活；其中,商为主存第j块所在主存的组数,余数为在该组的块数.块0块1块15Cache.0组1组127组块 0 块 1 块15 块16块17 块31 块2047主存块2032块2033图5.29 直接映射

19、示意图2.直接联映射方式下的地址变换 Cache块号 组号块内地址Cache块号块内地址组内块号 (2) Cache地址格式:(1) 主存地址格式:块号(0块)块内存储单元(0-511)块号(1块) 块内存储单元( 0-511)0000 0000 001 0 0000 00000000 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 00001 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1 1 1主存地址格式：0000 0000 000 0 0000 00000000 000

20、0 000 1 1 1 1 1 1 1 1 1组号(0-127)组内块号(0-15)(3) 地址变换(将主存地址转换为Cache地址):Cache块号b组号G(标志字段)MARCache块号b块内地址w CAR命中不命中访问主存块内地址W比较组号GCache地址根据CAR的内容访问Cache 主存地址中的“组内块号(Cache块号)+块内地址”= Cache地址注意：在直接映射中,主存组号作为识别是否命中的标志，标志位的长度由主存组数决定.3.直接映射的优缺点：块内地址(9位) 组内块号(4位)组号(7位) Cache地址格式块内地址(9位) 块号(4位)解:(1) 主存地址格式 (1) 分别

21、写出主存地址格式和Cache地址格式; (2) 画出直接映射及地址变换图; (3)主存地址为0022AH的单元在Cache中什么位置?例题:某机主存容量为1MB, Cache容量为8KB，每块512B,如果采用直接映射,请回答:(2)缺点:Cache的空间利用率低,块冲突较多,命中率也低.(1)优点:硬件实现简单,成本低.块0块1块15Cache.0组1组块 0 块 1 块15 块16块17 块31 块2047块2032块2033 127组主存7位4位9位组号G组内块号b块内地址主存地址比较组号不命中,访问主存Cache地址01b15(2) 直接映射及地址变换示意图命中,MARCAR4位9位则

22、根据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

23、MOD 8=2 22 命中 22 MOD 8=6 命中 26 MOD 8=216 不命中 16 MOD 8=04 不命中 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操作状态调进2226调进2226命中2226命中222616调进2241626调进2216264命中2216184替换练习1. 设有一个Cache的容量为2K字,每块16字,在直接映象方式下,求:(1)该Cache可容纳多少个块?

24、(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分成大小相等的组,各组再分成大小相等的块.

25、 主存在分块的基础上分组,每组块数等于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路组相联 块90组1组 2.组相联映射方式下的地址变换块内地址 (Cache组号)(1) 主存地址格式:(主存字块标记) (2) Cache地址格式:块内地址组号组内块号 组号组内块号(3) 地址变换(将主存地址转换为Ca

26、che地址):块内地址组号组内块号块内地址 (Cache组号)(主存字块标记) 组号组内块号主存字块标记组号G块内地址WMAR组号g组内块号b块内地址wCAR比较不命中访问主存命中主存字块标记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. 主存的存取时间 例：假

27、设主存容量为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)在组相联映射方式下, Cach

28、e分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) 主存的可容纳的块数

29、为: 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

30、.3 主存与Cache的地址映射和地址变换5.5.4 Cache的替换策略及写操作策略5.5.4 Cache的替换策略及写操作策略LRU-Least Recently UsedFIFO-First In First OutRAND 常用替换算法: 注意:只有全相联和组相联的高速缓存中有替换策略问题. 替换策略(replacement policy): Cache地址变换中一旦发生不命中,需将主存中一个新块调入Cache,如果此时发生块冲突, 决定从Cache中选择哪一个数据块,并将其从Cache中移去,将新的数据块写入的方法. 一. Cache的替换策略 1. RAND算法 特点:符合局部性原

31、理,命中率较高. 方法:根据局部性原理选择近期用的最少的数据块作为替换的块.具体做法:为每一块设置一个计数器,当某一块命中时,其计数器清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时同时写入主存,使主存与Cac