cache一致性协议实现的基本方法

1、Cache Cache 一致性协议实现的基本方法一致性协议实现的基本方法主讲：周艳芳副讲：缴万鑫知识知识回顾（一）回顾（一）解决主存速度与解决主存速度与CPU速度差距的办法：速度差距的办法：Cache -主存存储层次：采用高速缓冲存储器方式主存存储层次：采用高速缓冲存储器方式知识知识回顾（二）回顾（二） Cache存储器中保存的字块是主存中相应字块的一个副本。如果程序执行过程中要对该字块的某个单元进行读写操作，就会遇到如何保持Cache与主存的一致性问题。 1)不命中时：直接把待写的信息写入主存。 2)命中时：有两种写入方式。 写回法：只更新Cache单元，并加以标记， 当该块从Cache移出

2、时，再更新相应的主存单元。 写直达法：Cache单元与主存单元同时写。 写回法速度快，但有一段时间主存内容与 Cache内容不一致； 写直达法能随时保持主存数据的正确性，但有可能增加多次不必要的写主存。 问题引出问题引出Cache数据与主存数据一致是指：在采用Cache的系统中，同样一个数据可能既存在于Cache中，也存在于主存中，两者数据相同则具有一致性，数据不相同就叫做不一致性。如果不能保证数据的一致性，那么，后续程序的运行就要出现问题。Cache Cache 一致性一致性 目前，在并行系统的产品中大多数都采用基于总线的存储器结构。总线是保证高速缓存一致性的最方便的设备，它允许系统中各个处

3、理机能够监测对存储器进行的所有操作，如果这些操作破坏了本地高速缓存中数据的一致性状态，高速缓存控制器就可以采取相应的动作维护高速缓存的一致性。采用这种机制维护高速缓存一致性的协议的系统中，每个高速缓存都在监听其它高速缓存的操作，所以称为监听总线协监听总线协议议。而对于可扩展多处理机系统，常常采用互连网络实现多处理机互连，其网络带宽随着处理机数目的增加而增大，但是这些网络没有方便的监听机制，也难于进行有效的广播，所以常常采用基于目录的协议基于目录的协议。下面分别对这两类协议进行介绍。 解决解决CacheCache一致性问题的两种协议一致性问题的两种协议 如果接在共享总线上的处理机具有自己的本地高

4、速缓存，那么可以采用两种方法：1.写写无效策略无效策略和写更新策略：写更新策略：1）写无效（）写无效（Write invalidate ）当任何一个处理机写自己的高速缓存时，由它负责把其他的高速缓存复本变成无效的，使其他高速缓存中（和主存中）的复本都是“过时”的。根据对于主存中复本的处理不同，又可以分成写通过和写回策略：写通过：写通过：更新主存中的复本，最后的状态是一个高速缓存中的复本和主存中的复本是有效的，其他复本都是无效的。写回：写回： 它使主存中的复本也无效，最终只有一个高速缓存中的复本使有效的。2）写更新）写更新 当任何一个处理机写自己的高速缓存时，改写其它所有的复本。所以操作的结果是

5、所有数据块的复本都是“有效”的。监听总线协议监听总线协议 这两种策略都存在缺点和问题。写无效的问题在于两个方面：使各个高速缓存中数据块的复本无效的开销比较大；由于无效复本引起缺失造成的开销。而写更新的问题在于更新所有复本的开销比较大。2、写一次协议、写一次协议 结合了上面介绍的协议的优点，James Goodman 在1983 年提出了一种基于总线的多处理机系统的高速缓存一致性协议。它的主要思想和作法是：高速缓存块的第一次写采用写通过策略，产生一份正确的主存复本，并且使其他高速缓存的复本无效；之后，就采用写回策略：其他高速缓存和主存中的复本均无效。 在设计、分析高速缓存一致性协议时要考虑和解决

6、的几个主要问题有 1）高速缓存可能出现的状态集合 2）共享主存的状态 3）为维护一致性而引起的状态转换 下面分别结合写一次协议进行说明1）每个高速缓存复本可能出现的四种状态）每个高速缓存复本可能出现的四种状态 （1）有效）有效（Valid）与主存复本一致的高速缓存复本，即该复本未经修改，所以这个复本不是唯一的正确复本。别的高速缓存中也可能存在该数据块的有效复本。 （2）保留）保留（Reserved）这一高速缓存的复本是第一次被修改，并采用写通过方法写入主存。所以这个高速缓存中的复本与主存中的复本是一致的。而且系统中也只有这两个复本是有效的。 （3）重写）重写（Dirty）高速缓存中的复本不止一

7、次被修改过，由于不再采用写通过的方法，所以这个高速缓存中的复本是唯一的有效复本，与主存和其他高速缓存中的复本都不一致。主存中的复本也是无效的。 （4）无效）无效（Invalid）与主存中和其他高速缓存中的复本不一致或在高速缓存中根本没有该复本。2）进行高速缓存操作时用到的信号）进行高速缓存操作时用到的信号（1）P-Write：本地处理机写自己的高速缓存复本（2）P-Read：本地处理机读自己的高速缓存复本这两条命令都是局部/本地命令（3）Write- inv：远程高速缓存在写命中时在总线上广播一个无效命令（4）Read-inv：远程高速缓存在写缺失时在总线上广播一个无效命令（5）Read-bl

8、k：从另外一个高速缓存中读出一份有效复本。这两条属于一致性命令3）写操作可能遇到的几种情况）写操作可能遇到的几种情况（1）如果C1 为VALID，写C1 时，则写命中（Writehit） a. 如果内存单元所在的块在高速缓存中，则可以写高速缓存命中。 b. 如果内存单元所在的块不在高速缓存中，则写缺失，将内存单元所在块读入高速缓存，再进行写操作发P-Write 修改C1 内容，修改内存，发Write-Inv 给所有高速缓存，使它们的状态变为无效。同时使本地的高速缓存中数据块的状态变Reserved。（2）如果C1 为Reserved，对C1 进行写操作时，则写命中。发P-Write 命令修改C

9、1内容，不修改内存中的复本，C1 状态变为Dirty（3）如果C1 为Dirty，写C1 时则写命中。发出P-Write 命令修改C1 的内容，不修改主存中的复本，C1 保持Dirty 状态（4）如果C1 为Invalid，则写不命中。如果其他高速缓存中也没有该数据块的复本，只有主存中有该数据块的复本，则将主存中的复本复制到C1 中，再将要写入的内容13写入C1，这是C1 和主存内容不一致。把C1 状态置为Dirty。写入后，C1 与主存中的内容至少有一个单元不一致。（5）如果C1 为Invalid，C2 为Dirty，这时主存中的内容与C2 中的不一致。将C2 中的数据块复制到C1 中，将C

10、1 的状态置为Dirty，发Read-inv 使其他高速缓存的有关复本变成无效（6）如果C1 为Invalid，C2 为Reserved，这时主存中的内容和C2 的一致，将C1 的状态置为Dirty，发Read-inv，使其他高速缓存中的有关复本变成无效状态。4）读操作可能遇到的情况）读操作可能遇到的情况（1）如果C1 为Valid，读C1 则读命中（Read-Hit），C1 状态不变（2）如果C1 为Reserved，读C1 则读命中（Read-Hit），C1 状态不变（3）如果C1 为Dirty，读C1 则读命中（Read-Hit），C1 状态不变（4）如果C1 为Invalid，C2 和

11、C3 中没有相应复本。则读C1 时读缺失。这时只有内存中有正确的复本。将其取到C1 中，C1 改为Valid。（5）如果C1 为Invalid，C2 为Dirty，则读C1 时读缺失。这时只有C2 中的内容是正确的。发Read-Blk 信号将C2 的复本拷贝到C1 中，同时修改内存复本。C1 和C2 都改为Valid（6）如果C1 为Invalid，C2 为Reserved，则读C1 时发生读缺失，这时发Read-blk 信号，把C2 中的复本复制到C1 中，C1 和C2 的状态都改为Valid5）写一次协议存在的问题：）写一次协议存在的问题：（1）开销大：发无效命令使对应复本变成无效状态的开

12、销；读高速缓存时由于数据块复本变成无效状态造成读缺失，从其他地方取得数据的开销。（2）发诸如无效命令时，通常只用共享总线才能提供所需要有效的广播手段，其他高速缓存才能够进行监听。所以这种写一次协议的应用对象主要是共享总线的并行系统，因此可扩展性不好。 基于目录的高速缓存一致性协议基于目录的高速缓存一致性协议1、 基本思想基本思想 针对协议次协议存在的开销大、扩展性差的缺陷，提出基于目录的方法，使无效命令只发给存放特定数据块复本的某些高速缓存。比如，对于一台处理机而言，如果除了本地高速缓存之外，还有三个高速缓存中有这个数据块的复本，当对本地高速缓存进行写操作时，只要发三个无效命令给对应的高速缓存

13、即可，以。这种点对点的高效方式代替了广播方式。因此这种方法在共享总线结构的并行系统中应用时，可以降低总线带宽的占用；更为重要的，这种方法也可以有效地使用在通过交换网络进行通信的并行系统中。2、 目录目录 显然，为了能够发挥这种方法的优势，就要要解决解决这样的问题：无效命令发给谁？因此采用一个目录记录有关信息。这也是该方法命名的原因。常见的目录结构有三种：全映射目录、有限目录与链式目录，详细介绍全映射与链式目录。1） 全映射目录全映射目录 在全映射目录中，存放与全局存储器中每个数据块相关的信息。即该数据块在哪些高速缓存中。系统中的每个高速缓存可以同时存储任何存储任何数据块的复本。即每个目录项包含

14、N 个指针（N 为处理机的个数），一个复本可以在N 个高速缓存中。随着处理机数目N 的增大、存储器容量的增加，所需要目录的容量以N2 的数量级增加。在目录本身就很庞大的情况下，还需要增加一位C/D 位，以指示该复本是否允许写。所以每个高速缓存的数据块有两个状态位，有效与允许写。（1） 全映射目录的三种不同状态全映射目录的三种不同状态 通过一个例子进行说明：假设有有3 台处理机P1，P2，P3（对应的高速缓存为C1，C2，C3），都要对主存中的数据单元X 进行操作（实际上，需要对X 所在的数据块进行操作，下面类似“单元X 的复本”的只是为了明确讨论对象的一种说法）。第一种状态：系统中所有高速缓存

15、中都没有单元X 的复本P1，P2，P3 所有高速缓存中都没有单元X 的拷贝。 当三个高速缓存C1，C2，C3 同时请求单元X 的拷贝时，就进入了第二种状态。在这种状态下，目录项的重写位（C/D 位）被置为未写（C）状态，表示不允许任何处理机写入该数据块。 第三种状态是在C3 请求对该块进行写操作的许可权，这时重写位被置成重写（D）状态，而且有一个指针指向C3 的数据块。 下面详细分析第三种状态。 在第二种状态下，C1，C2，C3 同时请求X 单元的复本，这时目录项中的三个指针（处理机位）被置1，表示这三个高速缓存中已经有数据的复本。在第三种状态下，P3 请求对该复本的允许写权。则需要经过下面6

16、 个步骤： a. C3 检查出包含单元X 的块是有效的，但允许写位状态是不允许写状态。 b. C3 向包含X 的存储器模块发出写请求，并暂停P3 工作 c. 该存储器模块发出一个无效命令给 C1 和C2（根据目录项中的内容发无效命令） d. C1 和C2 收到无效命令之后，把相应位置0，表示含单元X 的数据块已经无效，并发送一个回答信号给存储器 e.存储器受到回答信号之后，将 C/D 位置1，清除指向C1 和C2 的指针，发允许写信号给C3 f.C3 收到允许写信号之后，修改高速缓存状态并激活P3在上面已经谈到，随着处理机数目N 的增大、存储器容量的增加，所需要目录的容量以N2 的数量级增加。

17、在目录本身就很庞大的情况下，还需要增加一位C/D 位，以指示该复本是否允许写。所以这种目录结构所需要的空间较为庞大。针对这个问题，提出了有限目录的方法。2）有限目录）有限目录 有限目录的基本思想是要解决全映射目录空间过大的问题。其采用的手段就是对任意一个数据块在高速缓存中同时存在的复本的数目加以一定的限制，这是基于处理机使用的局部性，即多机系统解决问题时，短时间内可能只集中使用其中几台机器，所以某一个数据块的复本只有部分处理机需要，因此只需要记录这几台机器，而不需要记录所有处理机，目录所需空间大大减少：记录处理机号码的所需空间呈Log2N 增长，总的空间需求为O（N XLog2N）。3）链式目

18、录）链式目录 链式目录是采用目录指针链来跟踪共享可写数据的复本；链表既可以采用单链表，又可以采用双链表。对于共享数据块的复本数没有限制。所占用的空间和可扩展性与有限目录近似。 链式目录的基本操作过程为链式目录的基本操作过程为（仍采用“全映射目录”中的例子）：（1）当P1 要读单元X 时，则主存送一个复本给C1，同时送给C1 一个链结束指针（CT），主存也保存一个指向C1 的指针（2）当P2 要读单元X 时，存储器送一份复本给C2，同时送给C2 一个指向C1 的指针，存储器保存指向C2 的指针16（3）重复以上过程，至所有高速缓存得到X 所在的复本。（4）如果P3 要对该单元进行写操作，它必须沿着链表发送一个无效的信