摘要: 计算机体系结构数十年来蓬勃发展，但内存性能的提升远远不及处理器性能的增长。这种增长速度的不平衡造成内存和处理器之间的性能差异越来越大，内存访问成为计算性能的瓶颈。与此同时，近年来广泛使用的多核处理器 (Multicore processor) 在降低功耗和增强计算能力的同时，也因其多核间的内存共享使得数据存取成为计算中更为严重的性能瓶颈。
数据预取 (Data prefetching) 是一种有效掩盖内存访问延迟的技术。在硬件和/或软件的支持下，预取技术能在处理器需要访问数据之前预先将数据从内存读入高速缓存，从而弥补处理器计算和内存数据访问之间的性能差距。许多预取技术已在单核处理器体系结构下得到应用。尽管这些预取技术可直接应用于多核处理器，但最近提出的一些基于多核体系结构的预取策略似乎更加新颖有效。针对这些最新进展，本文全面调研了单核和多核处理器结构下的各种预取策略，并根据预取策略设计中需要考虑的各类问题，采取自上而下的方法，提出了一个预取技术的有效分类法。此分类法由预取策略必须解决的五个最根本问题组成：预取数据，预取时间，预取出处，预取去处，和预取发起者。
（1）预取数据。预测什么数据需要预取是设计预取策略必须解决的首要问题。来自处理器的数据请求若不能命中高速缓存，则会引发对更低一级的缓存或内存的数据请求访问。这种缓存未命中会造成处理器浪费大量的时间等待数据。如果预取策略可以预测所需数据并提前发出请求指令，使得处理器在需要数据时所需数据已经被预取至高速缓存中，那么就可以节省大量因为等待数据而浪费的处理器周期。我们根据预测机制的不同，对预取策略进行了分类。这包括硬件预取策略，如分析历史信息的在线或离线预测，或预执行预测；包括利用编译技术或程序员插入预取指令的软件预取策略；也包括结合软硬件两种机制的混合预取策略。我们在文中详细介绍了每一种机制。
（2）预取时间。适时发出预取指令是预取策略必须解决的另一个重要问题。预取的数据应在缓存未命中发生之前到达预取的目的地，但为了避免将其他有用的数据替换出缓存，又不能过早到达。高效率的及时预取既取决于预取策略的时间开销，也取决于从当前时间至下一次缓存未命中发生时的时间窗口的长短。如果预取的时间开销超过了该时间窗口，调整预取距离则可避免无用的预取。我们对决定何时预取的机制进行了分类，包括基于事件，基于程序计数器，和基于软件控制的同步机制等。
（3）预取出处。体系结构中的多级缓存机制含有多个层次，包括各级高速缓冲存储器、主存储器、次级存储器和外部存储器。数据预取可以发生在多级缓存中的任何一个层次，例如从内存到高速缓存间的预取，或从次级存储器到内存的预取。当设计预取策略时，必须考虑最新的数据在哪里。在现有的多级缓存机制和缓存写回策略下，数据可能存储在任一级别的缓存中，因此，预取策略的设计必须能够正确地找到最新的数据拷贝源。
（4）预取去处。在预取策略中，为避免缓存抖动（Cache thrashing）和维护缓存一致性 (Cache coherence)，预取目的地的选择应更加谨慎。只有预取的目的地比预取源更接近处理器，才有可能获得性能优势。数据可以预取至处理器的私有缓存，或是多处理器的共享缓存，或是独立的预取缓存。独立的预取缓存则可以是处理器私有或由多核共享。
（5）预取发起者。预取指令可由请求数据的处理器，或是由专门提供预取服务的处理器发起。前者一般称为用户发起或基于拉动的预取，后者则称为基于推进的预取。根据预取发起者的位置, 本文对基于拉动和基于推进的预取进行了分类。
基于本文提出的分类法，我们分析并比较了一系列典型的预取策略，并讨论了它们的优缺点。本文还着重讨论了在多核处理器体系结构下，预取策略面临的挑战和必须考虑的设计问题，例如如何维护缓存的一致性，如何减少带宽竞争，如何利用多核处理器的强大计算能力运行复杂的预测算法等。此外，我们还讨论了在多核处理器下预取策略设计的潜在解决方案。