Boomerang： a Metadata-Free Architecture for Control Flow Delivery

本文主要是介绍Boomerang： a Metadata-Free Architecture for Control Flow Delivery，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Boomerang(回旋镖): a Metadata-Free Architecture for Control Flow Delivery

1. 摘要：

   • 问题：现在服务器的工作负载的具有大量的指令，占用更深的分层软件堆栈，整个堆栈的活动指令工作集很容易到MB，已经容易导致指令cache缺失率增加，从而导致前端停顿增加，另一方面这种大规模的指令工作集中的大量的分支也会使得BTB缺失，而导致流水线刷新。之前的解决方法都需要专用的元数据结构，因此需要大量的额外存储，同时更加复杂
   • 论文的目的：希望减少或者不使用之前技术需要的元数据成本，来实现高性能的控制流交付（delivery）
   • 论文的工作：
     • 解释了基于分支预测器的定向预取有效的原因
     • 提出了Boomerang，一种可提供高性能控制流交付的无元数据的结构。通过利用基于分支预测器的定向预取器，发现并且预填充I-cache块和BTB的缺失表项。在这种结构中，识别和填充BTB缺失表项不需要额外的硬件开销
     • 实验表明：Boomerang的性能和最新的控制流交付策略基本匹配，同时不需要后者如此多的元数据开销和复杂性

2. 介绍：

   • 降低I-cache和BTB缺失率的方法：硬件预取
     • I-cache的预取器主要通过依靠时序，记录和重播长序列指令，来达到降低缺失率，但是为了覆盖更多的指令，这些技术需要非常多的元数据来存储和索引这些记录的序列
     • BTB方面，基于空间和时间局部性的预取器通过采用两级的BTB来解决一级BTB太小的问题，但是第二级的BTB仍旧需要超过100KB的存储开销
     • 同时解决BTB和I-cache：Confluence技术，由于I-cache块携带着的分支指令包含着目标或者偏移量，因此通过使用基于时间流的指令预取器从预取的缓存块中提取分支信息来填充BTB。这种方案不需要为BTB提供元数据，但是仍旧需要提供昂贵的指令预取器的元数据
   • 论文一个主要的贡献：证明了之前的基于分支预测器的预取器可以应用在服务器的环境中，并且可以同时填充I-cache和BTB，并且只使用核内已有的结构。并且论文推翻了两个之前对于分支预测器的两个错误观点：
     • 分支预测器的预测准确率会限制掩盖LLC访问的长延迟
     • 需要大量的BTB才能够捕获目标工作集的分支指令
   • 论文通过在16核的RISC处理器实验环境中，利用一组传统的和扩展的服务器工作负载对Boomerang进行了评估。结果表明Boomerang消除了几乎所有的BTB相关的流水线刷新，并且将流水线前端的停顿减少了50%-75%，性能提高了27.5%。并且Boomerang达到了基本和Confluence相同的平均性能，但是没有后者的存储成本和复杂性

3. 缓解指令缓存缺失和BTB缺失的技术

   • I-cache：非顺序控制流导致的不连续会影响预取结果，因此需要控制流感知预取
     • 在97年和99年有一些文章提出利用分支预测器来预测未来的控制流，并提前将缓存块预取到L1 I-cache中，这种方式成本低，也比较简单。但是当时的实验环境是SPEC的工作复杂，并且只有适度的指令。在服务器端，由于工作负载的代码量超出了BTB的能力，分支预测器的准确率也有限，因此这种方法认为不再适用
     • 最先进的服务器指令预取器：基于时间流的原理，预取器记录指令的整个序列，之后由预取器重播，从而提前填充I-cache。这种方式的缺点在于需要大量的元数据存储开销
   • BTB：预测不连续的指令流，重定向取指流
     • 使用大容量的二级BTB和专用的BTB传送硬件来在两级BTB之间传递表项，从而能够增强低延迟的一级BTB。针对于这种结构，Bulk Preload利用的是BTB中的空间局部性，在一级BTB miss时，将二级BTB中空间上接近的表项预加载到第一级。PhantomBTB利用的则是BTB中的时间局部性，并且将第二级的BTB表项放入了LLC中。这些技术都需要在一级BTB发生miss之后，才能够触发预取
     • Confluence：使用一个基于时间流的指令预取器来填充I-cache和BTB，BTB通过提前预取的缓存块中的分支指令，通过提取指令中的分支目标来填充BTB。这种方式避免了二级BTB和BTB的预取器，但是由于指令预测器，仍旧需要大量的存储开销

4. 能否提供无元数据的控制流交付（delivery）

   • 大量的元数据开销在多线程和多核的情况下更加重要。对于利用分支预测指导预取的想法，首先这种方式不需要额外的元数据开销，而仅仅只需要核内已有的数据，一个一层的BTB和分支预测器，但是在服务器的环境中，有两个普遍的针对于分支预测的观点使得这种想法无法被利用：

     • 分支预测器的精度必须足够的高，从而才能够掩盖在多核NUMA处理器中访问LLC的长延迟。但是当分支指令增加时，预测精度将会以几何的倍数降低，而在服务器中分支指令的数量非常多
     • 对于一个小的BTB结构，由于大量的分支指令，会出现很多的BTB缺失，导致频繁的流水线刷新，也会阻碍分支预测器的提前工作

   • 分支预测精度是否限制了覆盖范围（limit coverage）

     • 论文以FDIP为例，比较了在不同预测器（TAGE，2-bit，Never-Taken）的情况下和最优的情况（PIF）的差异。FDIP通过增加FTQ（取指目标队列）将L1-I和前端流水线解耦和，FTQ利用BTB和分支预测器进行填充。PIF是最新的基于时间流的指令预取器

     • 衡量标准：测试在不同的LLC访问延迟情况下，所覆盖的前端流水线停顿周期占整体停顿周期的比例，以此来衡量预取带来的好处

     • 结果：在LLC延迟较低的情况，FDIP比PIF更好，因为后者无法快速的从分支预测错误中恢复。虽然TAGE可以很好的避免流水线被压缩，但是一个简单的分支预测器和FDIP结合就能够得到很好的结果
       

     • 论文进一步分析了前端流水线停顿的原因（顺序取指，条件分支，非条件分支）。实验环境：基于网格互连的16核NUCA处理器，LLC平均访问延迟30周期，预取器配置为next line, FDIP(32K), PIF(32K)

     • 分析结果：顺序取指仍旧占据了主导地位，FDIP基本上能够覆盖三种原因中大部分的cache miss，并且结果与PIF基本相同
       

     • 论文为了分析分支预测器的精度对结果的影响（TAGE的精度还是很高的），因此论文通过实现发现对于条件分支指令，92%的发生跳转的分支指令的目的指令都在当前缓存块的附近四个缓存块中，即条件分支的偏移非常短，正确的预测这些分支对于覆盖条件分支的不连续性并没有很大的作用（条件分支的预测准确率对预取结果影响不大）
       

   • BTB的大小是否限制了覆盖范围

     • 论文通过实验测试了不同的BTB大小在不同的LLC访问延迟下，对前端流水线的停顿周期的影响。结论：BTB大小从32K到2K，所覆盖的前端流水线的停顿周期的比例下降了12%（比较平缓）。BTB的大小的差异带来的主要影响是在无条件的分支
       

5. Boomerang(回旋镖)：利用核内已有的资源，能够同时解决L1-I和BTB缺失问题的一种统一的解决方案

   • 为了缓解I-cache的缺失问题，利用FDIP来指导预取；为了缓解BTB的缺失问题，在将要进入I-cache的缓存中提取分支指令和目的地址（仅使用核内已有的结果，少量扩展FDIP）
   • 基本的结构：FDIP（fetch directed instruction prefetching）
     • 解耦合的前端：通过一个较深的FTQ（取指目标队列）将取指部件和分支预测器单元（BP，BTB，RAS）解耦合。每个FTQ表项包括基本块的取指地址信息，基本块定义为以分支指令结尾的顺序指令序列
     • 分支预测单元每周期进行一次基本块预测，然后存储在FTQ中。取指单元从FTQ的头部读取表项，向L1-I发出N个取指请求，N为取指宽度。
     • 预取单元（引擎）：生成预取地址。当新的基本块的取指地址插入FTQ时，预取单元扫描这些地址，以发现在不久的将来会被访问的L1-I的block。当发现一个新的L1-I的block时，预取单元会向L1-I发送一个预取探针，以检查该块是在L1-I中还是在预取缓冲区中。如果块已经存在，则不需要任何操作；否则将会从更低层次的缓存中取到该块，然后放到L1-I的预取缓冲区
     • 预取缓冲区：存储从更低层次预取的缓存块，在取指请求在该缓冲区中命中时，才会将缓存块放入L1-I中
     • 由于预取单元不需要任何L1-I的响应，因此预取单元可以以很高的速率发出探测请求，即预取单元可以先于取指单元执行
   • boomerang的整体概括
     • BTB的组织：传统的BTB无法区分一个miss的产生原因是由于非分支指令还是由于真的BTB缺失，因此论文提出一种基于基本块的BTB的组织形式，BTB的每一个表项都对应于一个基本块，从而包括每个表项都可以包含一个确定的分支，并且指向另一个BTB表项，此时BTB缺失就是真正的BTB缺失
     • BTB发生miss：1) 向L1-I发射指向一个缓存块的探针，该缓存块包含着缺失BTB表项起始地址
     • 2. 该缓存块会被从L1-I取到或者从更低层次的缓存结构中取到
     • 3. 该缓存块会被发射到预译码器中，提取所有的分支和目标地址。如果在缺失的BTB表项的起始地址之后找到了分支指令，则第一个这样的分支就是该BTB表项对应的基本块的终止分支。此时会新建一个表项存放该分支和目标地址。如果没有找到这种分支，则发射另一个BTB缺失探针，指向顺序往下的下一个cache块，重复这种操作
     • 除了BTB表项对应的终止分支，其它分支都会被存储在BTB的预取缓冲区中。在访问BTB时也会并行访问该预取缓冲区。当缓冲区发生命中时，该表项将会被移动到BTB中。缓冲区的条目以先进先出的方式替换
   • BTB发生缺失时的预取：默认情况下，当发生BTB缺失时，FTQ将会停止填充
     • 不停止的预取（un-throttled）：分支预测器假设发生BTB缺失的分支不会跳转，然后继续为FTQ提供数据。缺点：错误路径上的预取会污染L1-I的预取缓冲区
     • 节流的预取（throttled）：类似于前一种，但是只发出对下一个N个顺序缓存块的预取请求（N为设定的值），从而减少错误预取带来的影响
       

这篇关于Boomerang： a Metadata-Free Architecture for Control Flow Delivery的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---