软件预取

1 软件预取

软件预取是在程序中显示地插入预取指令，以非阻塞的方式让处理器从DRAM中读取指定地址的数据进Cache。对于Cache来说这个指令和普通的load指令无异，其只是触发一次Cache查找并在Miss时从下级存储请求数据；对于处理器来说其不用等待读取的结果，可以直接执行后续指令，从而使计算和访存并发进行。预取指令很像non-block的读指令（事实上在486时代就是通过dummy read指令进行预取的），只是其不会产生任何异常（如缺页、TLB Miss等）。所以使用预取指令时不需要特别检查地址的有效性。

软件预取几乎对硬件没有要求，其最大的技术挑战在于如何在目标代码中正确添加预取指令。预取指令可以通过编译器自动添加（gcc和icc均支持），也可以通过程序员手工加入。从目前看到的结果上看，通过编译器自动添加预取的效果非常不确定。如：gcc只能对数组遍历循环自动插入预取指令（-fprefetch-loop-arrays），并且必须配合小循环展开使用（因为预取本身的开销，如果小循环不展开其预取指令的开销可能会对性能带来严重负面影响）。而且gcc官方文档也说明该编译选项可能生成更好或者更差的代码，结果高度依赖于循环结构，所以收益非常不确定。根据libevas项目的实测结果¹，此编译选项打开后有的用例产生了10%～15%的正增益，但是在另一些用例产生了高达25%的负增益。所以业界一般推荐程序员手工添加预取指令，并通过测试确认结果。

适合进行软件预取优化至少要满足如下要求：

1. 容易计算预取地址，并且计算开销足够小（相对于能从软件预取中得到的收益来说）；
2. 在不使用软件预取的情况下，原程序会频繁产生Cache Miss。

回顾我们之前在”访存模式“小节中提到的几个数据结构，数组应该是最满足第1点要求的数据结构了，其预取地址计算十分容易，并且计算开销很小。然而在大部分情况下硬件预取器都能很好地对数组做自动预取，所以很可能不满足第2点要求。

而链表又是另一个情况：其可以很好地满足第2个要求：因为目前商用的硬件预取器对间接访存都无能为力，而且离散的访存很容易就带来大量的Cache miss。但是对链表进行预取的地址计算开销非常大：假设你想向前预取3个节点，对于数组来说只要简单地&a[i+3]就好了，但是对于链表来说你不可能用node->next->next->next，因为这样的预取是毫无用处的：在每取一次next的过程中当前节点都必须被读取，所以永远只能预取最后一个节点。所以对链表的预取也比较困难，如果程序的计算量不够很可能没有效果。

1.1 gcc的软件预取支持

gcc提供的数据预取函数原型如下：

void __builtin_prefetch(const void *addr, ...)

其中参数列表如下：

• addr：需要预取的地址。 预取地址本身允许非法但是计算地址的过程不能有非法内存访问。比如预取p->next，如果p->next是非法地址则也是允许的，处理器将负责忽略非法的预取。然而如果p是非法地址那就会触发段违例异常；

• rw（可选）：1为写，0为读。 默认值为0（读预取）。处理器在进行写预取时通常伴随着使该地址在其他核的Cache中无效。

• locality（可选）：取值为0～3。 0表示时间局部性最低（实现时仅被预取到末级缓存，并提示处理器预取的数据访问后不会被复用）；3表示时间局部性最高（实现时会被预取到L1D Cache，并提示处理器预取的数据可能被重复访问）。默认值为3（预取到L1D Cache）。 大部分情况下对于数据预取来说我们都是默认预取到L1D Cache。然而由于目前处理器的L2缓存基本都是设计为指令和数据共享的，所以也可以利用这一特性将指令地址（即：函数地址）预取到locality为2的L2 Cache里，实现指令预取。

注意：在海思的Taishan V110核心上所有针对L3 Cache的预取指令都会被NOP；所有指令预取（PLI）都会被NOP。因此在此核心上若希望实施软件指令预取，唯一的办法只能是使用locality为2的数据读预取将函数体预取到共享的L2 Cache。

以下是不同参数的gcc预取函数与生成的ARMv8预取指令的对应关系（主要关注locality的影响）：

Streaming模式是针对流式数据访问优化的，其特点是短期内只会被用到一次（流过），阅后即焚。访问完成后不需要被保持在Cache里污染Cache。典型场景是memcpy、媒体流处理等。

该预取模式的具体实现取决于处理器的实现，处理器只是尽量保证这类预取对Cache的污染较小。如：AMD会在Cache Line中标记其为“Quick Eviction”，Intel会将此类数据固定预取到缓存中的特定一路上（即对于N路缓存来说这种预取只能占用其中1/N的空间）。

以下是不同参数的gcc预取函数与生成的x86预取指令的对应关系：

除了提供手工插入的预取函数以外，在自动预取优化方面gcc只有前面提到的针对大数组遍历循环优化的-fprefetch-loop-arrays。其涉及的相关编译参数如下（详见【gcc在线文档】）：

• prefetch-latency、simultaneous-prefetches
• min-insn-to-prefetch-ratio、prefetch-min-insn-to-mem-ratio
• prefetch-dynamic-strides、prefetch-minimum-stride
• l1-cache-line-size、l1-cache-size、l2-cache-size

从网上的实测结果来看gcc这些预取相关参数的设置十分玄学，并非按照处理器参数设置效果就最好，需要人工尝试调参。而且最终优化结果也无法保证，看起来离实用尚有差距。所以一般还是建议手工针对Cache Miss较高的部分进行预取优化，而不建议采用全局自动插入预取指令的方式。

在之后的章节里我们会对一些开源项目的软件预取应用进行分析。

1.2 软件预取的缺点

软件预取可以解决前面提到的硬件预取的限制， 但是其也存在如下缺点：

1.2.1 指令开销

不像完全独立于执行单元的硬件预取，软件预取需要占用指令空间和执行开销。请注意软件预取的开销不仅是一条预取指令，同时还包括消耗在计算预取地址上的逻辑。虽然预取指令允许使用非法地址，但是在计算预取地址的过程中所访问的内存依然要保证正确合法。如：从指针数组中取指针，或者从链表节点中取next时，必须保证访问的数组成员（不可越界）或链表节点（不能踩飞）合法。这些指针合法性检查本身都会带来一些开销，而取指针时的访存也可能产生TLB Miss等异常。由于软件预取常常用来解决硬件预取处理不了的间接内存访问，因此经常会遇到这类重量级的预取地址计算场景。

所以如果软件预取用得不好，可能带来性能恶化。如：在一个数组遍历过程中，倘若对每个数组成员的计算量太小，不足以和访存时延充分重叠时，加入软件预取可能会引入翻倍的开销——因为每个地址可能都在预取和访问时分别计算了两次，而程序又没有从预取中得到并发增益。对于这种情况通常考虑将小循环展开后再在合适的位置插入预取指令（这应该也是为什么gcc在打开-fprefetch-loop-arrays时会自动打开-funroll-loops），但小循环展开本身又会导致代码膨胀和占用更多的指令Cache。因此除非有较大的收益，否则应该谨慎使用软件预取。

1.2.2 无法动态适应实际情况

软件预取指令都是静态插入代码的，其预取的距离（distance）和度（degree）都是固定不变的，在运行时无法根据硬件的实际情况或实时负载变化。因此在不同的硬件平台上，或者不同负载下其结果不一定能保证最优。而随着硬件的演进，之前恰到好处的预取在新平台上可能就变得过早或过迟了，性能收益难以看护。这些问题都是在实施软件预取时必须考虑的。

1.2.3 常常需要对代码结构重构

由于预取的关键是要在数据被预取和被访问之间有足够的提前量，因此在循环体非常小的时候往往无法满足这样的前提，不得不使用诸如循环展开等技巧重构循环，保证在两轮预取之间的计算量足够以避免“晚”预取。类似的，对于某些大循环可能需要考虑采用循环拆分来避免出现“早”预取的问题。同时这样重构后的代码也非常晦涩难懂，严重影响未来的可维护性。后面对开源软件的预取实例分析的时候我们就会看到一些这样精巧但晦涩的代码。