预取技术是通过计算和访存的重叠，在Cache可能会发生失效之前发出预取请求以便在该数据真正被使用到时己提前将数据块取入Cache，从而避免Cache失效造成的处理器停顿。
预取技术是通过计算和访存的重叠，在Cache可能会发生失效之前发出预取请求以便在该数据真正被使用到时己提前将数据块取入Cache，从而避免Cache失效造成的处理器停顿。
现代处理器速度的快速发展和存储器速度 的慢速发展导致处理器要花费大量的时间等待 存储器数据的返回，这就是存储墙问题。例如，Alpha 21264 667 MHz的工作站一次访存失效造成的开销就高达128个时钟周期!
. 为了解决这些问题，已提出多种技术方案， 其中最主要的有缓存和预取技术两种。缓存技术是利用局部性原理， 使速度更快的上层存储器成为下层存储器的缓冲。基于技术的限制及成 本的考虑，上层存储器的容量要比下层存储器小得多。数据如果存在于上层存储器中，就可以直接对其进行读写， 这种情形叫做命中，命中的统计概率叫做命中率；如果未命中就必须涉及到访问下层存储器，这种情形也叫失效。按照产生失效的原因不同，缓存失效可分为：强制性失效、容量失效和冲突失效。 缓存技术能否通过较快的存储器屏蔽对较慢的存储器的访问， 完全取决于上层存储器的命中率。 提高相联度、Victim Cache、伪相联 Cache 等技术以及好的缓存替换算法都可降低缓存冲突失效，从而提高缓存命中率。 随着应用规模的不断扩大和上述技术的不断成熟， 容量失效和强制性失效在总的缓存失效次数当中所占的比例越来越大，成为影响缓存性能的主要因素。 预取技术可以通过计算和访存的重叠，隐藏因为缓存延时而引起的缓存失效，被认为是解决容量失效和强制性失效的有效手段。 随着缓存技术的广泛应用，预取技术也在存储控制器、操作系统、数据库、网络、文件系统等应用中起到了重要作用。
硬件预取是由硬件根据访存的历史信息，对未来可能的访存单元预先取入Cache，从而在数据真正被用到时不会造成Cache失效。但是由于只是基于访存的历史信息，硬件预取会取回大量无用的Cache块，占用访存带宽，还会导致严重的Cache污染问题。由于硬件预取是基于访存的历史信息来预测未来的访存模式，从而可以在数据使用之前将其从下一级的存储器中取回。
当代微处理器大都提供了预取指令来支持软件的预取。软件预取是指在编译时由编译器显示加入预取指令，提前将下一级存储器中的数据取回。因为加入了大量的预取指令，同时显示的预取指令需要计算出准确的预取地址，从而导致不能及时的发出预取指令以足够隐藏访存延时，影响了性能的提高。并且必须使额外的 预取指令开销不能超过预取所能带来的效益， 否则得不偿失。
考虑到硬件预取和软件预取的缺点，有不少学者提出用软硬件结合的方法来解决这些问题。基本方法都是围绕软件给予硬件一些关于程序的信息，克服单纯的硬件预取的盲目性，从而可以得到更高的性能，更具有吸引力。 如提出的GRP技术，它是由编译提供预取的时机、预取的步长、预取的元素数目等信息，由硬件完成预取动作。
Cache失效通常被分为三类，分别为强制性失效、冲突失效和容量失效。有很多技术关注的是减少冲突性失效，但是它们对于冲突失效和容量失效则不能解决。预取技术预测将会引起Cache失效的访存，利用存储器的空闲带宽，提前将其取回，从而隐藏由于访存延迟引起的处理器停顿。能够很好的解决强制性失效和容量失效。一般来说，CPU 并不直接与存储器交换数据，而是通过Cache间接进行。由平均访存时间公式和程序运行时间公式可以看出，Cache失效对于系统的性能有着很大的影响。因此，为了改进系统的性能，首先必须要找出Cache失效的特点。 通过对NPB访存行为的研究，发现在NPB 测试集中线性访存模式是造成Cache失效的最主要的原因。统计结果表明，由线性访存模式直接引起的Cache失效占程序总的 Cache失效次数的68.6%；而若考虑由此引起的Cache污染对失效率的影响该比例上升至78.2%。同时，线性访存模式具有模式简单，便于优化的优点。因 此，在研究Cache行为、提高Cache利用率以及设计新的软件可管理的Cache结构时应该对这 类访存模式给予考虑。 对于线性访存模式所引起的大量失效，预取是个很好的选择。使用预取技术，能使数据和指令可在 CPU 使用之前到达与 CPU 更近的存储层次，因此在真正需要它们时能及时的拿到或者可以减少延时和阻塞的时间。但是预取面临着下面几个问题：
a. 什么时候进行预取；
b. 预取什么样的数 据；
c. 预取到的数据放在什么位置。
而如果没有解决好其中某些问题，则会导致：
a. 大量无用数据块的取回，以及由此导致的带宽的浪费；
b. 预取的数据造成了将要使用数据的替换，造成 Cache性能的下降；
c. 预取时机过早或过晚，数据在没有使用前就被替换出去或者是要使用时还没有取回。
Cache对于NPB这类计算密集型的应用性能发挥不足；这是由于程序中不同代码段的数据集具有不同的访存模式而Cache却对它们采用了统一的策略所造成的。
编译指导的失效时预取
一个好的预取技术的基础是能够准确的预测程序未来的访存行为。而线性访存模式对应为程序中访问的地址随时间按照线性规律变化，并且这类访存模式在科学计算、数据库、 多媒体等应用中占有很大的比例。恰恰也正是线性访存模式造成了程序中相当一部分的Cache 失效。如果能够很好的解决线性访存模式的访存失效引起的大量CPU 停顿，则可能会大大改善系统的性能。根据局部性原理，程序即将用到的数据块多数情况下与当前访问的数据块在空间上是相邻的或者是临近的。失效时预取技术 (Prefetch On Miss ) 就是利用这个基本原理，具体做法是在访存引起 Cache 失效时取回两个 Cache 块：请求的数据块和顺序的一下个数据块。
编译指导的基于访存预测表的预取技术
以上提出的编译指导的失效时预取技术和传统失效时预取技术相比，可以大大的提高预取的准确度，减少Cache的污染。但是，编译指导的失效时预取只有在访存发生Cache失效时才会启动预取动作，预取顺序的下一个Cache块。对于数组顺序遍历的访问模式，失效时预取 (预取度为1)可以将失效率降低一半。但是可以看到，对于跨步式或是逆序的访问模式，失效时预取会糟糕。因为跨步式或是逆序的访问模式在访存发生Cache失效后不会在短时间内访问顺序的下一个Cache块，而失效时预取则不断的取回了大量的无用块，造成Cache污染。即使 增加了编译的指导对于这类访问模式也只能采取不预取的策略。但线性访存模式是最具有规律性的访问模式，很容易预测，同时在程序总访存量中占有很大的比例，所以应该采用更高级的策略来处理线性访问模式。如果硬件能够在编译所给的提示下，在Cache还没有发生失效时就能够预测到将会访问到的数据，并不断地将其提前取回，那么预取的性能将会大大的提升。
固定预取算法
OBL（One-Block Look-ahead）是一种简单的预取算法，它认为当数据块 i 被访问后，数据块 i 之后的块应该很快就会被访问。 除了在开始的时候不进行预取外，在每个数据块 i 被访问后，第 i+1 块都会被预取到缓存里。OBL 由于每次预取只取一个数据块，会导致频繁地使用 I/O 读磁盘， 从而浪费大量的寻道时间。 IBL （Infinite-Block Look-ahead）对OBL进行了简单的扩展，每次预取数据块 i 后的 n（预取度）个页面，相比 OBL 增大了预取的 I/O 块大小。 这两种算法都是固定进行预取，具有盲目性，可能会造成缓存污染和预取浪费， 特别是 IBL 的预取度比较大的时候。
顺序预取算法
基于空间局限性原理，对顺序序列来说，如果数据块被访问就意味着该数据块之后的数据很快就会被访问，这与固定预取算法的思想是一致的。 由此提出了基于顺序预取的算法，其实现可按功能分为三部分：
①顺序检测模块：对顺序序列的检测通常是基于访问历史来确定的。 对具有大容量缓存的存储可直接根据存在于缓存中数据进行分析，而对缓存容量较小的存储来说这些数据将不足以进行检测，于是提出了一种基于表格的算法；
②预取模块：此模块用来决定预取的时机和预取度，是顺序预取算法的核心部分。 通过预取数据命中率及预取浪费率等信息进行分析，从而自适应地改变预取行为；
③缓存管理模块：该模块用来管理页面的换出，希望把最为有用的数据留在缓存里面。 利用不同的 LRU 链管理顺序和随机的序列，通过边际效应的大小来决定淘汰页面，从而让淘汰的损失最小化。
基于应用暗示的预取算法
像视频、音频、数据备份和恢复等很多应用其 I/O 基本是顺序的，而 Web 应用其访问是基于链接的分枝访问，数据库应用经常需要进行随机访问。 顺序预取算法将不再适用于非顺序序列的应用，于是文献提出了由用户暗示的透明信息预取方法（TIP）。TIP 可以根据用户提供的访问方式在适当的时候发出异步的预取指令，指令内容由用户的暗示确定。 这类算法也可以有顺序检测模块，主要是增加了一个能够提供给上层应用接口的模块， 应用通过此模块告知预取模块相应的信息。 由于预取信息由相应的应用自己提供，基于用户对应用的了解，针对性强，预取也会更加准确。 通过以上描述可知，此类算法对应用不透明，需要上层应用的支持。
基于数据挖掘的预取算法
数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但是又潜在有用的信息和知识的过程。 由用户暗示的访问方式的信息，也可以由数据挖掘技术来提取； 对某些开发者无法得知每个用户访问特点的应用，例如 Web 应用、数据挖掘技术同样也能发挥重要作用。 预取算法根据数据挖掘对数据的分析提取出的信息决定需要预取的数据， 此算法对应用是透明的。 但是否能够进行高效的预取，还在于其数据挖掘算法能否准确提取出应用潜在的访问信息， 这也正是此算法的关键和难点所在。
温馨提示：
