A Event-Triggered Programmable Prefetcher for Irregular Workloads

作者：Sam Ainsworth and Timothy M.Jones

@ University of Cambridge(UK)

大数据应用中大量的内存不规则访问产生了memory-bound问题。为了减少一般性的复杂访问特征应用的的cache miss率，本论文提出了一种以事件触发的可编程预取器，其可以将通用处理单元的灵活性将基于事件的编程模型相结合来支持更加复杂的预取特征。此外，本工作还借助编译器，自动地从源代码中解析出事件。

论文为什么要做这件事？

大数据分析中的性能瓶颈

现代大规模数据分析中存在大量不规则、难预测的数据访问，这大大增加了传统存储结构中的缓存未命中次数，造成了CPU暂停的时间增加，造成了严重的memory-bound问题。

解决方法1：多线程

线程级并行可以将不同线程间的访存和计算重叠，以掩盖CPU的暂停时间。这种方法的问题是：不规则的多线程数据访问难免出现竞争关系；数据分块方法又很难确定，这些都是线程级并行的硬伤。

解决方法2：软硬件预取（规则->不规则->专用->可编程）

软硬件预取器也是提升cache命中率的有效方式。然而，现有的预取器对于复杂内存访问的内存级并行探索并不深入。大体上，现有的预取器可以分为以下几类。前三种都采用硬件手段实现。

• 传统预取器：这类预取器基本上基于传统应用中的时间局部性或者空间局部性进行内存预取。常见的有：stride prefetcher(空间局部性)/ history-based prefetcher(时间局部性)
• 不规则访问预取器：这类预取器对一些常见的不规则访问进行预取。例如pointer-chasing预取器、indirect array预取器等。
• 专用预取器：针对某一类应用，提取特殊的数据访问特征来定制硬件预取器。这类预取器往往在目标应用上能够取得很好的效果，但是往往需要算法是成熟的，不需要进一步改动了。
• 软件预取器：软件预取器在其他CPU线程上进行访存，为当前线程提供数据。这种方法可以让用户显式地自定义预取特征。

综上所述，现有的硬件预取器由于缺乏灵活性，对于现代数据应用中复杂的数据访问特征往往不见效，有时候还有相反的效果。软件预取器虽然支持用户对待预取的数据进行显式的自定义，但是因为毕竟在一个核心上，也是有数据等待的开销的。同时，软件预取器无法对提取到的数据进行反应，例如软件预取器就无法对指针追踪类的应用产生效果。

本文的基本想法

用通用的计算单元作为可编程的预取主体，用户或编译器来定义预取函数，在特定事件触发时进行对应的预取，从而实现对于一般性的复杂数据访问特征有效的预取器。

这个事情之前别人是怎么做的，存在什么问题？

预取器的研究前沿方向主要有以下几类：

• 明确指定特征的专用预取单元
  • 方法：通过分析应用中的特定访问特征，使用预取器进行并行数据加载。
  • 优点：专用硬件能够对特定应用实现很强的性能提升
  • 缺点：缺乏一般性
• 不明确指定特征的不规则访问预取器
  • 方法：对不规则的数据访问流进行分析以提取广泛的公共特征（pointer-chasing、indirect memory access等），对这些特征做加速
  • 优点：不需要明确指出应用相关的特征，不需要额外配置寄存器，没有手工开销
  • 缺点：在复杂的数据访问中，有时候会产生过度预取现象。
• 用helper线程实现预取（软件方法）
  • 方法：应用额外的CPU线程进行预取数据。
  • 优点：可用户自定义、编程难度大大降低。
  • 缺点：在高性能核上添加额外线程，会提升系统的能耗。并且有可能会有同步开销。此外，软件预取也要在当前线程内暂停等待结果，这有可能使得计算线程赶上预取线程。因此性能相对于硬件预取器要差一些。
• 可配置预取器
  • 方法：对某数据结构进行可编程预取器设计
  • 优点：可自定义、性能好。

总结：虽然现有的预取器都能或多或少的对某些特定应用、某个访存特征做加速，但是仍然不是完整的解决方案。

该论文解决了什么难点，难点存在的原因是什么，作者是如何发现这些难点的？

下面以数据库操作中的hash-join为例，来指出大规模数据操作的难点和各种预取器存在的问题。

上面是一个在数据库操作中常用的hash-join函数内核。我们先忽略红色的优化策略，整个算法的流程是这样的：对每个顺序访问的键值key求哈希值，根据此哈希值做数组访问，找到htab。这里涉及了一个数组的非线性随机访问，此处容易产生cache miss。下一步对于htab上链的一整个链表做访问和计算，这里也是一个指针追踪，容易产生多次的cache miss。

下面我们将逐步分析用预取器优化这个内存访问会有什么样的难点，图中浅绿色代表indirect access找到htab的过程，深绿色代表pointer-chasing的过程。斜线代表由cache miss产生的CPU stall。

（注意：这个图画错了，d和e应该反过来的。）

• 原始情况下会有大量的CPU stall
• 软件预取器：软件预取器的缺点是无法对指针追踪过程做预取（因为指针追踪需要依赖之前预取的数据，软件方法无法获取这个信息），因此只能加速非直接内存访问的部分。可以看到获得的收益比较小，并且由于预取也是当前线程去发射的指令，也有开销，因此效果提升不是非常明显。
• 多线程预取：这里用多线程预取的方法使得线程之间共享内存访问，使得不同线程的计算和访存可以并行。问题在于在pointer-chasing中难免会有数据的冲突，难免引入同步的开销。
• helper线程预取：搞一个专门的线程只为计算线程做预取。这个线程也是在当前计算核心上被执行，但是只进行访存不进行计算。这个问题在于helper线程也是单线程的思路，必须等待上一个访存结束再进行下一个访存的，必须等待预取结果再进一步预取。由于主线程不再被cache miss所限制，因而其会逐渐被访存线程赶上。
• 理想情况：保证helper线程的自定义特征之外，我们想要充分挖掘内存中的并行机会。额外的并行机会在于，可以看到其实不同的链之间是完全可以并行的，他们之间不存在数据依赖。helper线程的问题在于也只能是等待上一个链完全做完再做下一个链的，我们不希望计算的CPU有暂停以造成CPU资源的浪费，还是希望有一个单独的硬件来做预取，保证CPU的高效运转。

针对以上难点，作者各做了哪些优化，优化背后的思想是什么？

系统概况

文章提出了一个可编程的预取器，这个预取器被特定地址的数据结构的读事件触发，并且自定义预取操作，在额外的低功耗通用计算核心上进行预取。

主要运行流程：主核心中的读取请求和预取单元中的预取请求中的地址，在通过L1dcache的时候先进入预取器的地址过滤器。地址过滤器会对感兴趣的地址进行过滤，这个感兴趣的地址一般是在程序开始之前由编译器的一条单独指令初始化，往往是目标数据结构的地址空间。之后，将感兴趣的地址放入观察队列中。观察队列满了的时候就将最老的观察抛弃，因为预取本身不影响程序的正确性。之后调度器负责将感兴趣地址送给可编程的预取单元，进行相应的预取操作。当有空闲的可编程预取单元的时候，调度器才会将这个请求映射到可编程预取单元上。可编程预取单元是这个预取器的主体，但是他并不需要等待访存的结果，而是只发送访存的请求。可编程预取单元在L1cache中有空闲的MSHR时将请求发送给预取请求队列，之后预取请求队列再通过TLB地址转换和数据预取。注意到，可编程预取单元还连接了全局寄存器和EWMA计算单元，全局寄存器是负责存放一些重要数组的首地址，EWMA是负责为预取单元提供预取步长的。预取单元使用单独的指令缓存。

地址过滤器

• 初始化：通过编译器分析产生的感兴趣地址使用指令进行配置，为过滤器明确几段指定感兴趣的逻辑地址，以及每段感兴趣的逻辑地址对应的函数指针。
• 过滤后的地址被放入观察队列，如果它位于两段感兴趣的地址空间，则生成两个项。

观察队列和调度器

• 当有空闲PPU时，调度器将感兴趣数据的虚拟地址或者内容（cacheline）导入ppu的本地寄存器。将ppu 的地址设置为对应的函数入口位置，这个函数是用来计算预取地址的。
• 如果观察队列满了，则将最老的请求抛弃。

可编程预取单元（PPU）

• PPU负责产生新的预取请求。其上运行的函数主要通过当前数据的内容、当前数据的地址来计算预取的数据地址。
• PPU被设置为不能访问内存，他上面只有一个全局寄存器，在PPU之间共享，负责记录几个关键数据结构的位置；一个本地寄存器，负责做简单计算，还有从l1dcache中获得的数据内容。所以PPU上运行的函数往往只涉及简单的算术运算操作。
• PPU只有icache没有dcache。PPU代码跟主核心的代码是分离的，但是任何一个观察值的操作都可以在任何一个PPU上跑。
• 硬件要求：只需要简单的ARM Cortex M0+即可。只包括不超过12000个门电路。面积大小不到L1数据cache。

步长监控（EWMA）

步长监控模块负责预取即用的数据，为PPU模块提供步长信息。

内存请求标签

主要针对指针型访问。数组型访问可以通过感兴趣的内存地址来找到，而指针型的感兴趣标记可以通过MSHR中的特定标记来实现。

编程模型

目前主要讨论手写预取函数，之后会要讨论编译器生成手写函数。

因为PPU之间是完全独立的，每个都可以相应预取请求，所以预取器不需要stall来等待结果。

PPU编程模型是基于事件的，有一些限制。比如PPU的编程中不能有数据访问，栈或者存储。不能有函数调用，不能有系统调用。只是简单的算数运算。

赏

大哥大嫂过年好！

支付宝

微信