0 引言

    随着处理部件和存储部件的性能的持续拉大，高速缓存作为标准配置已广泛应用于各种处理器设计的存储层次中。设计者希望通过将经常用到的数据保存在高速缓存中，降低内存时延对处理器执行性能的影响，从而实现较高的性能价格比。因此，缓存的命中率对处理器的整体性能有至关重要的影响。

    预取技术是一种提高缓存命中率的有效方法。通过动态分析程序行为，对将来可能的数据访问模式进行预测并将可能访问的数据提前读取到高速缓存中。在处理器需要访问对应数据时，可以直接在高速缓存中获得所需的数据，从而避免处理器直接访问高延迟内存造成的高延时。为了达到好的预取效果，就需要预取技术能精确预测可能的数据访问，提高预取的准确性，避免内存带宽及缓存容量等稀缺资源的浪费。

    本文综合评述了影响预取准确性的关键因素，当前主流的预取技术以及各种预取技术的优缺点。并分析了当前多核平台和众核平台对预取技术的影响。在此基础上，对预取技术的发展方向进行了展望。

1 预取技术

    处理器平台运行着大量的应用，由于这些应用的访存行为各异，也衍生出了大量不同的预取策略来提高应用性能。在预取的相关研究中，主要关注的是如何针对相关应用制定与实现高效的预取策略，其核心是围绕利用程序执行过程中存在的空间局部性与时间局部性，提升性能。近年来多核平台的普及也为预取技术的发展提供了新的机遇与挑战。多核平台存在许多额外硬件资源，可以为程序的预取提供便利，从而加速程序的执行效率。本节分别对基于利用空间局部性的预取、基于时间局部性的预取和多核平台的帮助线程相关研究进行分析。

1.1 基于空间局部性的预取

    空间局部性指的是由于程序的顺序执行或数组的顺序访问，程序即将用到的信息可能与目前正在使用的信息物理地址相邻或邻近。可以利用这一点来为预取提供理论依据从而提高程序执行效率，减少内存访问延迟。但繁多的应用程序存在着不一样的程序逻辑，发掘各类应用的空间局部性需要在策略的复杂度和预取效率之间进行平衡。

    程序每次顺序地访问相邻物理地址块是程序空间局部性最直接最简单的一种形式，Next-Line预取^[1]正是基于这种想法提出的，即每次预取当前访问地址块之后的块来提升程序性能。其优点是实现简单，但由于这种情况只能涵盖一小部分程序逻辑，导致无效预取指令过多，进而影响预取效率。为了可以处理更为复杂的程序行为，可以在Next-Line预取的基础上添加不同跳转长度的预取支持^[2]及跳转长度预测机制^[3]，为处理更为复杂的情况提高预取效率。

    为了进一步发掘程序中的空间局部性关系来制定预取策略，可以对程序的执行情况做更为复杂的分析。一种比较有效的方法是引入统计的方法对内存访问流进行分析，从而提高预取的准确性。如通过统计最近的内存访问流生成访问直方图^[4]。当出现对某一已记录地址进行访问时查询直方图，从而决定预取多少条连续指令。空间局部性侦测表^[5]及其变种对程序局部性行为进行分析，通过调整各个代码块的大小提升代码执行过程中的空间局部性。然而，这类方法需要维护较大的表来记录并探寻空间局部性。分析发现，在商用负载中通常存在重复出现的较长的内存访问序列^[6]。为了进一步降低预取预测所需的存储空间，可以建立这些序列程序计数器与访问地址的关联，通过只维护关联关系，可以在维护一个较小的表的情况下，对众多商用应用上取得良好的预取效果。

1.2 基于时间局部性的预取

    时间局部性是指访问过的某些数据在不久的将来还会被访问到。基于时间局部性的预取主要是通过分析程序的访问模式，发现一条或数条重复发生的访问链（即一系列地址按照相同的访问顺序重复出现）进行预取。当该链被判断再次发生时，根据记录的序列推测下一个访问地址。最简单的时间局部性预取策略是基于Markov模型的预取策略^[7]。该策略通过利用一个表来记录给定地址的下一个潜在访问对象来实现Markov预取器。

    然而，由于相关性流的长度可能达到上百个，为了利用时间局部性，可能需要非常大的额外存储空间来存储相关流。因此，如何对存储空间进行优化是基于时间局部性预取策略需要解决的重要问题。由于现有高速缓存中命中率（hit rate）远远高于缺失率（miss rate），因此一种有效优化策略是通过记录缓存缺失的地址来代替记录整个访存行为降低所需的存储空间^[8]。除了利用地址相关性，还可以利用地址变化相关性（delta correlation）来优化存储空间。即通过记录两次访存之间的地址偏移量来训练预取策略。虽然这种策略会明显减少所需存储空间，但对于无规律的访问，也会导致覆盖率和精度的降低。很多情况下反复出现的指令流是由诸如循环迭代之类反复出现的代码块产生的^[9]。通过获取整个循环结构的工作集可以在保证精度的情况下精简预取所需的额外开销。通过对执行频度高的循环进行注释，预取器可以追踪和预测整个迭代循环的工作集，从而在保证精度的情况下降低预取所需的存储开销。

    为了进一步减少片上硬件开销，也可以将预测信息存储在片外^[10]，片上只存储对片外存储信息哈希建立的索引，以减少查询及访问延迟并利用“概率更新”机制来减少片外信息的更新频率，从而可以降低较长的流造成的存储开销。

1.3 帮助线程

    近年来，由于能耗墙和存储墙问题的突出，多核处理器已逐渐代替单核处理器成为主流硬件平台。其丰富的并行资源为提高应用性能提供了广阔的前景。并行资源的丰富也为进一步提升预取效率提供了空间。

    基于多核的预取策略优化主要是基于额外硬件资源生成帮助线程来提高预取效率。其核心思想是基于主线程的执行流生成精简版本作为预取帮助线程^[11]。主线程与预取帮助线程同时执行，由于预取线程执行的程序片段为主线程的精简版本，通常执行速度会快于主线程。因此可以将其执行读取数据的结果通过共享缓存反馈给主线程从而达到为主线程预取数据，加速主线程执行速度的效果。

    另一种帮助线程预取的策略是通过核间线程迁移基础上的帮助线程预取策略^[12]。之前的帮助线程主要是通过共享的缓存来为主线程的预取提供帮助，而由于共享缓存的速度较慢，无法达到较好的性能。为了进一步提高帮助线程的效果，可以通过核间线程迁移的方式利用高速的私有缓存实现高效的预取。在这种策略下，帮助线程仍然为主线程执行片段的精简版本。每个核运行一个线程，同时运行的线程包括一个主线程和数个帮助线程。当运行完一段指令后，对主线程进行迁移，即原本运行主线程的核开始运行帮助线程，而之前运行帮助线程的核由于已经完成了预取，主线程将迁移到这个核上，从而利用存储在该核私有缓存中的预取信息而不是共享缓存，提高了效率。

2 面向图形处理器（GPGPU）的预取技术

    图形处理器由于其强大的计算能力和对通用计算支持的逐步加强，目前越来越多地应用于通用计算领域。因此如何提高其片上存储部件的效率对其执行性能将产生至关重要的影响。与通用处理器（CPU）不同，由于GPGPU上各个硬件核心运行的线程访存模式较为接近，面向GPGPU的预取策略主要集中在利用空间局部性。除了预取策略的制定外，还有部分研究是围绕充分发掘GPGPU硬件资源来为预取提供额外支持而展开的，本节将分别对这两部分进行介绍。

2.1 GPGPU的预取策略制定

    GPGPU由于其高并行度的优势，越来越多的被应用到通用计算领域。与通用处理器类似，GPGPU虽然拥有更为丰富的计算资源，但其性能也受到了内存延迟的限制，而预取技术正是有效隐藏内存延迟的手段之一。

    虽然GPGPU相关应用都具有良好的空间局部性，但由于其自身硬件特点，为了取得性能提升并不能直接套用已有针对CPU的预取技术。高度并行化是GPGPU应用与传统的应用的显著差别之一。正是由于这个特点，GPGPU上每个线程的执行时间通常较短，这也意味着线程中如果存在循环体的话，循环次数也非常少。这种情况下针对线程自身并没有多少机会通过预取来提高性能。因而面向GPGPU的预取主要是进行线程间的预取^[13]，即当前执行的线程组（warp）为下一时刻将要执行的线程组中的线程进行预取，减少了之后执行线程的访存延迟。在GPGPU上执行的多个warp组间通常具有较好的访存规律性，若3个或3个以上warp中对应线程的访存偏移量一致，则认为偏移量可以应用至整体线程组。对于这种情况，可以针对每个warp维护一个访存偏移表，从而为预取提供依据。

    然而，在GPGPU线程的实际执行中，会对时间上连续的warp进行调度。因而如果简单实现连续warp间的预取会出现预取延迟，造成预取失效。为了克服这种预取延迟的问题，在GPGPU的warp分配过程中，需要对访存连续的warp的执行顺序进行调整^[14]，拉大访存连续warp的间隔，避免出现正在运行的warp和其帮助预取的warp连续执行的情况，从而使得预取能及时生效。

2.2 利用硬件资源的预取策略

    由于GPGPU中预取策略的制定比较单一，因此有部分研究的重点转移到了预取数据的存放问题。在GPGPU中，预取的数据通常存放在共享内存中。当出现内存替换时，可能会使预取数据被替换出去从而导致预取失效。而在GPGPU执行过程中，通常有大量寄存器长时间闲置^[15]。为了避免预取数据的替换，可以利用空闲的寄存器来存储预取数据。通过监视寄存器的工作状态来确定哪些寄存器适合用来存放预取数据，从而避免预取数据被替换出去，提升预取效果。

    由于GPGPU中丰富的硬件资源，在GPGPU程序运行过程中，不可避免地也会出现硬件流处理器闲置的情况。因此，可以利用这些闲置的流处理器资源来为预取提供支持。ISP（Idle Stream Multiprocessors）预取策略就是基于这种设想提出的^[16]，通过利用停滞的流处理器来为正在工作的warp预取数据，从而提高程序的执行效率。

3 预取技术分析和展望

    通用处理器与图形处理器由于其硬件特性以及其上运行的程序特性决定了两者预取技术的相关研究侧重点不同：CPU由于其上运行的程序种类多、程序逻辑复杂，简单的预取策略并不能同时满足所有的程序需求。因此相关研究更多的侧重于设计合理的预取策略，提升预取策略的覆盖面。为了充分发挥GPGPU性能，通常其上运行的程序已经具有良好的空间局部性，这也就决定了其预取策略主要围绕的是空间局部性制定的，主要关注的是如何高效地实现这一机制。

    表1是对CPU及GPGPU平台制定预取策略的依据和具体实现方式的总结。

    虽然针对CPU预取的相关研究已经取得了很好的效果，但仍然面临着许多挑战。由于运行程序的多样性，大量应用的访存行为不一致，单一的预取策略并不能同时很好地满足各种应用的需求。较为复杂的策略虽然能保证精度，但会引入较高的额外开销。而简单的预取策略在访问不规律下精度过低，导致效率不足。因此，需要研究自适应的预取策略，根据当前运行的程序状态，动态选择合适的预取策略，从而进一步提高程序性能。

    由于GPGPU应用的访存行为较为单一，现阶段的主要研究内容是如何更高效地实现预取，实现算法也比较简单。然而，GPGPU的强大性能使得许多原本不熟悉GPGPU特点的编程人员加入了平台应用的开发过程中，从而可能会出现不友好的访存行为，使得直接利用简单预取策略并不能取得理想的效果。同时，GPGPU上对预取的硬件支持也不够充分。因此，在未来的研究中，需要规范访存行为，利用CPU资源来协同修正GPGPU应用的访存行为，从而使其更规律，预取更高效。同时在GPGPU体系结构设计过程中，提供更多的预取硬件支持，提高预取效率。

4 结语

    随着计算硬件的迅速发展，处理器处理速度与内存访问速度的差异越来越大，内存访问延迟成为限制处理器性能的主要问题。预取技术作为降低两者速度差异的重要手段之一已得到广泛的应用。随着硬件设计的并行化，多核乃至众核硬件逐渐成为硬件平台的主流。如何为并行硬件设计高效预取技术，目前还处于刚刚起步阶段,也无法满足并行环境提高访存效率的需要。随着技术的不断进步，相信未来针对并行硬件的预取技术将会逐步得到完善。

参考文献

[1] SMITH A.Sequential program prefetching in memory hierarchies[J].IEEE Transactions on Computers，1978，11(12)：7-12.

[2] ISHII Y，INABA M，HIRAKI K.Access map pattern matching for high performance data cache prefetch[J].Journal of Instruction-Level Parallelism，2011，13：1-24.

[3] SAIR S，SHERWOOD T，CALDER B.A decoupled predictor-directed stream prefetching architecture[J].IEEE Transactions on Computers，2003，52(3)：260-276.

[4] HUR I，LIN C.Memory prefetching using adaptive stream detection[C].In Proceedings of the 39th International Symposium on Microarchitecture，2006：397-408.

[5] JOHNSON T L，MERTEN M C，HWU W M W.Run-time spatial locality detection and optimization[C].In Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture，1997：57-64.

[6] SOMOGYI S，WENISCH T F，AILAMAKI A，et al.Spatial memory streaming[C].In ISCA′06：Proceedings of the 33rd Annual International Symposium on Computer Architecture，2006：252-263.

[7] JOSEPH D，GRUNWALD D.Prefetching using Markov predictors[C].In Proceedings of the 24th Annual International Symposium on Computer Architecture，1997：252-263.

[8] NESBIT K J，SMITH J E.Data cache prefetching using a global history buffer[J].IEEE Micro，2005，25(1)：90-97.

[9] FUCHS A，MANNOR S，WEISER U，et al.Loop-Aware memory prefetching using code block working sets[C].Microarchitecture(MICRO)，2014 47th Annual IEEE/ACM International Symposium on.IEEE，2014：533-544.

[10] WENISCH T F，FERDMAN M，AILAMAKI A，et al.Practical off-chip meta-data for temporal memory streaming[C].In HPCA，2009：79-90.

[11] CHAPPELL R，STARK J，KIM S，et al.Simultaneous subordinate microthreading(ssmt)[C].In Proceedings of the International Symposium on Computer Architecture，May 1999.

[12] JAIN A，LIN C.Linearizing irregular memory accesses for improved correlated prefetching[C].Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture，2013：247-259.

[13] LEE J，LAKSHMINARAYANA N B，KIM H，et al.Manythread aware prefetching mechanisms for GPGPU applications[C].Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture，2010：213-224.

[14] JOG A，KAYIRAN O，MISHRA A K，et al.Orchestrated scheduling and prefetching for GPGPUs[C].Proceedings of the 40th Annual International Symposium on Computer Architecture，2013：332-343.

[15] LAKSHMINARAYANA N B，KIM H.Spare register aware prefetching for graph algorithms on GPUs[C].High Performance Computer Architecture(HPCA)，2014 IEEE 20th International Symposium on.IEEE，2014：614-625.

[16] FALAHATI H，HESSABI S，ABDI M，et al.Power-efficient prefetching on GPGPUs[J].The Journal of Supercomputing，2014：1-22.