《第四章存储子系统cache (2)》由会员分享，可在线阅读，更多相关《第四章存储子系统cache (2)（46页珍藏版）》请在金锄头文库上搜索。
1、高速缓冲存储器高速缓冲存储器一、概述一、概述1. 问题的提出问题的提出避免避免 CPU “空等空等” 现象现象CPU 和主存的速度差异和主存的速度差异缓存缓存CPU主存主存容量小容量小速度高速度高容量大容量大速度低速度低程序访问的局部性原理：程序访问的局部性原理：由于编程时指令地址的分布基本上连续，对循由于编程时指令地址的分布基本上连续，对循环程序段的执行往往要重复若干遍；在一个较环程序段的执行往往要重复若干遍；在一个较短的时间间隔内，对存储器的访问大部分将集短的时间间隔内，对存储器的访问大部分将集中在一个局部区域中，而对此地址范围之外的中在一个局部区域中，而对此地址范围之外的地址很少访问。这
2、种现象称之为局部性原理。地址很少访问。这种现象称之为局部性原理。2. Cache 的工作原理的工作原理(1) 主存和缓存的编址主存和缓存的编址主存和缓存按块存储主存和缓存按块存储 块的大小相同块的大小相同B 为块长为块长 主存块号主存块号主存储器主存储器012m1字块字块 0字块字块 1字块字块 M1主存块号主存块号块内地址块内地址m位位b位位n位位M块块B个字个字缓存块号缓存块号块内地址块内地址c位位b位位C块块B个字个字 字块字块 0字块字块 1字块字块 C1012c1标记标记Cache缓存块号缓存块号(2) 命中与未命中命中与未命中缓存共有缓存共有 C 块块主存共有主存共有 M 块块M
3、C主存块主存块 调入调入 缓存缓存主存块与缓存块主存块与缓存块 建立建立 了对应关系了对应关系用用 标记记录标记记录 与某缓存块建立了对应关系的与某缓存块建立了对应关系的 主存块号主存块号命中命中未命中未命中主存块与缓存块主存块与缓存块 未建立未建立 对应关系对应关系主存块主存块 未调入未调入 缓存缓存(3) Cache 的命中率的命中率CPU 欲访问的信息在欲访问的信息在 Cache 中的中的 比率比率命中率命中率 与与 Cache 的的 容量容量 与与 块长块长 有关有关 一般每块可取一般每块可取 4 8 个字个字块长取一个存取周期内从主存调出的信息长度块长取一个存取周期内从主存调出的信息
4、长度在一个程序执行期间，设在一个程序执行期间，设NcNc表示表示cachecache完成存取的完成存取的总次数，总次数，NmNm表示主存完成存取的总次数，表示主存完成存取的总次数，h h定义为定义为命中率，则有命中率，则有 h=h=NcNc/ /（Nc+NmNc+Nm) )(4) Cache 主存系统的效率主存系统的效率访问效率访问效率 e 与与 命中率命中率 有关有关若若tctc表示命中时的表示命中时的cachecache访问时间，访问时间，tmtm表示未命中时的表示未命中时的主存访问时间，主存访问时间，1-h1-h表示未命中率，则表示未命中率，则cache/cache/主存系统主存系统的平
5、均访问时间的平均访问时间tata为：为：tata=h*=h*tctc+ +（1-h)tm1-h)tm则则 e = 100% tc h tc+ (1h) tm 访问访问 Cache 的时间的时间 平均访问时间平均访问时间 e = 100%例：例：CPUCPU执行一段程序时，执行一段程序时，cachecache完成存取的完成存取的次数为次数为19001900次，主存完成存取的次数为次，主存完成存取的次数为100100次，次，已知已知cachecache存取周期为存取周期为50ns50ns，主存存取周期为，主存存取周期为250ns250ns，求，求cache/cache/主存系统的效率和平均访问主存
6、系统的效率和平均访问时间。时间。3. Cache 的基本结构的基本结构Cache替换机构替换机构Cache存储体存储体主存主存Cache地址映射地址映射变换机构变换机构由由CPU完成完成4. Cache 的的 读写读写 操作操作 访问访问Cache取出信息送取出信息送CPU 访问主存访问主存取出信息送取出信息送CPU将新的主存块将新的主存块调入调入Cache中中执行替换算法执行替换算法 腾出空位腾出空位 结束结束命中？命中？Cache满？满？CPU发出访问地址发出访问地址 开始开始是是否否是是否否读读Cache 和主存的一致性和主存的一致性 4. Cache 的的 读写读写 操作操作写写 写直
7、达法写直达法（Write through） 写回法写回法（Write back） 写操作时数据既写入写操作时数据既写入Cache又写入主存又写入主存 写操作时只把数据写入写操作时只把数据写入 Cache 而不写入主存而不写入主存当当 Cache 数据被替换出去时才写回主存数据被替换出去时才写回主存 写操作时间就是访问主存的时间写操作时间就是访问主存的时间，读操作时不，读操作时不涉及对主存的写操作，更新策略比较容易实现涉及对主存的写操作，更新策略比较容易实现写操作时间就是访问写操作时间就是访问 Cache 的时间的时间，读操作读操作 Cache 失效发生数据替换时，失效发生数据替换时，被替换的块
8、需写回主存，增加了被替换的块需写回主存，增加了 Cache 的复杂性的复杂性二、二、Cache 主存的地址映射与地址变换主存的地址映射与地址变换地址映象：把主存地址空间映象到地址映象：把主存地址空间映象到CacheCache地址空间，地址空间，具体地说就是把存放在主存中的程序按照某种规则装具体地说就是把存放在主存中的程序按照某种规则装入入CacheCache，并建立主存地址与，并建立主存地址与CacheCache地址之间的对应关地址之间的对应关系。系。地址变换：把程序装入地址变换：把程序装入CacheCache之后，在实际运行过程之后，在实际运行过程中，把主存地址如何变换成中，把主存地址如何变
9、换成CacheCache地址。地址。1. 全相联映射全相联映射主存主存 中的中的 任一块任一块 可以映射到可以映射到 缓存缓存 中的中的 任一块任一块设设Cache块容量为块容量为Cb，主存块容量为，主存块容量为Mb，则主存与，则主存与Cache之间存在之间存在Cb*Mb中映象关系中映象关系块块Mb1块块Cb1块块1 块块0块块Cb1块块1块块0Cache 存储器存储器主存储器主存储器引入目录表来存放映象关系，则目录表容量为引入目录表来存放映象关系，则目录表容量为CbCb，字长，字长为为CacheCache地址中的块号长度与主存地址中的块号长度之地址中的块号长度与主存地址中的块号长度之和再加上
10、一个有效位。和再加上一个有效位。块号块号B | B | 块内地址块内地址W W主存地址主存地址块号块号b| b| 块内地址块内地址W W B b 1 B b 1 B b 1 B b 1 B b 1 B b 1主存块号主存块号 CacheCache块号块号 有效位有效位相联比较相联比较命中命中有效位为有效位为1 1：表示目录表中由主存块号：表示目录表中由主存块号B B与与CacheCache块号块号b b之间的映像关系是有效的，也表示在之间的映像关系是有效的，也表示在CacheCache的第的第b b块块中存放的数据是主存第中存放的数据是主存第B B块数据的正确副本。块数据的正确副本。有效位为有
11、效位为0 0：表示目录表中由主存块号表示目录表中由主存块号B B与与CacheCache块号块号b b之间的映像关系是无效的，或者说他们之间没有任之间的映像关系是无效的，或者说他们之间没有任何关系，何关系， CacheCache的第的第b b块中存放的数据也不是主存第块中存放的数据也不是主存第B B块数据的正确副本。块数据的正确副本。特点：特点：块的冲突小，块的冲突小，CacheCache利用率高，但硬件代价高，影利用率高，但硬件代价高，影响响CacheCache的速度的速度2.直接映射直接映射主存中一块只能映像到主存中一块只能映像到cache的一个特定块中的一个特定块中,设主存设主存块号为块
12、号为B，Cache块号为块号为b，则映象关系表示为，则映象关系表示为b=B mod CbCb是是Cache的块容量，的块容量，Mb是主存的块容量，是主存的块容量，Me是主是主存的区容量存的区容量把主存按把主存按Cache的大小分区，每个分区的块数与的大小分区，每个分区的块数与Cache总块数正好相等。直接映象只能把主存各区中相对总块数正好相等。直接映象只能把主存各区中相对块号相同的那些块映像到块号相同的那些块映像到Cache中同一块号的那个特中同一块号的那个特定块中。定块中。 块块Mb1块块Mb-Cb+1 块块2Cb1 块块Cb+1 块块Cb块块 Cb1 块块1 块块0主存储体主存储体 块块
13、1 块块 0块块 Cb1Cache存储体存储体区区0 0区区1 1区区Me-1Me-1区号区号E |E |块号块号B | B | 块内地址块内地址W W主存地址主存地址块号块号b | b | 块内地址块内地址W W E 1 E 1 区号区号E(E(按地址访问按地址访问) ) 有效位有效位比较比较相等相等区号存储器区号存储器相等相等不等不等比较结果相等，有效位为比较结果相等，有效位为1 1，命中。，命中。比较结果相等，有效位为比较结果相等，有效位为0 0， CacheCache处该块作废。处该块作废。比较结果不等，有效位为比较结果不等，有效位为1 1，CacheCache处该块有用。处该块有用。
14、比较结果不等，有效位为比较结果不等，有效位为0 0，CacheCache处该块为空。处该块为空。特点：特点：冲突率高，冲突率高，CacheCache命中命中率低。率低。3. 组相联映射组相联映射把主存和把主存和CacheCache按同样大小划分成块，另外还把主存按同样大小划分成块，另外还把主存和和CacheCache按同样大小划分成组，每一组由相同的块数按同样大小划分成组，每一组由相同的块数组成。组成。主存组与主存组与CacheCache组采用直接映像，两个对应组内部采组采用直接映像，两个对应组内部采用全相联方式。用全相联方式。主存储体主存储体Cache存储体存储体区区0 0区区Me-1Me-
15、1块块0 0块块Gb-1Gb-1块块GbGb块块2Gb-12Gb-1块块Cb-GbCb-Gb块块Cb-1Cb-1块块0 0块块Gb-1Gb-1块块GbGb块块2Gb-12Gb-1块块Cb-GbCb-Gb块块Cb-1Cb-1组组0 0组组1 1组组Cg-1Cg-1组组0 0组组0 0组组Cg-1Cg-1区号区号E |E |组号组号G|G|组内块号组内块号B | B | 块内地址块内地址W W主存地址主存地址组号组号g | g | 组内块号组内块号b|b|块内地址块内地址w w GbGb个块个块 区号区号E,E,组内块号组内块号B B 组内块号组内块号b b相联比较相联比较相等相等块表存储器块表存
16、储器相等相等不等不等例：例：设主存容量设主存容量1MB1MB，CacheCache容量容量16KB16KB，块的大小为，块的大小为512B512B，采用直接地址映像方式：采用直接地址映像方式：1 1）写出）写出CacheCache的地址格式的地址格式2 2）写出主存的地址格式）写出主存的地址格式3 3）区号表的容量为多大？（不考虑有效位）区号表的容量为多大？（不考虑有效位）4 4）主存地址为）主存地址为CDE8FHCDE8FH的单元在的单元在CacheCache的什么位置？的什么位置？5 5）若将本例改为全相联地址映像方式，又该如何？）若将本例改为全相联地址映像方式，又该如何？三、替换算法三、
17、替换算法2. 先进先出先进先出 （ FIFO ）算法）算法 按调入按调入Cache的先后决定淘汰的顺序，即在的先后决定淘汰的顺序，即在需要更新时总是最先淘汰最先调入需要更新时总是最先淘汰最先调入Cache的的页面内容。页面内容。1.1.随机替换随机替换随机替换策略实际上是不要什么算法，简单随机替换策略实际上是不要什么算法，简单地根据一个随机数，选取地根据一个随机数，选取CacheCache中的一块替换中的一块替换掉。掉。3.近期最少使用（近期最少使用（ LRU）算法）算法选择近期最少访问的页面作为被替换的页面选择近期最少访问的页面作为被替换的页面4.最优化（最优化（ OPT）算法）算法以以将将
18、来来使使用用最最少少作作为为替替换换目目标标。是是一一种种理理想想的的算算法法，实实现现不不了了，只只能能作作为为衡衡量量其其它它算算法优劣的标准。法优劣的标准。LRULRU算法计数器的使用及管理规则是：算法计数器的使用及管理规则是：1 1）被装入或被替换的块，其对应计数器清为）被装入或被替换的块，其对应计数器清为0 0，同，同组中其他所有块所属计数器加组中其他所有块所属计数器加1 1；2 2）命中的块，其对应的计数器清为）命中的块，其对应的计数器清为0 0，同组中其他，同组中其他所有计数器中，凡是计数器值小于命中块所属计数所有计数器中，凡是计数器值小于命中块所属计数器原来值的都加器原来值的都
19、加1 1，其他计数器不变；，其他计数器不变；3 3）需要替换时，在同组的所有计数器中选择计数）需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块就是要被替换的块。值最大的计数器，它所对应的块就是要被替换的块。例：一个程序共有例：一个程序共有5 5个页面，分别为个页面，分别为P1-P5,P1-P5,程序执行程序执行过程中的页地址流（即程序执行中依次用到的页面）过程中的页地址流（即程序执行中依次用到的页面）如下：如下：P1P2P1P5P4P1P3P4P2P4P1P2P1P5P4P1P3P4P2P4，假设分配给这个程序，假设分配给这个程序的的CacheCache共共3 3个页面，则
20、使用个页面，则使用FIFO,LRUFIFO,LRU时命中率为多少时命中率为多少？提高存储系统性能的其它措施提高存储系统性能的其它措施一、双端口存储器一、双端口存储器双端口存储器由于同一个存储器具有两组相互独双端口存储器由于同一个存储器具有两组相互独立的读写控制电路而得名。由于进行并行的独立的读写控制电路而得名。由于进行并行的独立操作，因而是一种高速工作的存储器。立操作，因而是一种高速工作的存储器。地址寄存器地址寄存器地址寄存器地址寄存器译码译码译码译码存储体存储体地址地址A A地址地址B B数据数据A A数据数据B B无冲突读写控制无冲突读写控制 当当两两端端口口地地址址不不同同时时，在在两两
21、端端口口上上进进行行读读写写，不不会会发发生冲突生冲突，可同时进行读写。，可同时进行读写。有冲突读写控制有冲突读写控制 问题问题 当两个端口同时存取同一存储单元时，会发生端当两个端口同时存取同一存储单元时，会发生端口间的读写冲突。口间的读写冲突。 解解决决方方法法 设设置置BUSYBUSY标标志志，采采用用仲仲裁裁逻逻辑辑，由由芯芯片片上上的的判判断断逻逻辑辑决决定定由由哪哪个个端端口口优优先先进进行行读读写写操操作作，而而暂暂时关闭另一个被延迟的端口。时关闭另一个被延迟的端口。二、并行存储器二、并行存储器1.1.单体多字并行主存系统单体多字并行主存系统多个并行存储器共用一套地址寄存器，按同一
22、地址并多个并行存储器共用一套地址寄存器，按同一地址并行地访问各自的对应单元。行地访问各自的对应单元。M0地址寄存器地址寄存器M1MnW位位W位位W位位wn2.2.多体交叉存取方式并行主存系统多体交叉存取方式并行主存系统多个存储体具有自己的地址寄存器、数据线、时序，多个存储体具有自己的地址寄存器、数据线、时序，可以独立编制地并行工作。可以独立编制地并行工作。(1) 高位交叉高位交叉 M0M1M2M3体内地址体内地址体号体号体号体号地址地址00 000000 000100 111101 000001 000101 111110 000010 000110 111111 000011 000111
23、1111顺序编址顺序编址 各个体并行工作各个体并行工作M0地址地址01n1M1nn+12n1M22n2n+13n1M33n3n+14n1地址译码地址译码体内地址体内地址体号体号体号体号(1) 高位交叉高位交叉 M0M1M2M3体号体号体内地址体内地址地址地址0000 000000 010000 100000 110001 000001 010001 100001 111111 001111 011111 101111 11(2) 低位交叉低位交叉各个体轮流编址各个体轮流编址M0地址地址044n4M1154n3M2264n2M3374n1地址译码地址译码 体号体号体内地址体内地址 体号体号(2)
24、 低位交叉低位交叉 各个体轮流编址各个体轮流编址各体地址分配满足各体地址分配满足A=A=nj+knj+kA A：各分体内的地址；：各分体内的地址；n:n:存储体的个数存储体的个数j:j:正整数正整数k:k:存储体编号存储体编号通常在一个存储器周期内，通常在一个存储器周期内，n个存储体必须分时个存储体必须分时启动，则各个存储体的启动间隔为启动，则各个存储体的启动间隔为 t=T/n（n为交为交叉存取度）叉存取度）设存储器容量为设存储器容量为3232字，字长字，字长6464位，模块数为位，模块数为4 4，请分别画出顺序方式和交叉方式组成的存，请分别画出顺序方式和交叉方式组成的存储器结构和编址示意图。
25、储器结构和编址示意图。低位交叉的特点低位交叉的特点在不改变存取周期的前提下，增加存储器的带宽在不改变存取周期的前提下，增加存储器的带宽时间时间 单体单体访存周期访存周期 单体单体访存周期访存周期启动存储体启动存储体 0启动存储体启动存储体 1启动存储体启动存储体 2启动存储体启动存储体 3 设四体低位交叉存储器，存取周期为设四体低位交叉存储器，存取周期为T，总线传输周期，总线传输周期为为，为实现流水线方式存取，应满足，为实现流水线方式存取，应满足 T 4。连续读取连续读取 4 个字所需的时间为个字所需的时间为 T(4 1)例例例例: :设存储器容量为设存储器容量为设存储器容量为设存储器容量为3
26、232字，字长字，字长字，字长字，字长6464位，模块数位，模块数位，模块数位，模块数m=4m=4，分别用顺序方式和交叉方式进行组织。存储周期分别用顺序方式和交叉方式进行组织。存储周期分别用顺序方式和交叉方式进行组织。存储周期分别用顺序方式和交叉方式进行组织。存储周期T=200nsT=200ns，数据总线宽度为，数据总线宽度为，数据总线宽度为，数据总线宽度为6464位，总线传送周期位，总线传送周期位，总线传送周期位，总线传送周期=50ns=50ns。若连续读出。若连续读出。若连续读出。若连续读出4 4个字，问顺序存储器和交叉存个字，问顺序存储器和交叉存个字，问顺序存储器和交叉存个字，问顺序存储
27、器和交叉存储器的带宽各是多少储器的带宽各是多少储器的带宽各是多少储器的带宽各是多少? ?解：顺序存储器和交叉存储器连续读出解：顺序存储器和交叉存储器连续读出m=4个字的信息总量个字的信息总量都是：都是：q=64b4=256bit顺序存储器和交叉存储器连续读出顺序存储器和交叉存储器连续读出4个字所需的时间分别是：个字所需的时间分别是：t2=mT=4200ns=800ns=810-7st1=T+(m-1) 50ns=200ns+150ns=350ns=3.510-7s顺序存储器和交叉存储器的带宽分别是：顺序存储器和交叉存储器的带宽分别是：W2=q/t2=256b(810-7)s40MB/SW1=q
28、/t1=256b(3.510-7)s91.4MB/S三、相联存储器三、相联存储器一般存储器是按地址访问存储器的，而相联存储器是一般存储器是按地址访问存储器的，而相联存储器是按内容寻址的存储器。按内容寻址的存储器。相联存储器相联存储器可以选择记录的一个字段作为地址，该字可以选择记录的一个字段作为地址，该字段称为关键字（键）。段称为关键字（键）。 Key,Data基本原理：把存储单元所存内容的某一部分作为检索基本原理：把存储单元所存内容的某一部分作为检索项去检索该存储器，并将存储器中与该检索项符合的项去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入。存储单元内容进行读出或写入
29、。地址，被读写的信息地址，被读写的信息四四 虚拟存储器虚拟存储器1.1.虚拟存储器的基本概念虚拟存储器的基本概念l建建立立在在主主存存一一外外存存层层次次上上的的由由操操作作系系统统存存储储管管理理软软件件及及附附加加硬硬件件装装置置（存存储储器器管管理理部部件件MMUMMU）组组成成的的存储体系。存储体系。l它它以以透透明明的的方方式式给给用用户户提提供供了了一一个个访访问问速速度度接接近近主主存存储储器器，而而存存储储空空间间比比实实际际主主存存空空间间大大得得多多的的存存储储器。器。l此此时时程程序序的的逻逻辑辑地地址址称称为为虚虚地地址址，程程序序的的逻逻辑辑地地址址空间称为空间称为虚
30、地址空间虚地址空间。2.2.页式虚拟存储器页式虚拟存储器l建建立立一一张张虚虚地地址址页页号号与与实实地地址址页页号号的的对对照照表表，称称为为页页表表，记记录录程程序序的的虚虚页页面面调调进进主主存存时时被被安排在主存中的位置。安排在主存中的位置。l硬硬件件中中设设置置一一个个页页表表基基址址寄寄存存器器，存存放放当当前前所运行程序的所运行程序的页表的起始地址页表的起始地址。l页页表表中中的的每每一一行行对对应应一一个个虚虚页页号号，称称为为一一个个登记项登记项。l活跃的页表存放于专用存储器，称为活跃的页表存放于专用存储器，称为快表快表。主存和外存统一分页后进行管理。主存和外存统一分页后进行
31、管理。实地址实地址虚地址虚地址页表行地址页表行地址页表起始地址页表起始地址页表基址寄存器页表基址寄存器 实页号实页号 1 实页号实页号 页内地址页内地址 虚页号虚页号 页内地址页内地址页页 表表页式虚拟存储器地址转换页式虚拟存储器地址转换3.3.段式虚拟存储器段式虚拟存储器l为了将虚拟地址变换成主存实地址，需要一为了将虚拟地址变换成主存实地址，需要一个个段表段表。l每个程序段在段表中都占有一登记项，内容每个程序段在段表中都占有一登记项，内容有：有：段号、段起点、段长、装入位段号、段起点、段长、装入位等。等。l虚实地址变换，如后图所示。虚实地址变换，如后图所示。外存中程序分段（按照代码段、数据段
32、和共享外存中程序分段（按照代码段、数据段和共享段等）进行管理。段等）进行管理。主存地址主存地址虚地址虚地址段表行地址段表行地址段表起始地址段表起始地址段表基址寄存器段表基址寄存器 段段起起点点 . 段号段号 段内地址段内地址段段段段 表表表表段式虚拟存储器地址转换段式虚拟存储器地址转换4.4.段页式虚拟存储器段页式虚拟存储器l虚地址格式：虚地址格式：基号基号+ +段号段号+ +页号页号+ +页内地址；页内地址；l实地址格式：实地址格式：页号页号+ +页内地址；页内地址；l每个程序有一张每个程序有一张段表段表，每段对应有一张，每段对应有一张页表；页表；l要经过要经过两级查表两级查表才能完成地址转
33、换，才能完成地址转换，耗时长；耗时长；每个程序按模块分段，每段再划分为页，页每个程序按模块分段，每段再划分为页，页面大小与实存页面相同；面大小与实存页面相同；例：一个虚拟存储器有例：一个虚拟存储器有8 8个页面，页面大小为个页面，页面大小为10241024字，字，内存有内存有4 4个页面，页表的内容为：个页面，页表的内容为：虚页号虚页号 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7实页号实页号 3 1 - - 2 - 0 3 1 - - 2 - 0 对应以下虚地址的主存地址是什么？哪些虚拟地址将对应以下虚地址的主存地址是什么？哪些虚拟地址将引起页面失效？引起页面失效？1.0 2.3278 3.1023 4.1024 5.1025 6.1800 1.0 2.3278 3.1023 4.1024 5.1025 6.1800 7.40967.4096
