计算机系统结构原理

现代计算机系统以存储器为中心现代计算机系统以存储器为中心 3.1 存储系统原理存储系统原理 3.2 虚拟存储器虚拟存储器 3.3 高速缓冲存储器高速缓冲存储器(Cache)3.4 三级存储系统三级存储系统第第3章章 存储系统存储系统11/3/20221 3.1 3.1 存储系统原理存储系统原理3.1.1 存储系统的定义存储系统的定义3.1.2 存储系统的层次结构存储系统的层次结构3.1.3 存储系统的频带平衡存储系统的频带平衡3.1.4 并行访问存储器并行访问存储器 3.1.5 交叉访问存储器交叉访问存储器 3.1.6 无冲突访问存储器无冲突访问存储器11/3/202223.1.1 3.1.1 存储系统的定义存储系统的定义 在一台计算机中，通常有多种存储器在一台计算机中，通常有多种存储器种类：种类：主存储器、主存储器、Cache、通用寄存器、缓冲、通用寄存器、缓冲存储器、磁盘存储器、磁带存储器、光盘存存储器、磁盘存储器、磁带存储器、光盘存储器等储器等材料工艺：材料工艺：ECL、TTL、MOS、磁表面、激、磁表面、激光，光，SRAM，DRAM访问方式：访问方式：随机访问、直接译码、先进先出、随机访问、直接译码、先进先出、相联访问、相联访问、块传送、文件组块传送、文件组11/3/20223 存储器的主要性能：存储器的主要性能：速度、容量、价格速度、容量、价格 速度速度用存储器的访问周期、读出时间、频带宽度等表示。容量容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示。价格价格用单位容量的价格表示，例如：$C/bit。组成存储系统的关键：组成存储系统的关键：把速度、容量和价格把速度、容量和价格不同的多个物理存储器组织成一个存储器，这不同的多个物理存储器组织成一个存储器，这个存储器的速度最快，存储容量最大，单位容个存储器的速度最快，存储容量最大，单位容量的价格最便宜。量的价格最便宜。11/3/202241.1.存储系统的定义存储系统的定义 两个或两个以上速度、容量和价格各不相同的两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用连接起来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一程序员是透明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。单位容量的价格接近最便宜的那个存储器。虚拟存储器系统：对应用程序员透明虚拟存储器系统：对应用程序员透明Cache存储系统：对系统程序员以上均透明存储系统：对系统程序员以上均透明11/3/20225 从从外外部部看看 T Tm mi in n（T T1 1，T T2 2，T Tn n），用用存存储储周周期期表表示示 S Sm ma ax x（S S1 1，S S2 2，S Sn n），用用M MB B或或G GB B表表示示 C Cm mi in n（C C1 1，C C2 2，C Cn n），用用每每位位的的价价格格表表示示1 1(T T1 1,S S1 1,C C1 1)2 2(T T2 2,S S2 2,C C2 2)n n(T Tn n,S Sn n,C Cn n)由多个存储器构成的存储系统由多个存储器构成的存储系统11/3/20226 系系 统统 程程 序序 员员 看看：速速 度度 接接 近近 C Ca ac ch he e 的的 速速 度度，存存 储储 容容 量量 是是 主主 存存 的的 容容 量量，每每 位位 价价 格格 接接 近近 主主 存存 储储 器器。C Ca ac ch he e 存存 储储 系系 统统C Ca ac ch he e主主 存存 储储 器器 在一般计算机系统中，有两种存储系统：在一般计算机系统中，有两种存储系统：CacheCache存储系统：由存储系统：由CacheCache和主存储器构成和主存储器构成 主要目的：提高存储器速度主要目的：提高存储器速度11/3/20227 应应用用程程序序员员看看：速速度度接接近近主主存存储储器器的的速速度度，存存储储容容量量是是虚虚拟拟地地址址空空间间，每每位位价价格格接接近近磁磁盘盘存存储储器器。虚虚拟拟存存储储系系统统主主存存储储器器磁磁盘盘存存储储器器虚拟存储系统：由主存储器和硬盘构成虚拟存储系统：由主存储器和硬盘构成 主要目的：扩大存储器容量主要目的：扩大存储器容量11/3/202282.2.存储系统的容量存储系统的容量要求：要求：提供尽可能大的地址空间提供尽可能大的地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址 CacheCache存储系统存储系统另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中 虚拟存储系统虚拟存储系统11/3/202293.3.存储系统的价格存储系统的价格计算公式：当S2S1时，CC2 S2与S1不能相差太大 （S S，C C，T T）由由两两个个存存储储器器构构成成的的存存储储系系统统M1（S1，C1，T1）M2（S2，C2，T2）CC SC SSS11221211/3/2022104.4.存储系统的速度存储系统的速度表示方法：表示方法：访问周期、存取周期、存储周期、存取时间等命中率定义：命中率定义：在在M1存储器中访问到的概率存储器中访问到的概率 其中：N1是对M1存储器的访问次数 N2是对M2存储器的访问次数访问周期与命中率的关系：访问周期与命中率的关系：THT1(1H)T2 当命中率H1时，TT1HNNN11211/3/202211存储系统的访问效率：存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之访问效率主要与命中率和两级存储器的速度之比有关比有关例例3.13.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：解：eTTTH TH THHf HTTTT11111122121()()(,)当当H H0.90.9时，时，e e1 11 1(0.9(0.95(15(10.9)0.9)0.720.72当当H H0.990.99时，时，e e2 21 1(0.99(0.995(15(10.99)0.99)0.960.9611/3/202212提高存储系统速度的两条途径：提高存储系统速度的两条途径：一是提高命中率一是提高命中率H H，二是两个存储器的速度不要相差太大二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提高命中率依靠提高命中率例例3.23.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2105 T。如果要使访问效率到达e0.9，问需要有多高的命中率？11/3/202213解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得：H0.999998888877777 0.9999990 9111 05.()HH5.采用预取技术提高命中率采用预取技术提高命中率 方法：方法：不命中时，把不命中时，把M2存储器中相邻多个单存储器中相邻多个单元组成的一个数据块取出来送入元组成的一个数据块取出来送入M1存储器中。存储器中。11/3/202214 计算公式：计算公式：其中：H是采用预取技术之后的命中率 H是原来的命中率 n为数据块大小与数据重复使用次数的乘积HHnn1例例3.33.3：在一个Cache存储系统中，当Cache的块大小为一个字时，命中率H0.8；假设数据的重复利用率为5，T25T1。计算块大小为个字时，Cache存储系统的命中率？并分别计算访问效率。11/3/20221599.0201208.01 2nnHH0.558.1/10.8)5(1(0.81e10.8H:Cache访问效率为：，块大小为一个字时当0.9604.1/10.99)5(1(0.991e2 0.99H:4Cache2访问效率为：，个字时块大小为当解：解：n4520，采用预取技术之后，命中率提高到：11/3/202216)2.(.4096140968.0)1.(.105)1(19.0mmHHH例例3.43.4：在一个虚拟存储系统中，T2105 T，原来的命中率只有0.8，如果访问磁盘存储器的数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：解：假设数据在主存储器中的重复利用率为m，根据前面给出的关系，有如下方程组：11/3/202217解方程组：解方程组：由方程(1)得到：0.9H+90000-90000H=1)3.(.1.8999989999:解这个方程得H次。复利用率至少为数据在主存储器中的重44mm4096140968.0 1.8999989999:)2()3(得到代入把2.01.8999940961.89999409689999mm82.179996.409m11/3/202218 证明方法一：证明方法一：采用预取技术之后，不命中率不命中率(1-H)(1-H)降低倍：降低倍：nnHHnHH111 1因此：即：新的不命中率，新的命中率nH111/3/202219 证明方法二：证明方法二：在原有命中率的计算公式中，把访问次数扩大到n倍。由于采用了预取技术，命中次数为：nN1(n-1)N2,不命中次数仍为N2，因此新的命中率为：nnHNNnNNnNnNNnNnNNnnNH1)()()()1(2121211212111/3/2022203.1.2 3.1.2 存储系统的层次结构存储系统的层次结构多个层次的存储器多个层次的存储器：第第1层：层：Register Files(寄存器堆寄存器堆)第第2层：层：Buffers(Lookahead)(先行缓冲站先行缓冲站)第第3层：层：Cache(高速缓冲存储器高速缓冲存储器)第第4层：层：Main Memory(主存储器主存储器)第第5层：层：Online Storage(联机存储器联机存储器)第第6层：层：Off-line Storage(脱机存储器脱机存储器)用用i表示层数，表示层数，则有：工作周期工作周期TiTi+1，存储容量：存储容量：SiSi+1，单位价格：单位价格：CiCi+111/3/202221 第第 1 层层 第第 2 层层 第第 3 层层 第第 4 层层 第第 5 层层 第第 6 层层CPU内内部部通通用用寄寄存存器器堆堆联联机机外外部部存存储储器器（磁磁盘盘存存储储器器等等）脱脱机机外外部部存存储储器器（磁磁带带，光光盘盘存存储储器器等等）指指令令和和数数据据缓缓冲冲栈栈C Ca ac ch he e（静静态态随随机机存存储储器器）SRAM）主主存存储储器器（动动态态随随机机存存储储器器 DRAM）存存储储容容量量越越来来越越大大每每位位的的价价格格越越来来越越便便宜宜访访问问速速度度越越来来越越快快各级存储器的主要主要性能特性各级存储器的主要主要性能特性 CPU CPU与主存储器的速度差距越来越大与主存储器的速度差距越来越大 目前相差目前相差两个数量级 今后今后CPUCPU与主存储器的速度差距会更大与主存储器的速度差距会更大存存储储器器层层次次 通通用用寄寄存存器器 缓缓冲冲栈栈 C Ca ac ch he e 主主存存储储器器 磁磁盘盘存存储储器器 脱脱机机存存储储器器 存存储储周周期期 1 10 0n ns s 1 10 0n ns s 1 10 06 60 0n ns s 6 60 03 30 00 0n ns s 1 10 03 30 0m ms s 2 22 20 0m mi in n 存存储储容容量量 5 51 12 2B B 20002000字字 页面大小应该为页面大小应该为2K2K字。字。10P034.01H15Pn11/3/202280时时间间t t1 12 23 34 45 56 67 78 89 91 10 0实实际际页页地地址址流流P P1 1P P2 2P P1 1P P5 5P P4 4P P1 1P P3 3P P4 4P P2 2P P4 4命命中中次次数数1 11 11 11 1*4 44 44 4*4 4*2 22 2先先进进先先出出算算法法2 22 22 22 2*1 11 11 11 1*4 4（F FI IF FO O 算算法法）5 55 55 5*3 33 33 33 3*调调入入 调调入入 命命中中 调调入入 替替换换 替替换换 替替换换 命命中中 替替换换 替替换换2 2 次次1 11 11 11 11 11 11 11 1*2 22 2最最久久没没有有使使用用算算法法2 22 22 2*4 44 44 4*4 44 44 4（L LR RU U 算算法法）5 55 5*5 5*3 33 33 3*3 3*调调入入 调调入入 命命中中 调调入入 替替换换 命命中中 替替换换 命命中中 替替换换 命命中中4 4 次次1 11 11 11 11 11 1*3 3*3 3*3 33 3最最优优替替换换算算法法2 22 22 22 2*2 22 22 22 22 2（O OP PT T 算算法法）5 5*4 44 44 44 44 44 4调调入入 调调入入 命命中中 调调入入 替替换换 命命中中 替替换换 命命中中 命命中中 命命中中5 5 次次三三种种页页面面替替换换算算法法对对同同一一个个页页地地址址流流的的调调度度过过程程11/3/202281例例3.10：一个循环程序，依次使用P1，P2，P3，P4页面，分配给它的主存页面数只有2个。在 FIFO和LRU算法中，发生“颠簸颠簸”现象。时时间间 t t1 12 23 34 45 56 67 78 8实实际际页页地地址址流流P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P3 3P P4 4命命中中次次数数1 11 11 1*4 44 44 4*3 33 3先先进进先先出出算算法法2 22 22 2*1 11 11 1*4 4（F FI IF FO O 算算法法）3 33 33 3*2 22 22 2*调调入入调调入入调调入入替替换换替替换换替替换换替替换换替替换换0 0 次次1 11 11 1*4 44 44 4*3 33 3最最久久没没有有使使用用算算法法2 22 22 2*1 11 11 1*4 4（L LR RU U 算算法法）3 33 33 3*2 22 22 2*调调入入调调入入调调入入替替换换替替换换替替换换替替换换替替换换0 0 次次1 11 11 11 11 1*1 11 11 1最最优优替替换换算算法法2 22 22 22 22 2*3 3*3 3（O OP PT T 算算法法）3 3*4 4*4 44 44 44 4*调调入入调调入入调调入入替替换换命命中中命命中中替替换换命命中中3 3 次次5.5.堆栈型替换算法堆栈型替换算法 定义：定义：对任意一个程序的页地址流作两次主对任意一个程序的页地址流作两次主存页面数分配，分别分配存页面数分配，分别分配 m 个主存页面和个主存页面和 n 个个主存页面，并且有主存页面，并且有 mn。如果在任何时刻。如果在任何时刻 t，主存页面数集合主存页面数集合 Bt 都满足关系：都满足关系：Bt（m）Bt（n），），则这类算法称为堆栈型替换算法。则这类算法称为堆栈型替换算法。堆栈型算法的基本特点是：堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。命中率也提高，至少不下降。11/3/202283时时间间t t1 12 23 34 45 56 67 78 89 91 10 01 11 11 12 2实实际际页页地地址址流流P P1 1P P2 2P P3 3P P4 4P P1 1P P2 2P P5 5P P1 1P P2 2P P3 3P P4 4P P5 5命命中中次次数数1 11 11 1*4 44 44 4*5 55 55 55 55 5*5 5*主主存存页页面面数数2 22 22 2*1 11 11 1*1 1*1 1*3 33 33 3N N3 33 33 33 3*2 22 22 22 22 2*4 44 4调调入入调调入入调调入入替替换换替替换换替替换换替替换换命命中中命命中中替替换换替替换换命命中中3 3次次1 11 11 11 11 1*1 1*5 55 55 55 5*4 44 4主主存存页页面面数数2 22 22 22 22 2*2 2*1 11 11 11 1*5 5N N4 43 33 33 33 33 33 3*2 22 22 22 2*4 44 44 44 44 44 4*3 33 33 3调调入入调调入入调调入入调调入入命命中中命命中中替替换换替替换换替替换换替替换换替替换换替替换换2 2次次F FI IF FO O算算法法在在主主存存页页面面数数增增加加时时命命中中率率反反而而下下降降11/3/2022843.2.5 3.2.5 提高主存命中率的方法提高主存命中率的方法影响主存命中率的主要因素：影响主存命中率的主要因素：(1)程序在执行过程中的页地址流分布情况。(2)(2)所采用的页面替换算法。所采用的页面替换算法。(3)(3)页面大小。页面大小。(4)(4)主存储器的容量主存储器的容量(5)(5)所采用的页面调度算法所采用的页面调度算法 以下，对后三个因素进行分析。以下，对后三个因素进行分析。1.1.页面大小与命中率的关系页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。页面大小为某个值时，命中率达到最大。11/3/202285页面大小与命中率关系的解释：页面大小与命中率关系的解释：假设At和At+1是相邻两次访问主存的逻辑地址，dAtAt+1。如果如果SpSp，随着，随着SpSp增大，增大，A At 和和 A At+1在同一页在同一页面的可能性增加，即随着面的可能性增加，即随着SpSp的增大而提高。的增大而提高。如果如果SpSp，A At和和A At+1一定不在同一个页面内。一定不在同一个页面内。随着随着SpSp增大，主存页面数减少，页面替换更增大，主存页面数减少，页面替换更加频繁。随着加频繁。随着SpSp的增大而降低。的增大而降低。11/3/202286当Sp比较小的时候，前一种情况是主要的，随着Sp的增大而提高。当Sp达到某一个最大值之后，后一种情况成为主要的，随着Sp的增大而降低。当页面增大时，造 成的浪费也要增加当页面减小时，页 表和页面表在主存 储器中所占的比例 将增加页面大小页面大小 SP命中率命中率1S2 S11/3/2022872.2.主存容量与命中率的关系主存容量与命中率的关系 主存命中率主存命中率H H随着分配给该程序的主存容量随着分配给该程序的主存容量S S的增加而单调上升。的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。1.0命命中中率率H 主存容量 S11/3/2022883.3.页面调度方式与命中率的关系页面调度方式与命中率的关系 请求式：请求式：当使用到的时候，再调入主存 预取式：预取式：在程序重新开始运行之前，把上次在程序重新开始运行之前，把上次 停止运行前一段时间内用到的页面先调入到停止运行前一段时间内用到的页面先调入到 主存储器，然后才开始运行程序。主存储器，然后才开始运行程序。预取式的主要优点：预取式的主要优点：可以避免在程序开始运行时，频繁发生页面 失效的情况。预取式的主要缺点：预取式的主要缺点：如果调入的页面用不上，浪费了调入的时间，占用了主存的资源。11/3/2022893.3 3.3 高速缓冲存储器高速缓冲存储器3.3.1 基本工作原理基本工作原理3.3.2 地址映象与变换方法地址映象与变换方法3.3.3 Cache替换算法及其实现替换算法及其实现3.3.4 Cache存储系统的加速比存储系统的加速比3.3.5 Cache的一致性问题的一致性问题3.3.6 Cache的预取算法的预取算法11/3/202290Cache 存储系统与虚拟存储系统的比较存储系统与虚拟存储系统的比较 存储系统存储系统 Cache 存储系统存储系统 虚拟存储虚拟存储系统系统 要达到的目标要达到的目标 提高速度提高速度 扩大容量扩大容量 实现方法实现方法 全部硬件全部硬件 软件为主软件为主,硬件为辅硬件为辅 两级存储器速度比两级存储器速度比 310 倍倍 105倍倍 页（块）大小页（块）大小 116 字字 1KB16KB 等效存储容量等效存储容量 主存储器主存储器 虚拟存储器虚拟存储器 透明性透明性 对系统和应用程序员对系统和应用程序员 仅对应用程序员仅对应用程序员 不命中时处理方式不命中时处理方式 等待主存储器等待主存储器 任务切换任务切换 11/3/202291 主存储器地址（来自主存储器地址（来自 CPU）块号块号 B 块内地址块内地址 W 主存地址主存地址 未命中未命中 主存主存Cache 地址变换地址变换 命中命中 已满已满 未满未满 块号块号 b 块内地址块内地址 w Cache地址地址 Cache 替换策略替换策略 替换块替换块 装入块装入块 Cache 数据送数据送 CPU（一个字）（一个字）主存储器 3.3.1 3.3.1 基本工作原理基本工作原理3.3.2 3.3.2 地址映象与变换方法地址映象与变换方法 地址映象：地址映象：把主存中的程序按照某种规则装入到把主存中的程序按照某种规则装入到Cache中，并中，并建立主存地址与建立主存地址与Cache地址之间的对应关系。地址之间的对应关系。地址变换：地址变换：当程序已经装入到当程序已经装入到Cache之后，在程序运行过程中，之后，在程序运行过程中，把主存地址变换成把主存地址变换成Cache地址。地址。在选取地址映象方法要考虑的主要因素：在选取地址映象方法要考虑的主要因素：地址变换的硬件实现容易、速度要快，地址变换的硬件实现容易、速度要快，主存空间利用率要高，主存空间利用率要高，发生块冲突的概率要小。发生块冲突的概率要小。11/3/2022931.1.全相联映象及其变换全相联映象及其变换 映象规则：映象规则：主存的任意主存的任意 一块可以映象到一块可以映象到Cache 中的任意一块。中的任意一块。（映象关系有CbMb种）块块 0块块 1块块 0块块 1块块 i块块 Cb-1Cache块块 Mb-1主主存存储储器器 地址变换规则地址变换规则 用硬件实现非常复杂用硬件实现非常复杂 块块号号 B 块块内内地地址址W 主主存存地地址址 Cache 地地址址 块块号号 b 块块内内地地址址 w 相相联联比比较较 命命中中 B b 主主存存块块号号 B Cache 块块号号 b 有有效效位位 目目录录表表（由由相相联联存存储储器器构构成成，共共 Cb个个字字）11/3/2022952.2.直接映象及其变换直接映象及其变换 映象规则：映象规则：主存储器中一块只能映象到主存储器中一块只能映象到Cache的一个特的一个特定的块中。定的块中。Cache地址的计算公式：地址的计算公式：bB mod Cb 其中：b为Cache块号，B是主存块号，Cb是Cache块数。实际上，Cache地址与主存储器地址的低位部地址与主存储器地址的低位部分完全相同。分完全相同。11/3/202296 直接映象方式的地址映象规则直接映象方式的地址映象规则 块块 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命中，否则该块已经作废。比较结果不相等，有效位为1，Cache中的该块是有用的，否则该块是空的。11/3/202298 主主存存地地址址 区区号号 E 块块号号 B 块块内内地地址址W Cache 地地址址 块块号号 b 块块内内地地址址 w 块块失失效效 相相等等比比较较 比比较较相相等等且且有有效效为为 1 E 1 访访问问 Cache 区区号号 E（按按地地址址访访问问）有有效效位位 区区表表存存储储器器 直接映象方式的地址变换规则直接映象方式的地址变换规则 11/3/202299 提高提高Cache速度的一种方法：速度的一种方法：把区号存储器与把区号存储器与Cache合并成一个存储器合并成一个存储器 区区号号 E 块块号号 B 块块内内地地址址W Cache 地地址址 块块号号 b 块块内内地地址址 w 送送 CPU 访访问问主主存存 相相等等比比较较 相相等等 1/w 选选择择 1 E D0 D1 Dw-1 有有效效位位 区区号号 E 数数据据 D0 数数据据 D1 数数据据 Dw-1 按按地地址址访访问问的的 Cache 2.2.直接映象及其变换的优缺点直接映象及其变换的优缺点 主要优点：主要优点：硬件实现很简单，不需要相联访问存储器硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不需要进行地访问速度也比较快，实际上不需要进行地址变换址变换 主要缺点：主要缺点：块的冲突率比较高。块的冲突率比较高。11/3/20221013.3.组相联映象及其变换组相联映象及其变换 映象规则：映象规则：主存和主存和Cache按同样大小划分成块和组。按同样大小划分成块和组。主存和主存和Cache的组之间采用直接映象方式。的组之间采用直接映象方式。在两个对应的组内部采用全相联映象方式。在两个对应的组内部采用全相联映象方式。组相联映象方式的优点：组相联映象方式的优点：块的冲突概率比较低，块的冲突概率比较低，块的利用率大幅度提高，块的利用率大幅度提高，块失效率明显降低。块失效率明显降低。组相联映象方式的缺点：组相联映象方式的缺点：实现难度和造价要比直接映象方式高。实现难度和造价要比直接映象方式高。11/3/2022102 块块 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没有命中。11/3/2022104 区区号号 E 组组号号 G 组组内内块块号号 B 块块内内地地址址 W 主主存存地地址址 组组号号 g 组组内内块块号号 b 块块内内地地址址 w Cache 地地址址 不不等等 相相联联比比较较 相相等等 相相联联比比较较(Gb个个块块)区区号号 E,组组内内块块号号 B 组组内内块块号号 b 块块 表表 组相联映象的地址变换组相联映象的地址变换 提高提高Cache访问速度的一种方法：访问速度的一种方法：用多个相等比较器来代替相联访问用多个相等比较器来代替相联访问区区号号 E区区内内组组号号 G组组内内块块号号 B块块内内地地址址 W 主主存存地地址址 块块失失效效组组号号 g组组内内块块号号 b块块内内地地址址 w 与与Cache 地地址址或或相相等等比比较较相相等等比比较较相相等等比比较较 E,B beE,Bb E,B be 块块表表(按按地地址址访访问问,读读出出的的多多个个字字段段进进行行相相联联比比较较,e 为为有有效效位位)组相联映象方式组相联映象方式典型机器的典型机器的 Cache 分组情况分组情况 机器型号机器型号 Cache 块数块数 Cb 每组的块数每组的块数 Gb Cache 组数组数 Cg 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 256 2 128 11/3/20221074.4.位选择组相联映象及其变换位选择组相联映象及其变换地址映象规则：地址映象规则：主存和主存和Cache都按同样大小分块，都按同样大小分块，Cache在分块的基础上再分组，在分块的基础上再分组，主存按照主存按照Cache的组容量分区。的组容量分区。主存的块与主存的块与Cache的组之间采用直接映象方式，的组之间采用直接映象方式，主存中的块与主存中的块与Cache中组内部的各个块之间采中组内部的各个块之间采用全相联映象方式。用全相联映象方式。与组相联映象方式比较：与组相联映象方式比较：映象关系明显简单，实现起来容易。映象关系明显简单，实现起来容易。在块表中存放和参与相联比较的只有区号在块表中存放和参与相联比较的只有区号E11/3/2022108 位选择组相联的地址映象规则位选择组相联的地址映象规则 块块 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 主主存存储储器器 区区号号 E区区内内块块号号 B块块内内地地址址 W 主主存存地地址址 块块失失效效组组号号 g组组内内块块号号 b块块内内 w 与与Cache 地地址址或或相相等等比比较较相相等等比比较较 相相等等比比较较 E b E b E b区区号号E块块号号be区区号号E块块号号be区区号号E块块号号be块块表表(按按地地址址访访问问,读读出出的的多多个个区区号号进进行行相相联联比比较较,e 是是有有效效位位)位选择组相联的地址变换规则位选择组相联的地址变换规则5.5.段相联映象及其变换段相联映象及其变换映象规则：映象规则：主存和主存和Cache都按同样大小分块和段都按同样大小分块和段 段之间采用全相联映象方式段之间采用全相联映象方式 段内部的块之间采用直接映象方式段内部的块之间采用直接映象方式地址变换过程：地址变换过程：用主存地址中的段号与段表中的主存段号进行用主存地址中的段号与段表中的主存段号进行相联比较相联比较如果有相等的，用主存地址的段内块号按地址如果有相等的，用主存地址的段内块号按地址访问访问Cache的段号部分。的段号部分。把读出的段号s与主存地址的段内块号b及块内地址w拼接起来得到Cache地址；11/3/2022111 段相联映象地址映象规则段相联映象地址映象规则 块块 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 主主 存存 储储 器器 主主 存存 地地 址址段段 号号 S段段 内内 块块 号号 B块块 内内 地地 址址 W段段 号号 s段段 内内 块块 号号 b块块 内内 地地 址址 wC ache 地地 址址相相 联联 比比 较较 段段 0 S 按按 地地 址址 访访 问问 段段 1s1 主主 存存 段段 号号 SC ache 段段 号号 s有有 效效 位位 Ms-1 段段 表表（按按 地地 址址 和和 相相 联联 两两 种种 访访 问问 方方 式式）段段相相联联映映象象地地址址变变换换过过程程段相联映象方式的优缺点段相联映象方式的优缺点主要优点：主要优点：段表比较简单，实现的成本低。段表比较简单，实现的成本低。例如：例如：一个容量为256KB的Cache，分成8个段，每段2048块，每块16B。在段表存储器中只需要存8个主存地址的段号,而在块表中要存储8204816384个区号，两者相差2000多倍。主要缺点：主要缺点：当发生段失效时，要把本段内已经建立起来的所有映象关系全部撤消。11/3/20221143.3.3 Cache3.3.3 Cache替换算法及其实现替换算法及其实现使用的场合：使用的场合：直接映象方式实际上不需要替换算法直接映象方式实际上不需要替换算法 全相联映象方式的替换算法最复杂全相联映象方式的替换算法最复杂 主要用于主要用于组相联组相联、段相联等映象方式中、段相联等映象方式中要解决的问题：要解决的问题：记录每次访问记录每次访问Cache的块号的块号在访问过程中，对记录的块号进行管理在访问过程中，对记录的块号进行管理根据记录和管理结果，找出替换的块号根据记录和管理结果，找出替换的块号主要特点：主要特点：全部用硬件实现全部用硬件实现11/3/20221151.1.轮换法及其实现轮换法及其实现 用于组相联映象方式中，有两种实现方法。方法一：每块一个计数器方法一：每块一个计数器在块表内增加一个替换计数器字段，在块表内增加一个替换计数器字段，计数器的长度与Cache地址中的组内块号字段的长度相同。替换方法及计数器的管理规则：替换方法及计数器的管理规则：新装入或替换的块，它的计数器清新装入或替换的块，它的计数器清0，同组其，同组其它块的计数器都加它块的计数器都加“1”。在同组中选择计数器的值最大的块作为被替换在同组中选择计数器的值最大的块作为被替换的块。的块。11/3/2022116例例3.11：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 11/3/2022117方法二：每组一个计数器方法二：每组一个计数器替换规则和计数器的管理：替换规则和计数器的管理：本组有替换时，计数器加本组有替换时，计数器加“1”，计数器的值就是要被替换出去的块号。计数器的值就是要被替换出去的块号。例例3.12：NOVA3机的Cache采用组相联映象方式，Cache每组的块数为8，每组设置一个3位计数器。在需要替换时，计数器的值加“1”，用计数器的值直接作为被替换块的块号。轮换法的优点：轮换法的优点：实现比较简单，能够利用历史实现比较简单，能够利用历史上的块地址流情况上的块地址流情况轮换法的缺点：轮换法的缺点：没有利用程序的局部性特点没有利用程序的局部性特点11/3/20221182.LRU2.LRU算法及其实现算法及其实现为每一块设置一个计数器为每一块设置一个计数器 计数器的长度与块号字段的长度相同计数器的使用及管理规则：计数器的使用及管理规则：新装入或替换的块，计数器清新装入或替换的块，计数器清0，同组中其它，同组中其它块的计数器加块的计数器加1。命中块的计数器清命中块的计数器清0，同组的其它计数器中，同组的其它计数器中，凡计数器的值小于命中块计数器原来值的加凡计数器的值小于命中块计数器原来值的加1，其余计数器不变。，其余计数器不变。需要替换时，在同组的所有计数器中选择计数需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块被替换。值最大的计数器，它所对应的块被替换。11/3/2022119LRU算法的优缺点算法的优缺点主要优点：主要优点：(1)命中率比较高，命中率比较高，(2)能够比较正确地利用程序的局部性特点，能够比较正确地利用程序的局部性特点，(3)充分地利用历史上块地址流的分布情况，充分地利用历史上块地址流的分布情况，(4)是一种堆栈型算法，随着组内块数增加，是一种堆栈型算法，随着组内块数增加，命中率单调上升。命中率单调上升。主要缺点：主要缺点：控制逻辑复杂，控制逻辑复杂，因为增加了判断和处理是否命中的情况。11/3/2022120例例3.13：IBM 370/165机的Cache采用组相联映象方式。每组有4块，为了实现LRU替换算法，在块表中为每一块设置一个 2 位的计数器。在访问Cache的过程中，块的装入、替换及命中时，计数器的工作情况如表：块块地地址址流流主主存存块块1主主存存块块2主主存存块块3主主存存块块4主主存存块块5主主存存块块4块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器Cache块块0100101110111500501Cache块块101200201210211211Cache块块20110300301310310Cache块块3011011400401400装装入入装装入入装装入入装装入入替替换换命命中中11/3/20221213.3.比较对法比较对法 以三个块为例，分别称为块A、块B、块C 表示方法：表示方法：用TAB1表示 B块比 A 块更久没有被访问过。如果表示块 C 最久没有被访问过：每次访问之后要改变触发器的状态每次访问之后要改变触发器的状态 在访问块A之后：TAB1，TAC1 在访问块B之后：TAB0，TBC1 在访问块C之后：TAC0，TBC0ACBCACBCABACBCABLRUTTTTTTTTCBCABLRUACABLRUTTBTTA11/3/2022122 ALRU BLRUCLRU与门与门与门与门与门与门 0 1TAB 0 1TAC 0 1TBC R S R S R S 访问访问 A 访问访问 B 访问访问 C 每组个块的比较对法每组个块的比较对法11/3/2022123比较对法硬件需求量计算：比较对法硬件需求量计算：需要的触发器个数为：与门个数为Gb，每个门的输入端个数为Gb-1当每组的块数比较多时当每组的块数比较多时,采用分级办法实现 实质上是用降低速度来换取节省器件。例例3.14：IBM 3033机的Cache，每组的块数为16，分3级。从第1级到第3级分别为4、2、2。共需要触发器个数为：64818。如果不分级则需要触发器120个。bGbbCGG212()11/3/2022124 每每组组块块数数 3 3 4 4 6 6 8 8 1 16 6 6 64 4 2 25 56 6 触触发发器器个个数数 3 3 6 6 1 15 5 2 28 8 1 12 20 0 2 20 01 16 6 3 32 26 64 40 0 与与门门个个数数 3 3 4 4 6 6 8 8 1 16 6 6 64 4 2 25 56 6 与与门门输输入入端端数数 2 2 3 3 5 5 7 7 1 15 5 6 63 3 2 25 55 5 比较对法中每组块数与所需硬件的关系比较对法中每组块数与所需硬件的关系11/3/20221254.4.堆栈法堆栈法堆栈法的管理规则：堆栈法的管理规则：把本次访问的块号与堆栈中保存的所有块号进把本次访问的块号与堆栈中保存的所有块号进行相联比较。行相联比较。如果有相等的，则如果有相等的，则Cache命中。把本次访问块号命中。把本次访问块号从栈顶压入，堆栈内各单元中的块号依次往从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个单下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。元为止，再往下的单元直止栈底都不变。如果没有相等的，则Cache块失效。本次访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底，栈底单元中的块号被移出堆栈，它就是要被替换的块号。11/3/2022126 本次访问的块号本次访问的块号 栈顶栈顶 最近访问过的块最近访问过的块 压入过程到此为止压入过程到此为止 与本次访问的块号与本次访问的块号相等相等 栈底栈底 最久没有被访问过最久没有被访问过的块的块 例如：例如：每组为4块，则堆栈有4个存储单元，每个单元2位。NAIAIANBIBIBNCICIC()()()()()()00110011001111/3/2022127 每组每组4块的堆栈法逻辑图块的堆栈法逻辑图 I0 I1 CP D C A0 1 D C A1 1 NA 与门 D C B0 1 D C B1 1 NB 与门 D C C0 1 D C C1 1 NC 与门 D C D0 1 D C D1 1 D0 D1 堆栈法的主要优点：堆栈法的主要优点：块失效率比较低，因为它采用了块失效率比较低，因为它采用了LRU算法。算法。硬件实现相对比较简单。硬件实现相对比较简单。堆栈法的主要缺点：堆栈法的主要缺点：速度比较低，因为它需要进行相联比较。速度比较低，因为它需要进行相联比较。堆栈法与比较对法所用触发器的比例：堆栈法与比较对法所用触发器的比例：其中，Gb是Cache每一组的块数。当Gb大于8时，堆栈法所用的器件明显少于比较对法。GGGGbbbb()log122：11/3/20221293.3.4 Cache3.3.4 Cache存储系统的加速比存储系统的加速比1.1.加速比与命中率的关系加速比与命中率的关系Cache存储系统的加速比SP为：其中：Tm为主存储器的访问周期，Tc为Cache的访问周期，T为Cache存储系统的等效访问周期，H为命中率。提高加速比的最好途径是提高命中率提高加速比的最好途径是提高命中率STTTH TH THHTTf HTTpmmcmcmmc()()(,)11111/3/2022130 加速比加速比 SP 能够接近于期望值是能够接近于期望值是：加速比加速比SP与命中率与命中率H的关系的关系SP期望值期望值1命中率命中率 HSP max=TmTcTTmc11/3/20221312.Cache2.Cache命中率与容量的关系命中率与容量的关系 Cache的命中率随它的容量的增加而提高。的命中率随它的容量的增加而提高。关系曲线可以近似地表示为：容量容量 S命中率命中率 H1SH1111/3/20221323.Cache3.Cache命中率与块大小的关系命中率与块大小的关系 在组相联方式中在组相联方式中,块大小对命中率非常敏感块大小对命中率非常敏感 块很小时，命中率很低。随着块大小增加命中率也增加,有一个极大值有一个极大值 当块非常大时,进入Cache中的数据可能无用 当块大小等于Cache容量时,命中率将趋近零4.Cache4.Cache命中率与组数的关系命中率与组数的关系 在组相联方式中在组相联方式中,组数对命中率的影响很明显组数对命中率的影响很明显 随着组数的增加，Cache的命中率要降低。当组数不太大时(小于512),命中率的降低很少 当组数超过一定数量时,命中率的下降非常快11/3/2022133 Cache命中率与块大小的关系命中率与块大小的关系块大小命中率 H1初始 最 佳11/3/20221343.3.5 Cache3.3.5 Cache的一致性的一致性造成造成Cache与主存的不一致的原因：与主存的不一致的原因：(1)由于CPU写Cache，没有立即写主存 (2)由于IO处理机或IO设备写主存CPUI/OCPUI/OCacheXCacheX主主存存储储器器X主主存存储储器器X(a)CPU写写Cache (b)I/O写写主主存存Cache的更新算法的更新算法 (1)写直达法，写直达法，写通过法，写通过法，WT(Write-through)CPU的数据写入Cache时，同时也写入主存 (2)写回法，写回法，抵触修改法，抵触修改法，WB(Write-Back)CPU的数据只写入Cache，不写入主存，仅当替换时，才把修改过的Cache块写回主存写回法写回法与与写直达法写直达法的优缺点比较：的优缺点比较：(1)可靠性，写直达法优于写回法。可靠性，写直达法优于写回法。写直达法能够始终保证Cache是主存的副本。如果Cache发生错误，可以从主存得到纠正。11/3/2022136 (2)与主存的通信量，写回法少于写直达法。与主存的通信量，写回法少于写直达法。对于写回法：大多数操作只需要写Cache，不需要写主存；当发生块失效时，可能要写一个块到主存；即使是读操作，也可能要写一个块到主存。对于写直达法：每次写操作，必须写、且只写一个字到主存。实际上：写直达法的写次数很多、每次只写一个字；写回法是的写次数很少、每次要写一个块。举例说明：11/3/2022137例例3.15：写操作占总访存次数的20,Cache的命中率为99，每块为4个字。当Cache发生块替换时，有30块需要写回到主存，其余的块因为没有被修改过而不必写回主存。试比较写回法与写直达法的访存通信量。解：解：对于写直达法：写主存次数占总访存次数的20，对于写回法：(199)3041.2。因此，与主存的通信量，写回法要比写直达法少与主存的通信量，写回法要比写直达法少10多倍。多倍。11/3/2022138 (3)控制的复杂性控制的复杂性,写直达法比写回法简单。写直达法比写回法简单。对于写回法：要为每块设置一个修改位，而且要对修改位进行管理；为了保证Cache的正确性，通常要采用比较复杂的校验方式或校正方式。对于写直达法：不需要设置修改位；只需要采用简单的奇偶校验即可。由于Cache始终是主存的副本，Cache一旦有错误可以从主存得到纠正。11/3/2022139 (4)硬件实现的代价硬件实现的代价,写回法要比写直达法好。写回法要比写直达法好。对于写直达法：为了缩短写Cache流水段的时间，通常要设置一个小容量的高速寄存器堆（后行写数缓冲站），每个存储单元要有数据、地址和控制状态等3部分组成。每次写主存时，首先把写主存的数据和地址写到高速寄存器堆中。每次读主存时，要首先判断所读数据是否在这个高速寄存器堆中。写回法不需要设置高速缓冲寄存器堆。11/3/2022140 写写Cache的两种方法：的两种方法：(1)不按写分配法：不按写分配法：在写Cache不命中时，只把所要写的字写入主存。(2)按写分配法：按写分配法：在写Cache不命中时，还把一个块从主存读入Cache。目前，在写回法中采用按写分配法，在写回法中采用按写分配法，在写直达法中采用不按写分配法。在写直达法中采用不按写分配法。11/3/2022141解决解决Cache与主存不一致的主要方法：与主存不一致的主要方法：(1)共享共享Cache法。法。能根本解决Cache不一致，共享Cache可能成为访问的瓶颈，硬件复杂 (2)作废法。作废法。当某一处理机写局部Cache时，同时作废其他处理机的局部Cache。(3)播写法。播写法。把写Cache的内容和地址放到公共总线上，各局部Cache随时监听公共总线 (4)目录表法。目录表法。在目录表中存放Cache一致性的全部信息。(5)禁止共享信息放在局部禁止共享信息放在局部Cache中。中。Cac