2、直接映象及其变换 映象规则:主存中一块只能映象到 Cache的一个特定的块中 计算公式:b= B mod Cb 其中:b为 Cache的块号,B是主存的块号,Cb是 Cache的块数 整个 Cache地址与主存地址的低位部分完全相同。 块0 块1 区0 块Cb-1 块0 块 块1 块Cb+1 区1 匚块Cb1 匚块21 Cache 块Mb-Cb 块Mb-Cb+1 区M 块Mnl 主存储器 直接相联映象方式 地址变换过程 用主存地址中的块号B去访问区号存储器 把读出来的区号与主存地址中的区号E进行比较 比较结果相等,且有效位为1,则 Cache命中 比较结果相等,有效位为0,表示 Cache中的这一块已经作废。 比较结果不相等,有效位为0,表示 Cache中的这一块是空的。 比较结果不相等,有效位为1,表示 Cache中的这一块是有用的。 提高 Cache速度的一种方法: 把区号存储器与 Cache合并成一个存储器 直接映象方法的主要优点: 硬件实现很简单,不需要相联访问存储器 访问速度也比较快,实际上不进行地址变换 宜接映象方式的主要缺点:块的冲突率比较高
3—1 2、直接映象及其变换 • 映象规则：主存中一块只能映象到 Cache 的一个特定的块中。 计算公式：b＝B mod Cb 其中：b 为 Cache 的块号，B 是主存的块号，Cb 是 Cache 的块数。 整个 Cache 地址与主存地址的低位部分完全相同。 块 0 块 1 区 0 块 Cb-1 块 0 块 Cb 块 1 块 Cb+1 区 1 块 Cb-1 块 2Cb-1 Cache 块 Mb-Cb 块 Mb-Cb+1 区 Me-1 块 Mb-1 主存储器 直接相联映象方式 • 地址变换过程： 用主存地址中的块号 B 去访问区号存储器 把读出来的区号与主存地址中的区号 E 进行比较 比较结果相等，且有效位为 1，则 Cache 命中。 比较结果相等，有效位为 0，表示 Cache 中的这一块已经作废。 比较结果不相等，有效位为 0，表示 Cache 中的这一块是空的。 比较结果不相等，有效位为 1，表示 Cache 中的这一块是有用的。 • 提高 Cache 速度的一种方法： 把区号存储器与 Cache 合并成一个存储器 • 直接映象方法的主要优点： 硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不进行地址变换 • 直接映象方式的主要缺点：块的冲突率比较高
主存地 区号E 块号B块内地址 Cache地址 块号b快内地址 块失效<[相等比较相 比较相等且有效为1 访问C 区号E(按地址访问)有效创 区表存储器 直接相联地址变换 号E 块号B 快内地址 Cache地址 块号b 块内地址 送CPU个 访问主存相等比 较相等 / 选择 E D D Dw. 有效创区号E数据D0数据D 数据D 按地址访问的 Cache 图343快速度的直接相联地址变换 3、组相联映象及其变换 映象规则 主存和 Cache按同样大小划分成块,还按同样大小划分成组 从主存的组到 Cache的组之间采用直接映象方式。 在两个对应的组内部采用全相联映象方式
3—2 主存地 址 区号 E 块号 B 块内地址 W Cache 地址 块号 b 块内地址 w 块失效 相等比较 相等 比较相等且有效为 1 E 1 访问 Cache 区号 E（按地址访问） 有效位 区表存储器 直接相联地址变换 区号 E 块号 B 块内地址 W Cache 地址 块号 b 块内地址 w 送 CPU 访问主存 相等比较 相等 1/w 选择 … … … 1 E D0 D1 … Dw-1 … 有效位 区号 E 数据 D0 数据 D1 数据 Dw-1 按地址访问的 Cache 图 3.43 快速度的直接相联地址变换 3、组相联映象及其变换 • 映象规则： 主存和 Cache 按同样大小划分成块，还按同样大小划分成组。 从主存的组到 Cache 的组之间采用直接映象方式。 在两个对应的组内部采用全相联映象方式
块0 组0 组 2Gb- 区0 块0 GbCg-Gb 组 ……}组cg1 Gb-I Cb-I=GbCa-1 G 2Gb-1 Gb CaMMe-l Cg(Me-1) GbCq(Me-1)+Gb-1 Cb-Gb=CqGb-G Gb CqMMe-1+Gb Ca-I 了CgMe-Cg Cb-l=CaB Gb CqMMe-1)-+2Gb Me-Gb=GbCaMe-Gb CqMe-1 主存储器 组相联映象方式 地址变换过程: 用主存地址中的组号G按地址访问块表存储器。 把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较 如果有相等的,表示 Cache命中。 如果没有相等的,表示 Cache没有命中 提高 Cache的访问速度的一种方法: 把 Cache的地址变换与访问 Cache并行进行,并采用流水线方式工作。 把块表存储器中一个相联比较的组按块方向展开存放 用多个相等比较器来代替相联访问,加块查表的速度 组相联映象方式的优点: 块的冲突概率比较低,块的利用率大幅度提髙,块失效率明显降低。 组相联映象方式的缺点: 实现难度和造价要比直接映象方式高。 区号E 组号G 组内块号B|块内地址W
3—3 块 0 …… 组 0 Gb-1 Gb …… 组 1 2Gb-1 区 0 …… 块 0 GbCg-Gb 组 0 …… …… 组 Cg-1 Gb-1 Cb-1=GbCg-1 Gb …… 1 …… 2Gb-1 GbCg(Me-1) …… …… Cg(Me-1) GbCg(Me-1)+Gb-1 Cb-Gb=CgGb-Gb GbCg(Me-1)+Gb Cg-1 …… …… CgMe-Cg+1 Cb-1=CgGb-1 GbCg(Me-1)+2Gb- 1 块 2（Cb-1） Me-1 Cache …… Me-Gb=GbCgMe-Gb …… CgMe-1 Mb-1=GbCgMe-1 主存储器 组相联映象方式 • 地址变换过程： 用主存地址中的组号 G 按地址访问块表存储器。 把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。 如果有相等的，表示 Cache 命中。 如果没有相等的，表示 Cache 没有命中。 • 提高 Cache 的访问速度的一种方法： 把 Cache 的地址变换与访问 Cache 并行进行，并采用流水线方式工作。 把块表存储器中一个相联比较的组按块方向展开存放。 用多个相等比较器来代替相联访问，加块查表的速度。 • 组相联映象方式的优点： 块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。 • 组相联映象方式的缺点： 实现难度和造价要比直接映象方式高。 区号 E 组号 G 组内块号 B 块内地址 W
主存地址 组号 组内块号b 块内地址 Cache地址 相联比轾 相等 相联比较(Gi个块) 些区号组内块号B组内块号b 块表 组相联映象方式的地址变换 区号E区内组号G组内块号B块内地址W 主存地址 块失□组号日组内块号b工块内地址以 与 Cache地址 或 相等比 相等比 EB be elB E B 块表(按地址访问,读出的多个字段进行相联比较,为有效位) 组相联地址变换的一种实现方法 采用组相联映象方式的典型机器的 Cache分组情况 机器型号 Cache的块数Cb每组的块数 GbCache组数Cg
3—4 主存地址 组号 g 组内块号 b 块内地址 w Cache 地址 不等 相联比较 相等 相联比较(Gb个块) E 区号,组内块号 B 组内块号 b 块 表 组相联映象方式的地址变换 区号 E 区内组号 G 组内块号 B 块内地址 W 主存地址 块失效 组号 g 组内块号 b 块内地址 w 与 Cache 地址 或 ≠ 相等比 较 ＝ ≠ 相等比 较 ＝ ≠ 相等比 较 ＝ …… …… E, B b e E, B b …… E, B b e …… 块表(按地址访问,读出的多个字段进行相联比较,e 为有效位) 组相联地址变换的一种实现方法 采用组相联映象方式的典型机器的 Cache 分组情况 机器型号 Cache 的块数 Cb 每组的块数 Gb Cache 组数 Cg
DEC VAX-11/780 1024 512 Amdahl 470/V6 512 256 Intel i860 D-Cache 256 128 Honeywell 66/60 512 128 Amdahl 470/V7 2048 222448 512 IBM370/168 1024 128 IBM3033 1024 16 64 Motolola 88110 I-Cachel 256 2 128 4、位选择组相联映象及其变换 映象规则 除了分块之外, Cache分组,主存按照 Cache的组大小分区 主存中的块与 Cache中的组之间是直接映象关系, 主存中的块与 Cache中组内部的各个块之间是全相联映象方式。 区0 组0 Gb-1 C Cb-Gb=CqGb-Gb Cg(Mb-1 Cb-1=CaGb-I Ca(Mb-IH1 Cache Me-1 Mb-I=CqMe-1 主存储器 图3.47位选择组相联映象方式 ●与组相联映象方式比较:映象关系明显简单,实现起来容易。 在块表中存放和参与相联比较的只有区号E,不再有组内块号B
3—5 DEC VAX-11/780 1024 2 512 Amdahl 470/V6 512 2 256 Intel i860 D-Cache 256 2 128 Honeywell 66/60 512 4 128 Amdahl 470/V7 2048 4 512 IBM 370/168 1024 8 128 IBM3033 1024 16 64 Motolola 88110 I-Cache 256 2 128 4、位选择组相联映象及其变换 • 映象规则： 除了分块之外，Cache 分组，主存按照 Cache 的组大小分区。 主存中的块与 Cache 中的组之间是直接映象关系， 主存中的块与 Cache 中组内部的各个块之间是全相联映象方式。 块 0 1 …… 区 0 块 0 组 0 …… Cg-1 Gb-1 Cg Gb Cg+1 1 …… …… 1 2Gb-1 …… 2Cg-1 …… Cb-Gb=CgGb-Gb Cg-1 …… Cg(Mb-1) Cb-1=CgGb-1 Cg(Mb-1)+1 Cache …… Me-1 Mb-1=CgMe-1 主存储器 图 3.47 位选择组相联映象方式 • 与组相联映象方式比较：映象关系明显简单，实现起来容易。 在块表中存放和参与相联比较的只有区号 E，不再有组内块号 B
区号E 区内块号 块内地址W 主存地址 块失效□组号9组内块号b块内以 Cache地址 「相等比 相等 相等 E「b 区号E快号区号E快号e 区号E块号 块表(按地址访问,读出的多个区号进行相联比较,是有效位) 位选择组相联地址变换的一种实现方式 块0 段0 段 Cb-Sb=Sb(Cs-1 Cb-1=SbCs-I Mb-Sb=Sb(Ms-1 Ms-1 Mb-1=SbMs-1 主存储器 段相联映象方式 段相联映象及其变换 映象规则: 主存和 Cache都按同样大小分块,并分段
3—6 区号 E 区内块号 B 块内地址 W 主存地址 块失效 组号 g 组内块号 b 块内 w 与 Cache 地址 或 ≠ 相等比 较 ＝ ≠ 相等比 较 ＝ ≠ 相等比 较 ＝ …… …… E b E b …… E b …… 区号E 块号b e 区号E 块号b e 区号E 块号b e 块表(按地址访问,读出的多个区号进行相联比较,e 是有效位) 位选择组相联地址变换的一种实现方式 块 0 …… 段 0 Sb-1 块 0 Sb 段 0 …… …… 1 Sb-1 2Sb-1 Sb 1 …… 2Sb-1 …… …… Cb-Sb=Sb(Cs-1) Cs-1 …… Cb-1=SbCs-1 Cache Mb-Sb=Sb(Ms-1) …… Ms-1 Mb-1=SbMs-1 主存储器 段相联映象方式 5、段相联映象及其变换 • 映象规则： 主存和 Cache 都按同样大小分块，并分段
段之间采用全相联映象方式,段内部的块之间采用直接映象方式。 段相联方式的地址变换过程 首先用主存地址中的段号S与段表中的主存段号字段进行相联比较。 如果有相等的,用主存地址中的段内块号B按地址访问 Cache段号部分。 把读出的段号s与主存地址的段内块号及块内地址拼接得到 Cache地址 如果没有相等的,则发出 Cache块失效请求。 主存地址□ 段号S 段内块号B快内地址 匚段号s段内块号b块内地址 Cache地址 相联比较 段0 按地址访问 段1 主存段号S[ Cache段号s有效 M-1 段表(按地址和相联两种访问方式) 段相联地址变换方式 段相联方式的主要优点: 段表比较简单,实现的成本低。 例如:一个容量为256KB的 Cache,分成8个段,每段2048块,每块16B。 在段表存储器中只需要存储8个主存地址的段号S 而在块表中要存储8×2048=16384个区号(相当于段号) 两者相差2000多倍 段相联方式的主要缺点 当发生段失效时,要把本段内已经建立起来的映象关系全部撤消
3—7 段之间采用全相联映象方式，段内部的块之间采用直接映象方式。 • 段相联方式的地址变换过程： 首先用主存地址中的段号 S 与段表中的主存段号字段进行相联比较。 如果有相等的，用主存地址中的段内块号 B 按地址访问 Cache 段号部分。 把读出的段号 s 与主存地址的段内块号及块内地址拼接得到 Cache 地址。 如果没有相等的，则发出 Cache 块失效请求。 主存地址 段号 S 段内块号 B 块内地址 W 段号 s 段内块号 b 块内地址 w Cache 地址 相联比较 段 0 …… S 按地址访问 …… 段 1 s 1 …… ……… …… 主存段号 S Cache 段号 s 有效 位 …… Ms-1 段表（按地址和相联两种访问方式） 段相联地址变换方式 • 段相联方式的主要优点： 段表比较简单，实现的成本低。 例如：一个容量为 256KB 的 Cache，分成 8 个段，每段 2048 块，每块 16B。 在段表存储器中只需要存储 8 个主存地址的段号 S。 而在块表中要存储 8×2048＝16384 个区号（相当于段号）， 两者相差 2000 多倍。 • 段相联方式的主要缺点： 当发生段失效时，要把本段内已经建立起来的映象关系全部撤消
3.3.3 Cache替换算法及其实现 Cache替换算法使用时间: 发生段失效,且可以装入新调入块的几个 Cache块都已经被装满时 直接映象方式实际上不需要替换算法。 全相联映象方式的替换算法最复杂。 Cache替换算法要解决的问题: 1、记录每次访问 Cache的块号。 2、管理好所记录的 Cache块号,为找出被替换的块号提供方便。 3、根据记录和管理的结果,找出被替换的块号。 Cache替换算法的主要特点:全部用硬件实现 1、轮换法及其实现 用于组相联映象方式中,有两种实现方法。 方法一:每块一个计数器 在块表内增加一个替换计数器字段, 计数器的长度与 Cache地址中的组内块号字段的长度相同。 替换方法及计数器的管理规则: 新装入或替换的块,它的计数器清0;同组其它块的计数器都加 在同组中选择计数器的值最大的块作为被替换的块 ·例子: Solar-1665小型机的 Cache采用位选择组相联映象方式。 Cache每组的块数为4,因此,每块用一个2位的计数器 种轮换法的装入及替换过程 序列初始值装入块0装入块01装入块10装入块1替换块00 块00 10 块01 11 块10 10 块11 00 01 方法二:每组一个计数器 替换规则和计数器的管理: 本组有替换时,计数器加“1 计数器的值就是要被替换出去的块号。 例如:NOVA3机的 Cache采用组相联映象方式s Cache每组的块数为8,每组设置一个3位计数器。 在需要替换时,计数器的值加“1” 用计数器的值直接作为被替换块的块号 轮换法的优点:实现比较简单。 能够利用历史上的块地址流情况, 轮换法的缺点:没有利用程序的局部性特点
3—8 3.3.3 Cache 替换算法及其实现 • Cache 替换算法使用时间： 发生段失效，且可以装入新调入块的几个 Cache 块都已经被装满时。 直接映象方式实际上不需要替换算法。 全相联映象方式的替换算法最复杂。 • Cache 替换算法要解决的问题： 1、记录每次访问 Cache 的块号。 2、管理好所记录的 Cache 块号，为找出被替换的块号提供方便。 3、根据记录和管理的结果，找出被替换的块号。 • Cache 替换算法的主要特点：全部用硬件实现 1、轮换法及其实现 用于组相联映象方式中，有两种实现方法。 方法一：每块一个计数器 • 在块表内增加一个替换计数器字段， 计数器的长度与 Cache 地址中的组内块号字段的长度相同。 • 替换方法及计数器的管理规则： 新装入或替换的块，它的计数器清 0；同组其它块的计数器都加“1”。 在同组中选择计数器的值最大的块作为被替换的块。 • 例子：Solar-16/65 小型机的 Cache 采用位选择组相联映象方式。 Cache 每组的块数为 4，因此，每块用一个 2 位的计数器。 一种轮换法的装入及替换过程 序列 初始值 装入块00 装入块01 装入块10 装入块11 替换块00 块 00 00 00 01 10 11 00 块 01 00 01 00 01 10 11 块 10 00 01 10 00 01 10 块 11 00 01 10 11 00 01 方法二：每组一个计数器 • 替换规则和计数器的管理： 本组有替换时，计数器加“1”， 计数器的值就是要被替换出去的块号。 • 例如：NOVA3 机的 Cache 采用组相联映象方式。 Cache 每组的块数为 8，每组设置一个 3 位计数器。 在需要替换时，计数器的值加“1”， 用计数器的值直接作为被替换块的块号。 • 轮换法的优点：实现比较简单。 能够利用历史上的块地址流情况， • 轮换法的缺点：没有利用程序的局部性特点
2、LRU算法及其实现 在块表内为每一块设置一个计数器 计数器的长度与 Cache地址中的组内块号字段的长度相同。 计数器的使用及管理规则: 新装入或替换的块,其计数器清0,同组中其它块的计数器都加1。 命中的块,其计数器清0,同组的其它计数器中,凡是计数器的值小于命中 块所属计数器原来值的,都加1,其余计数器不变。 需要替换时,在同组的所有计数器中选择计数值最大的计数器,它所对应的 块就是要被替换的块 ·例子:IBM370165机的 Cache采用组相联映象方式。每组有4块,为了实 现LRU替换算法,在块表中为每一块设置一个2位的计数器。在访问 Cache的 过程中,块的装入、替换及命中时,计数器的工作情况如表 块地址流|主存块1主存块2「主存块3主存块4主存块5主存块4 块号计数器块号计数器块号计数器块号计数器块号计数器块号计数器 Cache块0 10 11500|501 Cache块101|200201210[211 cahe2閡0國103|003|o1|310310 Cache块3bd011014004014 00 装入装入装入装入替换命中 ●LRU算法的优点:命中率比较高 能够比较正确地利用程序的局部性特点, 充分地利用历史上块地址流的分布情况。 是一种堆栈型算法,随着组内块数增加,命中率单调上升, ●LRU算法的缺点 控制逻辑复杂,增加了判断和处理命中的情况。 3、比较对法 以三个块为例,三个块分别称为块A、B、C 表示方法 用TAB=1表示B块比A块更久没有被访问过, 如果要表示块C最久没有被访问过 从最近到最远分别是:A、B、C或B、A、C 即CLRU=TAB·TBC·TAC+TAB·TBC·TAC=TAB·TBC ARU=TAB·TAC BLRU=TAB·TBC ●每次访问之后要改变触发器的状态 在访问块A之后:TAB=1,TAC=1 在访问块B之后:TAB=0,TBC=1 在访问块C之后:TAC=0,TBC=0
3—9 2、LRU 算法及其实现 • 在块表内为每一块设置一个计数器， 计数器的长度与 Cache 地址中的组内块号字段的长度相同。 • 计数器的使用及管理规则： 新装入或替换的块，其计数器清 0，同组中其它块的计数器都加 1。 命中的块，其计数器清 0，同组的其它计数器中，凡是计数器的值小于命中 块所属计数器原来值的，都加 1，其余计数器不变。 需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的 块就是要被替换的块。 • 例子：IBM 370/165 机的 Cache 采用组相联映象方式。每组有 4 块，为了实 现 LRU 替换算法，在块表中为每一块设置一个 2 位的计数器。在访问 Cache 的 过程中，块的装入、替换及命中时，计数器的工作情况如表 块地址流 主存块 1 主存块 2 主存块 3 主存块 4 主存块 5 主存块 4 块号 计数器 块号 计数器 块号 计数器 块号 计数器 块号 计数器 块号 计数器 Cache块0 1 00 1 01 1 10 1 11 5 00 5 01 Cache块1 01 2 00 2 01 2 10 2 11 2 11 Cache块2 01 10 3 00 3 01 3 10 3 10 Cache块3 01 10 11 4 00 4 01 4 00 装入 装入 装入 装入 替换 命中 • LRU 算法的优点：命中率比较高 能够比较正确地利用程序的局部性特点， 充分地利用历史上块地址流的分布情况。 是一种堆栈型算法，随着组内块数增加，命中率单调上升。 • LRU 算法的缺点： 控制逻辑复杂，增加了判断和处理命中的情况。 3、比较对法 以三个块为例，三个块分别称为块 A、B、C • 表示方法： 用 TAB = 1 表示 B 块比 A 块更久没有被访问过， 如果要表示块 C 最久没有被访问过： 从最近到最远分别是：A、B、C 或 B、A、C 即 CLRU = TAB TBC TAC +TAB TBC TAC = TAB TBC LRU AB BC LRU AB AC B T T A T T = = • 每次访问之后要改变触发器的状态。 在访问块 A 之后：TAB＝1，TAC＝1 在访问块 B 之后：TAB＝0，TBC＝1 在访问块 C 之后：TAC＝0，TBC＝0
BLEU 与门 与门 与门 T T TBC 访问A 访问B 访问C 每组3个块的比较对法 硬件需求量计算: 需要的触发器个数为:c2=C 与门的个数为Gb个,每个与门的输入端个数为Gb-1个 其中:Gb为每组的块数。 每组块数34681664256 触发器个数3 15 28 120201632640 与门个数 643 6 16 64 256 与门输入端个2 7 15 63 255 当每组的块数比较多时,采用分级的办法实现 实质上是用降低速度来换取节省器件。 例如:IBM3033机的 Cache,每组的块数为16,分3级 从第1级到第3级分别为4、2、2。 共需要触发器个数为:6+4+8=18。 如果不分级则需要触发器120个 例如:IBM370/68机的 Cache,每组的块数为8,分2级 第1级为4,第2级为2。 总共需要触发器个数为:6+1×4=10个。 如果不分级,则需要28个触发器。 4、堆栈法 堆栈法的管理规则如下 把本次访问的块号与堆栈中保存的所有块号进行相联比较 如果有相等的,则 Cache命中。把本次访问的块号从栈顶压入,堆栈内各单 元中的块号依次往下移,直至与本次访问的块号相等的那个单元为止,再往下 的单元直止栈底都不变。 3-10
3—10 ALRU BLRU CLRU 与门 与门 与门 0 1 TAB 0 1 TAC 0 1 TBC 访问 A 访问 B 访问 C R S R S R S 每组 3 个块的比较对法 • 硬件需求量计算： 需要的触发器个数为： Gb b b C 2 G G 1 2 = ( − ) 与门的个数为 Gb 个，每个与门的输入端个数为 Gb-1 个 其中：Gb 为每组的块数。 每组块数 3 4 6 8 16 64 256 触发器个数 3 6 15 28 120 2016 32640 与门个数 3 4 6 8 16 64 256 与门输入端个 数 2 3 5 7 15 63 255 • 当每组的块数比较多时，采用分级的办法实现。 实质上是用降低速度来换取节省器件。 例如：IBM 3033 机的 Cache，每组的块数为 16，分 3 级。 从第 1 级到第 3 级分别为 4、2、2。 共需要触发器个数为：6＋4＋8＝18。 如果不分级则需要触发器 120 个。 例如：IBM 370/168 机的 Cache，每组的块数为 8，分 2 级。 第 1 级为 4，第 2 级为 2。 总共需要触发器个数为：6＋1×4＝10 个。 如果不分级，则需要 28 个触发器。 4、堆栈法 • 堆栈法的管理规则如下： 把本次访问的块号与堆栈中保存的所有块号进行相联比较。 如果有相等的，则 Cache 命中。把本次访问的块号从栈顶压入，堆栈内各单 元中的块号依次往下移，直至与本次访问的块号相等的那个单元为止，再往下 的单元直止栈底都不变