Cache(高速缓存)与主存一致性初探

Cache(高速缓存)与主存一致性初探 院系名称 姓 名 学 号 专 业计算机科学与技术专业 指导教师 II 摘 要 存储器是具有“记忆”功能的部件，它在计算机系统中占有十分重要的地位。 存储器的基本功能是存放以二进制形式表示的程序与数据。如何设计容量大、速度 快且造价低的存储器，一直是计算机发展中的关键问题，目前还没有哪一种存储器 功能完全满足计算机系统对存储器的需求。因此，计算机系统通常配备分层结构的 存储系统，以满足容量、速度和造价等方面的要求。 衡量存储器有三个指标：容量、速度和价格/位。一般地说，速度高的存储器， 每位价格也高，因此容量不能太大。所以存储器设计的约束有容量、速度和价格。 容量似乎没有限制，不管容量多大，总要开发出应用程序来使用。为了获得更好的 性能，存储器的速度必须能够跟上 CPU，即当 CPU 执行指令时，不想让他停下来等 待指令或操作数。价格问题也必须考虑，对于实用的系统，存储器的价格必须相对 于其他部件是合理的。因此三个指标之间需要进行权衡。 高速缓存系统中能否确保高速缓冲存储器和主存内容一致性，这个问题直接关系到 整个计算机系统的性能。这两部分的数据一致性问题产生的原因有二：其一，由于 CPU 对高速缓冲存储器的写入导致它的内容更新而主存内容陈旧；其二，由于 I/O 处理机或 多处理机系统中某一处理机修改了主存内容导致高速缓冲存储器内容陈旧。针对不同原 因，分析了写策略中七种解决方案，并就高速缓存系统采用的第二级脱片高速缓冲存储 器，以及第三级脱片高速缓冲存储器结构数据一致性问题进行初步探讨。 本文通过对存储器系统 Cache（高速缓存）与主存的概念进行描述和目前两者之间 一致性存在的一些问题进行研究。并分析在多处理机系统中，主存与各处理机私有 Cache 之间及各私有 Cache 之间存在的数据不一致性。对解决不一致性的方法：监听总 线协议、基于目录的 Cache 一致性协议、软件控制方法等进行详细的定性分析，并指出 各种方法的优缺点，供设计者参考；同时提出软件和硬件相结合的方法，能有效解决 Cache 的一致性问题。 关键词：存储器；主存；缓存；一致性 III Abstract Memory is a “ memory “ function components , it in a computer system occupies a very important position . The basic function of memory is stored in binary form of said programs and data . How to design capacity , speed is quick and low cost of memory , is always the key problems in the development of the computer , there is no memory function fully meet the needs of the memory of a computer system. Therefore, the computer system usually equipped with a layered structure of storage system, to satisfy the capacity, speed and cost requirements. Measure memory has three index : capacity , speed and price/a. Generally speaking , the high speed of memory, every price is high , therefore capacity can not be too big . So memory design constraints capacity , speed and price . There seems to be no limit capacity , no matter how much capacity , the total to develop applications to use . In order to obtain the better performance, the speed of the memory must be able to keep up with the CPU,and that is when the CPU executing instructions , dont want him to stop and wait for instructions or operand. The question of price must also consider, for practical system, memory prices relative to other parts must be is reasonable. So the three indexes to weigh between. Cache system can ensure cache memory and main memory contents consistency , the directly related to the entire computer system performance . The two parts of the data consistency issues of two reasons : first , because of the CPU cache memory write led to its contents to update the memory and out-of-date contents ; Second , because of I/O processor or multi-processor systems of a processor modified the main memory contents lead to cache content obsolete . According to different reasons , analyzes the strategy of written seven kinds of solutions, and the cache system USES 2 to take off the piece of cache, and the third class to take off the piece of cache structure data consistency problem for a preliminary discussion. This article through to the memory system Cache ( Cache ) and the concept of main storage describe between consistency and at present there are some problems. And analysis in multiprocessor system , main memory with the processor Cache between the private and private Cache of inconsistency between data. To solve the inconsistency method: surveillance bus agreement, the Cache directory based on consistency agreement, software control method of detailed qualitative analysis , and points out the advantages and disadvantages of each method for designers ; Some software and hardware the method of combining the Cache can effectively resolve the consistency of the problem. Key Words: Memory , The main memory , Cache , The consistency IV 目 录 1 引 言 .1 2 研究的背景和意义 .2 2.1 研究的背景 .2 2.1.1 主-辅存存储层次 2 2.1.2 CACHE-主存存储层次 .3 2.1.3 存储器分层结构 .3 2.2 研究的意义 .5 3 数据一致性问题的提出 .7 4 基于不同原因的写策略解决方案 .9 4.1 基于原因 1 的解决办法 .9 4.1.1 写直达 .9 4.1.2 写回发 .9 4.2 基于原因 2 的解决办法 .9 4.2.1 总线监视法 .9 4.2.2 硬件监视法 10 4.2.3 划出不可高速缓存存储区法 10 4.2.4 CACHE 清除法.10 4.3 基于原因 3 的解决办法 10 4.4 基于目录的 CACHE 一致性协议 10 5 数据一致性问题的发展与展望 13 6 结束语 15 参考文献 16 致 谢 18 1 1 引 言 高速缓冲存储器是存在于主存与 CPU 之间的一级存储器， 由静态存储芯片 (SRAM)组成，容量比较小但速度比主存高得多， 接近于 CPU 的速度。在计算机存 储系统的层次结构中，是介于中央处理器和主存储器之间的高速小容量存储器。它 和主存储器一起构成一级的存储器。高速缓冲存储器和主存储器之间信息的调度和 传送是由硬件自动进行的。 高速缓冲存储器的容量一般只有主存储器的几百分之一，但它的存取速度能与 中央处理器相匹配。根据程序局部性原理，正在使用的主存储器某一单元邻近的那 些单元将被用到的可能性很大。因而，当中央处理器存取主存储器某一单元时，计 算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央 处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单 元内。于是，中央处理器就可以直接对高速缓冲存储器进行存取。在整个处理过程 中，如果中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替， 计算机系统处理速度就能显著提高。 当然，计算机存储系统中，高速缓冲存储器系统的引入虽然为计算机系统处理 数据的速度带来了显著地提高，但是随之而来的 Cache（高速缓存）与主存间数据 一致性问题也是日益凸显出来。 存储器中的一致性问题，是伴随着存储器结构的概念而提出的，又一直是困扰着计 算机设计者的一个重要问题，也是很多从事计算机体系结构研究的人们所共同面对的一 个热门研究课题。特别是近年来出现的多处理系统，超并行机系统，超大规模计算机系 统等采用 DSM（Distributed Shared Memory）-分布式共享存储器技术的大型系统中， 都采用了多级 Cache 的存储器层次结构。在 Cache 的数据一致性问题上，就更显突出了。 如在 DSM 多处理机系统结构中，相邻层之间和同一层之内可能会出现数据不一致性。通 过存储器的共享数据，进程在同一算法下并行工作。为了减少内存访问延时和内存总线 的拥塞，要求 Cache 与每个处理器相关。这样同一数据在不同的 Cache 中有多个副本。 当处理机对共享存储器某个单元在其本地 Cache 中的拷贝要进行维护时，只要对该单元 的本地拷贝进行修改，这就有可能引起存储器的全局不一致性等等。所以如何在维护一 致性情况下又保证处理机代价最小是这本论文讨论的主要问题。 本文将在对计算机存储系统存储进行介绍的前提下，对高速缓存系统中 Cache（高 速缓存）与主存这两部分的数据一致性问题产生的各种原因进行充分的分析和研究，并 针对不同的原因，给予适当各种维护策略下的保证一致性的可行方案。 2 2 研究的背景和意义 2 2. .1 1 研研究究的的背背景景 存储器是具有“记忆”功能的部件，它在计算机系统中占有十分重要的地位。 存储器的基本功能是存放以二进制形式表示的程序与数据。如何设计容量大、速度 快且造价低的存储器，一直是计算机发展中的关键问题，目前还没有哪一种存储器 功能完全满足计算机系统对存储器的需求。因此，计算机系统通常配备分层结构的 存储系统，以满足容量、速度和造价等方面的要求。 衡量存储器有三个指标：容量、速度和价格/位。一般地说，速度高的存储器， 每位价格也高，因此容量不能太大。所以存储器设计的约束有容量、速度和价格。 容量似乎没有限制，不管容量多大，总要开发出应用程序来使用。为了获得更好的 性能，存储器的速度必须能够跟上 CPU，即当 CPU 执行指令时，不想让他停下来等 待指令或操作数。价格问题也必须考虑，对于实用的系统，存储器的价格必须相对 于其他部件是合理的。因此三个指标之间需要进行权衡。 2.1.1 主-辅存存储层次 由于计算机主存容量相对于程序员所需要的容量来说总是太小，程序与数据从 辅存调入主存是由程序员自己安排的，程序员必须花费很大精力和时间把大程序预 先分成块，确定好这些程序块在辅存中的位置和装入主存的地址，而且还要预先安 排好程序运行时各块如何和何时调入调出，因此存在存储空间的分配问题。操作系 统的形成和发展使得程序员尽可能摆脱主、辅存之间的地址定位，同时形成了支持 这些功能的“辅助硬件”，通过软件、硬件的结合，把主存和辅存统一成了一个整 体，如图 2-1 所示。这时，由主存、辅存形成了一个存储层次，即存储系统。从整 体看，其速度接近于主存的速度，其容量则接近于辅存的容量，而每位的平均价格 也接近于廉价的慢速的辅存平均价格。这种系统不断发展和完善，就逐步形成了现 在广泛使用的虚拟存储系统。在系统中，应用程序员可用机器指令地址码对整个程 序统一编址，如同程序员具有对应这个地址码宽度的全部虚存空间一样。该空间可 以比主存实际空间大得多，以致可以存得下整个程序。这种指令地址码称为虚地址 （虚存地址、虚拟地址）或逻辑地址，其对应的存储容量称为虚存容量或虚存空间； 而把实际主存的地址称为物理地址、实（存）地址，其对应的存储容量称为主存容 量、实存容量或实（主）存空间。 3 图 2-1 主-辅存存储层次 2.1.2 CACHE-主存存储层次 当用虚地址访问主存时，机器自动地把它经辅助软件、硬件变换成主存实地址。 察看这个地址所对应的单元内容是否已经装入主存，如果在主存就进行访问，如果 不在主存内就经辅助软件、硬件把它所在的那块程序和数据由辅存调入主存，而后 进行访问。这些操作都不必由程序员来安排，也就是说，对应用程员员是透明的。 主-辅存层次解决了存储器大容量要求和低成本之间的矛盾。 在速度方面，计算机的主存和 CPU 直保持了大约一个数量级的差距。显然这个 差距限制了 CPU 速度潜力的发挥。为了弥合这个差距，仅采用一种工艺的单一存储 器是行不通的，必须进一步从计算机系统结构和组织上去研究。设置高速缓冲存储 器（Cache）是解决存取速度的重要方法。在 CPU 和主存中间设置高速缓冲存储器， 构成高速缓存（Cache）-主存层次，要求 Cache 在速度上能跟得上 CPU 的要求。 Cache-主存间的地址映象和调度吸取了比它较早出现的主-辅存存储层次的技术， 不同的是因其速度要求高，不是由软、硬件结合而完全由硬件来实现，如图 2-2 所 示。 图 2-2 Cache-主存存储层次 2.1.3 存储器分层结构 从 CPU 的角度看，Cache-主存层次的速度接近于 Cache，容量与每位价格接近 于主存，因此，解决了速度与成本之间的矛盾。 4 综上所述，计算机的存储系统是采用了存储器的分层结构，而不只是依赖单一 的存储部件或技术。图 2-3 给出了一个通用分层结构，图中从上到下出现情况如下： 1每位的价格降低； 2容量增大； 3存取时间增大； 4CPU 存取存储器的频度降低。 图 2-3 存储器分层结构 因此，较小、较贵、较快的存储器可作为较大、较便宜、较慢的存储器的补充。 这个结构成功的关键是最后一项，即存取频度降低。 如果能够根据以上的 1到 3项来组织存储器，而且数据和指令能够根据 4分 布在存储器中，很显然，这个方案在保证给定的性能水平的情况下能降低总体价格。 下面用一个简单的例子来说明这一点。 假设 CPU 能够存取二级的存储器，第 1 级包含 1000 个字并有 1 微秒的存取时 间，第 2 级包含 1000000 个字并有 10 微秒的存取时间。假设要存取的一个字在第 1 级，那么 CPU 能直接存取它；假设它在第 2 级，则这个字首先传到第 1 级，然后 再由 CPU 存取它。为了简化，不考虑 CPU 确定这个字在第 1 级还是在第 2 级所需的 时间。图 2-4 表示了平均总存取时间和在第 1 级中存取字所需的时间占总的百分比 的函数关系。可见，第 1 级存取百分比高时，平均总的存取时间接近于第 1 级的存 取时间。此例说明了这种策略工作的原理。如果条件 1到 4都满足，则它能工作。 5 图 2-4 简单的两级存储性能 条件 4有效的基础是访问局部性原理。在程序执行过程中，处理器访问存储器 中的指令和数据倾向于成块进行。程序通常包含许多迭代循环的子程序，一旦进入 了一个循环或子程序，则需重复访问一小组指令。同样，对于表和数组的操作，包 含存取一块块的数据字。在一长段时间内，使用的块是变化的，而在一小段时间内， 处理器主要访问存储器中的固定块。 因此，通过分层结构组织数据，有可能使存取较低层的存取时间百分比低于存 取高层的百分比。根据上面给出的二级例子，让第 2 级的存储器包含所有程序的指 令和数据，当前的块临时放在第 1 级，第 1 级某些块回不时地交换回第 2 级。然而， 多数是对第 1 级中的指令和数据的访问。 这个原理可以应用到两级以上的存储器。考虑如图 2-3 所示的分层结构，最快、 最小和最贵的存储器是处理器的内部存储器。通常一个处理器包含几十个寄存器， 虽然有些机器包含几百个寄存器。向下跳二层是主存储器。主存储器通常用一个速 度更快、容量更小的高速缓存来扩充。高速缓存是透明的，它在主存和处理器寄存 器之间传送数据以提高性能。 2 2. .2 2 研研究究的的意意义义 高速缓冲存储器是存在于主存与 CPU 之间的一级存储器， 由静态存储芯片 (SRAM)组成，容量比较小但速度比主存高得多， 接近于 CPU 的速度。在计算机存 储系统的层次结构中，介于中央处理器和主存储器之间的高速小容量存储器。它和 主存储器一起构成一级的存储器。高速缓冲存储器和主存储器之间信息的调度和传 送是由硬件自动进行的。 6 高速缓冲存储器的容量一般只有主存储器的几百分之一，但它的存取速度能与 中央处理器相匹配。根据程序局部性原理，正在使用的主存储器某一单元邻近的那 些单元将被用到的可能性很大。因而，当中央处理器存取主存储器某一单元时，计 算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央 处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单 元内。于是，中央处理器就可以直接对高速缓冲存储器进行存取。在整个处理过程 中，如果中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替， 计算机系统处理速度就能显著提高。 在由主存和高速缓存组成的存储器层次结构中，主存是多处理机共享，而高速 缓存是每个处理机私有的。主存和高速缓存都以块为单位进行划分，以映射的方式 来检索。映射的方法有直接映射、组关联映射、区段关联映射和全相联映射。在主 存和高速缓存之间，是以块为单位进行搬送。主存中保存有各高速缓存的副本，高 速缓存的目录中，存放相应主存的块号及一些标志。通过对目录的检索来寻找高速 缓存中的数据。当处理机发出一个访问主存地址时，如果包含这个地址在内的模块 在高速缓存中，则称之为命中，该高速缓存可以使用。如果不在高速缓存中，则称 之为未命中（或 Cache 失效），这时，必须把这个模块从主存搬到高速缓存中，叫 做块搬送。如果高速缓存已满，则必须按一定的置换算法挑出一个模块搬出高速缓 存到主存，这叫置换。置换算法有 FIFO 算法，URL 算法等。 计算机高速缓存系统的发展为计算机设计者提出了一个重要课题：数据在 Cache（高速缓冲存储器）和主存之间交换时必须满足数据一致的要求，随着多任 务系统的采用，数据一致性问题越来越突出，以往关于这方面的著述具有了很大的 局限性，例如，对于 486 以上机种出现的第二级托片 Cache、第三级托片 Cache 如 何保存数据一致的问题尚未见于专门的论述。为了探索更适合于当前计算机发展的 趋势，必须适时追溯数据一致性问题出现和发展的历史轨迹，步入多任务系统的解 决方案。 因此高速缓存系统中能否确保高速缓冲存储器和主存内容一致性，这个问题直 接关系到整个计算机系统的性能。对于计算机整体性能的提升有十分重要的意义。 7 3 数据一致性问题的提出 高速缓存是旨在改善存储器平均响应时间的小型快速存储器，它在系统中位于微处 理器和主存之间，使得系统从 CPU 看具有 Cache 的速度，主存的容量。图 3-1 为一高速 缓冲存储器系统框图，它将微处理器频繁向主存请求的代码和数据予以拷贝。 图 3-1 高速缓存框图 Cachc 的操作与存储器一样具有读/写两种模式，其中读操作主要局限在不命中时 更新 Cache 内容，只影响存储系统工作速度。写操作不仅工作时间比读操作长，而且更 新主存内容，直接影响机器性能，据李学干、苏东庄在计算机系统结构一书中借典 型程序的统计可知，所有访存中约有 10%34%甚至更多的是写操作。写操作是直接导致 数据一致性问题产生的原因。 在一个系统中，同一个数据的多个拷贝可以同时存在，如果一个拷贝改变了而其它 的没变，那么两组不同的数据便与主存的同一地址有关。Cache 必须包含一个更新系统 以防止老数据(陈旧数据)被使用，即解决一致性问题。分析产生数据一致性问题的原因 主要有三个： 1 同样一个数据可能既存于 Cache 中，也存于主存中，这样可能前者己更新，后 者未更新，造成数据丢失。 2 在有 DMA 系统或多处理器系统中，有多个部件可以访问主存，这时可能其中有 些部件是直接访问主存，也可能每个 DMA 部件和每个处理器配一个 Cache，这样主存的 一块区域可能对应于多个 Cache 中的各 1 个块区，产生主存中的数据被某个总线主控部 件更新过，而某个 Cache 中的内容未更新，造成 Cache 中数据过时。 3 当主存中同时有多道程序运行时，Cache 中均有相应的数据副本与每道程序相 对应；对于共享数据，每道程序都有各自的 Cache 数据与主存数据相一致。当某道更新 8 了其相应的 Cache 数据和主存数据，而其它程序的 Cache 数据也有此页内容.则其内容 不会改变(例如写直达法约束)。这道程序再次读到的内容就会因是原先的内容而出错。 写策略是 Cache 使用的保证数据一致性的方法，保持系统主存更新，处理陈旧数据。 高速缓存一致性是指要求同一个信息项与后继存储器层次上的副本是一致的。如果 在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加 以修改。对于多处理机系统的存储器层次结构，相邻层之间和同层之间可能会出现数据 不一致性。比如某个处理机修改了该处理机的 Cache 的某个数据，则该数据块可能在别 的处理机上有相同的拷贝，由于该数据块得到了最新的修改，所以如果其它相同的拷贝 不及时得到修改的话，被其它处理机访问以后，可能出现错误。这也就是所谓的 Cache 不一致性。我们用图 3-2 一致性定义图来直观的表示： 图 3-2 一致性定义图 但是这种只对本地拷贝进行修改的方法就可能导致存储器的全局不一致性，也就是 这些拷贝并不一致。如何能够让处理器访问不会出错，并且维护一致性的代价最小是研 究高速缓存一致性和同步机制的主要研究课题。 9 4 基于不同原因的写策略解决方案 4 4. .1 1 基基于于原原因因 1 1 的的解解决决办办法法 原因 1 导致的数据一致性问题是建立在 Cache 内容与主存内容一一对应基础上，不 能相关更新造成的数据丢失，解决方法首先解决 Cache 与主存的相关动作。 4.1.1 写直达 它利用 Cache-主存贮层次在处理机和主存之间的直接通路，每当处理机写入 Cache 的同时，也通过此通路直接写入主存。从而主存随时跟踪 Cache 的最新版本，也就不会 有主存将数据丢失的问题但缺点也显而易见，它把开销花费在每次写 Cache 时就有对主 存的写入，造成总线活动繁忙。 4.1.2 写回发 这种方法是在 CPU 执行写操作时，信息只写入 Cache，仅当需要被替换时，才将已 被写入过的 Cache 块先送回主存，然后再调入新块。Cache-主存的地址映象表中需对 Cache 中每个块设置一个“修改位”，作为该块装入 Cache 后是否被修改过的标志，只 要修改过，就使该标志位置成“1”。它的开销花在每次需要替换时，增加了 Cache 的 复杂性。 以上两种解决方法的采用没有严格约束，从可靠性讲写直达法优于写回法，Cache 出错时可由主存来纠错。而写回法因有效块只在 Cache 中，故需在 Cache 中采用纠错码， 增力了冗余信息；从成本上讲，写回法低于写直达法，写直达法要花费大量缓冲器和其 它辅助逻辑。所以方法的采用主要山应用场合决定，单处理机系统以节省成本为主，多 采用写直达法。对共享主存的多处理系统，以可靠性为主，多采用写直达法。 4 4. .2 2 基基于于原原因因 2 2 的的解解决决办办法法 原因 2 是由于主存区块更新而 Cache 未更新产生的数据过时错误，解决方法应首重 主存内容的约束。 4.2.1 总线监视法 在这种方法中，由 Cache 控制器随时监视系统的地址总线，如其它部件将数据写到 主存，并且写入的主存区块正好是 Cache 中的区块对应的位置，那么 Cache 控制器会自 动将 Cache 中的区块标为“无效”。 10 4.2.2 硬件监视法 如果把主存映象到 Cache 的区块称为已映象区块，硬件监视法就是通过外加硬件电 路，使 Cache 本身能观察到主存中已映象区块的所有存取操作。解决办法是所有部件对 主存的存取都通过同一个 Cache 完成或每个部件配备各自的 Cache，当一个 Cache 有写 操作时，新数据既拷贝到主存，也拷贝到其它 Cache(播写法)。 4.2.3 划出不可高速缓存存储区法 这种方法是控制某些共享信息(如信号灯或作业队等)不得进入 Cache。即要在主存 中划出一个区域作为各部件共享区，CPU 对此区域的访问必须是直接的，避免了主存中 1 个区块映象到多个 Cache。的情况。 4.2.4 CACHE 清除法 这种方法是将 Cache 中所有己更新的数据写回到主存时，由专用硬件自动地将 Cache 内对应此区域的副本作废，或清除 Cache 中的所有数据，使 Cache 内容取决于内 存内容的变动，保持 Cache 的透明性。 当然以上几种方法并不是全部解决措施，还有目录表法等应用。无论何利，万法， 本质上的要求都是透明性要求，视具体应用场合采取适当措施。 4 4. .3 3 基基于于原原因因 3 3 的的解解决决办办法法 原因 3 本质上是原因 2 的补充，前述解决了 Cache 数据过时引起数据不一致的问题， 而对于多任务系统仍存在着主存内容过时引起的数据不一致性。只写存储器方式就是这 样的一种解决方案。 在这种方式中，进行写操作时，把数据只写入到主存储器的对应位置上，同时通过 查页表，如果发现 Cache 中有与主存被修改页面相同的页号，则清除 Cache 中对应数据 的有效位，即使某页作废。这样在下次进行此页数据的读操作时，由于 Cache 中对应的 有效位无效，处于不命中状态，CPU 肯定要从主存储器读写数据，同时把数据交换进 Cache 中，保证了数据的一致性。 4 4. .4 4 基基于于目目录录的的 C CA AC CH HE E 一一致致性性协协议议 基于目录的协议用于网络连接的处理机系统。当某台处理机采用写无效协议正在更 新一个变量并且其他的处理机也试图读该变量时，则会发生读缺失并可能导致总线的流 量大大增加。另外，写更新协议可以更新远程高速缓存中的数据，而其他处理机可能永 远也不会使用这些数据。因此，这些问题使采用总线来构造大型多处理机系统受到限制。 当用多级网络来构造有数百台处理机的大型系统时，就必须修改高速缓存的监听协议以 11 适应网络的性能。由于在多级网络上实现广播功能的代价很大，所以把一致性命令只发 给存放块拷贝的高速缓存。这样就产生了用于网络连接的多处理机系统的基于目录的协 议。 由共享存储器的控制器来管理状态信息，当需要维持数据一致时，检索这些状态， 直接使有关的 Cache 中的模块无效化，并在共享主存中建立一个目录，就叫目录法。 在多级网络中，用高速缓存目录存放有关高速缓存块拷贝驻留在哪里的信息，从而 支持高速缓存一致性。各种基于目录协议的不同之处主要是目录如何维护信息和存放什 么信息。Tang（1976）提出了第一个目录方案，用一个中心目录存放所有高速缓存目录 的拷贝。中心目录能提供为保证一致性所需要的所有信息。因此，它的容量非常大而且 必须采用联想方法来检索，这和单个高速缓存的目录类似。在大型处理机系统采用中心 目录将存在出现冲突和检索时间长两个缺点。 Censier 和 Feautrier（1978）提出分布式目录方案。每个存储器模块维护各自的 目录，目录中记录着每个存储块的状态和当前的信息。状态信息是本地的，但当前的信 息指明哪些高速缓存才有该存储器块的拷贝。不用广播的高速缓存一致性协议必须将所 有高速缓存中每个共享数据块拷贝的地址存储起来。这张高速缓存地址表，不管它是集 中的还是分布的，都称为高速缓存目录。每个数据块的目录项包含大量的指针，用来指 明块拷贝的地址。每个目录项还包含一个重写位，用来说明高速缓存允许把有关的数据 块写入。 不同类型的目录协议可分为三类：全映射（full-map）目录、有限（limited）目 录和链式（chained）目录。全映射目录存放与全局存储器中每个块有关的数据。这样， 系统中的每个高速缓存可以同时存储任何数据块的拷贝，即每个目录项包含 N 个指针， N 是系统中处理机的数目。 有限目录与全映射目录不同之处是不管系统规模有多大，它的每个目录项含有固定 数目的指针。链式目录将目录分布都各个高速缓存，其余与全映射目录相同。对三种高 速缓存目录的讨论详见 Chaiken，Fields，Kwihara 和 Agarwal（1990）文献。 4 4. .5 5 软软件件控控制制法法 软件解决 Cache 数据一致性问题的方法是以通过编译进行事先分析的办法为主流。 最简单的方法是：可写的共享数据都不放在 Cache 中，但这样对很多数据来讲，就失去 了 Cache 的意义。随着编译分析技术的发展，把程序分成计算单位，每个参数上都附上 Cache 可与 Cache 不可的标志。编译识别这些标志，再给模块附上状态，由硬件来检查 这些状态，进行一致性处理。但这种方法给用户和编译带来麻烦。另外还有循环分割法 等，这些方法都是使 Cache 整体无效化，但有效的数据也全被无效了。于是又提出只把 的确要无效化的模块（或参数）无效化。把每一个参数的层次进一步细分为 Post（写 12 回），Invalidate（无效化）和 Flush（两方）等的 Cache 控制，与写回 Cache 控制组 合起来，进行更细的控制。还有采用通过编译来分析共享存储器的读信息，注意这时 Cache 中的数据的有效性，分别判断是从 Cache 中读出，还是从共享主存中读出。这种 方法是用硬件来帮助由编译分析不出来的地方。这样一来，使用 Cache 中的数据的机会 就增多了。同样为帮助编译进行分析，而给每个参数都带上新编号，运行时对此进行管 理，也需要复杂的硬件开销。除了编译分析外，也可以用操作系统来保证 Cache 数据一 致性的办法。例如设置临界区，通过同步信号来保证 Cache 数据的一致性。也有用 TLB 表象管理虚存那样控制数据的一致性。 13 5 数据一致性问题的发展与展望 随着计算机吞吐能力的增强，单靠在 CPU 与主存之间增加一级 Cache 已远远满足不 了工作需要，从 486 机种开始出现了二级 Cache 结构，即第一级 Cache 与 CPU 集成在一 起成为在片 Cache，另外单独在中央处理器与主存之间增加第二级脱片 Cache，而目前 已发展到三级 Cache 结构，将第一、二级 Cache 均集成在中央处理器内，另增设第三级 脱片 Cache，从而数据一致性问题又有了新的发展.这二级(三级)Cache 与主存之间如何 保持数据的协调一致呢？ 1 穿透 LOOK THROUGH； 2 旁视 LOOK ASIDE 穿透结构的优点是减少对 DRAM 系统主存的请求数目，只有在 Cache 未命中情况下， 来自微处理器的存诸器请求才从 Cache 送往主存；旁视结构的优点是来自微处理器的存 储器请求同时送到 Cache 与主存，访问时微处理器若在 Cache 中命中则访问 Caehe，同 时取消送往主存的存储器请求，若未命中，那么 Cache 便不工作，由系统主存完成该存 储器请求。如图 3-3 Cache 读结构。 微处理器 外部 Cache 系统主存储器 （DRAM） 系统主存储器 （DRAM） 微处理器 外部 Cache 穿透旁观 图 3-3 Cache 读结构 这两种 Cache 读结构其实也就是 Cache 的组织结构，可做如下设想：二级 Cache 结 构中第一级 Cache。采用穿透结构，规模增大，采用交叉与多口结构联系第二级 Cache 与主存，配置超级流水线和预取支持。第二级 Cache 采用旁视结构，容量有限制增长， 14 负责对第一级 Cache 的预取操作，实质上数据一致性问题即成为第二级 Cache 与主存之 间的问题了，解决办法就可借用前文提到的各种办法：三级 Cache 结构将第二级 Cache 也移入 CPU，出现第三级脱片 Cache，当微处理从第二级 Cache 仍取不到数据时，由第 三级脱片 Cache 的预取操作弥补二级 Cache 结构中第一级 Cache 直接从主存提取的操作， 以提高效率，故第一级 Cache 仍采用穿透结构，第二、三级 Cache 均采用旁视结构，到 第三级的预取仍不能满足命中时才与主存交换信息，这样数据一致性问题成了第二、三 级 Cache 与主存之间的问题了，而第二、三级 Cache 结构完全一致，动作很容易协调， 所以我们可以把它们看作一个整体。数据一致性问题的解决仍是借助前文论述的各种方 法加以实现。 15 6 结束语 随着半导体技术、通讯技术等计算机相关技术的发展，存储系统的发展呈现出了新 的层次结构和典型的金字塔模型。现今有关处理器内部的高速缓存的层次结构的前沿研 究，主要集中在最后一级高速缓存的有效利用上。同时，多核技术带来了计算机性能的 飞速提升，为计算机的存储结构带来了许多的机遇和挑战，也为程序的快速运行提供了 更多的途径和可能。 通过以上的分析可以看出：用硬件的方法不影响编译和用户程序，也不必意识到 Cache 的存在。但硬件变复杂了，同时要增加通信开销和时间延迟。软件的办法，编译 负担太重。由于程序的不确定性，分析的保守性，会造成不必要的 Cache 不命中。如果 硬件变得简单些，各处理机可以单单进行无效化，通信开销就可大大减小了。还可以不 依赖处理机台数和通信方式。而在硬件方法中，总线型多机系统用监视法好，而交叉开 关和多级互连网络的多机系统中，还是目录法好。到底作何取舍，每个设计者将根据自 身的需求做一个合适的选择。软件和硬件相结合的方法，可能是解决 Cache 不一致性问 题的更有效的方法。 目前，关于 Cache 一致性的研究还在继续，主要方向有三个。一是如何实现这些维 护一致性的方法，因为一些方法迄今为止还停留在建议的阶段，要评价它们必须在实际 实现中才是有效的。二是由于并行处理领域还不成熟，大型多处理机的实际应用还很少， 难以在实际情况下评价这些方法。三是多处理机 Cache 的设计空间很大，而且涉及复杂 的平横。 高速缓存系统数据一致性问题是基于透明性要求产生的。随着计算机系统结构的发 展，Cache 经历了一级、二级、三级多次变革，每一次都带来了新的问题，但解决方案 的核心仍是写策略，围绕 Cache 与主存一致动作，及时更新 Cache 中过时数据和及时更 新主存中过时数据三个方向发展。由于辅助硬件的使用写策略也可以影响系统的性能， 所以高速缓存写策略应本着以下三个目标加以采用： (1)维持存储器的相关性。 (2)令微处理器存储在写主存上的等待态数目最少。 (3)令存储器写周期数最少。 当然，由于此课题本身较难，资料有限，再加上条件和自身水平的限制，而且本人 学习存储器系统一致性问题的时间也不是太长，所以本文所讲述的内容还不能说是一个 完整的体系。本文只是就此问题的提出、发展、以及解决方案和展望进行了初步探讨， 很多方面还需要进一步完善。因此今后还需要在存储器系统一致性方面继续学习，以便 更好的进行研究。 16 参参考考文文献献 1 Guang R Gao，Vivek Sarkar. Location ConsistencyA New Memory Model and Cache Consistency ProtocolJ.IEEE Transactions on Computer,2000,49(8). 2 CWallace，GTremblay，JNAmaral. The Location Consistency memory mode