第五章 并行存储器与存储系统的组织课件.ppt

第五章 并行存储器与存储系统的组织,存储器是现代计算机系统的核心。本章从计算机系统对存储器的要求出发，根据程序访问局部性的特点，分析具有层次结构的存储系统、并行存储器的概念及其组织实现，讨论高速缓冲存储器、虚拟存储器实现的映像管理规则、替换算法及其相关技术，介绍提高Cache存储系统和虚拟存储器性能的方法。第一节 并行存储器与相联存储器 第二节 存储系统的组织原理 第三节 Cache存储系统的组织基础 第四节 提高Cache存储系统性能的方法,一、什么是并行存储器 二、单体多字存储器 三、多体多字交叉编址存储器 四、多体多字存储器的无访问冲突 五、相联存储器,第一节 并行存储器与相联存储器,一、什么是并行存储器 1. 存储器频带平衡及其实现的基本途径 现代计算机是以主存储器为中心工作的，主存储器要完成取指令、取操作数、写运算结果以及与外围设备进行数据交换等输入输出的操作。 衡量主存储器的速度的参数主要有延迟和带宽（或频带）：延迟是指完成一次存储访问所需要的时间；带宽是指单位时间内可传输的二进制位数，主存储器是所有访问源的带宽之和。带宽又有最大带宽与实际带宽之分，最大频宽是指连续访问存储器时能提供的频宽，即指单位时间内可传输的最大二进制位数。由于存储器一般不可能满负荷工作，所以实际频宽要小于最大频宽。存储器频带平衡是指存储器的带宽应与计算机系统需求的带宽相适应。一般说来，对于主存储器解决频带平衡问题有3条途径：（1）设置各种缓冲寄存器，如各种先行缓冲栈。（2）采用并行存储器，让多个存储器并行工作。（3）采用存储系统，特别是Cache存储系统，往往会采用多级Cache存储系统。,2. 并行存储器及其种类 并行存储器能够提高存储器的频宽，从而能够提高存储器的访问效率。所谓并行存储器是指通过设置多个存储器或存储体，使它们并行工作，在一个存储周期内可以访问到多个存储字。并行存储器有单体多字存储器、多体多字交叉编址存储器两种。,二、单体多字存储器 1. 单体多字存储器的结构模型 一般的单体单字存储器的一个存储单元存放一个存储字，每个存储周期只能访问到一个存储字的位，如图5-1（a）所示，存储容量为m位（m为存储单元数）。其最大频宽为Bm=/TM。其中设存储字长与访问字长相同为位，TM为访问周期，在对存储器连续不间断的情况下，访问源（一般是CPU）的获得数据信息的速率也可达/TM。,1. 单体多字存储器的结构模型 要提高存储器的最大频宽，在相同的条件（存储器件相同，访问周期仍为TM；存储容量不变，仍为m位）下，只有提高存储器的字长。单体多字存储器是把存储器的存储字字长增加n倍为n位，存储单元数变为m/n。每个存储单元可存放n个指令字或数据字，从而在一个存储周期内能访问到n个指令字或数据字，相当于访问源获得数据信息的速率提高了n倍，即存储器最大频宽Bm=n/TM如图5-1（b）所示。,1. 单体多字存储器的结构模型 要提高存储器的最大频宽，在相同的条件（存储器件相同，访问周期仍为TM；存储容量不变，仍为m位）下，只有提高存储器的字长。单体多字存储器是把存储器的存储字字长增加n倍为n位，存储单元数变为m/n。每个存储单元可存放n个指令字或数据字，从而在一个存储周期内能访问到n个指令字或数据字，相当于访问源获得数据信息的速率提高了n倍，即存储器最大频宽Bm=n/TM如图5-1（b）所示。,1. 单体多字存储器的结构模型 在保证存储容量m不变的情况下，可以把存储器的地址数相应减少n倍，则地址数为m/n个。这时可把地址信息分成两部分，其中高部分仍作为存储器的地址去访问存储器（因为存储器的字数减少，访问存储器的地址码可以缩短），低部分则去控制一个多路选择器，从同时读出的n个数据中选择一个数输出。,2. 单体多字存储器的访问冲突 单体多字并行存储器的优点是实现简单，缺点是访问冲突概率大。访问冲突主要来自以下几个方面： （1）取指令冲突。 （2）读操作数冲突。 （3）写数据冲突。 （4）读写冲突。 前两种冲突容易解决，后两种冲突的解决比较困难。从存储器本身看，访问冲突产生的原因是地址寄存器和控制逻辑只有一套，如果在图5-1（b）中有n个独立的数据寄存器和n套读写控制逻辑，后两种冲突就自然解决了，前两种冲突也有所缓解。,三、多体多字交叉编址存储器 1. 多体多字交叉编址存储器及其种类 一个存储器通常是由多个存储体（存储模块）组成，假设一个主存储器包含n=2a个存储模块，每个存储模块有m=2b个存储单元（字），则存储器的容量为nm=2a+b个字，存储单元字地址的二进制位数（地址码位数）为a+b。存储器对存储单元的编址是顺序的，当由多个存储体（存储模块）组成一个更大容量的主存储器时，对存储器中的多个存储体的存储单元采用交叉编址方式。根据用地址码的高位还是低位来选择存储模块，交叉编址方式可分为地址码高位交叉编址和地址码的低位交叉编址。地址码高位交叉编址目前使用很普遍，该编址方式能很方便地扩展常规主存储器的容量，例如用16MB8的存储模块可构成64MB8的存储器。但只有低位交叉编址存储器才能有效地解决并行访问冲突问题，才能作为并存存储器的一种工作方式。,2. 高位交叉编址的存储器 高位交叉编址的存储器结构如图5-2所示，各个存储模块都有一套独立的地址寄存器和控制逻辑等。地址码的高a位用来区分存储体的存储模块地址，地址码的低b位是存储模块的体内地址。若高位交叉存储器由n个存储模块组成，每个存储模块的容量均m个字，则存储器的存储单元地址的高a=log2 n位称为存储模块的体号k=0,1,2,n-1，低b= log2 m位称为体内地址j=0,1,2,m-1。存储单元的地址A的计算公式为：A=mk+j。若已知地址A，可以计算出：对应的体号k =A/m，体内地j = A mod m。,3. 低位交叉编址的存储器 低位交叉编址的存储器的结构如图5-3所示，各个存储模块都有一套独立的地址寄存器和控制逻辑等。地址码的低a位用来区分存储体的存储模块地址，地址码的高b位是存储模块的体内地址。若高位交叉存储器由n个存储模块组成，每个存储模块的容量均m个字，则存储器的存储单元地址的低a= n位称为存储模块的体号k=0,1,2,n-1，高b= m位称为体内地址j=0,1,2,m-1。存储单元的地址A的计算公式为： A=nj+k。若已知地址A，可计算出： 对应的体号k=A mod n， 体内地址 j=A/n。 当按地址A访问存储器时，用地址码的低 n位作为一个译码器的输入，由译码器选中一个存储体，然后按地址码的高 m位给出的体内地址对选中的存储体内的一个存储单元进行读写操作。,4. 交叉编址存储器的带宽 为了提高主存储器的带宽，需要多个或所有的存储器能并行工作。由于程序执行过程中，CPU所访问的指令或数据的地址是按顺序连续的，所以在单处理机系统中，必须采用低位交叉编址存储器，并在一个存储周期内分时启动n个存储体，如图5-4所示（其中W表示存储字）。如果每个存储体的访问周期为TM，则各存储体的启动间隔t为：t=TM/n。 因此，采用交叉编址存储器提高带宽的工作方式实际是多个存储体流水线作业的并行存储器系统，,四、多体多字存储器的无访问冲突 在单处理机系统中，一个由n个存储体组成的低位交叉存储器的带宽并不能提高n倍，其根本原因是存在访问存储的冲突。产生访问冲突的根源主要有两个，一是程序中的转移指令，二是数据被访问的随机性，后者的影响更为严重。以一维数组和二维数组为例，介绍一种多维数组的无冲突访问的交叉编址存储器。 1. 一维数组的无冲突访问,2. 二维数组的无冲突访问,（a）按列访问有冲突的存储方案 （b）按对角线访问有冲突的存储方案,P.Budnik和D.J.Kuch提出了一种能够对交叉编址存储器存放mm二维数组实现上述要求的无冲突存储方案。方案要求交叉编址存储体的个数nm，并且n取质数，同时还要在行、列方向上错开一定的距离存储数组元素。设同一列相邻元素在交叉编址存储器中错开d1个存储体存放，同一行相邻元素在交叉编址存储器中错开d2个存储体存放。当n=22p+1（p为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：d1=2p，d2=1。,mm二维数组中的任意元素aij在无冲突交叉编址存储器中的体号和体内地址可以通过如下的一般公式来计算：体号=(2pi+j+k)mod n体内地址= i其中：0im-1，0jm-1，k是数组的第一个元素a00所在存储体的体号，一般取k=0；存储体的个数n是大于等于m的质数；p是满足n=22p+1的任意自然数。在这种错位存储方案中，有1/(m+1)的存储单元是空闲的，实际上浪费了一个存储体的空间。如果不要求同一行中的数组元素按地址顺序存储，则mm的二维数组实际上只需要m个存储体就能实现按行、列、对角线和反对角线的无冲突访问。这时存储器的存储空间无浪费，利用率最高。,五、相联存储器 1. 相联存储器与相联处理机相联存储器是指可以按所给信息内容的部分或全部特征作为检索项（即关键字项）来检索存放在存储器中的数据信息，将与特征相符的所有存储单元一次性找出。简单来讲，所谓相联存储器是指按存储字的全部或部分内容寻址的存储器。而以相联存储器为核心，配上必要的中央处理部件、指令存储器、控制部件和I/O接口等，就构成一台以存储器并行操作为特征的相联处理机。相联处理机的中央处理部件也应具有并行操作的能力，以便与相联存储器配合，因此相联处理机实质是单指令多数据流（SIMD）处理机。,2. 相联存储器的结构原理 相联存储器的结构模型如图5-10所示，该存储器有W个字，字长为m位，它主要包括存储体、运算操作器、控制电路和若干共用的数据寄存器等。,3. 相联检索的基本算法从相联存储器的结构可以看出，其实现的只是一种全等比较操作，实际上还可以有多种比较查找操作，基本的检索算法有以下几个：全等查找算法：所谓全等查找是指找出与CR未屏蔽的那部分内容完全相同的全部存储单元。最大值查找算法：所谓最大值查找是指要找出存储器中所存的最大数及存放此最大数的所有单元，相同的最大值可能有多个。幅值比较查找算法：幅值比较查找是指在给定某比较数后，要分别找出存储器中内容大于、等于、小于该比较数的存储单元位置，也就是将存储器的存储单元按给定幅值进行比较，将其分成3类。其他算法,一、存储系统的基本概念 二、存储系统组织的基本思想 三、存储的基本层次和三级存储系统 四、三级存储系统的组织方式 五、存储系统的性能指标,第二节 存储系统的组织原理,一、存储系统的基本概念 1. 存储系统的提出 衡量一个存储器性能的基本指标通常有三个：速度、容量、价格。 存储器容量SM=WLn。其中W为存储模块的字长（位或字节），L为每个存储模块的字数，n为并行工作的存储模块数。存储器速度可用访问时间TA、存储周期TM和频宽Bm等3个参数来描述。访问时间是指启动一次存储器操作（读或写）到完成该操作所需要的全部时间，存储周期是指存储进行连续两次独立的存储器操作（如连续两次读操作）所需的最小间隔时间，频宽是指单位时间内传输二进制位数。单体存储器最大频宽Bm=W/TM，n个存储体并行工作的最大频宽Bm=nW/TM。 存储器的价格包含存储体及其相应的外围电路，可用总价格C和每位价格c来表示，且有c=C/SM。,2. 什么是存储系统 两个或两个以上速度、容量和价格各不相同的存储器用硬件或软件或硬件与软件相结合的方法有机地连接起来的一个集合，其对应用程序员是一个透明的存储器，并具有速度高、容量大、价格低的特性，该存储器集合就称为存储系统。,二、存储系统组织的基本思想 1. 存储访问的特点 程序对存储空间的访问具有所谓程序访问局部性的特点。程序访问局部性包括时间局部性和空间局部性两方面。一是时间局部性，它是指程序在最近的未来要用到的信息很可能是现在正在使用的信息，最典型的例子是循环程序要被多次重复地执行。二是空间局部性，它是指程序在最近的未来要用到的信息与现在正在使用的信息很可能在程序空间上是相邻或相近的，这主要是由于指令通常是顺序执行和数据不是随机分散地存储所致。数据一般是以向量、阵列、树形和表格等形式存放，其中每类数据都是簇聚地存储。因此，程序执行时访问存储器的地址的分布不会是随机的、均匀的，而是簇聚成自然的块或页面。,2.存储系统的层次结构 根据程序访问局部性和存储器性能特点，可将存储系统的结构设计成由多级存储器组成的层次结构，而且在速度、容量和价格等性能指标方面的综合水平优于任何的单级存储器，以计算机系统实现对存储器的性能要求。程序访问局部性不仅使层次结构的存储系统在速度、容量和价格等性能指标方面的综合水平较高，而且可对存储空间采用分块或分页的管理方式来获得对Mi较高的命中率。,3.存储层次组织的基本操作 采用层次结构的方法将不同类型、性能各异的存储器组织在建立起来的存储系统，存储层次间有许多问题需要解决，这些问题应由存储系统的组织设计人员通过硬件或软件或硬件与软件相结合的方法来自动实现，从而保证对程序员是透明的。综合起来主要有以下四个操作。（1）存储层次间的数据信息的交换。（2）存储层次间的地址变换。（3）存储空间的替换。（4）存储层次间的数据信息一致性的维护。,三、存储的基本层次和三级存储系统 1.存储的基本层次。,2. 三级存储系统 从存储基本层次的存储层次组织的基本操作来看，高速缓冲存储器以下各存储层次的基本操作是由CPU来自动实现，即由CPU的组织设计者完成；联机外部存储器与脱机外部存储器存储层次的基本操作是用户借助操作系统非自动实现；只有高速缓冲存储器（Cache）、主存储器和磁盘存储器（辅存）等三个存储层次的基本操作是由存储系统来自动实现，即由存储系统的组织设计者完成。因此，由高速缓冲存储器（片外Cache）、主存储器和磁盘存储器（辅存）构成一个三级存储层次的存储系统，其结构模型如图5-14所示。,四、三级存储系统的组织方式 三级存储系统虽然包含了高速缓冲存储器、主存储器和磁盘存储器，但从程序员来看，不管存储系统的组织多么复杂，都只看到一个存储器。这个存储器采用与主存储器相同的按地址随机访问的方式工作，它的等效访问速度接近于Cache的访问速度，等效存储容量是虚拟地址空间的容量。Cache、主存储器、磁盘这三个物理存储器组成一个三级存储系统的组织方式有三种，一是将三级存储器建构成“Cache主存”和“主存磁盘”两个二级存储系统，二是将三级存储器建构成“Cache主存磁盘”一个存储系统，三是将三级存储器建构成一个“Cache磁盘”存储系统，即所谓全Cache存储系统。其中两个存储系统使用最为普遍，全Cache存储系统的使用要求很高，一个存储系统的使用有限制条件。,1、两个存储系统的组织方式 两个存储系统的组织方式就是将Cache、主存、磁盘三级存储器组织成两个相对独立的两级存储层次的存储系统，一个是由Cache和主存组成的“Cache主存”存储系统，或称为Cache存储器（系统），另一个是由主存和磁盘存储器组成的“主存辅存”存储器（系统），因为采用虚拟存储技术，又称为虚拟存储器（系统）。两个存储系统的结构模型如图5-14所示，组织模型如图5-15所示。,Cache存储系统与虚拟存储系统都是二级存储系统，在地址转换、替换算法和性能评价等方面有许多相似之处，但也有六个不同点：（1）一次性交换数据的数据量不同。（2）二级存储器之间的速度比不同。（3）访问不命中时CPU访问的通路不同。（4）设置的目标不同。（5）实现的方式不同。（6）透明性不同。,2、一个存储系统的组织方式 一个存储系统的组织方式就是把Cache、主存和磁盘3个存储器组织成一个“Cache主存磁盘”存储系统，一个存储系统的结构模型如图5-14所示，组织模型如图5-16所示。当CPU要访问存储器时，把虚拟地址直接送往存储管理部件MMU和Cache。Cache能够直接将虚拟地址转换为Cache的物理地址，再访问Cache，找出CPU所需要的数据或指令。如果Cache发生块失效，则用经过MMU变换得到的主存物理地址访问主存，把读出的一块数据或指令装入到Cache中，同时也把CPU所需要的数据或指令送入CPU。,3、全Cache存储系统的组织方式 全Cache存储系统的组织方式，没有设置主存储器，只用Cache和磁盘两种存储器构成 “Cache磁盘”存储系统。全Cache存储系统的等效访问周期与Cache的访问周期很接近，等效存储容量就是虚拟地址空间的容量。在多处理机系统中，一种全Cache存储系统的结构模型如图5-17所示。,五、存储系统的性能指标存储系统的性能指标一般包括的存储容量、单位容量的平均价格、命中率、访问周期和访问效率等五个。对于如图5-11所示的由M1、M2、Mnn个存储器组成的n级存储系统，假设各存储器的访问周期分别为T1、T2、Tn，容量分别为S1、S2、Sn，单位容量价格分别为C1、C2、Cn，T1T2 Tn，S1S2Sn，C1C2Cn，则存储系统的性能指标讨论如下。,1、存储容量 存储系统应对计算机的使用者提供尽可能大的地址空间，而且可对这个地址空间进行随机访问。根据存储系统的组织原理，最高层存储器Mn的存储容量Sn最大，则用户可使用Mn作为地址空间进行随机访问，存储系统的存储容量S就是高层存储器Mn的存储容量，即有：S = Sn,2、单位容量的平均价格 n级存储系统的单位容量平均价格C为：若希望存储系统的单位容量平均价格能接近于Cn，就应使S1S2Sn-1Sn。但如果S1、S2、Sn-1与Sn相差太大，则会使得CPU对M1、M2、Mn-1访问的命中率很低。同时，上式没有把由于采用存储系统所必须增加的辅助软硬件价格计算在内，所以要使C接近于Cn，还应使增加的辅助软硬件价格只占价格中很小的比例，否则存储系统的性能价格比将会显著降低。,3、命中率 命中率可简单地定义为由CPU产生的逻辑地址在存储器M1、M2、Mn-1中访问到指定信息的概率。命中率可用实验或模拟方法来获得，即执行或模拟一段有代表性的程序，若逻辑地址流指定的信息能在存储器M1、M2、Mn-1、Mn中被访问的次数分别为N1、N2、Nn，则Mk的命中率Hk为：命中率Hk与程序的访存地址流、存储层次间所采用的地址映像规则、替换的算法及Mk的容量都有很大的关系。显然，要求H1H2Hn，而且H1越接近于1越好。,4、访问周期 n级存储系统的访问周期T为：其中Tk为存储层次Mk的访问周期。当命中率H1H2Hn，而且H1越接近于1时，访问周期T就接近于速度比较快的M1存储器的访问周期T1。因此，命中率H1越大，整个存储系统的速度就越高，越接近于M1的工作速度。,5、访问效率n级存储系统的访问效率e为：可见，存储系统的访问效率主要与命中率和构成存储系统的两级存储器的访问周期比有关。,一、Cache存储系统的工作原理 二、几种地址映像和地址变换的方法 三、替换算法及其实现 四、Cache存储系统的一致性维护 五、Cache存储系统的性能指标,第三节 Cache存储系统的组织基础,一、Cache存储系统的工作原理 1.Cache工作的基本原理,2. Cache的地址映像与地址变换 地址映像是指把主存地址空间映像（或定位）到Cache地址空间的规则或方法，就是说按照某种规则把主存中的块装入Cache中，建立主存块与Cache块之间的空间位置对应关系。 一般来说，主存中的块可映像到Cache的一个或多个或全部块，主存块可映像到Cache块的数量用相联度来表示。因此，主存地址一般分为三个部分：标识 + 索引 + 块内地址；标识是主存地址高字段，用于判断Cache是否命中；索引位于主存地址中间，用于检索Cache命中时，主存块已映像到Cache中的哪个块。 地址变换是指程序在实际运行过程中，如何把主存地址变换成Cache地址。 无论用什么地址映像和地址变换方式，都要把主存和Cache划分同样大小的存储单位，即称为“块”。在进行地址映像和地址变换过程中，都以“块”为单位进行调度。,二、几种地址映像和地址变换的方法 根据所采用的地址映像和地址变换的方法不同，有不同类型的Cache系统。地址映像和地址变换一般有全相联、直接相联和组相联3种，其中组相联有很多变形。 1.全相联映像及其地址变换 全相联映像及其规则 全相联映像方式是指主存中的任意一块可以映像到Cache中任意的块位置上。如果Cache的块数为Cb，主存的块数为Mb，则主存与Cache之间的映像关系有CbMb种，相联度为Cb，全相联映像方式的映像规则如图5-19所示。,全相联映像及其规则,全相联的地址变换方法,全相联映像的优缺点 由于全相联映像方式规定任何一个主存块可以放在任何一个空闲的Cache块位置上，因此，全相联映像方式发生两个主存块争用一个Cache块位置的块冲突的概率较低，Cache存储器的空间利用率也较高。但是，全相联映像方式的地址变换需要容量为Cb个存储字的相联存储器来存放目录表。由于Cache存储器的容量越来越大，目前，计算机中的片外Cache容量已达256KB1MB，而一个Cache块的大小因受主存频宽的限制，只有几十个主存存储字的容量，因此，Cache的块数越来越大，要求相联存储器的容量越来越大。过大的相联存储器不仅价格贵，而且也会降低地址变换的速度。,2. 直接相联映像及其地址变换 直接相联映像及其规则 直接相联映像方式是指主存中的一块只能映像到Cache的一个特定块位置上，相联度为1。设主存块的块号为B，Cache块的块号为b，若Cache的块容量（块数）为Cb，则它们的映像关系可表示为：b= B mod Cb。,2. 直接相联映像及其地址变换 直接相联的地址变换方法 根据直接映像关系，Cache地址仍然可分为两个部分，即块号b和块内地址w；而主存地址则包括三个部分，即区号E、区内块号B和块内地址W。显然，Cache地址中的块号b与主存地址中的区内块号B、Cache地址中的块内地址w与主存地址中的块内地址W完全相同，主存地址比Cache地址长出的部分是区号E。因此，在直接映像方式中，Cache中的b块数据可能来自主存中不同区但块号与b相同的块数据。在程序执行过程中，要判断当前访问的存储字所在的块是否在Cache中，只需要区分Cache的某块数据究竟是主存中哪一个区的。,直接相联映像的优缺点 直接相联映像方式的优点是硬件实现简单，只需要少量的比较电路；不需要相联存储器，只需要小容量按地址访问一般Cache型的存储器，成本很低。另外，地址变换的速度也较快，因为一旦命中且有效，那么主存地址的低位部分（除去区号E）就是Cache地址。直接映像方式的缺点是块冲突率比较高，当两个或两个以上的块映射到相同的Cache块位置而发生冲突时，从而会使Cache的命中率急剧下降。即使其他Cache块位置空闲也不能被使用，利用率很低。,3. 组相联映像及其地址变换 组相联映像及其规则 组相联映像方式是把主存按Cache的容量分区（设有Me个区），主存中的各区和Cache再按同样大小划分成数量相同的组（设Cache或主存区中有Cg个组），组内按同样的大小划分成数量相同的块（设组中有Gb个块），主存的组到Cache的组之间采用直接映像方式，两个对应组的块之间采用全相联映像方式，相联度为Gb，组相联映像方式的映像规则如图5-24所示。,组相联的地址变换方法,组相联的地址快速变换方法,4. 段相联映像及其地址变换 段相联映像方式是把主存和Cache的容量分为具有相同块数M的若干段（Cache的段数为Cg=Cb/M，主存的段数为Mm=Mb/M），段与段之间采用全相联映像，而段内采用直接相联映像。段相联映像方式的映像规则如图5-27所示。,段相联映像方式的地址变换过程如图5-28所示。当要访问Cache时，用主存地址中的段号S相联访问段表存储器。如果发现有相等的，表示要访问的Cache块已装入到Cache中，再用主存地址中的段内块号B按地址访问从段表存储器中读出一个字。若有效位为1，则命中。从这个字中取出Cache段号s与主存地址中送过来的块号B与块内地址W拼接起来形成Cache地址。如果相联比较不等或有效位不为1，则不命中，应调入新块。特别地图5-28中的段表仍有有效位等，只是没有给出。当然，从主存中调入所需要的新块或从主存中调入一次来重写块时，都要修改段表存储器。,5. 位选择组相联映像及其地址变换 位选择组相联映像也是在直接相联映像、全相联映像和组相联映像的基础上的一种变形。在位选择组相联映像方式中，Cache仍然在分块的基础上按相同大小将块分组（设有Cg个组，每组有M个块）；而主存则在分块的基础上按相同大小将块分区，每个区的块数为Cache的组数Cg，设有Me个区（即Me=Mb/Cg）。主存中的区内的块与Cache中的组之间为直接相联映像，即主存中的各区区内块号相同的块仅能映像到Cache中与主存中区内块号相同的组上；而主存中区内的块与Cache中的组内块为全相联映像，即主存中区内的块可以映像到Cache中与主存中区内块号相同的组中的任何一个块。,5. 位选择组相联映像及其地址变换 位选择组相联映像方式的地址变换过程如图5-30所示。当要访问Cache时，用主存地址中的区内块号B按地址访问块表存储器。从块表存储器中读出一组字，字数为区内的块容量M。把这些字中的区号与主存地址中相应的区号E进行相联比较。如果发现有相等的，表示要访问的Cache块已装入到Cache中，若有效位为1，则命中。从这个字中取出Cache块号b与主存地址中送过来的组号G与块内地址W拼接起来形成Cache地址。如果相联比较不等或有效位不为1，则不命中，应调入新块。,三、替换算法及其实现 当处理机要用到的指令或数据不在Cache中时，则访存发生Cache块失效。而在需要把包含该指令或数据所在的主存块按所使用的映像规则装入Cache时，如果又出现Cache块位置冲突，就必须按某种替换策略选择将Cache中的哪一块替换出去，这就是Cache块替换算法要解决的问题。 Cache存储系统中的替换算法很多，主要有随机替换算法、FIFO替换算法、LRU替换算法、OPT替换算法等。如何选择评价替换算法，则要看替换算法是否便于实现、速度的快慢和实现的成本等。特别需要注意的是所谓的“颠簸”现象，即在程序按主存块地址流访问Cache过程中，每次发生替换时的被替换块就是下次要使用的页，这就叫“颠簸”。但是Cache存储系统要求访问速度很高，替换算法必须全部用硬件实现。,1.随机替换算法（RAND） 随机替换算法的优点是实现起来非常容易，因此，在有些小型微型计算机中被采用。例如，PDP-11/70的Cache系统采用组相联映像方式，每组只有两块。当发生块冲突时，使用一个二态的随机数发生器，从组内的两块中随机选择一块替换出去。 随机替换算法既没有利用程序的局部性特点，也没有利用历史的地址流分布情况，因此效果不是太好。,2.先进先出替换算法（FIFO） 先进先出替换算法是指选择最早装入的块作为被替换的块。FIFO替换算法的优点是实现比较简单，且能够利用历史上的块地址流分布情况，把最先装入的作为被替换的。但它还是没有利用程序的局部性特点。 每块一个计数器的实现方法 在映像关系表中每个存储字内增设一个替换计数器字段，字段的长度与主存块可映像到Cache中的块数有关。 新装入块时，将该块所属的计数器清零，主存块可映像到Cache中的块所属的计数器加1（例如，全相联映像方式是所有的其它块计数器，组相联映像方式是同组的其它块计数器）；需要替换时，在主存块可映像到Cache的块（例如，全相联映像方式是所有的块，组相联映像方式是同组的块）中选择计数器值最大的块作为被替换的块。,每组一个计数器的实现方法以组相联映像方式来讨论，其它映像方式类同。 FIFO算法实际上是同组内的块按顺序轮流替换，因此只要为每个组设置一个计数器即可。如果每组的块数为Gb，设置一个模为Gb的计数器，它最先指向该组最先进来的块，该块被替换后计数值加1，指向下一个要替换的块。,3. 近期最少使用替换算法（LRU） 近期最少使用替换算法是指选择近期最少被访问的块作为被替换的块。近期最少使用替换算法与先进先出替换算法相类似，都是根据“历史”使用情况来预估未来将被使用的情况，但它在一定程度上反映了程序访问的局部性。 计数器法 在块表中为每一块设置一个计数器，计数器的长度与组内块号字段的长度相同。计数器的使用及管理规则是：（1）被装入或被替换的块，其对应的计数器清零，同组中其他所有块对应的计数器都加1。（2）命中的块，其对应的计数器清零。同组中其他所有计数器中，凡是计数值小于命中块对应的计数器原来值的，都加1，其他计数器不变。（3）需要替换时，在同组的所有计数器中选择计数值最大（一般为全1）的计数器对应的块就是被替换块。,堆栈法 近期最少使用替换算法的实质是根据被访问的近远次序，将主存块可映像到Cache中的块作一个排序，该排序可用一个堆栈来存放。栈顶恒存放近期最近被访问过的块，而栈底恒存放近期最久没有被访问过的块，即准备被替换掉的块。因此，如果从块被替换次序与调入Cache次序相比较来看，近期最少使用替换算法可认为是一个堆栈型替换算法，而先进先出替换算法是一个队列型替换算法。堆栈法实现组相联映像LRU算法的管理规则如下：（1）把本次访问的某组的Cache组内块号与堆栈中保存的所有组内块号进行相联比较，如果发现有相等的，则Cache命中。将本次访问的组内块号从堆栈中取出，再从栈顶压入堆栈而成为新的栈顶，并使原先存放该组内块号的项以上到栈顶的那些项均下移一行，而存放该组内块号的项以下到栈底的那些项都不动。（2）如果相联比较没有发现有相等的，则Cache块失效。将本次访问的组内块号从栈顶压入堆栈而成为新的栈顶，原先存放在堆栈中的各项均下移一行，将栈底挤出。,堆栈法 近期最少使用替换算法的实质是根据被访问的近远次序，将主存块可映像到Cache中的块作一个排序，该排序可用一个堆栈来存放。栈顶恒存放近期最近被访问过的块，而栈底恒存放近期最久没有被访问过的块，即准备被替换掉的块。因此，如果从块被替换次序与调入Cache次序相比较来看，近期最少使用替换算法可认为是一个堆栈型替换算法，而先进先出替换算法是一个队列型替换算法。堆栈法实现组相联映像LRU算法的管理规则如下：（1）把本次访问的某组的Cache组内块号与堆栈中保存的所有组内块号进行相联比较，如果发现有相等的，则Cache命中。将本次访问的组内块号从堆栈中取出，再从栈顶压入堆栈而成为新的栈顶，并使原先存放该组内块号的项以上到栈顶的那些项均下移一行，而存放该组内块号的项以下到栈底的那些项都不动。（2）如果相联比较没有发现有相等的，则Cache块失效。将本次访问的组内块号从栈顶压入堆栈而成为新的栈顶，原先存放在堆栈中的各项均下移一行，将栈底挤出。,比较对法 比较对法的基本思想是让两个块组成一个比较对，用一个触发器的状态表示该比较对的两块被访问过的先后顺序，经门电路组合，可从多个块中找出最久未被访问过的块。 假设有3个块A、B和C，3个块共有6种不同的排列，分别为：AB、BC、AC、BA、CB和CA，但其中AB与BA、BC与CB、AC与CA是重复的，即它们可组合成 =3个有效的比较对：AB、AC和BC。对每一个比较对用一个触发器的状态表示两块被访问过的顺序。例如触发器的TAB=1表示A比B更近被访问过，TAB=0表示B比A更近被访问过，TAC 和TBC 也类似定义。若C是最久未被访过的块，根据逻辑关系，那么一定有：同理，若B和A是最久未被访过的块，那么也一定有：,当块数增加时，需要的触发器和与门要增加，与门的输入端数也要增加。若块数为p，两两组合，则触发器的个数为： C2p=P(P-1)/2，即触发器个数随块数的平方递增；与门的个数为p，与门的输入端数为p-1。,4. 近期最久不被使用替换算法（OPT） 近期最久不被使用替换算法是指选择近期最久不被访问的块作为被替换的块。显然，只有让程序先运行一遍得到程序的全部序列，才能在替换时确定未来一段时间内哪一块最久不被使用。该替换算法既利用了块或页地址流的历史使用情况，又正确反映了程序局部性的特点，命中率最高，所以又可称为最优替换算法。但它的实现控制逻辑比较复杂，在Cache存储器中是一般不使用该算法。,四、Cache存储系统的一致性维护 由于Cache中的内容只是主存部分内容的副本，而且CPU能同时访问Cache和主存，主存又能同时被CPU和外围设备访问。因此，Cache中的副本应同主存中的相应内容保持一致，要保持Cache与主存内容一致，则需要维护，这就是Cache系统的一致性问题，这是Cache能否可靠工作的一个关键问题。 1. Cache一致性及其产生原因 （1）CPU写Cache。如图5-33（a）所示，由于CPU写Cache，把Cache某单元中内容从X修改成了X，而主存对应单元中的内容还是X。 （2）I/O写主存。如图4-25（b）所示，由于输入/输出设备写入数据到主存，把主存某单元内容从X修改成了X，而Cache对应单元中的内容还是X。,2. Cache一致性的维护方法 维护Cache与主存之间存储数据的一致性，要从产生Cache与主存之间存储数据的不一致性的原因出发来考虑。对于I/O写主存引起的不一致性，最简单的维护方法是禁止可写数据进入Cache或使I/O设备与处理机共享Cache（即I/O设备可同时写Cache和主存），但这都极大地降低了Cache存储系统的性能。 对于CPU写Cache引起的不一致性，主要在于选择合适的Cache更新算法。这又有写Cache命中和写Cache不命中两种情况: 写Cache命中时的更新算法 写Cache命中时的更新算法有两种，即写回法和写直达法。 (1)写回法（Write-back）是指CPU在执行写操作时，被写数据只写入Cache，不写入主存。仅当需要替换时，才把被修改过的Cache块写回到主存。,(2)写直达法（Write-through）是指CPU在执行写操作时，必须把数据同时写入Cache和主存。在Cache的映像关系表中不需要“修改位”。块替换时，也不需要把被替换块写回主存。,写Cache不命中时的更新算法 写Cache不命中时更新算法也有两种，即不按写分配法和按写分配法，它是按是否要把包括所写字在内的一个块从主存读入Cache来分的。 (1)不按写分配法。在发生写Cache不命中时，只把所要写的字写入主存，而不把包括所写字在内的一个块从主存读入Cache。 (2)按写分配法。在发生写Cache不命中时，先把所要写的字写入主存，再把包括所写字在内的一个块从主存读入Cache。,3. 写直达法与写回法的比较 （1）写直达法的可靠性优于写回法。写直达法能够始终保持Cache是与主存一致的副本，而写回法在一段时间内有可能Cache并不是与主存一致的副本。 （2）写直达法与主存通信量多于写回法。由于Cache的命中率一般都很高，对于写回法，CPU的绝大部分写操作只需写Cache，仅在Cache不命中时才写主存；而写直达法的每一个写操作都要写主存。 （3）写直达法的控制难于比写回法。写回法要在映像关系表中设置一个“修改位”，并要对“修改位”进行管理和判断；而写直达法则不需要设置“修改位”。另外，当Cache发生错误时，写直达法可从主存得到纠正，而写回法则自己实现错误纠正。 （4）写直达法实现的硬件代价高于写回法。由于写直达法的每一个写操作都要写主存，为了节省写主存的时间，通常要采用一个高速缓冲存储器，把要写主存的数据和地址先写到这个高速缓冲存储器中，读主存时则先判断数据是否在这个高速缓冲存储器中。而写回法则不需要这个高速缓冲存储器。,五、Cache存储系统的性能指标 在计算机系统中设置Cache的主要目的是提高存储系统的速度，因此，Cache存储系统的性能指标包括平均访问时间、加速比和CPU时间。 加速比 设Cache的访存周期为Tc，主存的访存周期为Tm，Cache系统的等效访问周期为Te，Cache的命中率为H，它们之间的