ch04.存储器.校验

1、 主讲：黄铝文主讲：黄铝文124.1 概述概述4.3 高速缓冲存储器高速缓冲存储器345六、存储器的校验六、存储器的校验编码的纠错编码的纠错 、检错能力与编码的最小距离有关。、检错能力与编码的最小距离有关。L 编码的最小距离编码的最小距离D 检测错误的位数检测错误的位数C 纠正错误的位数纠正错误的位数海明码是具有海明码是具有位位纠错能力的编码纠错能力的编码L 1 = D + C ( DC )1 . 编码的最小距离编码的最小距离任意两组合法代码之间任意两组合法代码之间 二进制位数二进制位数 的的 最少差异。最少差异。L = 3 具有具有 一位一位 纠错能力纠错能力6海明码的组成需增添海明码的组成

2、需增添 ？位检测位位检测位检测位的位置检测位的位置 ？检测位的取值检测位的取值 ？2k n + k + 12i ( i = 0、1、2 、3 )检测位的取值与该位所在的检测检测位的取值与该位所在的检测“小组小组” 中中承担的奇偶校验任务有关承担的奇偶校验任务有关组成海明码的三要素组成海明码的三要素2 . 海明码的组成海明码的组成7各检测位各检测位 Ci 所承担的检测小组为所承担的检测小组为gi 小组独占第小组独占第 2i1 位位gi 和和 gj 小组共同占第小组共同占第 2i1 + 2j1 位位gi、gj 和和 gl 小组共同占第小组共同占第 2i1 + 2j1 + 2l1 位位 C1 检测的

3、检测的 g1 小组包含第小组包含第 1，3，5，7，9，11C2 检测的检测的 g2 小组包含第小组包含第 2，3，6，7，10，11C4 检测的检测的 g3 小组包含第小组包含第 4，5，6，7，12，13C8 检测的检测的 g4 小组包含第小组包含第 8，9，10，11，12，13，14，8例（例（P101）:求求 0101 按按 “偶校验偶校验” 配置配置的海明码的海明码解：解： n =4 根据根据 2k n + k +1 得得 k = 3海明码排序如下海明码排序如下:二进制序号二进制序号名称名称1 2 3 4 5 6 7C1 C2 C40 0101 的海明码为的海明码为 0100101

4、。 01 0 1109按配偶原则配置按配偶原则配置 0011 的海明码的海明码 二进制序号二进制序号 名称名称1 2 3 4 5 6 7C1 C2 C41 0 000 1 1解：解： n = 4 根据根据 2k n + k + 1取取 k = 3C1= 3 5 7 = 1C2= 3 6 7 = 0C4= 5 6 7 = 0 0011 的海明码为的海明码为 1000011。练习练习1103. 海明码的纠错过程海明码的纠错过程形成新的检测位形成新的检测位 Pi如增添如增添 3 位位 （k = 3）新的检测位为新的检测位为 P4 P2 P1以以 k = 3 为例，为例，Pi 的取值为的取值为P1 =

5、 1 3 5 7P2 = 2 3 6 7P4 = 4 5 6 7对于按对于按 “偶校验偶校验” 配置的海明码配置的海明码 不出错时不出错时 P1= 0，P2 = 0，P4 = 0C1C2C4其位数与增添的检测位有关其位数与增添的检测位有关11P1= 1 3 5 7 = 0 无错无错P2= 2 3 6 7 = 1 有错有错P4= 4 5 6 7 = 1 有错有错P4P2P1 = 110第第 6 位出错，可纠正为位出错，可纠正为 0100101，故要求传送的信息为故要求传送的信息为 0101。纠错过程如下纠错过程如下例例4.5解：解： 已知接收到的海明码为已知接收到的海明码为 0100111（按配

6、偶原则配置）试问要求传送的信息是什么（按配偶原则配置）试问要求传送的信息是什么? 12练习练习2P4 = 4 5 6 7 = 1P2 = 2 3 6 7 = 0P1 = 1 3 5 7 = 0 P4 P2 P1 = 100第第 4 位错，可不纠位错，可不纠写出按偶校验配置的海明码写出按偶校验配置的海明码0101101 的纠错过程的纠错过程练习练习3按配奇原则配置按配奇原则配置 0011 的海明码的海明码配奇的海明码为配奇的海明码为 010101113七、提高访存速度的措施七、提高访存速度的措施 采用高速器件采用高速器件 双端口存储器系统双端口存储器系统 采用层次结构采用层次结构 Cache 主

7、存主存 并行操作存储器，可以提高访问的速度，并行操作存储器，可以提高访问的速度，增加增加存储器的带宽存储器的带宽 ARLAB存存储储体体 译码器L译码器RARRDBDRLDRRCB读写电路L读写电路RDBABCB判别逻辑电路14七、提高访存速度的措施七、提高访存速度的措施ARLAB存存储储体体 译码器L译码器RARRDBDRLDRRCB读写电路L读写电路RDBABCB 双端口存储器系统双端口存储器系统 如果双端口同一时刻内访问存储器同一内存单元时，如果双端口同一时刻内访问存储器同一内存单元时，便发生便发生。判别逻辑电路可以决定对哪个端口优先进行操作，判别逻辑电路可以决定对哪个端口优先进行操作，

8、而对另一个被而对另一个被读写的端口设置读写的端口设置标志。标志。15七、提高访存速度的措施七、提高访存速度的措施 采用高速器件采用高速器件 调整主存结构调整主存结构1. 单体多字系统单体多字系统 W位位W位位W位位W位位W位位地址寄存器地址寄存器主存控制部件主存控制部件. . . . . . . . . . .单字长寄存器单字长寄存器 数据寄存器数据寄存器 存储体存储体 采用层次结构采用层次结构 Cache 主存主存 增加存储器的带宽增加存储器的带宽 162. 多体并行系统多体并行系统(1) 高位交叉高位交叉 各个体并行工作各个体并行工作顺序存储器顺序存储器1718(2) 低位交叉低位交叉M0

9、地址地址044n4M1154n3M2264n2M3374n1地址译码地址译码 体号体号体内地址体内地址交叉存储器交叉存储器各个体轮流编址各个体轮流编址19低位交叉的特点低位交叉的特点在不改变存取周期的前提下，增加存储器的带宽在不改变存取周期的前提下，增加存储器的带宽时间时间 单体单体访存周期访存周期 单体单体访存周期访存周期启动存储体启动存储体 0启动存储体启动存储体 1启动存储体启动存储体 2启动存储体启动存储体 320举例举例 22(3) 存储器控制部件（简称存控）存储器控制部件（简称存控）易发生代码易发生代码丢失的请求源，丢失的请求源，优先级优先级最高最高严重影响严重影响 CPU工作的请

10、求源，工作的请求源，给予给予 次高次高 优先级优先级控制线路控制线路排队器排队器 节拍节拍发生器发生器QQCM来自各个请求源来自各个请求源主脉冲主脉冲存控标记存控标记 触发器触发器写数的优先级高于读数、读指令，读数写数的优先级高于读数、读指令，读数的优先级高于读指令。的优先级高于读指令。23一、概述一、概述1. 问题的提出问题的提出避免避免 CPU “空等空等” 现象现象CPU 和主存（和主存（DRAM）的速度差异的速度差异缓存缓存CPU主存主存容量小容量小速度高速度高容量大容量大速度低速度低程序访问的局部性原理程序访问的局部性原理24一、概述一、概述当当CPU从主存中取出指令和数据时，在一个

11、较从主存中取出指令和数据时，在一个较短的时间间隔内，由程序产生的地址往往短的时间间隔内，由程序产生的地址往往在主在主存空间的某个很小的区域内。存空间的某个很小的区域内。CPU对局部范围的存储器地址频繁进行访问，对局部范围的存储器地址频繁进行访问，而对此范围以外的地址访问甚少的现象，称为而对此范围以外的地址访问甚少的现象，称为程序程序访问的局部性访问的局部性。1. 问题的提出问题的提出25一、概述一、概述1. 问题的提出问题的提出Cache大多采用大多采用器件。器件。随着微机技术的发展，在随着微机技术的发展，在CPU芯片中也集成了芯片中也集成了Cache，称，称为一级为一级Cache（L1 Ca

12、che）；安装在主板上的）；安装在主板上的Cache则称为则称为L2 Cache（二级缓存）。（二级缓存）。Pentium 以后的以后的CPU则将则将L2 Cache与与CPU内核一起封内核一起封装，或直接把装，或直接把L2 Cache集成到集成到CPU内，以进一步提高速度。这内，以进一步提高速度。这样主板上的样主板上的Cache就称为三级就称为三级Cache（L3 Cache）了。）了。 26一、概述一、概述1. 问题的提出问题的提出272. Cache 的工作原理的工作原理一、概述一、概述 Cache和主存都被分成若干个和主存都被分成若干个大小相等大小相等的的块，每块由若干字节组成。由于块

13、，每块由若干字节组成。由于Cache的容量的容量远小于主存的容量，它保存的信息只是主存中远小于主存的容量，它保存的信息只是主存中部分部分若干块若干块的副本。的副本。28设主存有设主存有2n个字节单元，地址码为个字节单元，地址码为n位，将主存分块位，将主存分块（block），每块有），每块有B个字节个字节，块内字节数为，块内字节数为b，B=2b，则，则共共分成分成M=2n/B块块。Cache也由也由的块组成，由于其容量小，所以的块组成，由于其容量小，所以块的数目小得多，主存中只有块的数目小得多，主存中只有块的内容可存放在块的内容可存放在cache中。中。主存主存地址为地址为n位（位（n=m+b）

14、，），则：主存的块数则：主存的块数M=2m，块内字节数块内字节数B=2b。Cache地址为地址为（c+b），），c位是位是Cache字字块地址，即块地址，即，Cache为为C2c 。Cache2. Cache 的工作原理的工作原理主存和缓存按块存储 块的大小相同B 为块长2. Cache 的工作原理的工作原理当当CPU发出发出请求时有两种情况：请求时有两种情况： 所需要的数据已所需要的数据已在在Cache中，那么直接中，那么直接访问访问Cache就行了；就行了； 这种情况称为这种情况称为访问访问Cache命中命中。 所需要的数据尚未调所需要的数据尚未调入入Cache，那么就要把该，那么就要把该

15、数据所在的整个字块从主存一次调进来。数据所在的整个字块从主存一次调进来。 这种情况称为这种情况称为访问访问Cache不命中不命中。 302. Cache 的工作原理的工作原理命中率命中率 与与 Cache 的的容量容量与与块长块长有关有关 CRAY_1 16体交叉 块长取 16 个存储字 IBM 370/168 4体交叉 块长取 4 个存储字每个体宽64-bit（64位4 = 256位） 效率效率 与与 有关有关设 Cache 为 h，访问 Cache 的时间为 tc ，访问 的时间为 tm 则 e = 100% tc h tc+ (1h) tm 访问 Cache 的时间 平均访问时间 e =

16、 100%例4.7（P111）：假设CPU执行某段程序时，共访问Cache命中20 00次，访问主存50次。已知Cache的存取周期为50ns，主存的存取周期200ns。求Cache-主存系统的 、和。（1）h： 2000 /（2000+50） 0.97 （2）由题意可知，访问主存的时间为访问Cache时间的4（200ns/50ns 4）倍，假设访问Cache的时间为t，则访问主存的时间为4t，则访问为 （3）平均访问时间为50ns0.97+200ns（1-0.97） 54.5ns352. Cache 的工作原理的工作原理3. Cache 的基本结构的基本结构用户编程只需主存地址即可，主存与用

17、户编程只需主存地址即可，主存与Cache信息交换由机器硬件完成。信息交换由机器硬件完成。4.3Cache替换机构主存Cache地址映射变换机构块号 块内地址块号 块内地址Cache存储体3. Cache 的基本结构的基本结构CPU访问的访问的Cache不命中工作过程不命中工作过程404. Cache 的 读 操作数据数据一般只写到一般只写到CacheCache，当当CacheCache中的数据被再次中的数据被再次更新时，将原更新的数据写入主存相应单元，并接受更新时，将原更新的数据写入主存相应单元，并接受新的数据。新的数据。41CPUCache主主 存存4. Cache 的 读 操作从从CPUC

18、PU发出的写信号送发出的写信号送CacheCache的同时也写入主存。的同时也写入主存。42CPUCache主主 存存4. Cache 的 读 操作Cache 和主存的一致性 4. Cache 的 读 操作 （Write through） （Write back） 写操作时数据既写入Cache又写入主存 写操作时只把数据写入 Cache 而不写入主存当 Cache 数据被替换出去时才写回主存 ，读操作时不涉及对主存的写操作，更新策略比较容易实现，读操作 Cache 失效发生数据替换时，被替换的块需写回主存，增加了 Cache 的复杂性4. Cache 的 写 操作 访问Cache取出信息送CP

19、U 访问主存取出信息送CPU将新的主存块调入Cache中执行替换算法 腾出空位 结束命中？Cache满？CPU发出访问地址 开始是否是否为了把主存信息调入为了把主存信息调入到到Cache存储器中，必存储器中，必须应用某种函数把主存须应用某种函数把主存地址映象到地址映象到Cache，称作，称作。在信息按照在信息按照这种映象关系装入这种映象关系装入Cache后，执行程序时，应将主存地址变换后，执行程序时，应将主存地址变换成成Cache地地址，这个变换过程叫做址，这个变换过程叫做 几种几种基本基本地址映象方式地址映象方式： 直接映象、全相联映象、组直接映象、全相联映象、组相相联映象联映象45 在在直

20、接映象方式直接映象方式中，主存中，主存和和Cache中字块的对应关系采用中字块的对应关系采用直接映象函数直接映象函数： j = i mod 2c 其中，其中，j是是Cache的字块号，的字块号，i是主存的字块号。是主存的字块号。 在在这种映象方式这种映象方式中，主存的第中，主存的第0块，第块，第2c块，第块，第2c+1块，块，只能映象到只能映象到Cache的第的第0块，块， 而主存的第而主存的第1块，第块，第2c+1块，第块，第2c+1+1块，块，只能映象到只能映象到Cache的第的第1块。以此类推。块。以此类推。 46 字块2m1 字块2c+1 字块2c+11 字块2c +1 字块2c 字块

21、2c1 字块1 字块0主存储体 字块 1 标记 字块 0 标记字块 2c1标记Cache存储体t位012c1 字块字块地址 主存字 块标记t 位c 位b 位主存地址 比较器（t位）= 不命中有效位=1？*m位 Cache内地址否是可以和 个 对应只能和 个 对应 字块2c+1 字块2c 字块0 字块 047000000 00 00000000 00 01000000 00 10000000 00 11000000 01 00000000 01 01000000 01 10000000 01 11000000 10 00000000 10 01000000 10 10000000 10 1100

22、0000 11 00000000 11 01000000 11 10000000 11 11000001 00 00000001 00 01000001 00 10000001 00 11000001 01 00000001 01 01000001 01 10000001 01 11000001 10 00000001 10 01000001 10 10000001 10 11000001 11 00000001 11 01000001 11 10000001 11 11字块字块0字块字块1字块字块2字块字块3 标记标记t tc cb bt tc cb b00 0000 0100 1000 1

23、101 0001 0101 1001 1110 0010 0110 1010 1111 0011 0111 1011 11主存地址主存地址主存块标记主存块标记t 地址为字地址地址为字地址地址为字地址地址为字地址字地址字地址字节地址字节地址11109876543210840字节地址字节地址字地址字地址452301420字地址字地址字节地址字节地址89101145670123840直接映象的直接映象的优点是实现简单，只需利用优点是实现简单，只需利用，即可确定所需字块是否已，即可确定所需字块是否已在在Cache存储器中。存储器中。主存地址：主存地址：t+c+bm+b。低（末）。低（末）b位是字块内位

24、是字块内地址，地址，块长度为块长度为2bB，；中间中间c位位是是Cache字块字块地地址，即址，即，Cache为为2cC；高（高（m-c）= t 位位就是主存字块标记，也就是用于判断就是主存字块标记，也就是用于判断CPU所需所需内容是否可在内容是否可在Cache中命中的依据中命中的依据。Cache地址：地址：c+b。505051直接映象方式的缺点是不够灵活，即每个直接映象方式的缺点是不够灵活，即每个主存的块只能对应主存的块只能对应惟一惟一的的Cache存储器块，存储器块，因此，即使因此，即使Cache存储器别的许多块空着存储器别的许多块空着也不能占用。这使得也不能占用。这使得Cache存储空间

25、得不到充存储空间得不到充分利用，并降低了命中率。分利用，并降低了命中率。5253例例4.8（P120）：假设主存容量为）：假设主存容量为512KB，Cache容量为容量为4KB，每个字，每个字块为块为16个字，每个字为个字，每个字为32位。位。（1）Cache地址和主存地址各有多少位？各可容纳多少块？地址和主存地址各有多少位？各可容纳多少块？（2）在直接映射方式下，主存的第几块映射到）在直接映射方式下，主存的第几块映射到Cache中的第中的第5块（设块（设起始字块为第起始字块为第1块）块）（3）画出直接映射方式下的主存地址字段中各段的位数。）画出直接映射方式下的主存地址字段中各段的位数。（1）

26、Cache容量4KB 212B，即Cache地址为12位，。每个字为32位，即4个字节，422；最低2位表示。每个字块为16个字，1624，那么，每个字块的块内地址为4+26位，即。，C2664（块）。 219B，即主存地址为19位。19-b。M2138192（块）54例例4.8（P120）：假设主存容量为）：假设主存容量为512KB，Cache容量为容量为4KB，每个字，每个字块为块为16个字，每个字为个字，每个字为32位。位。（1）Cache地址和主存地址各有多少位？各可容纳多少块？地址和主存地址各有多少位？各可容纳多少块？（2）在直接映射方式下，主存的第几块映射到）在直接映射方式下，主存

27、的第几块映射到Cache中的第中的第5块（设块（设起始字块为第起始字块为第1块）块）（3）画出直接映射方式下的主存地址字段中各段的位数。）画出直接映射方式下的主存地址字段中各段的位数。（2） j = i mod 2c j是Cache的字块号，i是主存的字块号。Cache的字块数量为64 （ 26 ）块；的字块数量为8192（ 213 ）块。j = 5，主存的字块数分别为5，64+5，213-26+5，共128（213 / 26 27）个块。 字块字块地址 主存字 块标记t 位c 位b 位m位 Cache内地址主存地址（3）；即得到位。55例例4.8（P120）：假设主存容量为）：假设主存容量为

28、512KB，Cache容量为容量为4KB，每个字，每个字块为块为16个字，每个字为个字，每个字为32位。位。 字块字块地址 主存字 块标记t 位c 位b 位m位 Cache内地址主存地址（4）。Cache地址为。如果访存地址为1000101 000101 0111 10，则表明？如果访存地址为 69 5 7 2，则表明？Cache地址为 5 7 2，则表明？主存字块号为第69块，Cache是第5块。若Cache的标志位是或不是69，则表明？全相联映象方式全相联映象方式是最灵活但成本最高的一种方式是最灵活但成本最高的一种方式。该该方式允许主存中的每一个字方式允许主存中的每一个字块映象到块映象到C

29、acheCache存储器存储器的任何一个字块位置上，也允许从确实已被占满的任何一个字块位置上，也允许从确实已被占满的的CacheCache存储器中替换出任何一个旧字块。存储器中替换出任何一个旧字块。 5657 中的 可以映射到 中的 字块2m1字块2c1字块1 字块0字块2c1字块1字块0标记标记标记主存地址主存储器 字块058字块字块0字块字块1字块字块i字块字块0字块字块1字块字块2c-1标记标记标记标记标记标记字块字块2m-1主存字块主存字块标记标记块内地址块内地址m=t+c位位 b位位主存地址主存地址比较器（比较器（m位）位） 有效位有效位=1主存储器主存储器命中命中 不命中不命中Ca

30、che存储器存储器m=t+c所有标记所有标记59这是一个灵活且非常理想的方案。只要这是一个灵活且非常理想的方案。只要Cache有空的存储块，需要访问的主存块就可以有空的存储块，需要访问的主存块就可以复制到空的复制到空的Cache块中，块中，Cache的利用率很高。的利用率很高。是地址变换机构比较复杂，当是地址变换机构比较复杂，当Cache的块数的块数较多时，比较器所需逻辑电路难以设计和实现。较多时，比较器所需逻辑电路难以设计和实现。因此因此。60组组相相联映象方式联映象方式是是直接映象和全相联映象方直接映象和全相联映象方式式的一种折衷方案。的一种折衷方案。将将CacheCache的字块分成若干

31、组，的字块分成若干组，CacheCache中的中的与与主存字块主存字块，与组建立与组建立直接映象的直接映象的与与。组组相连既克服相连既克服直接映象灵活性直接映象灵活性不足的缺点，不足的缺点，又比全又比全相连映象降低相连映象降低了逻辑电路的复杂性。了逻辑电路的复杂性。 61也就是用于判断也就是用于判断CPU所需内容是否可在所需内容是否可在Cache中命中的依据。中命中的依据。62字块2m1字块2c-r+1 字块2c-r + 1 字块2c-r字块2c-r 字块1 字块0 字块 3标记 字块 1标记字块 2c1标记 字块 2标记 字块 0标记字块 2c2标记 字块内地址组地址主存字块标记s = t

32、+ r 位q = cr 位b 位组012c-r1主存地址Cache主存储器m 位共 ，每组内两块（r = 1)1按模 映射到 的中的 字块0 字块 1 字块 0 字块2c-r 字块2c-r+16465例例4.9（P120）：假设主存容量为）：假设主存容量为512K16位，位，Cache容量为容量为409616位，块长为位，块长为4个个16位的字，访存地址为字地址。位的字，访存地址为字地址。（2）在全相联映射方式下，设计主存的地址格式。）在全相联映射方式下，设计主存的地址格式。（3）在二路组相联映射方式下，设计主存的地址格式。）在二路组相联映射方式下，设计主存的地址格式。（4）若主存容量为）若主

33、存容量为512K32位，块长不变，在四路组相联映射方式位，块长不变，在四路组相联映射方式下，设计主存地址格式。下，设计主存地址格式。（1）由题设可知，Cache容量4096字 212字，即Cache地址为12位，。Cache的字块长度为4个字，422，即。 219，即主存地址为19位。19-b。 66例例4.9（P120）：假设主存容量为）：假设主存容量为512K16位，位，Cache容量为容量为409616位，块长为位，块长为4个个16位的字，访存地址为字地址。位的字，访存地址为字地址。（2），（3），二路组相联，即二路组相联，即Cache每组两个字块，每组两个字块，r1，一共有，一共有210 / 21 29，67例例4.9（P120）：假设主存容量为）：假设主存容量为512K16位，位，Cache容量为容量为409616位，块长为位，块长为4个个16位的字，访存地址为字地址。位的字，访存地址为字地址。（4）由题设知，）由题设知，Cache容量不变，即容量不变，即，68（2）设）设Cache初态为空，初态为空，CPU依次从主存第依次