计算机系统结构第5章_存储系统.ppt

计算机系统结构计算机系统结构第五章第五章 存储系统存储系统5.1 存储系统介绍存储系统 指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统。计算机系统中，一般使用具有层次结构的存储系统，主要可分为三个存储层面：高速缓冲存储器、主存储器和辅助存储器。高速缓冲存储器主要用于改善主存储器与中央处理器（CPU）的速度匹配问题，而辅助存储器则主要用于扩大计算机系统的存储空间。5.1.1 存储系统的层次结构层次存储系统是指把各种不同存储容量、存取速度、访问方式和单位存储价格的存储器，按照一定的层次结构组成多层存储器，并通过管理软件和辅助硬件有机组合成统一的存储体系，使计算机系统中使用到的各种程序和数据层次的分布到各个存储器中。辅助软硬件辅助软硬件主存主存辅存辅存图5-1 主/辅存结构5.1.1 5.1.1 存储系统的定义存储系统的定义 在一台计算机中，通常有多种存储器在一台计算机中，通常有多种存储器种类：种类：主存储器、主存储器、Cache、通用寄存器、缓冲存储器、通用寄存器、缓冲存储器、磁盘存储器、磁带存储器、光盘存储器等磁盘存储器、磁带存储器、光盘存储器等材料工艺：材料工艺：ECL、TTL、MOS、磁表面、激光，、磁表面、激光，SRAM，DRAM访问方式：访问方式：随机访问、直接译码、先进先出、随机访问、直接译码、先进先出、相联访问、相联访问、块传送、文件组块传送、文件组 存储器的主要性能：存储器的主要性能：速度、容量、价格速度、容量、价格 速度速度用存储器的访问周期、读出时间、频带宽度等表示。容量容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示。价格价格用单位容量的价格表示，例如：$C/bit。组成存储系统的关键：组成存储系统的关键：把速度、容量和价格不同的多个物理把速度、容量和价格不同的多个物理存储器组织成一个存储器，这个存储器的速度最快，存储容量存储器组织成一个存储器，这个存储器的速度最快，存储容量最大，单位容量的价格最便宜。最大，单位容量的价格最便宜。1.1.存储系统的定义存储系统的定义 两个或两个以上速度、容量和价格各不相同的存储器用硬件、两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用程序员是透明的，并且，从应用程序员看，它是个存储系统对应用程序员是透明的，并且，从应用程序员看，它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。那个存储器。虚拟存储器系统：对应用程序员透明（通过操作系统的存储管虚拟存储器系统：对应用程序员透明（通过操作系统的存储管理系统调度）理系统调度）Cache存储系统：对系统程序员及以上均透明（全部用硬件调存储系统：对系统程序员及以上均透明（全部用硬件调度）度）由多个存储器构成的存储系统由多个存储器构成的存储系统n 在一般计算机系统中，有两种存储系统：在一般计算机系统中，有两种存储系统：CacheCache存储系统：由存储系统：由CacheCache和主存储器构成和主存储器构成 主要目的：提高存储器速度主要目的：提高存储器速度虚拟存储系统：由主存储器和硬盘构成虚拟存储系统：由主存储器和硬盘构成 主要目的：扩大存储器容量主要目的：扩大存储器容量2.2.存储系统的容量存储系统的容量对存储系统进行编址的要求：对存储系统进行编址的要求：提供尽可能大的地址空间提供尽可能大的地址空间能够随机访问能够随机访问方法有两种：方法有两种：只对系统中存储容量最大的那个存储器进行编址，其他存储器只在内部编址或不编址 CacheCache存储系统存储系统另外设计一个容量很大的逻辑地址空间，把相关存储器都映射这个地址空间中 虚拟存储系统虚拟存储系统3.3.存储系统的价格存储系统的价格计算公式：当S2S1时，CC2 S2与S1不能相差太大4.4.存储系统的速度存储系统的速度表示方法：表示方法：访问周期、存取周期、存储周期、存取时间等命中率定义：命中率定义：在在M1存储器中访问到的概率存储器中访问到的概率 其中：N1是对M1存储器的访问次数 N2是对M2存储器的访问次数访问周期与命中率的关系：访问周期与命中率的关系：THT1(1H)T2 当命中率H1时，TT1存储系统的访问效率：存储系统的访问效率：访问效率主要与命中率和两级存储器的速度之比有关访问效率主要与命中率和两级存储器的速度之比有关例例3.13.1：假设T2T，在命中率H为0.9和0.99两种情况下，分别计算存储系统的访问效率。解：解：当当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.96提高存储系统速度的两条途径：提高存储系统速度的两条途径：一是提高命中率一是提高命中率H H，二是两个存储器的速度不要相差太大二是两个存储器的速度不要相差太大其中：第二条有时做不到(如虚拟存储器)，这时，只能依靠提依靠提高命中率高命中率例例5.25.2：在虚拟存储系统中，两个存储器的速度相差特别悬殊，例如：T2105 T。如果要使访问效率到达e0.9，问需要有多高的命中率？解：解：0.9H90000(1-H)189999.1 H89999计算得：计算得：H0.999998888877777 0.9999995.采用预取技术提高命中率采用预取技术提高命中率 方法：方法：不命中时，把不命中时，把M2存储器中相邻多个单存储器中相邻多个单元组成的一个数据块取出来送入元组成的一个数据块取出来送入M1存储器中。存储器中。计算公式：计算公式：其中：H是采用预取技术之后的命中率 H是原来的命中率 n为数据块大小与数据重复使用次数的乘积例例5.35.3：在一个Cache存储系统中，T25T1。当Cache的块大小为一个字时，命中率H0.8。假设数据的重复利用率为5，Cache块大小为个字，Cache存储系统的命中率？并分别计算访问效率。解：解：n4520，采用预取技术之后，命中率提高到：例例5.45.4：在一个虚拟存储系统中，T2105 T，原来的命中率只有0.8，如果访问磁盘存储器的数据块大小为4K字，并要求访问效率不低于0.9，计算数据在主存储器中的重复利用率至少为多少？解：解：假设数据在主存储器中的重复利用率为m，根据前面给出的关系，有如下方程组：解方程组：解方程组：由方程(1)得到：0.9H+90000-90000H=15.1.2 5.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+1各级存储器的主要主要性能特性各级存储器的主要主要性能特性 CPUCPU与主存储器的速度差距越来越大与主存储器的速度差距越来越大 目前相差目前相差两个数量级 今后今后CPUCPU与主存储器的速度差距会更大与主存储器的速度差距会更大5.1.3 5.1.3 存储系统的频带平衡存储系统的频带平衡例例5.5：Pentium4的指令执行速度为8GIPS，CPU取指令8GW/s，访问数据16GW/s，各种输入输出设备访问存储器1GW/s，三项相加，要求存储器的频带宽度不低于25GW/s。如果采用PC133内存，主存与CPU速度差188倍 如果采用PC266内存，主存与CPU速度差94倍解决存储器频带平衡方法解决存储器频带平衡方法 (1)多个存储器并行工作多个存储器并行工作 (2)设置各种缓冲存储器设置各种缓冲存储器 (3)采用存储系统采用存储系统5.1.4 5.1.4 并行访问存储器并行访问存储器方法：方法：把把m字字w位的存储器改变成为位的存储器改变成为m/n字字nw位的存储器位的存储器逻辑实现：逻辑实现：把地址码分成两个部分，一部分作为存储器的地址把地址码分成两个部分，一部分作为存储器的地址另一部分负责选择数据另一部分负责选择数据主要缺点：访问冲突大主要缺点：访问冲突大 (1)(1)取指令冲突取指令冲突 (2)(2)读操作数冲突读操作数冲突 (3)(3)写数据冲突写数据冲突 (4)(4)读写冲突读写冲突 并行访问存储器结构框图并行访问存储器结构框图1.1.高位交叉访问存储器高位交叉访问存储器主要目的：主要目的：扩大存储器容量扩大存储器容量实现方法：实现方法：用地址码的高位部分区分存储体号用地址码的高位部分区分存储体号参数计算方法参数计算方法:m：每个存储体的容量，n：总共的存储体个数，j：存储体的体内地址，j0，1，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器的地址：Amkj 存储器的体内地址：AjA mod m。存储器的体号：Ak 5.1.5 5.1.5 交叉访问存储器交叉访问存储器 高位交叉访问存储器结构框图高位交叉访问存储器结构框图2.2.低位交叉访问存储器低位交叉访问存储器 主要目的：主要目的：提高存储器访问速度提高存储器访问速度 实现方法：实现方法：用地址码的低位部分区分存储体号用地址码的低位部分区分存储体号 参数计算参数计算:m：每个存储体的容量，n：总共的存储体个数，j：存储体的体内地址，j0，1，2，.，m-1 k：存储体的体号，k0，1，2，.，n-1 存储器地址A的计算公式为：Anjk 存储器的体内地址：Aj 存储器的体号：AkA mod n 低位交叉访问存储器结构框图低位交叉访问存储器结构框图 地址是编码方法：地址是编码方法：由由8 8个存储体构成的低位交叉编址方式个存储体构成的低位交叉编址方式 n n个存储体分时启动个存储体分时启动 一种采用流水线方式工作的并行存储器 每存储体的启动间隔为：t 其中：Tm为每个存储体的访问周期,n为存储体个数。访问冲突访问冲突 共有共有n n个存储体，每个存储周期只能取到个存储体，每个存储周期只能取到k k个有效字个有效字,其余其余n-kn-k个存储体有冲突。个存储体有冲突。假设p(k)是k的概率密度函数，即p(1)是k1的概率，p(2)是k2的概率，,p(n)是kn的概率。k的平均值为：N是每个存储周期能够访问到的平均有效字的个数。通常把 N N称为并行存储器的加速比。称为并行存储器的加速比。定义转移概率为g，即读出的是转移指令，且转移成功的概率。这时有：p(1)p(1)g g p(2)p(2)(1-p(1)g(1-p(1)g(1-g)g(1-g)g p(3)p(3)(1-p(1)-p(2)g(1-p(1)-p(2)g(1-g)(1-g)2 2g g p(k)p(k)(1-g)(1-g)k-1k-1g(g(k1,2,n1)p(n)p(n)(1-g)(1-g)n-1n-1 g g(1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)g(1-g)g(1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)2 2g g(1-g)(1-g)n-2n-2g g (1-g)(1-g)n-2n-2g g n(1-g)n(1-g)n-1n-1以上共以上共n n行，前行，前n-2n-2行分别为等比级数行分别为等比级数把把n-1n-1行拆分成行拆分成2 2项项则：则：1g1g2(1-g)g2(1-g)g3(1-g)3(1-g)2 2g g (n-1)(1-g)(n-1)(1-g)n-2n-2g gn(1-g)n(1-g)n-1n-11-(1-g)1-(1-g)n-1n-11-(1-g)1-(1-g)n-1n-1 (1-g)-(1-g)(1-g)-(1-g)n-1n-1 (1-g)(1-g)2 2-(1-g)-(1-g)n-1n-1 (1-g)(1-g)n-2n-2-(1-g)-(1-g)n-1n-1 n(1-g)n(1-g)n-1n-11 1(1-g)(1-g)(1-g)(1-g)2 2(1-g)(1-g)n-2n-2(1-g)(1-g)n-1n-1例例5.7：Star-100巨型机存储系统采用并行和交叉相结合的方式工作，有32个存储体低位交叉，每次并行读写512位，存储周期为1280ns，处理机字长32位，计算它的速度提高多少倍？和频带宽度Bm。解：解：因为：n32，w512，Tm1280ns，Bmnw/tm32512b/1280ns 12.8Gb/s1.6GB/s400MW/s提高提高512512倍倍实际速度的提高要远远小于这个数字实际速度的提高要远远小于这个数字 5.1.6 5.1.6 无冲突访问存储器无冲突访问存储器1.1.一维数组一维数组(向量向量)的无冲突访问存储器的无冲突访问存储器 按连续地址访问，没有冲突，位移量为2的变址访问，速度降低一倍，具体方法：具体方法：存储体的个数取质数，且存储体的个数取质数，且nn向量长度。向量长度。原因：原因：变址位移量必然与存储体个数互质 例如：例如：Burroughs公司巨型科学计算机BSP 存储体个数为17 向量长度16我国研制的银河巨型向量机 存储体的个数为37 向量长度322.2.二维数组的无冲突访问存储器二维数组的无冲突访问存储器要求：要求：一个一个nn的二维数组，按行、列、对角线和反对角线访的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问。问，并且在不同的变址位移量情况下，都能实现无冲突访问。顺序存储：顺序存储：按行、对角线访问没有冲突，但按列访问每次冲突 错位存储：错位存储：按行、按列访问无冲突，但按对角线访问有冲突nn二维数组无冲突访问存储方案二维数组无冲突访问存储方案 (P Budnik 和和 D J Kuck提出提出)：并行存储体的个数并行存储体的个数mn，并且取质数，同时还要在行、列方，并且取质数，同时还要在行、列方向上错开一定的距离存储数组元素。向上错开一定的距离存储数组元素。设同一列相邻元素在并行存储器中错开设同一列相邻元素在并行存储器中错开d1个存储体存放，同个存储体存放，同一行相邻元素在并行存储器中错开一行相邻元素在并行存储器中错开d2个存储体存放。当个存储体存放。当m22p1（p为任意自然数）时，能够同时实现按行、按列、为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：按对角线和按反对角线无冲突访问的充要条件是：d12P，d21。例如：例如：44的二维数组，取并行存储体的个数的二维数组，取并行存储体的个数m5，由关系，由关系式式m22P1，解得到，解得到p1，计算得到：，计算得到：d1212 d2145 nn数组中的任意一个元素数组中的任意一个元素aij在无冲突并行存储器中的体号地在无冲突并行存储器中的体号地址和体内地址的计算公式：址和体内地址的计算公式：体号地址：体号地址：(2P ijk)MOD m 体内地址：体内地址：i 其中：0in1，0jn1，k是数组的第一个元素a00所在体号地址，m是并行存储体的个数，要求mn且为质数，p是满足m22P1关系的任意自然数。主要缺点：主要缺点：浪费存储单元 对于对于nn数组数组,有有(m-n)m个存储单元浪费个存储单元浪费 主要优点：主要优点：实现简单 列元素顺序存储，行元素按地址取模顺序存储列元素顺序存储，行元素按地址取模顺序存储3.3.二维数组的无冲突访问存储器二维数组的无冲突访问存储器(之二之二)规则：规则：对于任意一个对于任意一个nn的的数组，如果能够找到满足数组，如果能够找到满足n22P关关系的任意自然数系的任意自然数p，则这个二维数组就能够使用，则这个二维数组就能够使用n个并行存储个并行存储体体实现按行、列、对角线和反对角线的无冲突访问。实现按行、列、对角线和反对角线的无冲突访问。4 44 4数组用数组用4 4个存储体的无访问冲突存储方案个存储体的无访问冲突存储方案实现方法：实现方法：假设假设aij是是4 44 4数组中的任意一个元素，数组中的任意一个元素，下标下标i和和j都可以用两位都可以用两位二进制表示。假设二进制表示。假设i和和j的高位和低位分别为的高位和低位分别为iH、iL、jH和和jL，则则aij在无冲突并行存储器中的体号地址和体内地址如下：在无冲突并行存储器中的体号地址和体内地址如下：体号地址：体号地址：2(iL jH)(iH iL jL)体内地址：体内地址：j 其中：其中：0i3，0j3主要优点：主要优点：没有浪费的存储单元没有浪费的存储单元，主要缺点：主要缺点：在执行并行读和写操作时需要借助比较复杂的对准网在执行并行读和写操作时需要借助比较复杂的对准网络络。5.2 高速缓冲存储器Cache计算机系统为改善CPU与主存储器之间的速度匹配问题，在CPU和主存储器之间加入一个高速、小容量的缓冲存储器Cache，构成Cache主存储器的存储系统，使得存储系统对CPU而言，速度接近于高速缓冲存储器Cache，存储容量接近于主存储器。Cache存储器主要由三个部分组成：(1)Cache存储器，用于存放由主存储器调入的指令与数据块；(2)地址转换部件，用于实现主存储器地址到Cache存储器地址的转换；(3)替换部件，当缓存满时根据指定策略进行数据块替换，并对地址转换部件做对应修改。Cache工作原理Cache工作原理(续1)系统工作时，地址转换部件维护一个映射表，用于确定Cache存储器中是否有所要访问的块，以及确定其位置。该映射表中的每一项对应于Cache存储器的一个分块，用于指出当前该块中存放的信息对应于主存储器的哪个分块。为提高CPU对Cache存储器的访问命中率，Cache存储器的工作原理是基于程序访问局部性原理程序访问局部性原理的，它不断地将与当前指令集相关联的一部分后继指令集从主存储器读取到Cache存储器，以供CPU访问，从而达到存储系统与CPU速度匹配的目的。5.2.2 地址映象与变换方法地址映象是将主存储器中的数据分块按某种规则装入Cache存储器中，并建立主存储器地址与Cache存储器地址之间的对应关系。地址变换是指当主存储器中的分块按照地址映象方法装入Cache存储器后，在实际运行过程中，主存储器地址如何转换成为相应的Cache存储器地址。地址的映象和变换是紧密相关的，采用什么样的地址映象方法，就有与这种映象方法相对应的地址变换方法。5.2.2 地址映象与变换方法u在选取地址映象方法要考虑的主要因素：在选取地址映象方法要考虑的主要因素：1.地址变换的硬件容易实现，地址变换的速度要快，2.Cache空间利用率要高，3.3.发生块冲突的概率要小。发生块冲突的概率要小。一般可分为以下几种类型：(1)全相联映象及其变换方法(2)直接映象及其变换方法(3)组相联映象及其变换方法(1)全相联映象及其变换方法全相联映象是指主存储器中的任意分块可以被放置到Cache存储器中的任意一个位置。其中，主存储器与Cache存储器的分块大小相同。映像规则(1)全相联映象及其变换方法 主存储器块号与Cache存储器块号的映象关系存放在一个用高速缓存实现的目录表中，目录表中的存储单元由三部分组成：主存储器块号、Cache存储器块号，以及有效位。(2)直接映象及其变换方法直接映象是指将主存储器中的某一分块在Cache存储器中都有唯一对应的位置。主存储器按Cache大小分成若干区，在区内进行分块，分块大小与Cache存储器中分块大小相等，主存储器中每个区包含分块的个数与Cache存储器中分块的个数相等。uCache地址的计算公式：bB mod Cb 其中：b为Cache块号，B是主存块号，Cb是Cache块数。u实际上，Cache地址与主存储器地址的低位完全部分相同(2)直接映象及其变换方法地址映像规则(2)直接映象及其变换方法12/24/2022u地址变换过程：地址变换过程：用主存地址中的块号用主存地址中的块号B去访问区号存去访问区号存储器，把读出来的区号与主存地址中的区号储器，把读出来的区号与主存地址中的区号E进行比较进行比较 比较结果相等，有效位为比较结果相等，有效位为1，则，则Cache命中，否则该块已经作废。命中，否则该块已经作废。比较结果不相等，有效位为比较结果不相等，有效位为1，Cache中的该块被其他块占用，否则该块是空的。中的该块被其他块占用，否则该块是空的。(2)直接映象及其变换方法直接映像地址变换规则(2)直接映象及其变换方法u提高提高Cache速度的一种方法：速度的一种方法：把区号存储器与把区号存储器与Cache合并成一个存储器合并成一个存储器(2)直接映象及其变换方法12/24/2022直接映象及其变换的优缺点：直接映象及其变换的优缺点：主要优点：主要优点：硬件实现很简单，不需要相联访问存储器硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不需要进行地址访问速度也比较快，实际上不需要进行地址 变换。变换。主要缺点：主要缺点：块的冲突率比较高。块的冲突率比较高。(3)组相联映象及其变换方法组相联映象把主存储器和Cache按同样大小划分成块，再将主存储器和Cache按同样大小划分成组，每一组由相同的块数组成，然后将主存储器按Cache大小分成区，主存储器每个区的组数与Cache的组数相同。组相联映象在各组之间是直接映象，但组内各块之间是全相联映象。(3)组相联映象及其变换方法映像规则(3)组相联映象及其变换方法12/24/2022u地址变换过程：地址变换过程：用主存地址中的组号用主存地址中的组号G按地址访问块表存储按地址访问块表存储器。把读出来的一组区号和块号与主存地址中的器。把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。区号和块号进行相联比较。如果有相等的，表示如果有相等的，表示Cache命中；否则表示命中；否则表示Cache没有命中。没有命中。(3)组相联映象及其变换方法(续1)地址变换规则(3)组相联映象及其变换方法 组相联映象方式的优点：组相联映象方式的优点：块的冲突概率比较低，块的冲突概率比较低，块的利用率大幅度提高，块的利用率大幅度提高，块失效率明显降低。块失效率明显降低。组相联映象方式的缺点：组相联映象方式的缺点：实现难度和造价要比直接映象方式高。实现难度和造价要比直接映象方式高。(3)组相联映象及其变换方法12/24/2022u提高提高Cache访问速度的一种方法：访问速度的一种方法：把块表存储器中一个相联比较的组按把块表存储器中一个相联比较的组按块方向展开存放。块方向展开存放。用多个相等比较器来代替相联访问，用多个相等比较器来代替相联访问，加块查表的速度。加块查表的速度。(3)组相联映象及其变换方法12/24/20225.2.3 Cache替换算法及实现当CPU读Cache时，有两种可能：(一)需要的数据已在Cache中，那么只需直接访问Cache；(二)是需要的数据尚未装入Cache，则CPU从主存储器中读取信息的同时，需按所需的映象规则将该地址所在的那块存储内容从主存储器拷贝到Cache中。对于第二种情况，若该块所映象的Cache块位置已全部被占满，则必须选择将Cache中的某一块替换出去，需要Cache替换算法解决如何选择被换出块的问题。Cache替换算法随机替换算法随机替换算法随机法是Cache替换算法中最简单的一种。这种方法是随机地选择可以被替换的一块进行替换。有些系统设置一个随机数产生器，依据所产生的随机数选择替换块，进行替换。先进先出替换算法先进先出替换算法(FIFO)这种策略总是把最先调入的Cache块作为被替换的块替换出去。最近最少使用替换算法最近最少使用替换算法(LRU)LRU法是依据各块的使用情况，总是选择最近最久没被使用的块作为被替换的块进行替换。因为目前为止最久没有被访问的块，很可能也是将来最少访问的块。Cache替换算法堆栈替换算法堆栈替换算法堆栈替换算法使用栈顶到栈底各项的先后次序来记录Cache中或Cache中同一组内各个块被访问的先后顺序。栈顶恒存放近期最近被访问过的块的块号，栈底恒存放近期最久没有被访问过的块的块号，即准备被替换掉的块的块号（LRU堆栈实现）。比较对替换算法比较对替换算法LRU算法用一组硬件的逻辑电路记录同一组中各个块使用的时间和次数，然后按照各个块被访问过的时间顺序排序，从中找出最久没有被访问过的块。用一个两态的触发器的状态来表示两个块之间的先后顺序，再经过门电路就可以找到LRU块。Cache替换算法比较对法比较对法 以三个块为例，三个块分别称为块以三个块为例，三个块分别称为块A、B、Cu 表示方法：表示方法：用用TAB1表示表示 B块比块比 A 块更久没有被访问过。块更久没有被访问过。如果要表示块如果要表示块 C 最久没有被访问过：最久没有被访问过：从最近到最远分别是：从最近到最远分别是：A、B、C 或或 B、A、CCache替换算法12/24/2022即：即：u每次访问之后要改变触发器的状态。每次访问之后要改变触发器的状态。在访问块在访问块A之后：之后：TAB1，TAC1 在访问块在访问块B之后：之后：TAB0，TBC1 在访问块在访问块C之后：之后：TAC0，TBC0Cache替换算法12/24/2022每组个块的比较对法每组个块的比较对法Cache替换算法12/24/2022u硬件需求量计算：硬件需求量计算：需要的触发器个数为：需要的触发器个数为：与门的个数为与门的个数为Gb个，每个与门的输入个，每个与门的输入端个数为端个数为Gb-1个个,其中：其中：Gb为每组的块数。为每组的块数。u 当每组的块数比较多时当每组的块数比较多时 采用分级的办法实现。采用分级的办法实现。实质上是用降低速度来换取节省器件。实质上是用降低速度来换取节省器件。Cache替换算法12/24/2022比较对法中每组数与所需硬件的关系比较对法中每组数与所需硬件的关系Cache替换算法12/24/2022例如例如：IBM 3033机的机的Cache，每组的块数为每组的块数为16，分，分3级。从第级。从第1级到第级到第3级分别为级分别为4、2、2。共需要触发器个数为：共需要触发器个数为：64818。如果不分级则需要触发器如果不分级则需要触发器120个。个。Cache替换算法12/24/2022 堆栈法的管理规则：堆栈法的管理规则：把本次访问的块号与堆栈中保存的所有块号把本次访问的块号与堆栈中保存的所有块号进行相联比较。进行相联比较。如果有相等的，则如果有相等的，则Cache命中。把本次访问命中。把本次访问的块号从栈顶压入，堆栈内各单元中的块号依的块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。单元为止，再往下的单元直止栈底都不变。Cache替换算法12/24/2022 如果没有相等的，则如果没有相等的，则Cache块失效。本次块失效。本次访问的块号从栈顶压入，堆栈内各单元的块号访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底，栈底单元中的块号被依次往下移，直至栈底，栈底单元中的块号被移出堆栈，它就是要被替换的块号。移出堆栈，它就是要被替换的块号。Cache替换算法12/24/2022u堆栈法的主要优点：堆栈法的主要优点：块失效率比较低，因为它采用了块失效率比较低，因为它采用了LRU算算法。法。硬件实现相对比较简单。硬件实现相对比较简单。u 堆栈法的主要缺点：堆栈法的主要缺点：速度比较低，因为它需要进行相联比较。速度比较低，因为它需要进行相联比较。Cache替换算法各种各种Cache替换算法的优缺点替换算法的优缺点(1)随机替换算法：优点是简单，容易实现；缺点是没有考虑到Cache块的使用历史情况，没有利用程序的局部性特点，从而命中率较低，失效率较高。(2)FIFO替换算法：优点是由于它不需记录各个块的使用情况，实现起来也较容易；缺点是虽然考虑到了各块进入Cache的先后顺序这一使用“历史”，但还不能正确地反映程序的局部性特点。(3)LRU替换算法：LRU算法较好地反映了程序的局部性特点，失效率较低，但LRU算法比较复杂，硬件实现较困难，特别是当组的大小增加时，LRU的实现代价将越来越高。5.2.4 cache一致性问题由于Cache中保存的是主存储器的一部分副本，则有可能在一段时间内，主存储器中某单元的内容与Cache中对应单元的内容出现不一致。例如：（1）CPU在写入Cache时，修改了Cache中某单元的内容，而主存储器中对于单元的内容却可能没有改变，还是原来的。此时，如果I/O处理器或其他处理器要用到主存储器中的数据，则可能会出现主存储器内容跟不上Cache对应内容的变化而造成的数据不一致性错误。（2）I/O处理机或其他处理机已修改了主存储器某个单元的内容，而Cache中对于单元的副本内容却可能没有改变。这时，如果CPU访问Cache并读取数据，也可能会出现Cache内容跟不上主存储器对于内容的变化而产生的不一致性错误。5.2.4 cache一致性问题对于Cache中的副本与主存储器中的内容能否保持一致，是Cache能否可靠工作的一个关键问题。要解决这个问题，首先要选择合适的Cache更新算法。对Cache不一致性问题的解决，主要是需要更新主存储器内容，一般有两种常用更新算法：83(1)写直达法写直达法:又称写通过法，又称写通过法，WT（Write-through）CPU在执行写操作时，把数据同时写入在执行写操作时，把数据同时写入Cache和主存。和主存。(2)写回法写回法:又称为抵触修改法，又称为抵触修改法，WB（Write-Back）CPU的数据只写入的数据只写入Cache，不写入主存。不写入主存。仅当替换时，才把修改过的仅当替换时，才把修改过的Cache块写回到主存。块写回到主存。5.2.4 cache一致性问题84写回法与写直达法的优缺点比较：写回法与写直达法的优缺点比较：(1)写回法较写直达法速度要快；(2)在可靠性方面，写回法不如写直达法；(3)写直达法的控制较比写回法简单；(4)写直达法易于实现，但硬件实现代价相对较大。5.2.4 cache一致性问题855.2.4 cache一致性问题例如：例如：写操作占总访存次数的操作占总访存次数的20，Cache的命中率的命中率为为99，每块为，每块为4个字。当个字。当Cache发生块替换时，有发生块替换时，有30块需要写回到主存，其余的块因为没有被修改过而块需要写回到主存，其余的块因为没有被修改过而不必写回主存。试比较写回法与写直达法的访存通信不必写回主存。试比较写回法与写直达法的访存通信量。则对于写直达法，写主存次数占总访存次数的量。则对于写直达法，写主存次数占总访存次数的20,而对于写回法，而对于写回法，(199)3041.2。因此，与主存的通信量，写回法要比写直达法少因此，与主存的通信量，写回法要比写直达法少10多倍。多倍。5.2.4 cache一致性问题进行“写”操作时，也可能出现写不命中。由于“写”操作并不需要访问该单元中的所有的数据，在出现Cache写不命中时，无论写回法还是写直达法，都需要考虑在写操作的同时是否将其调入Cache，一般有两种选择：(1)按写分配法：写失效时，除了完成写入主存储器外，还把该写地址单元所在的块由主存储器调入Cache。(2)不按写分配法：写失效时，只完成写入主存储器，而不把该写地址单元所在的块从主存储器调入Cache。5.2.5 Cache性能分析评价Cache存储器，主要是看Cache命中率的高低，命中率主要与下面几个因素有关：(1)程序在执行过程中的地址流分布情况，其中地址流的分布情况是由程序本身决定的；可通过编写适应Cache的代码；(2)当发生Cache块失效时，所采用的替换算法；(3)Cache的容量，块的大小、块的总数；(4)采用组相联时组的大小等。5.2.5 Cache性能分析(续1)Cache命中率与容量的关系Cache的容量越大，则Cache的命中率将越高。5.2.5 Cache性能分析(续2)Cache命中率与块大小的关系在采用组相联映象方式的Cache中，当Cache的容量一定时，块的大小也会影响命中率。5.2.5 Cache性能分析(续3)Cache命中率与组数的关系当Cache的容量一定时，分组的数目对于Cache命中率的影响也是很明显的：组数分得越多，命中率会下降，命中率会随着组数的增加而下降；当组数不太大时，命中率降低得相当少；当组数超过一定数量时，命中率下降非常快。Cache系统加速定义：5.2.5 Cache性能分析(续4)从Cache系统加速比定义可以看出，Cache系统的加速比与Cache的命中率H和主存储器访问周期Tm及Cache访问周期Tc有关，而Cache系统中，主存储器的访问周期和Cache的访问周期一般是一定的，所以只要提高Cache的命中率，就可以获得较高的Cache系统加速比，提高存储系统的速度。5.3 Cache性能的优化除加速比定义衡量Cache存储系统性能外，Cache存储器的平均访问时间是测评存储系统性能的一种更好的指标：平均访问时间=命中时间+失效率*失效开销从平均访问时间这一指标来看，还可以从3个方面对Cache的性能进行优化：（1）降低Cache失效率 （2）减少失效开销 （3）减少命中时间5.3.1降低Cache失效率的方法Cache失效的原因分析：(1)强制性失效：对块第一次访问，该块不在Cache中，需从主存储器中将该块调入Cache中。(2)容量失效：如果程序执行时，Cache容纳不了所需的所有块，则会发生容量失效。当某些块被替换后，可能随后重新访问又被调入。(3)冲突失效：在组相联映象或直接相联映象中，如果太多的冲突块映象到同一组中，产生冲突，则可能会出现某个块刚被替换出去，随后又重新访问而被再次调入。5.3.1降低Cache失效率的方法(续1)增加Cache块大小 Cache命中率和块大小的关系：在Cache容量一定时，当块大小开始增加时，命中率也开始增加，但当增加到一定程度后，命中率反而开始下降。失效率和命中率是两个相关的概念，命中率增加时，失效率下降；命中率下降时，失效率反而增加。另外，Cache容量越大，则使失效率达到最低的块大小就越大。5.3.1降低Cache失效率的方法(续2)增加Cache容量 Cache容量越大，命中率越高，相关，失效率则越低。但增加Cache容量不仅会增加成本，而且也可能会因为复杂的电路结构等而增加Cache的访问时间。指令和数据硬件预取 指令和数据硬件预取是指在处理器访问指令和数据之前，就把它们预取到Cache中或预取到可以比存储器访问速度更快的外部缓冲区中。指令预取一般有恒预取和不命中预取两种方法。5.3.1降低Cache失效率的方法(续3)编译器控制预取 硬件预取的一种替代方法是在编译时加入预取指令，在数据被使用之前发出预取请求。有以下两种方式：(1)寄存器预取：将数据预取到寄存器中。(2)Cache预取：只将数据预取到Cache中，并不放入寄存器。编译器优化以降低Cache失效率这种方法是采用软件方法来优化Cache性能，试图通过优化编译时间来改善Cache性能：(1)程序代码和数据重组(2)循环交换(3)分块5.3.2 减少Cache失效开销与降低失效率